algoritma semut

Download algoritma semut

Post on 05-Dec-2015

87 views

Category:

Documents

29 download

Embed Size (px)

DESCRIPTION

just read this paper, and you will understand what is this

TRANSCRIPT

MAKALAH KECERDASAN BUATANALGORITMA SEMUT, GENETIKA DAN PARTICLE SWARM

Oleh :Welly Nopi HealtantoI0411041

JURUSAN TEKNIK MESIN FAKULTAS TEKNIKUNIVERSITAS SEBELAS MARETSURAKARTA2015

A. Algoritma Semut (Ant Colony)Algoritma semutdiperkenalkan olehMoysondanManderickdan secara meluas dikembangkan olehMarco Dorigo merupakan teknik probabilistik untuk menyelesaikan masalah komputasi dengan menemukan jalur terbaik melalui grafik.Algoritmaini terinspirasi oleh perilakusemutdalam 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 jejakferomon. 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) danalgoritma genetiksaat grafik mungkin berubah secara dinamis; algoritma koloni semut dapat berjalan secara kontinyu dan menyesuaikan dengan perubahan secarawaktu nyata(real time). Hal ini menarik dalamroutingjaringan dan sistem transportasi urban.1. Pencarian jalur terpendekSecara umum penyelesaian masalah pencarian jalur terpendek dapat dilakukan menggunakan dengan dua metode, yaitu metode algoritma konvensional dan metode heuristik. Metode algoritma konvensional diterapkan dengan cara perhitungan matematis seperti biasa, sedangkan metode heuristik diterapkan dengan perhitungan kecerdasan buatan dengan menentukan basis pengetahuan dan perhitungannya. a. Metode konvensionalMetode konvensional berupa algoritma yang menggunakan perhitungan matematis biasa. Ada beberapa metode konvensional yang biasa digunakan untuk melakukan pencarian jalur terpendek, diantaranya Djikstraa, Floyd- Warshall, dan algoritma Bellman-Ford.b. Metode heuristikAdalah sub bidang dari kecerdasan buatan yang digunakan untuk melakukan pencarian dan penentuan jalur terpendek. Ada beberapa algoritma pada metode heuristik yang biasa digunakan dalam pencarian jalur terpendek. Salah satunya adalah algoritma semut.

Gambar 1. Algoritma Koloni Semut2. Prinsip Kerja Algoritma Semuta. Cara kerja semut mencari jalur optimalSemut mampu mengindera lingkungannya yang kompleks untuk mencari makanan dan kemudian kembali ke sarangnya dengan meninggalkan zat feromon pada jalur-jalur yang mereka lalui. Feromon adalah zat kimia yang berasal dari kelenjar endokrin dan digunakan oleh makhluk hidup untuk mengenali sesama jenis, individu lain, kelompok, dan untuk membantu proses reproduksi.Berbeda dengan hormon, feromon menyebar ke luar tubuh dan hanya dapat mempengaruhi dan dikenali oleh individu lain yang sejenis (satu spesies).Proses peninggalan feromon ini dikenal sebagai stigmergy, sebuah proses memodifikasi lingkungan yang tidak hanya bertujuan untuk mengingat jalan pulang ke sarang, tetapi juga memungkinkan para semut berkomunikasi dengan koloninya.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. Agar semut mendapatkan jalur optimal, diperlukan beberapa proses:1. Pada awalnya, semut berkeliling secara acak, hingga menemukan makanan. Lihat Gambar 2.2. Ketika menemukan makanan mereka kembali ke koloninya sambil memberikan tanda dengan jejak feromon. 3. Jika semut-semut lain menemukan jalur tersebut, mereka tidak akan bepergian dengan acak lagi, melainkan akan mengikuti jejak tersebut. 4. Kembali dan menguatkannya jika pada akhirnya mereka pun menemukan makanan. 5. Seekor semut yang secara tidak sengaja menemukan jalur optimal akan menempuh jalur ini lebih cepat dari rekan-rekannya, melakukan round-trip lebih sering, dan dengan sendirinya meninggalkan feromon lebih banyak dari jalur-jalur yang lebih lambat ditempuh. 6. Feromon yang berkonsentrasi tinggi pada akhirnya akan menarik semutsemut lain untuk berpindah jalur, menuju jalur paling optimal, sedangkan jalur lainnya akan ditinggalkan. 7. Pada akhirnya semua semut yang tadinya menempuh jalur yang berbedabeda akan beralih ke sebuah jalur tunggal yang ternyata paling optimal dari sarang menuju ke tempat makanan. Lihat Gambar 3

Gambar 2. Lintasan Awal Semut Menuju Tempat MakananKeterangan Gambar 2:A : Tempat awal koloni (sarang)B : Tujuan koloni semut (makanan)Jalur 1 (biru): Lintasan yang ditempuh oleh semut 1 Jalur 2 (hitam): Lintasan yang ditempuh oleh semut 2

