What the…?

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

Saat ini sedang banyak dilakukan penelitian terhadap perilaku alam yang mungkin bisa diterapkan untuk mencari solusi pada permasalahan2 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 teman2 atau ‘koloni’ semut. Pekerjaan menelusuri jalur didistribusikan kepada beberapa agen semut. Pada awalnya semut2 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 semut2 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 sendiri2 yang membedakan. Tiap varian cocok untuk jenis permasalahan tertentu. walaupun ada banyak varaisi, basisnya tetaplah AS.

Sudah Diaplikasikan pada Berbagai Macam Kasus

- Travelling Salesman Problem (TSP) dan Asymmetric TSP (ATSP)

- The Single Machine Total Weighted Tardiness Scheduling Problem (SMTWTP)

- The Generalized Assignment Problem (GAP)

- Quadratic Assignment Problem (QAP)

- Job-Shop Scheduling Problem (JSP)

- The Set Covering Problem (SCP)

- Network Routing Applications

- And many more…

Di TA gw sendiri ACO bakal diaplikasiin pada permasalahan Penjadwalan Sumber Daya Proyek. [TA? glek…]

More Papers…

www.cs.ualberta.ca/~bulitko/F02/papers/IC.06-ECAL92.pdf

http://iridia.ulb.ac.be/pub/mdorigo/journals/IJ.10-SMC96.pdf

http://www.agent.ai/doc/upload/200302/merk00_1.pdf

http://users.ox.ac.uk/~ierc0002/PPSN00.pdf