Ant Colony Optimization for Capacitated Minimum Spanning Tree Problem

Minggu uts baru saja lewat. Salah satu yang berkesan selama ujian kemarin adalah mata kuliah intelejensia kolektif. Ujiannya sebetulnya sederhana, hanya me-review sebuah paper, dengan catatan mencoba mengimplementasikan apa yang disampaikan paper tersebut dalam waktu satu minggu (sambil ada uts yang lain juga, hehe). Kebetulan saya mendapat paper yang isinya tidak terlalu sulit untuk diimplementasikan dalam artian tidak membutuhkan spesifikasi konfigurasi tertentu (mis. simulasi, jaringan komputer, atau framework parallel programming). Paper yang saya review adalah “A Hybrid ACO algorithm for the capacitated Minimum Spanning Tree Problem“, oleh Marc Reimann dari ETHZ.

Singkat kata, ada dua buah topik yang terlibat di sini. Pertama adalah algoritma ACO (Ant Colony Optmization) yaitu algoritma optimasi yang terinspirasi dari perilaku semut dalam mencari makanan. Berdasarkan hasil pengamatan, jalur yang dilalui oleh semut (dari sarang ke lokasi makanan) jika makanan ditemukan merupakan jalur yang terpendek (shortest path). Semut itu sendiri bergerak secara acak namun saling berkomunikasi a la pramuka dengan memanfaatkan jejak zat kimia bernama feromon. Jika makanan ditemukan maka semut tersebut akan meninggalkan feromon dalam perjalanan pulang ke sarang. feromon ini akan menguap seiring dengan waktu namun akan diperkuat jika ditambahkan oleh semut lainnya. Walaupun di awal dinyatakan bahwa semut bergerak secara acak namun dengan adanya media komunikasi berupa feromon, semut tersebut memiliki kecenderungan lebih tinggi untuk memilih jalan yang aroma feromonnya lebih kuat.

Topik kedua yaitu persoalan capacitated minimum spanning tree. Sejujurnya, baru kali itu saya mengetahui tentang persoalan tsb. Kalau persoalan minimum spanning tree tentu sudah pernah dengar dari kuliah matematika diskret di awal S1. Nah, kalau ditambah batasan tambahan? Ternyata setelah browsing sana-sini dan melototin papernya sambil begadang, lama kelamaan ngerti juga. Ternyata adanya batasan ‘capacitated‘ itu maksudnya adalah jika ada satu node yang dipastikan akan menjadi akar pohon dan tiap node lainnya punya nilai demand maka untuk tiap sub-pohon yang terhubung ke node akar tidak boleh melebihi nilai konstanta kapasitas untuk persoalan tersebut. ketika nilai demand dari tiap node merupakan nilai satuan, maka kapasitasnya secara sederhana berarti tiap sub-pohon hanya boleh mengandung node paling banyak senilai konstanta kapasitas.

Di paper tersebut, persoalan CMST diceritakan sebagai relaksasi dari persoalan Capacitated Vehicle Routing Problem. Untuk menyelesaikan persoalan ini langkah yang dilakukan antara lain pengelompokan node (node clustering), pertukaran node antar kelompok (local search), dan terakhir mencari MST untuk tiap kelompok menggunakan algoritma Prim. Adapun letak penggunaan algoritma ACO adalah pada pengelompokan node. Pembentukan kelompok node dilakukan sedemikian rupa sehingga ketika menggabungkan dua buah kelompok menjadi kelompok baru batasan kapasitasnya tetap terpenuhi. Pemodelan jalur semut atau pengambilan keputusan terletak pada menentukan kelompok mana yang akan digabung menjadi kelompok baru. Salah satu kriterianya adalah nilai saving yang dinyatakan sebagai nilai penghematan jika dua buah cluster digabung menjadi satu. kriteria ini digabung dengan distribusi feromon dalam ruang keputusan yang jumlah pilihannya dibatasi membentuk distribusi peluang (probability density function) yang dimanfaatkan untuk mengambil keputusan secara acak.

Langkah berikutnya adalah pertukaran antar node di satu kelompok dengan node di kelompok lain. Karena tidak dijelaskan lebih lanjut mengenai kriteria dampak penukaran dua buah node dan kalaupun menggunakan nilai saving saya hampir tidak menemukan perbedaan dengan langkah sebelumnya, saya tidak mengimplementasi langkah ini dan lanjut ke algoritma prim. Sebagai percobaan, sampel data kasus diambil dari OR Library. Berbeda dari paper tersebut yang membandingkan algoritma versi ACO dengan algoritma metaheuristik lain (Tabu Search dan Evolutionary), dalam percobaan yang saya lakukan solusi dibandingkan dengan solusi upper bound (karena persoalannya minimasi) yaitu tiap node terhubung ke node akar. Berdasarkan hasil percobaan menggunakan kasus tc80 solusi yang dihasilkan algoritma ACO yang saya implementasi berhasil mengurangi total cost sebesar 80% (biaya solusi < 20% biaya asal) dari nilai upper bound tersebut.

Program tsb saya implementasikan menggunakan delphi. Namun, sepertinya implementasi versi saya masih termasuk lambat (mungkin karena ada banyak operasi set, konversi string, dan array dinamik). Jadinya ketika mengikuti parameter di paper tersebut, untuk kasus di atas (80 node+1 node akar) perlu waktu rata-rata 20 menit (80 semut, 800 iterasi yang ditotal jadi 16000 percobaan) padahal setelah 200an iterasi hampir tidak lagi ditemukan solusi yang lebih baik dan sepertinya tidak perlu semut sebanyak itu untuk simulasi (10 semut sepertinya cukup walau untuk konvergen ke solusi terbaik ada di iterasi 250an).

Sebetulnya sebelum uts ini hal serupa (mengimplementasi dan mereview paper) juga dilakukan dan topik yang saya pilih mengenai contour correspondence yang dimodelkan menjadi persoalan Quadratic Assignment Problem. Tapi sepertinya lebih enak membahas yang ini dulu, hehehe

5 comments

  1. petra · November 1, 2009

    kok sepertinya berat yah😛

  2. yaniwid · November 2, 2009

    Menarik ya, asal ide ACO ini. UTS-nya jadi berapa (puluh) jam?🙂

  3. pebbie · November 2, 2009

    48 jam Bu, hehe
    24 jam pertama melototin papernya, 24 jam berikutnya bikin program, running percobaan, dan nulis laporan😀

  4. mianurindah · November 16, 2009

    matkul intelegensia kolektif ??
    ko dulu kaya ga ada ya Peb :p
    tapi gapapa sih, nampak berat untuk ukuranku, :p
    heheheeee

    menarik bgt yaaa!
    pernah baca sekilas juga, paper tentang ant based algorithm, disini dipake untuk load balance di jaringan telco,
    great!
    share terus ilmunya ya Peb!😀

  5. arham blogpreneur · Desember 12, 2009

    waduh ngak paham semuanya saya… kira kira major apa yah???

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s