Gambar 3.Lintasan Optimal Semut Menuju tempat MakananKeterangan Gambar 3:A : Tempat awal koloni (sarang)B : Tujuan koloni semut (makanan)Jalur Optimal : Jalur yang dilewati semut setelah beberapa iterasiSeluruh proses ini menunjukkan berlangsungnya optimisasi alami kaum semut yang bisa kita tiru dalam kehidupan sehari-hari.

b. Algoritma Semut dalam Kecerdasan BuatanDalam algoritma semut, diperlukan beberapa variabel dan langkah-langkah untuk menentukan jalur terpendek, yaitu:Langkah 1:a. Inisialisasi harga parameter-parameter algoritma. Parameter-parameter yang di inisialisasikan adalah: 1. Intensitas jejak semut antar kota dan perubahannya (ij)2. Banyak kota (n) termasuk x dan y (koordinat) atau dij (jarak antar kota) 3. Penentuan kota berangkat dan kota tujuan 4. Tetapan siklus-semut (Q) 5. Tetapan pengendali intensitas jejak semut ()6. Tetapan pengendali visibilitas ()7. Visibilitas antar kota = 1/dij (ij)8. Jumlah semut (m)9. Tetapan penguapan jejak semut ()10. Jumlah siklus maksimum (NCmax) bersifat tetap selama algoritma dijalankan, sedangkan ij akan selalu diperbaharui harganya pada setiap siklus algoritma mulai dari siklus pertama (NC=1) sampai tercapai jumlah siklus maksimum (NC=NCmax) atau sampai terjadi konvergensi. b. Inisialisasi kota pertama setiap semut.Setelah inisialisasi ij dilakukan, kemudian m semut ditempatkan pada kota pertama yang telah ditentukan.

Langkah 2:Pengisian kota pertama ke dalam tabu list. Hasil inisialisasi kota pertama semut pada langkah 1 harus diisikan sebagai elemen pertama tabu list. Hasil dari langkah ini adalah terisinya elemen pertama tabu list setiap semut dengan indeks kota pertama.

Langkah 3: Penyusunan jalur kunjungan setiap semut ke setiap kota. Koloni semut yang sudah terdistribusi ke kota pertama akan mulai melakukan perjalanan dari kota pertama sebagai kota asal dan salah satu kotakota lainnya sebagai kota tujuan. Kemudian dari kota kedua, masing-masing koloni semut akan melanjutkan perjalanan dengan memilih salah satu dari kota-kota yang tidak terdapat pada tabuk sebagai kota tujuan selanjutnya. Perjalanan koloni semut berlangsung terus menerus hingga mencapai kota yang telah ditentukan. Jika s menyatakan indeks urutan kunjungan, kota asal dinyatakan sebagai tabuk(s) dan kota-kota lainnya dinyatakan sebagai {N-tabuk}, maka untuk menentukan kota tujuan digunakan persamaan probabilitas kota untuk dikunjungi sebagai berikut,

dengan i sebagai indeks kota asal dan j sebagai indeks kota tujuan.

Langkah 4:a. Perhitungan panjang jalur setiap semut. Perhitungan panjang jalur tertutup (length closed tour) atau Lk setiap semut dilakukan setelah satu siklus diselesaikan oleh semua semut. Perhitungan dilakukan berdasarkan tabuk masing-masing dengan persamaan berikut:

dengan dij adalah jarak antara kota i ke kota j yang dihitung berdasarkan persamaan:

b. Pencarian rute terpendek.Setelah Lk setiap semut dihitung, akan diperoleh harga minimal panjang jalur tertutup setiap siklus atau LminNC dan harga minimal panjang jalur tertutup secara keseluruhan adalah atau Lmin.c. Perhitungan perubahan harga intensitas jejak kaki semut antar kota. Koloni semut akan meninggalkan jejak-jejak kaki pada lintasan antar kota yang dilaluinya. Adanya penguapan dan perbedaan jumlah semut yang lewat, menyebabkan kemungkinan terjadinya perubahan harga intensitas jejak kaki semut antar kota. Persamaan perubahannya adalah:

dengan k ij adalah perubahan harga intensitas jejak kaki semut antar kota setiap semut yang dihitung berdasarkan persamaan

untuk (i,j) kota asal dan kota tujuan dalam tabukij = , untuk (i,j) lainnyaLangkah 5:a. Perhitungan harga intensitas jejak kaki semut antar kota untuk siklus selanjutnya.Harga intensitas jejak kaki semut antar kota pada semua lintasan antar kota ada kemungkinan berubah karena adanya penguapan dan perbedaan jumlah semut yang melewati. Untuk siklus selanjutnya, semut yang akan melewati lintasan tersebut harga intensitasnya telah berubah. Harga intensitas jejak kaki semut antar kota untuk siklus selanjutnya dihitung dengan persamaan:ij = ij + ijb. Atu