Algoritma Ant Colony

Dasar algoritma ini adalah kemampuan dari sekumpulan semut (colony) yang mampu menemukan jalur terpendek dari sarangnya ke sumber makanan. Hal ini dapat dilakukan karena ketika semut berjalan pasti akan meninggalkan jejak berupa bau atau yang sering disebut pheromone. Berikut gambar dari tingkah laku semut pada umumnya.

Gambar Ant Colony System

Seiring perkembangan algoritma dari ant koloni ini, munculah algoritma pengembangan dari algoritma ant koloni antara lain: ant coloni optimization dan multiple ant coloni sistem.

 Ant colony optimization (ACO)

Algoritma Ant Colony Optimization (ACO) merupakan salah satu metode metaheuristik yang menerapkan semut sebagai agen dengan update Pheromone-nya untuk dapat melakukan proses pencarian solusi yang efektif dan efisien. Ant Colony Optimization (ACO) diadopsi dari perilaku koloni semut yang dikenal sebagai system semut (Dorigo, M., dan Gambardella, L., 1996). Pada ACO setiap semut ditempatkan di semua titik graph (dalam hal ini titik – titik yang dikunjungi) yang kemudian akan bergerak mengunjungi seluruh titik. Setiap semut akan membuat jalur masing – masing sampai kembali ketempat semula dimana mereka ditempatkan pertama kali. Jika sudah mencapai keadaan ini, maka semut telah menyelesaikan sebuah siklus (tour). Solusi akhir adalah jalur terpendek dari seluruh jalur yang dihasilkan oleh pencarian semut tersebut.

Algoritma ACO telah banyak diaplikasikan dalam berbagai bidang yang mencakup beberapa persoalan, yaitu :

1. Traveling Salesman Problem (TSP), yaitu mencari rute terpendek dalam sebuah graph menggunakan rute Hamilton.

2. Quadratic Assignment Problem (QAP), yaitu menugaskan sejumlah n resources untuk ditempatkan pada sejumlah m lokasi dengan meminimalisasi biaya penugasan (assignment).

3. Job-shop Scheduling Problem (JSP) juga salah satu contoh aplikasi Ant Colony Optimization, yaitu untuk mencari lintasan sejumlah n pekerjaan menggunakan sejumlah m mesin demikian sehingga seluruh pekerjaan diselesaikan dalam waktu yang seminimal mungkin.

4. Vehicle Routing Problem (VRP)

5. Pengaturan rute kendaraan

6. Pewarnaan graph

7. Implementasi pada jaringan komunikasi

8. Network routing, dll.