Archive for November 20th, 2009

A Brief Introduction to Ant Colony Optimisation

Sedikit perkenalan mengenai algoritma optimisasi koloni semut.

Jadi begini. Ada algoritma yang dinamakan Ant Colony Optimisation (ACO). Katakan sekelompok semut ingin berburu makanan di N dan membawanya ke sarang F dengan peta seperti tergambar di bawah ini. Tiap kali semut berjalan, ia akan meletakkan feromon di tanah yang menarik semut berikutnya untuk mengambilnya. Ini adalah cara berkomunikasi secara stigmergis, yaitu dengan memodifikasi lingkungan. Pada tahap awal pencarian, semut-semut akan menunjukkan pola pemilihan jalur yang acak. Secara teoritis, probabilitas seekor semut untuk memilih jalur yang tersedia (misalnya dalam gambar di bawah ini ada 4) adalah 100% dibagi jumlah jalur. Namun, karena satu dan lain hal™, semut-semut cenderung memilih salah satu jalan. Akibatnya, feromon di jalur itu menjadi lebih banyak daripada feromon di jalur lain, dan pada kondisi akhir, mayoritas semut hanya akan melewati satu jalur.

Ant Colony Optimisation
Ant Colony Optimisation

Nah, algoritma ini juga bisa dipakai di Computer Science, misalnya untuk mencari jalur terpendek dari satu titik ke titik yang lain jika diketahui suatu graf yang memuat noktah-noktah yang mewakili lokasi dan jalur yang menghubungkan noktah-noktah tersebut. Teknik ini secara umum pertama kali diajukan oleh Marco Dorigo, yang sekarang menjadi profesor di Université Libre de Bruxelles, pada disertasi PhD-nya di Politecnico di Milano pada 1991. Seiring berjalannya waktu, algoritma ini terus dikembangkan dan variannya banyak diajukan. Salah satu implementasinya adalah Short-ACO (S-ACO). Pada teknik ini, semut secara eksplisit memiliki 2 “mode”, yaitu mode forward ketika mencari makanan, dan backward ketika kembali ke sarang. Beberapa perkembangan lain pada teknik ini adalah penghapusan kalang (jika ada) sesuai urutan jalur yang ditempuh semut, pemilihan jalur secara probabilistis ketika semut pada mode forward (pada mode ini semut tidak menjatuhkan feromon), intensitas feromon berdasarkan kualitas makanan, dan penguapan feromon yang mempengaruhi jumlah semut yang melewati sebuah jalur.

Wis semene dhisik. Ngantuk. Koreksi dipersilakan, dan terima kasih.

Kalau minta saus, silakan klik gambar di atas. 🙂

Referensi: Ant Colony Optimization

NB: Matur nuwun nggo si tong nyaring nanging berisi sing marakke aku krisis eksistensial njur sinau bab iki. Kowe wong Singapur, masiyo Cino nanging mungkin iso Boso Melayu. Ning rak kowe ra iso Basa Jawa to? :mrgreen:

Advertisements

lambrtz looks like this

Me

You can write comments in any language that you want, but please bear in mind that I only understand 4 languages: English, Indonesian, Javanese and Malay.

Archives

Categories

November 2009
S M T W T F S
« Oct   Dec »
1234567
891011121314
15161718192021
22232425262728
2930  
Click to view my Personality Profile page

Advertisements