Ant Colony Optimization

Ant Colony Optimization (ACO), atau yang diterjemahkan secara bebas: Optimasi Koloni Semut, adalah sebuah teknik metaheuristik optimasi yang terinspirasi oleh perilaku nyata koloni semut dalam menemukan jarak terpendek dari sumber makanan kembali ke sarangnya tanpa menggunakan petunjuk visual. Teknik ini kemudian digunakan untuk penyelesaian permasalahan optimasi diskret.

aco

Untuk memudahkan kita membayangkan bagaimana perilaku semut untuk selalu menemukan jarak terpendek, silahkan perhatikan ilustrasi gambar di bawah.

ants

Gambar bagian a menunjukkan iring-iringan semut dari sumber makanan balik ke sarang. Kemudian jalur iring-iringan semut tersebut terputus (Gambar b). Anggap saja ada orang yang iseng meletakkan sesuatu di situ. Semut-semut yang berada sebelum jalur yang terputus itu lalu berusaha mencari jalan lain untuk mencapai kelompok semut yang berada di depannya, sebagaimana terlihat dalam Gambar c. Setelah beberapa saat, para semut itu berhasil menemukan jalan terpendek (Gambar d). Bukan tidak mungkin, sang semut berusaha mendaki benda yang menghalangi jalurnya, bila itu memungkinkan.

Untuk memastikan, silahkan Anda cari iring-iringan semut. Kemudian jadilah orang iseng dengan meletakkan ranting kecil, atau mungkin jari Anda, di tengah-tengah iringan tersebut. Perhatikanlah apa yang terjadi. Asal bukan semut merah yang Anda ganggu, pasti akan didapati fenomena yang sama.

antcolonyoptimization_smallNah perilaku semut inilah yang memotivasi Marco Dorigo dalam memperkenalkan Ant System (Sistem Semut), yang merupakan sistem ACO yang pertama, dalam disertasi PhD nya. Sistem Semut ini merupakan hasil penelitiannya mengenai pendekatan computational intelligence untuk permasalahan combinatorial optimization. Penelitian dilakukan di Politeknik Milan, Italia, bekerja sama dengan Alberto Colorni dan Vittorio Maniezzo. Dalam penelitian itu, Sistem Semut diterapkan pada penyelesaian masalah penugasan : TSP (Travelling Salesman Problem) dan QAP (Quadratic Assignment Problem).

Sejak tahun 1995, Dorigo, Luca Maria Gambardella dan Thomas Stützle bekerja mengembangkan pelbagai variasi dari paradigma Sistem Semut, termasuk hybrid version dengan teknik local search. Tahun 1997, Dorigo dan Gambardella memperkenalkan Ant Colony System (ACS), sementara setahun sebelumnya, Stützle bekerja sama dengan H.H. Hoos memperkenalkan MAX-MIN Ant System (MMAS). Keduanya, ACS dan MMAS, telah berhasil diterapkan ke dalam penyelesaian symmetric and asymmetric TSP.

Bau pada tahun 1999, metaheuristik Ant Colony Optimization (ACO) didefinisikan oleh Dorigo dan G. Di Caro.

aco-chronologyPerlu dicatat bahwa apa yang dikemukakan oleh Dorigo dalam tesisnya adalah merupakan artificial system yang terinspirasi oleh perilaku semut dalam menemukan jarak terpendek. Perilaku binatang kecil tersebut, dalam arti yang sebenarnya, telah diteliti dan dipublikasikan tahun 1959 oleh Pierre-Paul Grass. Namun penelitian yang intens baru dilakukan sejak tahun 1983, yang mana kemudian dimasukkan sebagai bagian dari kronologi algoritma ACO ini (lihat gambar sebelah kiri).

Kekonvergenan ACO sendiri, yang merupakan ‘syarat perlu’ bagi sebuah teknik optimasi, baru bisa dibuktikan tahun 2000 oleh W.J. Gutjahr. Setahun kemudian barulah muncul publikasi mengenai multicriteria ACO.

Karena banyaknya penerapan dari ACO ini, termasuk penerapan dalam permainan sudokuDorigo dan Stützle menulis sebuah buku yang bertujuan untuk mengulas penerapan-penerapan tersebut. Buku mereka berjudul Ant Colony Optimization dan diterbitkan oleh MIT Press tahun 2004.

Sumber:

http://www.aco-metaheuristic.org
http://en.wikipedia.org/wiki/Ant_colony_optimization

6 comments on “Ant Colony Optimization

  1. Ping-balik: Sudoku « Riset Operasi

  2. Ping-balik: Particle Swarm Optimization « Riset Operasi

  3. Ping-balik: Optimasi Lebah

  4. Ping-balik: Optimasi Lebah « Riset Operasi

  5. mas saya mau nanya (kalo boleh…hehe), kebetulan saya tertarik ngangkat ACO ini buat skripsi, nah perbedaan antara ACS dan MMAS itu apa ya? dan kecenderungan implementasi ACS dan MMAS itu biasanya pada bidang dan permasalahan apa?
    kalo boleh, bisa dishare link-link sumbernya mas…hehe…

    thanks ya…

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s