Tugas RPL 2

Teori Koloni Semut(ANT COLONI)
Referensi:http://risetoperasi.wordpress.com/2009/01/21/ant-colony-optimization/

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.

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.