Ant Colony

Algoritma Ant Colony (ACO)

Metode Ant Colony diadopsi dari perilaku koloni semut, secara alamiah koloni semut mampu menemukan rute terpendek dalam perjalanan dari sarang ke sumber makanan berdasarkan jejak semut-semut yang lain pada lintasan yang telah dilalui. Semakin sering lintasan dilalui maka semakin banyak pula semut lain yang akan melewati lintasan tersebut dan sebaliknya lintasan yang dilalui semut dalam jumlah sedikit, semakin lama semakin berkurang kepadatan semut yang melewatinya, atau bahkan tidak dilewati sama sekali.

Pada saat semut melewati lintasan, semut meninggalkan sejumlah informasi, berupa zat kimia yang disebut pheromone. Melalui pheromone inilah terjadi komunikasi tidak langsung dan juga pertukaran informasi antar semut selagi membangun suatu solusi. Proses peninggalan pheromone ini dikenal sebagai stigmetry, yaitu sebuah proses memodifikasi lingkungan yang tidak hanya bertujuan untuk mengingat jalan pulang ke sarang, tetapi juga memungkinkan para semut berkomunikasi dengan sesamanya.

Agar semut mendapatkan jalur optimal dalam perjalanannya, diperlukan beberapa proses :

1. Pada awalnya, semut berkeliling secara acak, hingga menemukan makanan. 

2. Ketika menemukan makanan mereka kembali ke sarangnya sambil memberikan tanda dengan jejak pheromone. 3. Jika semut-semut lain menemukan jalur tersebut, maka mereka tidak akan bepergian dengan acak lagi, melainkan akan mengikuti jejak tersebut. 

4. Jika pada akhirnya mereka pun menemukan makanan, mereka kembali menguatkan jejaknya. 

5. Pheromone yang berkonsentrasi tinggi pada akhirnya akan menarik semut-semut lain untuk berpindah jalur, menuju jalur paling optimal, sedangkan jalur lainnya akan ditinggalkan. 

Multiple Ant Colony System

Multiple Ant coloni system adalah salah satu pengembangan dari algoritma ant koloni sistem selain ACO. Pada algoritma ini biasanya akan dibentuk beberapa coloni semut atau yang sering disebut multiple ant colony yang memiliki tugas-tugas yang berbeda satu koloni dengan koloni lainnya. Sebagai contoh missal pada kasus VRP dengan time window dibentuk koloni pertama yang digunakan untuk meminimalisir jumlah kendaraan, sedangkan koloni yang kedua digunakan untuk meminimalisir biaya/cost. Berikut ini algoritma MACS untuk solusi kasus VRPTW.

Kelebihan Ant Colony 

Kelebihan dari algoritma Ant Colony Optimization(ACO) adalah optimal dalam mencari jarak terdekat, dan sudah mampu menghitung minimalisasi total time travel walaupun kurang optimal. Sedangkan kelemahan dari algoritma ini adalah komplexitas yang cukup banyak sehingga runing timenya juga cukup lama. kelebihan dari algoritma multiple ant colony system (MACS) hampir sama dengan ACO namun MACS lebih optimal dalam minimalisasi total time travel. sedangkan kelemahannya juga hampir sama dengan ACO, yang membedakannya adalah runing time yang cenderung lama karena komplesitas yang banyak. Sedangkan algoritma terakhir yaitu tabu search memiliki kelebihan dan kelemahan yang sama dengan ACO namun untuk runing timenya tabu search cenderung cukup cepat

Sumber :

Mulia, Dedi. 2011. Aplikasi Algoritma Ant System (AS)Dalam Kasus Traveling Salesman Problem (TSP).Jakarta: UIN Jakarta.