Ant-Colony Optimization

Ant-Colony Optimization (ACO) termasuk dalam kelompok Swarm Intelligence,  yang merupakan salah satu jenis pengembangan paradigma yang digunakan untuk menyelesaikan masalah optimasi di mana inspirasi  yang  digunakan  untuk  memecahkan masalah tersebut berasal dari perilaku kumpulan atau kawanan (swarm) serangga. ACO adalah teknik probabilitas untuk menyelesaikan permasalahan, berdasarkan tingkah laku semut dalam sebuah koloni yang mencari sumber makanan. ACO biasanya digunakan untuk menyelesaikan discrete optimization problems dan persoalan yang kompleks dimana terdapat banyak variabel. Hasil yang diperoleh dengan menggunakan ACO, walaupun tidak optimal namun mendekati optimal.

Ant-based techniques pertama kali  digunakan  oleh  Dorigo  et.  al [1996] dengan menggunakan ACO untuk  menyelesaikan Traveling Salesman Problem (TSP).

ACO   sudah   diterapkan   di   berbagai   masalah   seperti   Vehicle Routing Problems, penjadwalan   proyek dengan   sumber daya terbatas,   data  mining,   penjadwalan pekerjaan  (job  scheduling) dan  beberapa  masalah  kombinatorial  yang  lain.

Cara Kerja ACO

Salah  satu  hal  yang  menarik  dari  perilaku  semut adalah kemampuannya  dalam  menemukan  jarak  terpendek  antara sarang  mereka dan  sumber makanan.

Setiap semut dalam kawanan yang berjalan akan meninggalkan pheromone (semacam zat kimia) pada jalur yang dilaluinya. Pheromone ini menjadi semacam sinyal bagi sesama semut.

Pheromone adalah  zat  kimia  yang  berasal  dari  kelenjar  endokrin  dan   digunakan   oleh   makhluk   hidup   untuk   mengenali   sesama   jenis,   individu lain, kelompok, dan untuk membantu proses reproduksi. Berbeda dengan  hormon,  pheromone  menyebar  ke  luar  tubuh  dan  hanya  dapat  mempengaruhi dan dikenali oleh individu lain yang sejenis (satu spesies).

Sumber: https://www.sciencedirect.com/science/article/abs/pii/S0142061515005840

Jalur yang pendek akan menyisakan sinyal yang lebih kuat. Semut berikutnya, pada saat memutuskan jalur mana yang harus dipilih, biasanya akan  cenderung  memilih  untuk  mengikuti  jalur  dengan  sinyal  yang  paling kuat, sehingga  jalur  terpendek  akan  ditemui  karena  lebih  banyak  semut  yang  akan melewati jalur tersebut. Semakin   banyak   semut   yang   menempuh   suatu   lintasan   tertentu,   maka aroma pheromone   pada   lintasan   tersebut   akan   semakin   kuat.

Pada awalnya semut akan terdistribusi merata melalui dua lintasan. Setelah beberapa saat semut-semut mulai memilih lintasan terpendek karena pheromone yang ditinggalkan semut akan mengumpul di lintasan yang lebih pendek.

• Seekor semut k pada  simpul i akan  memilih  simpul j yang  dituju  pada  layer berikutnya dengan probabilitas:
• dimana α menunjukkan derajat kepentingan pheromone dan N_i^(k) adalah pilihan yang dipunyai semut k (neighborhood) pada saat ia berada pada simpul i. Neighborhood dari semut k pada simpul i akan mengandung semua simpul yang bisa dituju yang tersambung secara langsung ke simpul i, kecuali simpul yang sudah dikunjungi sebelumnya.
• Seekor semut k ketika   melewati   ruas   akan   meninggalkan      Jumlah pheromone  yang  terdapat  pada  ruas ij setelah  dilewati  semut k diberikan  dengan rumus:
• Dengan meningkatnya  nilai  pheromone  pada  ruas i−j,  maka  kemungkinan  ruas  ini akan  dipilih  lagi  pada  iterasi  berikutnya  semakin    Setelah  sejumlah  simpul dilewati maka akan terjadi penguapan pheromone dengan aturan sebagai berikut:

Variasi Ant Algorithm

• Versi pertama disebut dengan Ant System (AS), yang diaplikasikan pada Travelling Salesman Problem
• Elitist Ant System (EAS)
• Rank-Based Ant System (ASrank)
• Min-Max Ant System (MMAS)
• Ant Colony System (ACS)
• Approximate Nondeterministic Tree Search (ANTS)
• Hyper-Cube Framework for ACO