Assalamualaikum WR. WB.
Halooo ketemu lagi nih semoga gak bosan dengan saya kali ini mari kita membahas tentang Implementasi pada gis, Dalam implementasi gis saat ini sudah banyak menggunakan algoritma Ant Colony, Djikstra dll apa itu..?? yukk langsung saja
- ACO atau Algoritma semut merupakan algoritma yang digunakan untuk menyelesaikan masalah-masalah optimasi yang terinspirasi dari perilaku semut. Sebut aja Artificial Ant (semut tiruan).
Saat ini sedang banyak dilakukan penelitian terhadap perilaku alam yang mungkin bisa diterapkan untuk mencari solusi pada permasalahan2 optimasi. Kita sudah sering mendengar JST dan Algoritma Genetika yang meniru system kerja tubuh manusia. Perilaku hewan juga ditiru, burung, lebah, angsa… dan algoritma semut hanya salah satunya.
Perilaku Semut Yang Mana?
Pada saat semut menemukan sumber makanan, maka semut perlu menentukan jalur yang terpendek antara sumber makanan dan sarang semut. Disinilah peran teman2 atau ‘koloni’ semut. Pekerjaan menelusuri jalur didistribusikan kepada beberapa agen semut. Pada awalnya semut2 tersebut akan melalui semua jalur yang memungkinkan secara acak. Kemudian jalur yang terpendek pada saat itu dibubuhi jejak, yang disebut dengan pheromone. Pada dunia nyata, pheromone merupakan alat komunikasi berupa hormon yang dikeluarkan oleh semut sebagai penunjuk jalan bagi semut yang lain.
Saat ini sedang banyak dilakukan penelitian terhadap perilaku alam yang mungkin bisa diterapkan untuk mencari solusi pada permasalahan2 optimasi. Kita sudah sering mendengar JST dan Algoritma Genetika yang meniru system kerja tubuh manusia. Perilaku hewan juga ditiru, burung, lebah, angsa… dan algoritma semut hanya salah satunya.
Perilaku Semut Yang Mana?
Pada saat semut menemukan sumber makanan, maka semut perlu menentukan jalur yang terpendek antara sumber makanan dan sarang semut. Disinilah peran teman2 atau ‘koloni’ semut. Pekerjaan menelusuri jalur didistribusikan kepada beberapa agen semut. Pada awalnya semut2 tersebut akan melalui semua jalur yang memungkinkan secara acak. Kemudian jalur yang terpendek pada saat itu dibubuhi jejak, yang disebut dengan pheromone. Pada dunia nyata, pheromone merupakan alat komunikasi berupa hormon yang dikeluarkan oleh semut sebagai penunjuk jalan bagi semut yang lain.
Dengan adanya informasi pheromone, maka semut2 selanjutnya tidak akan berjalan secara acak lagi, namun akan lebih tertarik mengikuti jalur yang ada pheromonenya. Semakin banyak semut melalui suatu jalur, semakin banyak pula jumlah pheromone yang tertinggal di jalur tersebut. Sehingga, lama kelamaan semua semut melalui satu jalur yang seragam, yaitu jalur yang terpendek. Perilaku semut yang seperti ini merupakan salah satu bentuk autocatalytic-suatu perulangan dengan feedback yang positif.
Macam-Macam Algoritma Semut?
- Versi pertama disebut dengan Ant System (AS), yang diaplikasikan pada TSP
- Elitist Ant System (EAS)
- Rank-Based ANt System (ASrank)
- Min-Max Ant System (MMAS)
- Ant Colony System (ACS)
- Approximate Nondeterministic Tree Search (ANTS)
- Hyper-Cube Framework for ACO
- Dsb
- Djikstra merupakan salah satu varian bentuk algoritma popular dalam
pemecahan persoalan terkait masalah optimasi pencarian lintasan
terpendek sebuah lintasan yang mempunyai panjang minimum dari verteks a
ke z dalam graph berbobot, bobot tersebut adalah bilangan positif jadi
tidak dapat dilalui oleh node negatif. Namun jika terjadi demikian, maka
penyelesaian yang diberikan adalah infiniti (Tak Hingga). Pada
algoritma Dijkstra, node digunakan karena algoritma Dijkstra menggunakan
graph berarah untuk penentuan rute listasan terpendek. Berikut Pseudo
Code dan Flowchart Algoritma Djikstra:
Implementasi Djikstra
Algoritma ini bertujuan untuk menemukan jalur terpendek berdasarkan
bobot terkecil dari satu titik ke titk lainnya. Misalnya titik
mengambarkan gedung dan garis menggambarkan jalan, maka algoritma
Dijkstra melakukan kalkulasi terhadap semua kemungkinan bobot terkecil
dari setiap titik.
Pertama-tama tentukan titik mana yang akan menjadikan node awal, lalu
beri bobot jarak pada node pertama ke node terdekat satu persatu,
Dijkstra akan melakukan pengembangan pencarian dari satu titik ke titik
lain dan ke titik selanjutnya tahap demi tahap inilah urutan logika dari
algoritma Dijkstra :
- Beri nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga terhadap node lain (belum terisi)
- Set semua node “Belum Terjamah” dan set node awal sebagai “Node keberangkatan”
- Dari no keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung jaraknya dari titik keberangkatan. Sebagai contoh, jika titik keberangkatan A ke B memiliki bobot jarak 6 dan dari B ke node C berjarak 2, maka jarak ke C melewati B menjadi 6+2=8. Jika jarak ini lebih kecil dari jarak sebelumnya (yang telah terekam sebelumnya) hapus data lama, simpan ulang data jarak dengan jarak yang baru.
- Saat kita selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.
- Set “Node belum terjamah” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selajutnya dan lanjutkan dengan kembali ke step 3
Okee cukup sekian kali ini sampai berjumpa di lain waktu hahahaha...
Wassalamualaikum WR. WB.
Tidak ada komentar:
Posting Komentar