ANT COLONY OPTIMIZATION: ALGORITMA OPTIMASI ALA SEMUT

Ant colony optimization (ACO) adalah metode optimasi metaheuristik yang terinspirasi dari perilaku koloni semut. Ide awalnya berasal dari pengamatan semut-semut dalam mencari sumber makanan. Meskipun masing-masing individu semut memiliki kemampuan kognitif yang terbatas, tetapi dengan bekerja sama mereka mampu menemukan jalan atau lintasan terpendek antara sumber makanan dan sarang mereka.

Ketika mencari sumber makanan, awalnya kawanan semut mengekspor area sekitar sarangnya secara acak. Jika salah satu semut menemukan sumber makanan, informasi lintasan yang telah dilalui semut tersebut disimpan kemudian semut kembali ke sarangnya dengan membawa makanan. Selama perjalanan kembali ke sarangnya, semut tersebut meninggalkan jejak yang berupa feromon. Feromon ini adalah zat kimia yang semut keluarkan untuk menandai jalur yang telah dilewati sehingga jalur ini menjadi pemandu semut lain menuju ke sumber makanan. Proses yang telah disebutkan di atas diilustrasikan oleh Gambar 1 di bawah ini.

 

Gambar 1. Kawanan semut mencari lintasan atau jalur terpendek antara sarangnya (N) dan sumber makanan (F) (Hemmati-Sarapardeh et al, 2020).

 

Kemampuan koloni semut pada kehidupan nyata diadopsi menjadi sebuah metode untuk mendekati solusi yang optimal dari sebuah permasalahan, oleh karena itu metode ini disebut ant colony optimization. Awalnya, metode ACO hanya untuk mendekati solusi optimal dengan domain diskrit, kemudian dikembangkan untuk permasalahan yang lebih umum dengan domain kontinu. Secara sederhana metode ACO terdiri dari beberapa langkah berikut,

1.     Kawanan semut ditempatkan di titik-titik awal.

2.     Semut-semut bergerak pada jalur-jalurnya secara acak dan meninggalkan jejak feromon pada jalur yang dilalui. Jalur yang lebih dekat antara titik awal dan titik solusi memiliki konsentrasi feromon lebih banyak.

3.     Semut-semut akan memilih jalur dengan jumlah konsentrasi feromon lebih banyak.

4.     Feromon pada jalur akan menguap atau konsentrasinya menurun ketika jalur tersebut jarang dilalui semut.

5.     Seiring berjalannya waktu, semut-semut akan memilih jalur terpendek karena konsentrasi feromonnya lebih kuat. Jalur ini merupakan jalur menuju solusi terbaik yang ditemukan.

Beberapa aspek teknis yang perlu diperhatikan pada metode ACO ini diantaranya terkait parameter tuning yang akan sangat menentukan performa dalam mendekati solusi, secara komputasional akan mahal ketika berhadapan dengan masalah skala besar, dan tidak ada kepastian solusi yang diperoleh merupakan solusi yang pasti terbaik. Kelebihan metode ACO adalah efektif dalam menangani masalah optimasi yang kompleks, dapat beradaptasi dengan baik jika terdapat perubahan data atau batasan masalah, memiliki kemampuan yang baik dalam eksplorasi (mencari solusi baru) dan eksploitasi (memanfaatkan solusi yang sudah ditemukan), serta metode ini relatif mudah untuk diimplementasikan. ACO dapat diterapkan pada beberapa permasalahan seperti masalah rute perjalanan/kendaraan, penjadwalan, jaringan komunikasi/komputer, optimasi logistik, evakuasi bencana, dan lain sebagainya. -Harmon-

 

Referensi

Hemmati-Sarapardeh, A., Larestani, A., Menad, N.A. and Hajirezaie, S., 2020. Applications of artificial intelligence techniques in the petroleum industry. Gulf Professional Publishing.