algoritma koloni semut

Download Algoritma Koloni Semut

Post on 26-Oct-2015

83 views

Category:

Documents

1 download

Embed Size (px)

DESCRIPTION

kecerdasan buatan

TRANSCRIPT

Algoritma Koloni Semut

Algoritma Koloni SemutOleh :

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 sungguhansebuah koloni individu bekerjasamasebuah jalur pheromone bagi komunikasi stigmergy localsebuah rangkaian pergerakan untuk menemukan jalan tersingkatsebuah ketetapan yang menggunakan informasi local tanpa melihat ke depan.Koloni dari individu yang bekerja samaSemut 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 LokalSemut 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 StokastikSebagaimana 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