ALGORITMA SEMUT

Ant Colony Optimization (ACO) Algorithm

What the…?

ACO atau Algoritma semut merupakan algoritma yang digunakan untuk menyelesaikan masalah - masalah optimasi yang terinspirasi dari perilaku semut. Sebut saja Artificial Ant ( semut tiruan ).

Saat ini sedang banyak dilakukan penelitian terhadap perilaku alam yang mungkin bisa diterapkan untuk mencari solusi pada permasalahan - permasalahan optimasi. Kita sudah sering mendengar JST dan Algoritma Genetika yang meniru system kerja tubuh manusia. Perilaku hewan juga ditiru, burung, lebah, angsa… dan algoritma semut hanya salah satunya.

Perilaku Semut Yang Mana?

Pada saat semut menemukan sumber makanan, maka semut perlu menentukan jalur yang terpendek antara sumber makanan dan sarang semut. Disinilah peran teman - teman atau ‘koloni’ semut. Pekerjaan menelusuri jalur didistribusikan kepada beberapa agen semut. Pada awalnya semut - semut tersebut akan melalui semua jalur yang memungkinkan secara acak. Kemudian jalur yang terpendek pada saat itu dibubuhi jejak, yang disebut dengan pheromone. Pada dunia nyata, pheromone merupakan alat komunikasi berupa hormon yang dikeluarkan oleh semut sebagai penunjuk jalan bagi semut yang lain.

Ilustrasi koloni semut menemukan jalur terpendek untuk mencari makanan

Dengan adanya informasi pheromone, maka semut - semut selanjutnya tidak akan berjalan secara acak lagi, namun akan lebih tertarik mengikuti jalur yang ada pheromonenya. Semakin banyak semut melalui suatu jalur, semakin banyak pula jumlah pheromone yang tertinggal di jalur tersebut. Sehingga, lama kelamaan semua semut melalui satu jalur yang seragam, yaitu jalur yang terpendek. Perilaku semut yang seperti ini merupakan salah satu bentuk autocatalytic-suatu perulangan dengan feedback yang positif.

Siapa pencetus Algoritma Semut?

Marco Dorigo

Dorigo Marco. Pada tahun 1992 sebagai thesis PhD nya. Setelah itu banyak dilakukan penelitian mengaplikasikan Algoritma Semut pada berbagai jenis permasalahan optimasi, dan muncul banyak variasi Algoritma Semut.

Macam-Macam Algoritma Semut?

- Versi pertama disebut dengan Ant System ( AS ), yang diaplikasikan pada TSP

- Elitist Ant System ( EAS )

- Rank - Based ANt System ( ASrank )

- Min - Max Ant System ( MMAS )

- Ant Colony System ( ACS )

- Approximate Nondeterministic Tree Search ( ANTS )

- Hyper - Cube Framework for ACO

- Dsb

Masing - masing punya karakteristik sendiri - sendiri yang membedakan. Tiap varian cocok untuk jenis permasalahan tertentu. walaupun ada banyak varaisi, basisnya tetaplah AS.

kutipan dari: http://alwaysrun.wordpress.com/2008/05/22/ant-colony-optimization-aco-algorithm/