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:

7 Responses to “A Brief Introduction to Ant Colony Optimisation”


  1. 1 Nicholas Hwa 20/11/2009 at 12:24 AM

    Empat jam cuma habis satu bab.😥

  2. 2 Mizzy 20/11/2009 at 9:24 AM

    Duh jadi inget, dulu dan sekarang saya sering iseng menghalangi barisan semut yang lagi jalan berderetan dengan naro benda di antaranya, supaya barisan itu putus😆 . Menarik mengamati kebingungan apa yang dilakukan semut-semut itu😛

  3. 3 itikkecil 20/11/2009 at 11:05 AM

    *oot* saya menghalangi semutnya pake bedak…
    *digampar lambrtz*

  4. 4 S™J 20/11/2009 at 3:29 PM

    Kowe wong Singapur, masiyo Cino nanging mungkin iso Boso Melayu. Ning rak kowe ra iso Basa Jawa to?

    muahahahaa… haleluya😎

  5. 5 jensen99 21/11/2009 at 11:09 PM

    Ternyata itu melibatkan feromon… Selama ini kukira hanya komunikasi pake gesekan antena kalo ketemu semut lain saja.😀

  6. 6 Nicholas Hwa 21/11/2009 at 11:49 PM

    @Mizzy, itikkecil
    Kejam!😈

    @itikkecil
    Ee gakpapa kok kalau mau OOT, siapa tahu malah jadi ide baru.:mrgreen:

    @S™J
    Wakaka fokusnya ke sono.😆

    @jensen99
    Saya juga baru tahu waktu baca itu buku.😀

  7. 7 Kurotsuchi 23/11/2009 at 1:48 AM

    untung algoritma macam beginian nggak diaplikasikan di bidang studi saya. kalo enggak, per segmen nggak bisa ditrace untuk pencarian jalur berdasarkan waktu tempuh tercepat dan jarak terdekat:mrgreen:

    dalam jagad coding-mu, ini murni simulasi independen atau butuh data dasar berbasis line? kalo versi kami, coding memang ada sebagai dasar proklamasi dan eksekusi, tapi tetep dengan membaca atribut pada data dasar format vektor bertipe line, dimana dalam salah satu atributnya ada field numerik berisi informasi segmen length dan field numerik yang mewakili waktu tempuh.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




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