Algoritma Koloni Semut

Oleh :

Ia Mas Candra Dewi (F1B009019)Indra Sasmita

(F1B009027)

Algoritma semut pertama kali dikemukakan oleh Dorigo dan kawan - kawan sebagai sebuah pendekatan awal terhadap berbagai masalah sulit seperti masalah travelling salesman problem dan masalah tugas ganda. Banyak aktivitas tertentu sedang terjadi dalam dunia ilmu pengetahuan sekarang ini dengan memakai algoritma semut sebagai dasar untuk mengatasi masalah- masalah meentukan jalur terpendek seperti rute kendaraan, pesanan barang yang beruntun, warna grafik, jalur pada jaringan komunikasi dan sebagainya.

3.1 PengantarInspirasi algoritma semut dibangun oleh

pengamatan terhadap koloni semut sungguhan. Semut adalah serangga social, yakni serangga yang hidup secara berkoloni atau berkelompok dan mempunyai tingkah laku yang khas untuk lebih mempertahankan hidu koloni secara keseluruhan daripada hidup sebagai individu. Sebuah tingkah laku yang penting dan menarik dari koloni semut adalah cara mereka mencari makanan, khususnya bagaimana semut dapat menemukan jalan yang paling singkat dari sarang mereka ke tempta sumber- sumber makanan.

Semut berjalan dari sumber-sumber makana menuju ke sarang mereka atau sebaliknya, semut menyimpan di atas tanah sebuah zat yang disebut pheromone, membentuk jalur pheromone pada jalan mereka.

Hal ini telah dikemukakan bahwa tingkah laku untuk mengikuti jalur pheromone ini dapat memunculkan jalan yang paling singkat yakni jika ada jalan dari sarang ke lokasi sumber makanan, sebuah koloni semut mungkin dapat memanfaatkan jalur pheromone yang ditinggalkan oleh beberapa ekor semut untuk menemukan jalan yang paling singkat ke lokasi sumber makanan, kemudian pulang ke sarang.

Eksperimen tehadap jembatan ganda (bercabang dua) dikemukakan oleh Denebourg untuk dapat mempelajari cara semut mencari makanan. Sarang koloni semut dan spesies Linipithema humile dan sebuah sumber makanan dipisahkan oleh sebuah jembatan ganda (bercabang dua) yang masing-masing cabangnya mempunyai kekuatan yang sama. Semut dengan bebas bergerak antara sumber makanan dan sarang dan persentase semut yang memilih salah satu cabang yang diamati. Hasilnya adalah bahwa setelah sebuah fase transisi awal di mana semut mondar-mandir ke sana ke mari, akhirnya semut cenderung untuk berkumpul pada beberapa jalur.

Pada eksperimen di atas tidak ada pheromone pada dua cabang jembatan. Meskipun demikian, pada akhirnya beberapa ekor semut memilih salah satu cabang, yakni sebagaimana atas tampak pada gambar 3.1.B. Karena semut menyimpan pheromone ketika berjalan, tentu saja semut pada cabang atas yang lebih besar jumlahnya yang menghasilkan pheromone lebih banyak yang menyebabkan beberapa semut lain untuk memilih cabang tersebut. Kita pertama-tama mengandaikan bahwa jumlah pheromone pada sebuah cabang sesuai dengan jumlah semut yang berada pada cabang tersebut.

Pengandaian ini mengimplikasikan bahwa penguapan pheromone tidak diketahui. Jika sebuah eksperimen terakhir terjadi hampir sejam yang lalu, masuk akal untuk berasumsi bahawa jumlah pheromone yang menguap dapat diabaikan. Kemungkinan untuk memilih sebuah cabang pada waktu tertentu tergantung pada jumlah pheromone di cabang tersebut, yang sesuai dengan jumlah semut yang menggunakan cabang tersebut. Um dan Lin dimisalkan adalah jumlah semut yang telah menggunakan cabang atas dan bawah sesudah m semut menyeberangi jembatan dengan Um + Lm = m. Kemungkinan Pu (m) dengan semut (m + 1) yang memilih cabang di atas adalah:

