3. Metode ant colony.
Koloni semut merupakan algorima yang bersifat heuristik untuk menyelesaikan masalah optimasi. Algoritma ini diinspirasikan oleh lingkungan kooni semut pada saat mencari makanan. Semut dapat mencari makanan. Semut dapat mencari lintasan terpendek dari suatu sumber makanan menuju sarangnya, tanpa harus melihatnya secara langsung. Karena terinspirasi dari semut asli dinamakan algoritma koloni semut. Semut-semut mempunyai penyelesaian yang unik dan sangat maju, yaitu menggunakan jejak pheromone pada suatu jalur untuk berkomunikasi dan membangun solusi, semakin banyak jejak pheromone ditinggalkan, maka jalur tersebut akan diikuti oleh semut lain.
Gambar. Metode ant colony.
menurut Yuwono, Sasmito, Aribowo, dan Wardoyo (2009), 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 x dan y (koordinat) atau dij (jarak antar kota)
3. Penentuan kota berangkat dan kota tujuan
4. Tetapan siklus-semut (Q)
5. Tetapan pengendali intensitas jejak semut ( )
6. Tetapan pengendali visibilitas ( )
7. Visibilitas antar kota = 1/dij ( ij)
8. Jumlah semut (m)
9. Tetapan penguapan jejak semut ( )
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 yang telah ditentukan.
- Langkah 2 :
Pengisian kota pertama ke dalam tabu list. Hasil inisialisasi kota pertama semut pada langkah 1 harus
diisikan sebagai elemen pertama tabu list. Hasil dari langkah ini adalah terisinya elemen pertama tabu list setiap semut dengan indeks kota pertama.
- Langkah 3 :
Penyusunan jalur kunjungan setiap semut ke setiap kota. Koloni semut yang sudah terdistribusi ke kota pertama akan mulai melakukan perjalanan dari kota pertama 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 hingga mencapai kota yang telah ditentukan. 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,
p k/ij = 0, untuk j lainnya dengan i sebagai indeks kota asal dan j sebagai indeks kota tujuan.
- Langkah 4 :
a. Perhitungan panjang jalur setiap semut.
Perhitungan panjang jalur tertutup (length closed tour) atau Lk setiap semut dilakukan setelah
satu siklus diselesaikan oleh semua semut. Perhitungan 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 diperoleh harga minimal panjang jalur tertutup setiap
siklus atau LminNC dan harga minimal panjang jalur 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 perubahannya adalah:
dengan k ij adalah perubahan harga intensitas jejak kaki semut antar kota setiap semut yang dihitung berdasarkan persamaan
untuk (i,j) kota asal dan kota tujuan dalam tabuk
k/ij = 0, untuk (i,j) lainnya
- 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 dua 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 dua dengan harga parameter intensitas jejak kaki semut antar kota yang sudah diperbaharui.
itulah sedikit penjelasan dari metode ant colony. semoga dapat membantu.
sumber:
Yuwono, Sasmito, Aribowo, dan Wardoyo. (2009), Implementasi Algoritma Koloni Semut Pada Proses Pencarian Jalur Terpendek Jalan Protokol Di Kota Yogyakarta, seminar nasional informatika 2009 (semnasIF 2009), hal A-111-A-120.
Tidak ada komentar:
Posting Komentar