Algoritma Semut

Algoritma semut diperkenalkan oleh Moyson dan Manderick dan secara meluas dikembangkan oleh Marco Dorigo, merupakan teknik probabilistik untuk menyelesaikan masalah komputasi dengan menemukan jalur terbaik melalui grafik. Algoritma ini terinspirasi oleh perilaku semut dalam menemukan jalur dari koloninya menuju makanan.

Nov11

Algoritma Semut (Ant Algorithm) merupakan algoritma yang  dimunculkan  sebagai  suatu  pendekatan  multi-agen terhadap  optimasi  berbagai permasalahan yang berkaitan dengan graf. Sampai saat ini, berbagai  upaya  pengembangan  dilakukan  untuk memperluas pemanfaatan dari Algoritma Semut. Berbagai pemanfaatan  yang  sudah  umum  digunakan  antara  lain untuk  menyelesaikan  permasalahan  rute  kendaraan, pengurutan  sekuensial,  pewarnaan  graf,  permasalahan routing pada jaringan dan berbagai pemanfaatan lainnya.

Algoritma Semut terinspirasi oleh pengamatan  terhadap suatu koloni  semut. Semut merupakan hewan yang hidupsebagai suatu kesatuan dalam koloninya dibandingkan jika dipandang sebagai individu yang hidup sendiri-sendiri dan tidak  bergantung  terhadap  koloninya.  Suatu  perilaku penting  dan  menarik  untuk  ditinjau  dari  suatu  koloni semut  adalah  perilaku mereka  pada  saat mencari makan, terutama  bagaimana  mereka  mampu  menentukan  rute untuk  menghubungkan  antara  sumber  makanan  dengan sarang mereka.

Ketika  berjalan  menuju  sumber  makanan  dan sebaliknya,  semut  meninggalkan  jejak  berupa  suatu  zat yang  disebut  Pheromone.  Semut-semut  dapat  mencium Pheromone,  dan  ketika  memilih  rute  yang  akan  dilalui, semut  akan memiliki  kecenderungan  untuk memilih  rute yang memiliki tingkat konsentrasi Pheromone yang tinggi. Jejak  Pheromone  tersebut  memungkinkan  semut  untuk menemukan  jalan  kembali  ke  sumber  makanan  atau sarangnya.

Seiring  waktu,  bagaimanapun  juga  jejak  Pheromone akan  menguap  dan  akan  mengurangi  kekuatan  daya tariknya.  Lebih  lama  seekor  semut  pulang  pergi melalui suatu  jalur,  lebih  tinggi  pula  jumlah  Pheromone  yang menguap.  Sebagai  perbandingan,  sebuah  jalur  yang pendek  akan  diikuti  oleh  semut  lainnya  dengan  lebih cepat, dan dengan demikian konsentrasi Pheromone akan tetap tinggi.

Penguapan  Pheromone  juga  mempunyai  keuntungan untuk  mencegah  konvergensi  pada  penyelesaian  optimal secara  lokal.  Jika  tidak  ada  penguapan  sama  sekali,  jalur yang  dipilih  semut  pertama  akan  cenderung  menarik secara  berlebihan  terhadap  semut-semut  yang mengikutinya.  Pada  kasus  yang  demikian,  eksplorasi ruang penyelesaian akan terbatasi.

Oleh  karena  itu,  ketika  seekor  semut menemukan  jalur yang  bagus  (jalur  yang  pendek)  dari  koloni  ke  sumber makanan,  semut  lainnya  akan  mengikuti  jalur  tersebut, dan  akhirnya  semua  semut  akan  mengikuti  sebuah  jalur tunggal.  Ide  algoritma  koloni  semut adalah untuk meniru perilaku  ini melalui  ‘semut  tiruan’  berjalan  seputar  grafik yang menunjukkan masalah yang harus diselesaikan. Perilaku  mengikuti  jejak  Pheromone  tersebut  telah dibuktikan  secara  eksperimental,  digunakan  oleh  koloni semut  untuk  mengetahui  rute  terpendek  untuk  mencapai sarang  atau  sumber  makanan  berdasarkan  jejak-jejak Pheromone  yang ditinggalkan oleh masing-masing  semut yang ada.

Berdasarkan  perilaku  tersebut, maka  dikembangkanlah suatu  algoritma  untuk  menyelesaikan  suatu  masalah komputasi  dengan  menemukan  jalur  terbaik  melalui grafik.

Pada  tahun 1996, dunia AI pun  ikut belajar dari semut  dengan  diperkenalkannya  algoritma  semut, atau  Ant  Colony  Optimization,  sebagai  sebuah simulasi  multi  agen  yang  menggunakan  metafora alami  semut  untuk  menyelesaikan  problem  ruang fisik. Algoritma  semut  diperkenalkan  oleh  Moyson dan Manderick dan  secara meluas  dikembangkan oleh  Marco  Dorigo,  merupakan  teknik probabilistik  untuk  menyelesaikan  masalah komputasi  dengan  menemukan  jalur  terbaik melalui  grafik.  Algoritma  ini  terinspirasi  oleh perilaku  semut  dalam  menemukan  jalur  dari koloninya menuju makanan.