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.
Untuk memudahkan kita membayangkan bagaimana perilaku semut untuk selalu menemukan jarak terpendek, silahkan perhatikan ilustrasi gambar di bawah.
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.
Nah 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.
Perlu 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 sudoku, Dorigo 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.
0 komentar:
Posting Komentar