Assalamualaikum gaes 😊 .
Kali ini agak sedikit berbeda nih bahasannya tapi tetap gak keluar dari materi sistem informasi geografis kok.. 👌
Yang pertama yang akan dibahas adalah mengenai koloni semut 🐜 . penasaran kan kira-kira apa hubungannya sehingga kumpulan dari binatang ini bisa diulas untuk dijadikan sebagai sebuah pembelajaran?
langsung aja pertama adalah kita bahas mengenai konsep dasar dari Algoritma yang bernama Ant Colony .
*Konsep Dasar Algoritma Koloni Semut
Koloni semut merupakan algorima yang bersifat heuristik untuk menyelesaikan masalah optimasi. Algoritma ini diinspirasikan oleh lingkungan kooni semut pada saat mencari makanan. Semut dapat mencari makanan. Semut dapat mencari lintasan terpendek dari suatu sumber makanan menuju sarangnya, tanpa harus melihatnya secara langsung. Karena terinspirasi dari semut asli dinamakan algoritma koloni semut. Semut-semut mempunyai penyelesaian yang unik dan sangat maju, yaitu menggunakan jejak pheromone pada suatu jalur untuk berkomunikasi dan membangun solusi, semakin banyak jejak pheromone ditinggalkan, maka jalur tersebut akan diikuti oleh semut lain.
State transition rule yang digunakan dalam ant system adalah :Pk(r,s) =8<:[ (r;s)][ (r;s)]β] uεJk(r)[ (r;u)][ (r;u)]β, jika sεJk (r)0,lainnya (2) Pk(r,s)merupakan probabilitas semut k yang berada di node r memilih node s untuk tujuan selanjutnya.
Sedangkan τ(r,s) adalah pheromone yang terdapat pada arc(r,s),Jk(r)merupakan himpunan node yang belum dikunjungi oleh semut k yang berada pada node r dan β adalah parameter yang menentukan besarnya pengaruh jarak terhadap jum-lahpheromone.
Untuk visibility measure,η(r,s),dapat dihitung dengan Persamaan (3) [6]:η(r,s) =1δ(r,s) (3) denganδ (r,s) merupakan biaya pada(r,s).Dalam ant system, apabila semua semut telah menyelesaikan rute yang dibentuk maka terjadi perubahan jumlah pheromone, disebut global pheromone updating rule dengan Persamaan :τ(r,s)(1,α).τ(r,s) +α.Σ∞k=1∆τk(r,s) dengan ∆τ(r,s) =1Lk, jika(r,s)ε rute yang dilalui semut, dan∆τ(r,s) = 0, jika rute tidak dilalui semut.Pada persamaan (4), parameterαdisebutglobal pheromone decay, Lk merupakan panjangdari tour yang dilakukan oleh semutk dan m adalah jumlah semut. Perubahan pheromone diatas bertujuan untuk memberikan jumlah pheromone yang lebih besar pada tour yang lebih pendek.
Untuk visibility measure,η(r,s),dapat dihitung dengan Persamaan (3) [6]:η(r,s) =1δ(r,s) (3) denganδ (r,s) merupakan biaya pada(r,s).Dalam ant system, apabila semua semut telah menyelesaikan rute yang dibentuk maka terjadi perubahan jumlah pheromone, disebut global pheromone updating rule dengan Persamaan :τ(r,s)(1,α).τ(r,s) +α.Σ∞k=1∆τk(r,s) dengan ∆τ(r,s) =1Lk, jika(r,s)ε rute yang dilalui semut, dan∆τ(r,s) = 0, jika rute tidak dilalui semut.Pada persamaan (4), parameterαdisebutglobal pheromone decay, Lk merupakan panjangdari tour yang dilakukan oleh semutk dan m adalah jumlah semut. Perubahan pheromone diatas bertujuan untuk memberikan jumlah pheromone yang lebih besar pada tour yang lebih pendek.
*Algoritma Dijkstra
Algoritma Dijkstra dinamai sesuai dengan nama penemunya yaitu Edsger Dijkstra. Algoritma Dijkstra menggunakan prinsip greedy, dimana pada setiap langkah dipilih sisi dengan bobot minimum yang menghubungkan sebuah simpul yang sudah terpilih dengan simpul lain yang belum terpilih [8]. Input algoritma ini adalah sebuah graf berarah dan berbobot, G dan sebuah source vertex s dalam G. V adalah himpunan semua simpul dalam graph G. Setiap sisi dari graph ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua edge disebut E. Weights dari edges dihitung dengan fungsi w: E → [0, ∞]; jadi w(u,v) adalah jarak non-negatif dari vertex u ke vertex v. Cost dari sebuah edge dapat dianggap sebagai jarak antara dua vertex, yaitu jumlah jarak semua edge dalam path tersebut. Untuk sepasang vertex s dan t dalam V, algoritma ini menghitung jarak terpendek dari s ke t.
Wassalamualaikum 🙋 .
Tidak ada komentar:
Posting Komentar