Pages

Kamis, 29 Agustus 2013

Ant Colony Optimization Algorithm / Algoritma Semut

Algoritma semut adalah algoritma yang baru berkembang dalam dunia komputer. Algoritma semut terinspirasi dari tingkah laku semut. Algoritma semut sangat cocok untuk masalah-masalah yang memerlukan optimalisasi.  Algoritma semut pertama kali diperkenalkan oleh Dorigo dan kawan-kawan. 

Algoritma Semut merupakaan algoritma yang terinspirasi dari alam yang bertipe phenotypic. Berbeda dengan algoritma genetika yang bertipe genotypic. Maksud dari phenotypic adalah representasi dari solusinya sudah bisa bernilai real value, biasanya kalau algoritma yang bertipe genotypic representasi solusinya masih dalam bentuk kode-kode seperti bilangan biner.

Cara kerja dari algoritma semut adalah mirip seperti tingkah laku semut yang ada di alam. Semut memiliki sebuah mekanisme yang dapat mereka gunakan agar mereka tidak tersesat dalam mencari makanan. Semut memiliki zat khusus yang bernama feromon, zat inilah yang mereka gunakan dalam menjelajah diluar sarang mereka. Zat feromon dapat mereka gunakan untuk menandai jalur yang mereka pergunakan.

Semut dalam mencari makanan diluar sarang sangat berbahaya untuk hidupnya. Oleh karena itu semut mencari jalur yang paling aman dan paling cepat untuk mereka lewat dengan aman. Biasanya semakin bagus jalur dari sarang kepusat makana maka akan semakin banyak feromon yang ada pada jalur tersebut. feromon yang dikeluarkan oleh semut itu pada hakikatnya dapat menguap, namun apabila jalur tersebut sangat bagus maka semut senantiasa mempertebal zat feromon tersebut pada jalur tersebut. Berbeda dengan jalur yang kurang bagus, biasanya feromon akan mereka biarkan menguap begitu saja sehingga apabila zat tersebut sudah menghilang maka jalur tersebut tidak akan mereka gunakan lagi.

Dari konsep tersebut maka algoritma semut sangat berguna untuk mencari solosi masalah-masalah optimasi seperti masalah NP hard. Masalah dalam NP hard yang lumayan terkenal adalah Travelling salesmen Problem (TSP). pada TSP bertujuan untuk mencari jalur terpendek untuk seorang penjual barang agar melalui setiap kota dengan jalur terpendek. 

Algoritma semut dalam TSV dapat dijelaskan dengan langkah-langkah berikut :
  1. inisialisasi semua jalur dan feromon awal
  2. tempatkan tiap-tiap semut pada masing-masing kota
  3. ulangi langkah 3 sampai 7 jika belum habis iterasinya
  4. untuk setiap semut telusuri semua kota
  5. pilih jalur antara dua kota dengan mempertimbangkan feromon
  6. setelah semut mengunjungi tiap kota maka lakukan pengecekan jalur terpendek
  7. jika jalur terpendek baru lebih pendek dari jalur terpendek lama maka simpan jalur baru.
Demikian sekilas tentang algoritma semut. Semoga artikel singkat ini bermanfaat untuk pembaca.

Tidak ada komentar:

Posting Komentar