Ant Colony Optimization (ACO) diadopsi dari perilaku koloni semut yang dikenal sebagai system semut. Secara alamiah koloni semut mampu menemukan rute terpendek dalam perjalanan dari sarang menuju ke sumber makanan dankembali lagi, pada saat semut berjalan, semut meninggalkan sebuah informasi yang disebut pheromone, di tempat yang dilaluinya dan menandai rute tersebut. Pheromonedigunakan sebagai komunikasi antar semut pada saat membangun rute.
Langkah-langkah membangun solusi dengan kombinasi metode ACO:
1. Inisialisasi parameter yang dimiliki ACO :a.Intensitas pheromone(τij). b.Tetapan siklus semut (q0). c.Tetapan pengendali intensitas visibilitas (β), nilai β ≥ 0. d.Tetapan pengendali pheromone(α), nilai α ≥ 0. e.Jumlah ants(m). f.Tetapan penguapan pheromone(ρ), nilai ρ harus > 0 dan < 1. g.Jumlah siklus maksimum (NCmax).
2. Memberikan nilai bobot (w) untuk jarak, tikungan, lubang, kepadatan.
3. Menghitung visibilitas antar node dengan SAW
4. Mentukan node selanjutnya yang akan dituju, ulangi proses sampai node tujuan tercapai. Dengan menggunakan persamaan (3)atau persamaan (4) dapat ditentukan node mana yang akan dituju yaitu dengan :a.Jika q ≤ q0 maka pemilihan node (aturan transisi) yang akan dituju menggunakan persamaan (3.)b.Jika q > q0 maka pemilihan node yang akan dituju (aturan transisi) menggunakan persamaan (4)
5. Apabila telah memilih node yang dituju, node tersebut disimpan ke dalam tabu list untuk menyatakan bahwa node tersebut telah menjadi bagian dari membangun solusi. Setelah itu intensitaspheromonedi sisi tersebut diubah dengan menggunakan persamaan (5).Perubahan pheromonetersebut dinamakan perubahan pheromonelocal. Aturan transissi kembali dilakukan sampai node tujuan tercapai.
6. Apabila node tujuan telah dicapai, panjang rute, banyaknya lubang, banyaknya tikungan dan kepadatan dari masing-masing ants akan dilakukan perangkingan dengan metode SAW untuk mencari path yang terbaik
7. Pembaruan pheromonepada node-node yang termuat dalam path terbaik tersebut menggunakan persamaan (6). Perubahan pheromoneini dinamakan perubahan pheromoneglobal.
8. Pengosongan tabu list, tabu list perlu dikosongkan untuk diisi lagi dengan urutan node yang baru. Algoritma diulang lagi dari langkah 2 dengan harga parameter intensitas pheromoneyang sudah di perbarui.
9. Setelah semua proses telah diuji (jumlah siklus maksimum sudah terpenuhi) maka akan di dapatkan path terbaik.
Tidak ada komentar:
Posting Komentar