January 20, 2012

Algoritma Semut

2 comments
algoritma semut pict

Ant Colony Optimization (ACO) Algorithm 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.

Photobucket

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.

Ilmuwan Pencetus Algoritma Semut?

dorigo marco pictDorigo Marco pada tahun 1992 meneliti algoritma semut 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)
- Ant Colony System (ACS)
- Approximate Nondeterministic Tree Search (ANTS)
- Hyper-Cube Framework for ACO
- Rank-Based ANt System (ASrank)
- Min-Max Ant System (MMAS)
- 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

Tags:



Artikel Terkait :



2 Responses so far

  1. Di terapkan pada coding blog manteb nih

Leave a Reply