ACO Series Part 1: Ant System Algorithm for Knapsack Problem
Behavior Semut
Semut memiliki penglihatan yang kurang jelas, namun mereka dapat menemukan jalur terpendek dari sarang menuju ke sumber makanan mereka. Bagaimana cara mereka melakukan itu?
Ketika seekor semut keluar dari sarangnya, ia akan berjalan-jalan secara random untuk menemukan sumber makanan sambil meninggalkan jejak feromon — feromon merupakan sebuah aroma khas yang dikeluarkan oleh semut dengan tujuan untuk menjadi penanda bagi semut lain — . Ketika seekor semut menemukan makanan, maka dia akan kembali ke sarang mengikuti jejak feromon yang telah ditinggalkan.
Berdasarkan kuantitas dan kualitas makanan yang ditemukan, semut akan memanggil temannya — semut lain — untuk membantu dia membawa sisa-sisa makanan yang telah ditemukan tadi. Dengan behavior yang sama, semut-semut lain akan mengikuti jejak feromon yang telah ditinggalkan dari sarang hingga ke sumber makanan tersebut. Lalu pertanyaannya, bagaimana cara semut dapat menemukan jalur terpendek hanya dengan mengandalkan feromon?
Sederhananya, jalur yang jauh akan memakan waktu 2 kali, 3 kali, bahkan berkali-kali lipat waktu yang dibutuhkan dibandingkan untuk menempuh jalur yang pendek. Hal ini akan menyebabkan feromon yang tertinggal akan menguap dan intensitasnya tidak setinggi di jalur yang pendek. Oleh sebab itu, semut-semut akan cenderung memilih jalur yang memiliki intensitas feromonnya paling banyak, yang mana jalur pendek memiliki intensitas feromon paling tinggi dibandingkan jalur yang jauh. Semakin banyak semut yang melewati jalur tersebut, maka aroma feromonnya akan semakin kuat. Ilustrasinya seperti berikut.
Dengan behavior ini, pada tahun 1991, Marc Dorigo membuat sebuah teknik metaheuristik berdasarkan perilaku biologis koloni semut untuk memecahkan persoalan optimisasi dengan sebutan Ant Colony Optimization (ACO).
Knapsack Problem
Dalam dunia matematika, ketika kita dihadapi dengan beberapa kriteria atau kondisi tertentu dan kita ingin memilih sebuah elemen terbaik maka hal itu disebut sebagai proses optimisasi. Secara umum, optimisasi berfokus pada pencarian nilai optimal, yaitu pencarian nilai maksimum dan pencarian nilai minimum dari sebuah himpunan fungsi real. Bentuk matematisnya direpresentasikan sebagai berikut.
Salah satu permasalahan optimisasi yang cukup terkenal ialah Knapsack problem. Knapsack problem biasanya diilustrasikan dengan sebuah tas yang dapat membawa beberapa barang, yang mana masing-masing barang tersebut memiliki weight dan profit.
Di kasus knapsack, kita ingin meminimalkan beban (weight) di tas kita, namun di saat yang bersamaan barang-barang yang kita masukkan ke dalam tas memiliki nilai profit yang tinggi. Jika kita ingin ubah persoalan tersebut ke dalam bentuk matematis, maka hasilnya sebagai berikut
maximize: profit barang
subject to: minimize weight barang
Berdasarkan persamaan di atas, profit akan diperlakukan sebagai fungsi objektif dan weight sebagai fungsi kendala.
Meskipun knapsack bukan termasuk permasalahan optimisasi untuk mencari shortest path, namun permasalahan ini juga dapat diselesaikan dengan metode Ant Colony Optimization (ACO).
Ant Colony Optimization (ACO)
Kita sudah tahu bahwa algoritma ACO merupakan penerapan dari behavior sebuah koloni semut yang berguna untuk mencari solusi terbaik dari sebuah permasalahan optimisasi. Fakta lainnya mengenai ACO ialah ACO merupakan salah satu dari sekian banyak algoritma di metode Swarm Intelligence.
Swarm Intelligence merupakan sebuah kecerdasan kolektif yang muncul dari sekolompok agen sederhana.
-Bonebau et al, 1991
Algoritma ACO idealnya dapat memecahkan permasalahan optimasi kombinatorial diskrit seperti Travelling Salesman Problem (TSP), Vehicle Routing Probelm (VRP), Minimum Spanning Tree Problem (MST), Knapsack Problem, dan lain-lain.
Selain itu, algoritma ACO menjadikan semut sebagai agen-agen pembawa solusi optimal yang membutuhkan 2 (dua) parameter, yaitu:
- Pheromone trails
- Attractive coefficient
Parameter tersebut akan memengaruhi nilai probabilitas semut untuk memilih node yang akan ia kunjungi, persamaan probabilitasnya sebagai berikut.
- τ : Pheromone intensity
- η : Attractive coefficient
- α dan β : Berfungsi untuk meng-influence parameter
Setelah itu, feromon akan diupdate mengikuti rumus-rumus berikut
Di mana L merupakan panjang tur yang dihasilkan oleh semut ke-k. Hal di atas akan terus diulang hingga proses telah memenuhi kriteria pemberhentian.
Meski ACO terlihat sederhana dan efektif dibandingkan algoritma lain, kenyataannya ACO sering kali terjebak di lokal optimum karena efek dari intensitas feromon itu sendiri. Jalur yang memiliki intensitas feromon paling tinggi, membuat semut akan kesulitan untuk keluar dari jalur tersebut dan berakhir terjebak di lokal optimum.
Dari beberapa paper yang aku baca, ternyata ACO sudah mengalami banyak modifikasi untuk menyesuaikan terhadap berbagai permasalahan optimisasi dan mengatasi kekurangan dari ACO bentuk standar.
Salah satu insight yang aku dapat, agar tidak terjebak di lokal optimum ialah dengan menambahkan faktor mutasi. Mutasi akan dibagi menjadi 2 bagian, yaitu mutasi dari dalam dan mutasi dari luar, dua bagian tersebut akan dihitung berdasarkan tingkat konsentrasi matriks feromon. Selain itu, kita juga bisa memakai konsep elitisme di dalam suatu generasi semut. Dan yang terakhir, tidak hanya mewariskan jejak feromon, kita juga dapat mewariskan solusi optimal ke generasi berikutnya.
What am I working on . . .
Saat ini, aku sedang mengerjakan project tentang pencarian parameter-parameter ACO yang menghasilkan solusi optimal untuk kasus knapsack. Semoga suatu saat, semua insight menarik yang nanti aku dapat selama pengerjaan project bisa di-share di sini dan dapat menjadi insight baru bagi teman-teman semua. Semoga . . .
Sources:
¹Materi perkuliahan Swarm Intelligence oleh Pak Riksa Meidy Karim, M.Sc dan Bu Amalya Citra Pradana, M.Sc
²Knapsack Problem — WikiPedia
³Ant Colony Optimization — WikiPedia
⁴A New Ant Colony Optimization for the Knapsack Problem