Sedangkan kemungkinan PL(m) yang memilih cabang bawah adalah PL(m) =1- PU (n). Bentuk fungsional dari kemungkinan memilih sebuah cabang diperoleh dari mengikuti jalur pheromone, parameter h dan k kemungkinan untuk dicocokkan dengan bentuk data eksperimen. Dinamika pilihan semut mengikuti persamaan Um+1 = Um + 1, jika u m 1 m L P, U = U + y di mana y adalah sembarang variabel yang dijabarkan secara keseluruhan pada interval [0,1].

Proses yang dilakukan adalah jenis mekanisme optimasi terhadap setiap semut yang hanya member sedikit konstribusi, meskipun seekor semut sanggup menemukan jalan antara sarang dan tempat penyimpanan makanan, hanya semut tertentu yakni semut yang berasal dari koloni yang memiliki tingkah laku menemukan jalan tersingkat. Menurut marco dan Gianni di caro, eksperimen yang dilukiskan ini terjadi dalam keadaan khusus. Sebuah bukti pheromone membimbing untuk menemukan jalan tersingkat pada kasus umum diabaikan.

Bruckstein mempertimbangkan masalah penemuan sumber jalan tersingkat dengan petunjuk yang jelas dan bukan dengan pheromone dan membuktikan jalan semut berbentuk garis lurus. tingkah laku ini adalah sifat koloni. Juga menarik untuk diperhatikan bahwa semut dapat membentuk tingkah laku khusus ini dengan menggunakan bentuk sederhana dari komunikasi tidak langsung yang dperantarai oleh bentangan pheromone, yang dikenal sebagai stigmergy.

Grasse dalam karyanya Bellicositermes Natatalensi dan Cubitermes, mengemukakan bahwa stigmergy adalah stimulasi bagi para pekerja karena hasil yang mereka capai. Pekerja adalah salah satu kasta atau tingkat dalam koloni rayap. Sebagai contoh, Grasse mengamati bahwa Bellicositermes Natatalensi dan Cubitermes ketika membangun sarang baru, mulai dengan kegiatan membentuk pil tanah secara acak dan tidak terkoordinasi. Ketika pil tanah dibentuk dalam wilayah yang terbatas, mereka menjadi stimulus baru yang menyebabkan rayap menambah pil tanah sehingga tang dasar dan akhirnya seluruh sarang dibangun.

Kekhasan pada stigmergy yang berasal dari sarana- sarana komunikasi lain adalah sifat fisik komunikasi serangga yang berkomunikasi sesuai dengan modifikasi lingkungan fisik yang dikunjungi oleh serangga tersebut, sifat local informasi, yang hanya dapat diterima oleh serangga yang mengunjungi keadaan lingkungan dimana informasi tersebut disampaikan. Sikap yang memungkinkan untuk membahas komunikasi stigmergy ada, yaitu komunikasi tidak langsung yang diperantarai oleh modifikasi fisik keadaan lingkungan yang hanya dapat diterima secara local oleh pembawa komunikasi.

Bentuk stigmergy dari komunikasi pada umumnya dan komunikasi yang dipengaruhi oleh cara semut mencari makanan pada khususnya adalah sebuah bentuk yang menarik untuk system multi perantara artificial yang dipakai pada masalah- masalah optimasi yang sulit. Ciri stigmergy yang disebutkan diatas dapat dengan mudah disampaikan oleh perantara artificial dengan mengasosiasi masalah yang menampakan variable lingkungan yang tepat dan memberikan nilai variable terhadap perantara artificial. Cara semut mencari makanan adalah dengan komunikasi stigmergy dilaksanakan lewat pheromone yang disimpan d I tanah oleh semut ketika berjalan.

3.2 Optimasi Koloni Semut (ACO)

Metaheuristic ACO adalah istilah algoritma ACO akan digunakan untuk menunjukkan instansi metaheuristic ACO. Pada metaheuristic ACO, sebuah koloni semut buatan bekerjasama dalam menemukan solusi yang baik terhadap masalah- masalah optimasi yang sulit. Kerjasama adalah komponen utama algoritma ACO. Tujuannya adalah mengalokasikan sumber perhitungan pada serangkaian perantara sederhana yang relative (semut buatan) yang dikomunikasikan secara tidak langsung oleh stigmery. Solusi yang baik adalah sifat interaksi kooperatif perantara.

