algoritma semut

b. Algoritma semut
Algoritma Semut diadopsi dari perilaku
koloni semut yang dikenal sebagai sistem semut
(Dorigo, 1996). Secara alamiah koloni semut
mampu menemukan rute terpendek dalam perjalanan
dari sarang ke tempat-tempat sumber makanan.
L R L R
(a) (b)
L R L R
(c) (d)
Gambar 1. Perjalanan semut menemukan sumber
makanan.
Koloni semut dapat menemukan rute
terpendek antara sarang dan sumber makanan
berdasarkan jejak kaki pada lintasan yang telah
dilalui. Semakin banyak semut yang melalui suatu
lintasan, maka semakin jelas bekas jejak kakinya.
Hal ini menyebabkan lintasan yang dilalui semut
dalam jumlah sedikit, semakin lama semakin
berkurang kepadatan semut yang melewatinya, atau
bahkan akan tidak dilewati sama sekali. Sebaliknya
lintasan yang dilalui semut dalam jumlah banyak,
semakin lama akan semakin bertambah kepadatan
semut yang melewatinya, atau bahkan semua semut
melalui lintasan tersebut.
Gambar 1.a menujukkan perjalanan semut
dalam menemukan jalur terpendek dari sarang ke
sumber makanan, terdapat dua kelompok semut
yang melakukan perjalanan. Kelompok semut L
berangkat dari arah kiri ke kanan dan kelompok
semut R berangkat dari kanan ke kiri. Kedua
kelompok berangkat dari titik yang sama dan dalam
posisi pengambilan keputusan jalan sebelah mana
yang akan diambil. Kelompok L membagi dua
kelompok lagi. Sebagian melalui jalan atas dan
sebagian melalui jalan bawah. Hal ini juga berlaku
pada kelompok R. Gambar 1.b dan Gambar 1.c
menunjukkan bahwa kelompok semut berjalan pada
kecepatan yang sama dengan meninggalkan feromon
atau jejak kaki di jalan yang telah dilalui. Feromon
yang ditinggalkan oleh kumpulan semut yang
melalui jalan atas telah mengalami banyak
penguapan karena semut yang melalui jalan atas
berjumlah lebih sedikit dari pada jalan yang di
bawah. Hal ini disebabkan jarak yang ditempuh
lebih panjang daripada jalan bawah. Sedangkan
feromon yang berada di jalan bawah penguapannya
cenderung lebih lama. Karena semut yang melalui
jalan bawah lebih banyak daripada semut yang
melalui jalan atas. Gambar 1.d menunjukkan bahwa
semut-semut yang lain pada akhirnya memutuskan
untuk melewati jalan bawah karena feromon yang
ditinggalkan masih banyak. Sedangkan feromon
pada jalan atas sudah banyak menguap sehingga
semut-semut tidak memilih jalan atas tersebut.
Semakin banyak semut yang melalui jalan maka
semakin banyak semut yang mengikutinya, semakin
sedikit semut yang melalui jalan, maka feromon
yang ditinggalkan semakin berkurang bahkan hilang.
Dari sinilah kemudian terpilihlah jalur terpendek
antara sarang dan sumber makanan.
Dalam algoritma semut, diperlukan beberapa
variabel dan langkah-langkah untuk menentukan
jalur terpendek