Belajar Ant Colony, beserta Studi Kasusnya | Kecerdasan Buatan dengan Meniru Semut

Pengenalan Ant Colony    

ACO atau ant colony mengambil inspirasi dari perilaku mencari makan beberapa spesies semut. Semut ini menyimpan feromon di tanah untuk manandai jalur yang menguntungkan yang harus diikuti oleh anggota koloni lainnya. ACO adalah teknik probabilistic untuk memecahkan masalah komputasi yang dapat direduksi untuk menemukan jalur yang bai melalui grafik.Algoritma ini merupakan anggota dari keluarga algoritma antcolony, dalam metode swarm intelligence. Kecerdasan swarm adalah pendekaran yang relative baru untuk memecahkan masalah yang mengambil inspirasi dari perilaku social serangga dan hewan lain.

Sejarah Ant Colony            

Ant system adalah algoritma ACO pertama yang diusulkan dalam literature. Ant System awalnya diajukan oleh Marco Dorigin 1992, dalam tesis PhD-nya. Algoritma pertama bertujuan untuk mencari jalur yang optimal dalam grafik, berdasarkan perilaku semut. Kemudian pada tahun 1997, Dorigo dan Gambardella mengusulkan ACS (Ant Colony System). Perbedaan penting antara ACS dan AS adalah bentuk aturan keputusan yang digunakan semut selamat proses konstruksi. ACS menggunakan aturan proporsional pseudorandom. 1996, Hoos dan Stützle menemukan max-min ant system (MMAS). MMAS berbeda dari AS karena hanya semut terbaik yang menambahkan jejak feromon, dan nilai minimum dan maksimum feromon secara eksplisit.

Natural Ants (Sifat/Karakter Semut)

Dalam eksperimen yang dikenal sebagai “eksperimen jembatan ganda '', sarang koloni semut Argentina dihubungkan ke sumber makanan melalui dua jembatan yang panjangnya sama, seperti pada Gambar 1 (a). Awalnya, setiap semut secara acak memilih salah satu dari dua jembatan. Namun, karena fluktuasi acak, setelah beberapa waktu salah satu dari dua jembatan menghadirkan konsentrasi feromon yang lebih tinggi daripada yang lain dan, oleh karena itu, menarik lebih banyak semut. 

Hal ini membawa lebih banyak feromon pada jembatan tersebut sehingga lebih menarik sehingga setelah beberapa waktu seluruh koloni menyatu menuju penggunaan jembatan yang sama. Perilaku tingkat koloni ini, berdasarkan autokatalisis, yaitu memanfaatkan umpan balik positif, dapat digunakan semut untuk menemukan jalur terpendek antara sumber makanan dan sarangnya.

Goss dkk.  dianggap sebagai varian dari percobaan jembatan ganda di mana satu jembatan secara signifikan lebih panjang dari yang lain, seperti pada Gambar 1 (b). Dalam kasus ini, fluktuasi stokastik pada pemilihan awal jembatan jauh berkurang dan mekanisme kedua memainkan peran penting: semut yang secara kebetulan memilih jembatan pendek adalah yang pertama mencapai sarang. 

Oleh karena itu, jembatan pendek menerima feromon lebih awal daripada jembatan panjang dan fakta ini meningkatkan kemungkinan semut lebih lanjut memilihnya daripada jembatan panjang.

Konsep Dasar Ant Colony

Untuk menerapkan ACO, masalah optimasi diubah menjadi masalah mencari jalur terbaik pada grafik berbobot. Semut buatan (selanjutnya disebut semut) secara bertahap membangun solusi dengan bergerak sesuai grafik. Proses konstruksi solusi bersifat stokastik dan bias oleh model feromon, yaitu, seperangkat parameter yang terkait dengan komponen grafik (baik node maupun edge) yang nilainya dimodifikasi pada saat runtime oleh semut. 

Semut menyusun solusi sebagai berikut. Setiap semut mulai dari kota yang dipilih secara acak (puncak dari grafik konstruksi). Kemudian, pada setiap langkah konstruksi, ia bergerak di sepanjang tepi grafik. Setiap semut menyimpan ingatan tentang jalannya, dan dalam langkah-langkah berikutnya ia memilih di antara tepi-tepi yang tidak mengarah ke simpul yang telah dikunjunginya. 