Persamaan dan perbedaan antara semut buatan dan semut sungguhan

1. sebuah koloni individu bekerjasama2. sebuah jalur pheromone bagi

komunikasi stigmergy local3. sebuah rangkaian pergerakan untuk

menemukan jalan tersingkat4. sebuah ketetapan yang

menggunakan informasi local tanpa melihat ke depan.

Koloni dari individu yang bekerja sama

Semut asli dalam algoritma semut terbentuk dari sebuah populasi atau koloni, dari kesatuan- kesatuan yang secara bersamaan maupun tidak menemukan solusi yang baik terhadap tanggung jawab yang diberikan. Meskipun kerumitan dari setiap semut buatan dapat membangun solusi yang mudah. Semut bekerjasama dengan sarana informasi yang mereka temukan pada lingkungan yang dikunjunginya.

Jalur pheromone dan stigmergySemut buatan memodifikasi beberapa aspek

lingkungan mereka sebagaimana dilakukan oleh semut sungguhan. Semut sungguhan menyimpan pada tempat yang mereka kunjungi sebuah zat kimia, pheromone sedangkan semut buatan mengubah sejumlah informasi yang tersimpan pada keadaan masalah yang mereka kunjungi.informasi ini melaporkan sejarah muktahir semut atau hasil dan dapat dibaca atau ditulis oleh semut tertentu yang memaasuki keadaan tersebut. Informasi angka ini disebut sebagai jalur pheromone buatan. Pada algoritma ACO, jalur pheromone hanya merupakan saluran komunikasi antar semut.

Bentuk komunikasi ini mempunyai peran utama dalam penggunaan pengetahuan kolektif. Efek utamanya adalah mengubah cara lingkungan dirasakan oleh semut. Biasanya pada algoritma ACO, mekanisme penguapan memodifikasi informasi pheromone sepanjang waktu. Peguapan pheromone memungkinkan koloni semut untuk secara perlahan melupakan sejarah masa lalu sehingga dapat melangsungkan penelitian pada arah baru tanpa menjadi terdesak oleh keputusan masa lampau.

Pencarian jalan tersingkat dan Perantara Lokal

Semut buatan dan semut sungguhan mempunyai sebuah tugas yang biasa, yaitu menemukan jalan tersingkat (harga minimum) yang menghubungkan tempat asal (sarang) dengan tempat tujuan (makanan) semut sesungguhnya pun demikian, bergerak langkah demi langkah melalui daerah yang berdekatan dari masalah. Tentu saja definisi tepat dari daerah dan batas adalah masalah khusus.

Kebijakan Transisi Keadaan yang Lamur/ Tidak Jelas dan Stokastik

Sebagaimana semut sungguhan, semut buatan mencari solusi dengan menggunakan kebijakan keputusan yang mungkin untuk bergerak melalui keadaan- keadaan yang berdekatan. Seperti semut sungguhan, semut buatan menggunakan informasi local dan tidak menggunakan pandangan ke depan untuk meramalkan keadaan yang akan dating. Oleh karena itu, penggunaan kebijakan mencakup tempat, ruang dan waktu.

Kebijakan adalah penggunaan informasi sebelumnya yang ditampilkan oleh pengkhususan masalah dan modifikasi local pada lingkungan (jalur pheromone) yang disebabkan oleh semut yang lalu. Semut buatan juga mempunyai ciri khusus yang tidak dimiliki oleh semut sungguhan.

1. semut buatan hidup dalam dunia yang khas dan pergerakannya tterjadi dari keadaan khas ke keadaan khas.

2. semut buatan mempunyai sebuah keadaan internal yang mengandung memori kegiatan semut di masa lampau.

3. semut buatan menyimpan sejumlah pheromone yang merupakan fungsi dari kualitas penemuan solusi. Pada realitas, beberapa semut sungguhan mempunyai tingkah laku yang sama, yaitu mereka menyimpan lebih banyak pheromone dalam kasus dimana sumber- sumber makanan lebih banyak.

4. pemakaian waktu pada semut buatan dalam menyimpan pheromone merupakan masalah relative dan sering tidak mencerminkan tingkah laku semut sungguhan. Sebagai contoh dalam banyak kasus, semut buatan memperbaharui jalur pheromone hanya setelah menemukan solusi.

