Algoritma semut diperkenalkan oleh Moyson dan Manderick dan secara meluas dikembangkan oleh Marco Dorigo, merupakan teknik probabilistik untuk menyelesaikan masalah komputasi dengan menemukan jalur terbaik melalui grafik. Algoritma ini terinspirasi oleh perilaku semut dalam menemukan jalur dari koloninya menuju makanan.
Pada dunia nyata, semut berkeliling secara acak, dan ketika menemukan makanan mereka kembali ke koloninya sambil memberikan tanda dengan jejak feromon. Jika semut-semut lain menemukan jalur tersebut, mereka tidak akan bepergian dengan acak lagi, melainkan akan mengikuti jejak tersebut, kembali dan menguatkannya jika pada akhirnya merekapun menemukan makanan.
Seiring waktu, bagaimanapun juga jejak feromon akan menguap dan akan mengurangi kekuatan daya tariknya. Lebih lama seekor semut pulang pergi melalui jalur tersebut, lebih lama jugalah feromon menguap. Sebagai perbandingan, sebuah jalur yang pendek akan berbaris lebih cepat, dan dengan demikian kerapatan feromon akan tetap tinggi karena terletak pada jalur secepat penguapannya. Penguapan feromon juga mempunyai keuntungan untuk mencegah konvergensi pada penyelesaian optimal secara lokal. Jika tidak ada penguapan sama sekali, jalur yang dipilih semut pertama akan cenderung menarik secara berlebihan terhadap semut-semut yang mengikutinya. Pada kasus yang demikian, eksplorasi ruang penyelesaian akan terbatasi.
Oleh karena itu, ketika seekor semut menemukan jalur yang bagus (jalur yang pendek) dari koloni ke sumber makanan, semut lainnya akan mengikuti jalur tersebut, dan akhirnya semua semut akan mengikuti sebuah jalur tunggal. Ide algoritma koloni semut adalah untuk meniru perilaku ini melalui 'semut tiruan' berjalan seputar grafik yang menunjukkan masalah yang harus diselesaikan.
Algoritma optimisasi koloni semut telah digunakan untuk menghasilkan penyelesaian yang mendekati optimal pada masalah salesman yang melakukan perjalanan. Algoritma semut lebih menguntungkan daripada pendekatan penguatan tiruan (simulaten annealing) dan algoritma genetik saat grafik mungkin berubah secara dinamis; algoritma koloni semut dapat berjalan secara kontinyu dan menyesuaikan dengan perubahan secara waktu nyata (real time). Hal ini menarik dalam routing jaringan dan sistem transportasi urban.
The Ant Colony System
ANTS
Kalau kamu ngeliat judul diatas apa yang kamu bayangin??Hmm…kartun keluaran Pixma picture??atau ini adalah artikel yang ngebahas tentang struktur anatomi semut(bisa ga sih…)??Apa pun itu asal kamu berpikiran tentang hewan
Tulisan ini emang menceritakan tentang semut and the ganks (koloni semut)tapi bukan secara biologi ya, melainkan diambil dari sudut pandang ilmu komputer. Emang apa hubungannya?? Inilah kehebatan dari makhluk kotak itu. Hampir segala bidang kehidupan bisa diselesaikan secara komputerisasi. Tapi bukan nyelesaian masalah si semut melainkan menyelesaikan berbagai macam masalah komputerisasi yang diinspirasi dari perilaku koloni semut (ant colony optimization). So,let’s check it out
A Little Facts About Ants
Semut seperti yang kita ketahui, berukuran mini dan selalu hidup berkelompok. Jarang kita temui semut itu jalan sendirian (kalopun ada mungkin nyasar atau lagi patah hati jadi pengennya sendirian. J). Koloni semut punya team work yang solid mulai dari bangun rumah sampe cari makanan, jadi jangan heran kalo kamu nemuin cake kesukaanmu yang baru kamu tinggalin bentar udah rame digerogoti sama mereka. Tapi kepikiran ga sih bagaimana koloni semut bisa nyampe ke sumber makanannya secara cepat padahal daerah itu tadinya ga ada semut!?
Nah,inilah fakta kecilnya yaitu semut bisa menemukan rute terpendek dari sarang ke sumber makanannya.
How Ants Communicate Each Other??
Semut dapat berkomunikasi dengan teman – temannya tidak secara langsung melainkan berkomunikasi dengan suatu zat kimia yang disebut dengan feromon. Feromon adalah zat atau yang biasanya disebut parfum serangga dimana dengan adanya zat ini maka setiap semut dapat mengenali posisi temannya sehingga semua semut dapat berkumpul kembali dengan koloninya. Setiap semut ketika melewati suatu jalur tertentu akan meninggalkan jejak feromon (Pheromone Trail). Jejak ini kemudian akan diikuti oleh semut – semut yang lainnya. Pada awalnya semut berpencar dari sarang mereka menuju ke sumber makanan. Semut berikutnya yang melalui jalur tersebut dapat mengidentifikasi feromon yang diletakkan oleh semut sebelumnya, memutuskan dengan probabilitas yang tinggi untuk mengikutinya, dan menguatkan jalur yang dipilihnya itu dengan feromon miliknya. Perilaku inilah yang menyebabkan semut dapat menemukan jalur terpendek. Dengan kata lain semakin besar feromon yang terdapat pada jalur itu maka jumlah semut yang melewatinya juga akan semakin besar bahkan kemungkinan semua semut akan melalui jalur tersebut.
Gambarannya adalah sebagai berikut:
Dari gambar ini dapat terlihat bahwa pada awalnya semut berjalan pada jalur yang sama dengan asumsi semua semut berjalan dengan kecepatan yang sama. Kita anggap A adalah sarang dan E adalah sumber makanan. Kemudian perhatikan gambar (b), pada gambar terdapat rintangan yang membuat jalur terpisah menjadi dua. Semut akan berpencar, beberapa akan ke jalan H dan yang lain akan memilih jalan C. Semut yang berjalan dari jalur C akan lebih cepat sampai ke sumber makanan karena jalur C lebih pendek. Hal ini juga mempengaruhi jalur pulangnya, maka dapat dipastikan semut yang berjalan pada jalur C akan tiba di sarang lebih dulu daripada yang melewati jalur H. Hal ini akan diikuti oleh semut yang lainnya berdasarkan dengan jejak feromon tadi. Berdasarkan dari semut yang duluan sampai maka tingkat semut yang melewati jalur C akan lebih besar karena tingkat feromon yang ada pada jalur C lebih besar dan ini akan mempengaruhi semut yang lainnya untuk mengikuti jalur tersebut sehingga semut akan memilih satu jalur yaitu jalur yang terpendek.
Computer And Ants
Berdasarkan dari perilaku semut inilah terciptalah algoritma koloni semut (ant colony system). Ant Colony System (ACS) merupakan salah satu algoritma yang menerapkan prinsip dari swarm intelligence (kecerdasan komunitas) ,yaitu algoritma yang didasarkan atau terinspirasi dari perilaku sosial serangga dan perilaku sosial binatang lainnya dimana dalam suatu komunitas terdapat beberapa agen yang saling berinteraksi, bernegoisasi, dan berkoordinasi satu sama lain dalam mengerjakan suatu pekerjaan bersama. Konsep kerjasama ini yang dikenal dengan multi agent system (MAS). Untuk konsep MAS lebih detil dapat didownload dari e-book ini
Algoritma ini dikemukakan pertama kali oleh Marco Dorigo dan Luca M. Gambardella pada tahun 1997. Ant System telah banyak diterapkan dalam berbagai kajian permasalahan optimisasi kombinatorial seperti traveling salesman problem (TSP), quadratic assignment problem, jobscheduling, vehicle routing, graph coloring, dan network routing[Dorigo, Di Caro, dan Gambardella]. Jadi semut yang ada pada komputer adalah agent – agent cerdas.
Dikutip dari: http://id.wikipedia.org/wiki/Algoritma_Semut
Tidak ada komentar:
Posting Komentar