Sekilas Tentang Algoritma Semut ( AntNet Algorithm )

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. 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 akan semakin jelas bekas jejak kakinya. Hal ini akan menyebabkan lintasan yang dilalui semut dalam jumlah sedikit, semakin lama akan 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 akan melalui lintasan tersebut.

Gambar berikut menujukkan perjalanan semut dalam menemukan jalur terpendek dari sarang ke sumber makanan.

 

 Perjalanan semut menemukan sumber makanan.

Gambar a di atas menunjukkan ada dua kelompok semut yang akan melakukan perjalanan. Satu kelompok bernama L yaitu kepompok yang berangkat dari arah kiri yang merupakan sarang semut dan kelompok lain yang bernama kelompok R yang berangkat dari kanan yang merupakan sumber makanan. Kedua kelompok semut dari titik berangkat sedang dalam posisi pengambilan keputusan jalan sebelah mana yang akan diambil. Kelompok semut L membagi dua kelompok lagi. Sebagian melalui jalan atas dan sebagian melalui jalan bawah. Hal ini juga berlaku pada kelompok semut R. Gambar b dan gambar 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 dikarenakan 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 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 bawah maka semakin banyak semut yang mengikutinya.   

Demikian juga dengan jalan atas, semakin sedikit semut yang melalui jalan atas, 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, yaitu: 

Langkah 1 :  
a. Inisialisasi harga parameter-parameter algoritma. Parameter-parameter yang di inisialisasikan adalah :  

1. Intensitas jejak semut antar kota dan perubahannya (τij)
2. Banyak kota (n) termasuk koordinat (x,y) atau jarak antar kota (dij)
3. Kota berangkat dan kota tujuan
4. Tetapan siklus-semut (Q) 
5. Tetapan pengendali intensitas jejak semut (α), nilai α ≥ 0
6. Tetapan pengendali visibilitas (β), nilai β ≥ 0
7. Visibilitas antar kota = 1/dij (ηij) 
8. Banyak semut (m) 
9. Tetapan penguapan jejak semut (ρ) , nilai  ρ harus > 0 dan  < 1 untuk mencegah jejak pheromone yang tak terhingga.
10. Jumlah siklus maksimum (NCmax) bersifat tetap selama algoritma dijalankan, sedangkan  τij akan selalu diperbaharui harganya pada setiap siklus algoritma mulai dari siklus pertama (NC=1) sampai tercapai jumlah siklus maksimum (NC=NCmax) atau sampai terjadi konvergensi.        

b.  Inisialisasi kota pertama setiap semut. Setelah inisialisasi  τij dilakukan, kemudian m semut ditempatkan pada kota pertama tertentu secara acak.  

Langkah 2 : 
Pengisian kota pertama ke dalam  tabu list. Hasil inisialisasi kota pertama setiap semut dalam langkah 1 harus  diisikan sebagai elemen pertama  tabu list. Hasil dari langkah ini adalah terisinya elemen pertama  tabu list  setiap semut dengan indeks kota tertentu, yang berarti bahwa setiap tabuk(1) bisa berisi indeks kota antara 1 sampai n sebagaimana hasil inisialisasi pada langkah 1.

Langkah 3 :
Penyusunan rute kunjungan setiap semut ke setiap kota. Koloni semut yang sudah terdistribusi ke sejumlah atau setiap kota, akan mulai melakukan perjalanan dari kota pertama masing-masing sebagai kota asal dan salah satu kota-kota lainnya sebagai kota tujuan. Kemudian dari kota kedua masing-masing, koloni semut akan melanjutkan perjalanan dengan memilih salah satu dari kota-kota yang tidak terdapat pada  tabuk sebagai kota tujuan selanjutnya. Perjalanan koloni semut berlangsung terus menerus sampai semua kota satu persatu dikunjungi atau telah menempati  tabuk. Jika  s menyatakan indeks urutan kunjungan, kota asal dinyatakan sebagai  tabuk(s) dan kota-kota lainnya dinyatakan sebagai {N-tabuk}, maka untuk menentukan kota tujuan digunakan persamaan probabilitas kota untuk dikunjungi sebagai berikut :

dengan i sebagai indeks kota asal dan j sebagai indeks kota tujuan.

Langkah 4 :
a. Perhitungan panjang rute setiap semut.
Perhitungan panjang rute tertutup (length closed tour) atau Lk setiap semut dilakukan setelah satu siklus diselesaikan oleh semua semut. Perhitungan ini dilakukan berdasarkan tabuk masing-masing dengan persamaan berikut :

dengan dij adalah jarak antara kota i ke kota j yang dihitung berdasarkan persamaan :

b. Pencarian rute terpendek.
Setelah Lk setiap semut dihitung, akan didapat harga minimal panjang rute tertutup setiap siklus atau LminNC  dan harga minimal panjang rute tertutup secara keseluruhan adalah atau Lmin.

c. Perhitungan perubahan harga intensitas jejak kaki semut antar kota.
Koloni semut akan meninggalkan jejak-jejak kaki pada lintasan antar kota yang dilaluinya. Adanya penguapan dan perbedaan jumlah semut yang lewat, menyebabkan kemungkinan terjadinya perubahan harga intensitas jejak kaki semut antar kota. Persamaan perubahan ini adalah : 

adalah perubahan harga intensitas jejak kaki semut antar kota setiap
semut yang dihitung berdasarkan persamaan :

Langkah 5 : 

 a. Perhitungan harga intensitas jejak kaki semut antar kota untuk siklus selanjutnya. Harga intensitas jejak kaki semut antar kota pada semua lintasan antar kota ada kemungkinan berubah karena adanya penguapan dan perbedaan jumlah semut yang melewati. Untuk siklus selanjutnya, semut yang akan melewati lintasan tersebut harga intensitasnya telah berubah. Harga intensitas jejak kaki semut antar kota  untuk siklus selanjutnya dihitung dengan persamaan :

b. Atur ulang harga perubahan intensitas jejak kaki semut antar kota.  Untuk siklus selanjutnya perubahan harga intensitas jejak semut antar kota perlu diatur kembali agar memiliki nilai sama dengan nol.

Langkah 6 :
Pengosongan  tabu list, dan ulangi langkah 2 jika diperlukan.  Tabu list perlu dikosongkan untuk diisi lagi dengan urutan kota yang baru pada siklus selanjutnya, jika jumlah siklus maksimum  belum tercapai atau belum terjadi konvergensi. Algoritma diulang lagi dari langkah 2 dengan harga parameter intensitas jejak kaki semut antar kota yang sudah diperbaharui.