5. algoritma ACO dapat diperkaya dengan kemampuan ekstra seperti melihat ke depan untuk memperbaiki efisiensi system secara keseluruhan seperti optimasi local melangkah mundur dan sebagainya yang tidak terdapat pada semut sungguhan.

Meta Heuristik ACO

Pada algoritma ACO, sebuah koloni dari semua semut yang berukuran terbatas dengan cirri yang dilukiskan, menemukan solusi yang berkualitas terhadap masalah optimasi. Setiap semut mencari solusi atau sebuah komponen solusi, mulai dari suatu keadaan awal yang dipilih menurut beberapa criteria.

Komposisi fungsional dari pheromone local yang tersedia dan nilai heuristic menentukan table keputusan semut, yakni table yang mungkindigunakan oleh keputusan semut untuk mengarahkan pencarian mereka ke tempat- tempat yang lebih menarik.

Seluruh meta heuristic ACO, disamping dua komponen yang dikemukan diatas yang terbentuk dari perspektif local, dapat juga terdiri dari beberapa komponen ekstra yang menggunakan informasi global dan yang bekerja di bawah aksi daemon/ tempat pheromone algoritma.

Secara umum, pembaharuan pheromone langkah demi langkah dan komponen- komponen pembaharuan pheromone saling terpisah dan hanya dalam beberapa kasus mereka hadir bersamaan atau keduanya tidak ada.

Algoritma ACO tersedia khusus untuk masalah yang didistribusikan dimana keberadaan sumber - sumber eksogen menentukan sebuah ketidakseimbangan masalah (dalam kasus nilai atau lingkungan). Sebagai contoh banyak yang berkaitan dengan transportasi pada hakikatnya didistribusikan dan selalu tidak mungkin untuk mendapatkan sebuah model tepat dari ketidaktepatan pokok yang mendasarinya. Sebaliknya karena stigmergy hanya merupakan metode komunikasi antar semut dan ditempatkan dalam ruang tertentu, algoritma ACO tidak dapat berhasil dengan baik dalam kasus dimana setiap keadaan mencakup lingkungan yang luas. Seekor semut yang mengunjungi sebuah keadaan dengan lingkungan yang luas berkemungkinan besar untuk bergerak semaunya. Karena itu, kemungkinan bahwa banyak semut mengunjungi keadaan yang sama sangatlah kecil, berbeda dengan penggunaan jalur pheromone.

3.3 PENERAPAN ALGORITMA ACO

Kelebihan Agoritma Semut

Algoritma Semut merupakan Algoritma yang dikembangkan untuk optimasi sistem-sistem yang berbasis TSP. Algoritma ini dapat menemukan rote terpendek dalam ruang pencarian yang lebih sempit dan waktu yang lebih singkat daripada metode konvensional.

Kekuatan algoritma semut terletak pada beberapa hal yang membedakan algoritma semut dengan algoritma pencarian lainnya, yaitu:

1. Algoritma semut bekerja dengan umpan balik yang positif dalam penemuan dan pencapaian solusi yang baik. Di mana pada suatu titik tertentu suatu kelompok memilih option yang berbeda dan salah sate memberikan basil yang baik, lalu di masa yang akan datang pilihan tersebut akan selalu digunakan.

2. Algoritma Semut mempunyai sifat sinergi yang tinggi. Keefektifan pencarian ditunjukkan dengan memberikan sejumlah semut yang saling bekerjasama dan setiap kerjasama akan saling independen.

3. Penggunaan struktur yang luas dalam algoritma semut membantu dalam menemukan solusi yang dapat diterima pada tahap awal proses penelitian.

4. Kecakapan algoritma ini untuk diaplikasikan pada versi yang sama untuk masalah kombinasi optimasi yang berbeda, seperti dalam ATSP (Asymmetric Travelling Salesman Problem) yang merupakan perluasan dari TSP (Travelling Salesman Problem).

5. Algoritma ini dapat diaplikasikan untuk masalah kombinasi optimalisasi yang lain, seperti QAP (Quadratic Assingment Problem) dan JSP (Job Shop Scheduling Problem) dengan perubahan yang minimal.

TERIMA

KASIH