Semut membangun solusi setelah mengunjungi semua simpul pada grafik. Pada setiap langkah konstruksi, semut secara probabilistik memilih tepi untuk diikuti di antara yang mengarah ke simpul yang belum dikunjungi. 

Aturan probabilistik bias oleh nilai feromon dan informasi heuristik: semakin tinggi feromon dan nilai heuristik yang terkait dengan sebuah sisi, semakin tinggi probabilitas semut akan memilih sisi tertentu tersebut. Setelah semua semut menyelesaikan turnya, feromon di tepinya diperbarui. 

Setiap nilai feromon awalnya diturunkan dengan persentase tertentu. Setiap tepi kemudian menerima sejumlah feromon tambahan yang sebanding dengan kualitas larutan yang dimilikinya (ada satu larutan per semut). Prosedur ini diterapkan berulang kali sampai kriteria terminasi terpenuhi.

Elemen Ant Colony

• Defining the problem. Langkah pertama penerapan ACO pada masalah optimasi kombinatorial (COP) terdiri dari pendefinisian model COP sebagai triplet (S, Ω, f), dimana:S adalah ruang pencarian yang ditentukan melalui serangkaian variabel keputusan diskrit yang terbatas; Ω adalah sekumpulan batasan di antara variabel; danf: S → R_0 ^ + adalah fungsi tujuan yang akan diminimalkan (karena memaksimalkan f sama dengan meminimalkan over -f, setiap COP dapat digambarkan sebagai masalah minimisasi).

• ACO meta-heuristic. Dalam ACO, semut buatan membangun solusi untuk masalah optimasi kombinatorial dengan melintasi grafik konstruksi yang terhubung sepenuhnya, yang didefinisikan sebagai berikut. Pertama, setiap variabel keputusan yang dipakai 〖 X〗_i^ =v_i^j  disebut komponen solusi dan dilambangkan dengan c_ij. Himpunan semua komponen solusi yang mungkin dilambangkan dengan C. Kemudian grafik konstruksi GC (V, E) didefinisikan dengan menghubungkan komponen C baik dengan himpunan simpul V atau dengan himpunan tepi EA nilai jejak feromon Tij diasosiasikan dengan masing-masing komponen cij. Nilai feromon memungkinkan distribusi probabilitas berbagai komponen solusi untuk dimodelkan. Nilai feromon digunakan dan diperbarui oleh algoritma ACO selama pencarian.

• Edge-Selection. Semut adalah agen komputasi sederhana dalam algoritme pengoptimalan koloni semut. Ini secara berulang membangun solusi untuk masalah yang dihadapi. Solusi perantara disebut sebagai kondisi solusi. Pada setiap iterasi algoritme, setiap semut berpindah dari status x ke status y, sesuai dengan solusi perantara yang lebih lengkap. Jadi, setiap ant k menghitung satu set Ak (x) dari ekspansi yang layak ke keadaan saat ini di setiap iterasi, dan berpindah ke salah satu dari kemungkinan tersebut. Untuk ant k, probabilitas P_xy^k untuk pindah dari keadaan x ke keadaan y bergantung pada kombinasi dua nilai, yaitu daya tarik η_xy dari gerakan tersebut, sebagaimana dihitung oleh beberapa heuristik yang menunjukkan keinginan apriori dari gerakan itu dan tingkat jejak T_xy dari gerakan tersebut, yang menunjukkan seberapa mahirnya di masa lalu untuk membuat gerakan tersebut. 
  

• Daemon Action. Setelah solusi dibuat, dan sebelum memperbarui nilai feromon, seringkali beberapa tindakan khusus untuk masalah mungkin diperlukan. Ini sering disebut aksi daemon, dan bisa digunakan untuk mengimplementasikan aksi khusus dan / atau terpusat, yang tidak bisa dilakukan oleh semut tunggal. Tindakan daemon yang paling banyak digunakan terdiri dari aplikasi pencarian lokal ke solusi yang dibangun: solusi yang dioptimalkan secara lokal kemudian digunakan untuk memutuskan nilai pheromone mana yang akan diperbarui.

