Algoritma ACO (Ant Colony Optimization) 15


Algoritma ACO (Ant Colony Optimization) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik tujuan dengan jarak paling rendah.
Ant Colony Optimization adalah teknik probabilitas untuk menyelesaikan permasalahan, berdasarkan tingkah laku semut dalam sebuah koloni yang mencari sumber makanan. Teknik ini dapat digunakan untuk menemukan solusi dari permasalahan kompleks untuk mendapatkan jalur optimal dalam grafik.



Diasumsikan ada sebaran titik yang harus dilalui semuanya
semua titik terhubung secara langsung dengan titik-titik lainnya, dan semua jalurnya dapat dilalui 2 arah
Jarak yang dihasilkan untuk masing-masing titik akan diambil secara acak antara angka 1 sampai 8
Tentukan Jalur yang harus diambil untuk mengelilingi semua titik dengan jarak terpendek



Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan alpha dan beta
Alpha dan Beta adalah koefisien yang digunakan untuk perhitungan taueta
Semakin besar nilai alpha, semakin besar nilai taueta
Semakin besar nilai beta, semakin kecil nilai taueta

* Tentukan rho dan Q
rho dan Q adalah koefisien yang digunakan untuk perhitungan feromon
Semakin besar nilai rho, semakin kecil nilai feromon
Semakin besar nilai beta, semakin besar nilai feromon

* Tentukan jumlah titik yang harus dilalui
Diasumsikan dalam kasus ini, ada 8 titik yang harus dilalui

* Tentukan jumlah semut yang melakukan pencarian jalur
Nantinya setiap semut akan melalui semua titik yang telah disebutkan diatas
Diasumsikan dalam kasus ini, ada 10 semut yang melakukan pencarian jalur

* Tentukan banyak iterasi yang digunakan dalam perhitungan
Nantinya setiap semut akan melakukan perulangan ini untuk melakukan pencarian jalur
Diasumsikan dalam kasus ini, jumlah iterasi adalah 100 kali


Langkah-langkah penggunaan algoritma ini adalah

1. Tentukan Array Jarak untuk setiap titik yang tersedia
Sesuai asumsi diatas, jarak untuk tiap titik akan dihitung secara acak dengan angka 1 sampai 8

2. Tentukan Array Semut yang digunakan untuk melakukan pencarian jalur
Setiap semut pada Array Semut akan memiliki array Jejak untuk mencatat jalur-jalur yang dilewati
Beri nilai jejak acak sebagai jejak awal mula dari setiap semut

3. Cari Jejak Terbaik dan Jarak Terpendek dari setiap jejak awal pada semua semut
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

* Gunakan Fungsi ini untuk mencari Jejak Terbaik yang memiliki Jarak Terpendek
Jejak terbaik adalah jejak yang memiliki jarak terpendek
Perhitungan mengenai jarak terpendek dilakukan oleh fungsi cariJarakTerpendek

* Gunakan Fungsi ini untuk mencari jarak terpendek pada setiap jejak.
Jarak terpendek dihitung dari jumlah Jarak yang ditempuh pada Array Jejak

4. Tentukan Array feromon
Feromon digunakan untuk perhitungan pencarian titik berikutnya
Beri nilai awal feromon dengan nilai yang sangat rendah sekali, yaitu 0.01

5. Lakukan proses pencarian jalur sebanyak n iterasi (poin 5a – 5c)

5a. Lakukan proses pencarian jejak baru pada setiap semut
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

5a1. Lakukan perulangan pada setiap semut
Lakukan pencarian jejak baru ke semua titik-titik lain secara acak

5a1a. Untuk semut dengan index k, yang berada pada titik titikX, hitung probabilitas untuk berpindah ke semua titik tujuan

5a1b. Untuk semut dengan index k, yang berada pada titik titikX, tentukan titik acak berikutnya

5b. Lakukan proses perubahan nilai feromon pada masing-masing jarak antar titik
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

5b1. Update semua nilai feromon untuk setiap jalur
Cari jarak terpendek pada jalur tersebut
Jika titik-titiknya bersebelahan dan jaraknya bersebelahan, maka nilai feromon akan semakin besar

5c. Cari Jejak Terbaik dan Jarak Terpendek dari jejak semut yang telah mengalami perubahan
Apabila jarak terpendek ternyata lebih baik (rendah) daripada jarak terpendek terbaik, maka ambil nilai jejak nya sebagai jejak terbaik


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd16a


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.


Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *

15 pemikiran di “Algoritma ACO (Ant Colony Optimization)

    • pip Penulis

      Algoritma ini seharusnya dapat digunakan untuk melakukan optimasi terhadap kasus apapun termasuk didalamnya adalah optimasi parameter

    • pip Penulis

      Saya belum pernah mendengar secara detail dari kasus tersebut, tetapi seharusnya jika berbicara model pencarian jalur secara umum, algoritma ini tentunya dapat menyelesaikan permasalahan tersebut

    • pip Penulis

      Selama kasus tersebut bersifat optimasi, artinya jawaban yang didapatkan adalah memenuhi beberapa konstrain tertentu dan dihitung menggunakan rumus fitness, maka seharusnya algoritma ini dapat digunakan untuk menyelesaikan permasalahan anda.

  • Wati

    Berdasarkan kode diatas, definisi / variable titikX, titikTerpakai seperti apa ? Diprogram tidak ada untuk kedua variabel tersebut.
    Dan juga method isBersebelahan ?

    • pip Penulis

      Variabel titikX digunakan sebagai lokasi semut pada jalur tertentu yang sudah ditentukan sebelumnya. Jika terdapat jalur A-B-C maka pada lokasi pertama nilai variabel titikX adalah A, pada lokasi kedua nilai variabel titikX adalah B, pada lokasi ketiga nilai variabel titiX adalah C.

      Variabel titikTerpakai digunakan untuk mencatat titik2 mana sajakah sudah sudah dilalui dan belum dilalui. Hal ini bertujuan untuk mencegah titik yang sudah dilalui akan dipilih kembali ke dalam rute berikutnya. Jika sebuah jalur dibentuk dari 3 buah titik A, B, C, maka variabel ini diperlukan untuk mencegah solusi seperti A-B-A, C-B-B, dst.

      Metode isBersebelahan digunakan untuk mengetahui apakah parameter titik pertama dan kedua pada jalur semut bersebelahan atau tidak. Sebagai contoh jika terdapat jalur A-B-C, maka titik A dan titik B adalah bersebelahan sehingga fungsi isBersebelahan akan mengembalikan nilai true, sedangkan titik A dan titik C tidak bersebelahan sehingga fungsi isBersebelahan akan mengembalikan nilai false.

    • pip Penulis

      Bahasa pemrograman yang saya gunakan adalah Visual Basic. Hasil implementasi dapat anda ujicoba secara langsung dengan mengunduh file yang sudah saya sertakan diatas.