• Update Pheromone. Setelah semua semut menyelesaikan solusi, jejak diperbarui oleh,
  
  
  
  dimana Txy^k adalah jumlah feromon yang disimpan untuk transisi keadaan η_xy, adalah koefisien penguapan feromon dan ΔT_xy^k adalah jumlah feromon yang disimpan, biasanya diberikan untuk masalah TSP (dengan gerakan yang sesuai dengan busur grafik) oleh 

  
  dimana Lk adalah biaya tur semut ke-k (biasanya panjang) dan Q adalah konstanta

  
  

Aplikasi Ant Colony

• ACO diperpanjang untuk proses terintegrasi dan desain sistem kontrol
• Optimasi koloni semut untuk masalah kontrol optimal
• Algortima Ant Colony dalam  optimasi parameter PID untuk sistem kontrol torsi langsung mining hoist

Aplikasi Pencarian Rute Terbaik dengan Metode Ant Colony Optimazation (ACO)

https://jurnal.ugm.ac.id/ijccs/article/view/3052 

Pengawalan Lalu Lintas adalah suatu kegiatan penyelenggaran pengamanan bergerak di jalan dalam rangka melindungi keselamatan jiwa manusia, harta benda, kegiatan VVIP/VIP/ Protokol kenegaraan secara terus menerus selama perjalanan dari satu tempat ke tempat lain dengan menggunakan kendaraan bermotor sehingga kegiatan dapat berjalan aman, tertib dan lancar. Pengambilan keputusan rute jalan yang akan dilalui berdasarkan pertimbangan situasi jalan (jarak tempuh, banyak lubang, banyak tikungan dan kepadatan arus lalu lintas).

Ant Colony Optimization (ACO) merupakan teknik probabilistik untuk memecahkan masalah perhitungan dengan menemukan jalur terbaik melalui graf, algoritma ini terinspirasi dari perilaku semut bersama dengan koloninya dalam mencari makanan. Simple Additive Weighting (SAW) merupakan salah satu metode untuk menyelesaikan masalah Multi-Attribute Decision Making (MADM) dengan mencari penjumlahan terbobot dari rating kinerja setiap alternatif pada semua atribut.

Penelitian ini mengkombinasikan metode Ant Colony Optimization dengan Simple Additive Weighting.

Implementasi Algoritma Ant Colony Optimization pada Aplikasi Pencarian Lokasi Tempat Ibadah Terdekat di Kota Bandung

https://join.if.uinsgd.ac.id/index.php/join/article/view/v1i13 

Indonesia merupakan negara yang penduduknya memeluk berbagai agama, yaitu di antaranya agama: Islam, Kriten, Budha, Hindu. Bandung merupakan kota yang banyak wisatawannya, baik wisatawan lokal maupun mancanegara, fasilitas umum yang ada di Kota Bandung dibutuhkan, salah satunya tempat ibadah. Informasi tentang tempat ibadah cukup diperlukan oleh para wisatawan, karena cukup sulit mendapatkan informasi tempat ibadah di Kota Bandung, khususnya sulit dalam mendapatkan rute terdekat (shourtest paht) menuju tempat ibadah tersebut. Penelitian ini dibuat untuk merancang sebuah aplikasi yang memberikan informasi serta petunjuk arah tempat ibadah di Kota Bandung, dengan menerapkan Algoritma Ant Colony Optimization. Aplikasi ini digunakan pada perangkat Smatrphone/Android, oleh karena itu, aplikasi ini cukup flexibel untuk digunakan. Aplikasi ini menggunakan dukungan web service, sehingga data mudah di inputkan oleh admin.

Berdasarkan pembahasan penelitian yang sudah penulis buat, maka dapat diambil kesimpulan sebagai berikut : 

1. Telah berhasil membuat aplikasi SIG pencarian Tempat Ibadah terdekat kota Bandung berbasis Android. 2. Telah berhasil menerapkan algoritma Ant Colony Optimization pada aplikasi.Pencarian Tempat Ibadah terdekat di Kota Bandung. 

3. Aplikasi ini dapat menampilkan info lokasi Tempat Ibadah beserta rute terpendek pada peta. 

4. Aplikasi ini dapat membantu para wisatawan dalam mencari Tempat Ibadah terdekat tanpa bertanya-tanya pada masyarakat sekitar. 

5. Aplikasi ini mejadikan Google Map API sebagai pemetaannya. 

6. Aplikasi ini mengefesienkan waktu user dalam mencari Tempat Ibadah terdekat.