DISTANCE THEORY

DISTANCE THEORY

 

 

Algoritma Koloni Semut (ACO)

Ant Colony Optimization ACO atau Algoritma Koloni Semut adalah sebuah probabilistik komputasi teknik untuk memecahkan masalah yang dapat dikurangi untuk menemukan jalur yang baik melalui grafik.

Algoritma ini adalah anggota dari keluarga algoritma koloni semut, pada intelijen segerombolan metode, dan hal itu merupakan beberapa metaheuristic optimasi. Awalnya diusulkan oleh Marco Dorigo tahun 1992 di gelar PhD tesis [1] [2], algoritma pertama yang bertujuan untuk mencari jalan yang optimal dalam grafik; berdasarkan perilaku semut mencari jalan antara koloni dan sumber makanan . Aslivvz ide ini telah diversifikasi untuk menyelesaikan kelas yang lebih luas dari masalah numerik, dan sebagai hasilnya, beberapa masalah telah muncul, menggambar tentang berbagai aspek perilaku semut.

Ringkasan

Di dunia nyata, semut (awalnya) berjalan secara acak, dan ketika menemukan makanan kembali ke koloni mereka sambil meletakkan feromon jejak. Jika semut lain menemukan jalur tersebut, mereka tidak cenderung untuk menjaga bepergian secara acak, tapi malah mengikuti jejak, kembali dan menguatkannya jika pada akhirnya mereka menemukan makanan.

Seiring waktu, Namun, jejak feromon mulai menguap, sehingga mengurangi kekuatan yang menarik. Semakin banyak waktu yang diperlukan untuk seekor semut melakukan perjalanan menyusuri jalan setapak dan kembali lagi, semakin banyak waktu yang harus feromon menguap.
Jalan pendek, dengan perbandingan, akan berjalan lebih cepat, dan dengan demikian kerapatan feromon akan tetap tinggi seperti yang diletakkan di jalan secepat dapat menguap. Penguapan feromon juga mempunyai keuntungan untuk menghindari konvergensi solusi optimal secara lokal. Jika tidak ada penguapan sama sekali, jalur yang dipilih oleh semut pertama akan cenderung menarik secara berlebihan yang berikut. Dalam hal ini, eksplorasi ruang solusi akan dibatasi.

Jadi, ketika seekor semut menemukan yang baik (yakni, pendek) jalur dari koloni ke sumber makanan, semut lain lebih cenderung mengikuti jalan, dan umpan balik yang positif pada akhirnya menyebabkan semua semut berikut satu jalan. Ide dari algoritma koloni semut adalah untuk meniru perilaku ini dengan "simulasi semut" berjalan di sekitar grafik yang menunjukkan masalah yang harus diselesaikan.

Detail
 
Gagasan awalnya berasal dari mengamati makanan eksploitasi sumber daya di antara semut, di mana semut 'secara individual memiliki kemampuan kognitif terbatas secara kolektif mampu menemukan jalur terpendek antara sumber makanan dan sarang.

1. Semut pertama menemukan sumber makanan (F), melalui cara apapun (a), kemudian kembali ke sarang (N), meninggalkan jejak feromon (b)
2. Semut tanpa pandang bulu cara mengikuti empat kemungkinan, tapi penguatan landasan membuatnya lebih menarik sebagai rute terpendek.
3. Semut mengambil rute terpendek, panjang bagian-bagian dari cara-cara lain kehilangan jejak feromon.

Dalam serangkaian percobaan pada koloni semut dengan pilihan antara dua tidak sama panjang jalan yang mengarah ke sumber makanan, ahli biologi telah mengamati bahwa semut cenderung menggunakan rute terpendek. [3] [4] Sebuah model yang menjelaskan perilaku ini adalah sebagai berikut

1. Semut (disebut "kilat") berjalan lebih atau kurang secara acak di sekitar koloni;
2. Jika menemukan sumber makanan, itu kembali lebih atau kurang langsung ke sarang, meninggalkan dalam jalur jejak feromon;
3. Feromon ini yang menarik, di dekatnya semut akan cenderung mengikuti, lebih atau kurang langsung, trek;
4. Kembali ke koloni, semut ini akan memperkuat rute;
5. Jika dua rute yang mungkin untuk mencapai sumber makanan yang sama, yang lebih pendek akan, dalam waktu yang sama, yang ditempuh oleh lebih banyak semut daripada rute yang panjang akan
6. Rute pendek akan semakin ditingkatkan, dan karena itu menjadi lebih menarik;
7. Rute yang panjang akhirnya akan menghilang, feromon yang mudah menguap;
8. Akhirnya, semua semut telah ditentukan dan karena itu "dipilih" rute terpendek.

Semut menggunakan lingkungan sebagai media komunikasi. Mereka bertukar informasi secara tidak langsung dengan mendepositokan feromon, semua rincian status mereka "bekerja". Bertukar informasi memiliki lingkup lokal, hanya seekor semut yang terletak di mana feromon dibiarkan mempunyai pengertian dari mereka. Sistem ini disebut "Stigmergy" dan terjadi di banyak hewan sosial masyarakat (hal itu telah dipelajari dalam kasus pembangunan pilar dalam sarang rayap).

Mekanisme untuk menyelesaikan masalah terlalu kompleks untuk ditangani oleh satu semut adalah contoh yang baik dari diri-sistem terorganisir. Sistem ini didasarkan pada umpan balik positif (yang deposit menarik feromon semut lain yang akan memperkuat sendiri) dan negatif (disipasi dari rute oleh sistem mencegah penguapan dari labrakan). Secara teoritis, jika jumlah feromon tetap sama dari waktu ke waktu pada semua sisi, tidak ada rute yang akan dipilih. Namun, karena umpan balik, sedikit variasi pada pinggir akan diperkuat dan dengan demikian memungkinkan pilihan dari tepi. Algoritma akan bergerak dari keadaan yang tidak stabil di mana tidak ada ujung lebih kuat daripada yang lain, untuk negara yang stabil di mana rute terdiri dari tepi paling kuat

 

 Algoritma Djikstra

 Algoritme Dijkstra, (sesuai penemunya  Edsger Dijkstra), adalah sebuah algoritma yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph).

Algoritma ini dioublikasikan pada tahun 1959  jurnal Numerische Mathematik yang berjudul “A Note on Two Problems in Connexion with Graphs” dan dianggap sebagai algoritma greedy.
Permasalahan rute terpendek dari sebuah titik ke akhir titik lain adalah sebuah masalah klasik optimasi yang banyak digunakan untuk menguji sebuah algoritma yang diusulkan. Permasalahan rute terpendek dianggap cukup baik untuk mewakili masalah optimisasi, karena permasalahannya mudah dimengerti (hanya menjumlahkan seluruh edge yang dilalui) namun memiliki banyak pilihan solusi.

Menurut Andrew Goldberg peneliti Microsoft Research Silicon Valley, mengatakan ada banyak alasan mengapa peneliti terus mempelajari masalah pencarian jalan terpendek. “Jalan terpendek adalah masalah optimasi yang relevan untuk berbagai macam aplikasi, seperti jaringan routing, game, desain sirkuit, dan pemetaan”.

Diskripsi matematis untuk grafik dapat diwakili G = {V. E}, yang berarti sebuah grafik (G) didefenisikan oleh satu set simpul (Vertex = V) dan koleksi Edge (E).
Algoritma Dijkstra bekerja dengan membuat jalur ke satu simpul optimal pada setiap langkah. Jadi pada langkah ke n, setidaknya ada n node yang sudah kita tahu jalur terpendek. Langkah-langkah algoritma Dijkstra dapat dilakukan dengan  langkah-langkah berikut:

1. Tentukan titik mana yang akan menjadi node awal, lalu beri bobot jarak pada node pertama ke node terdekat satu per satu, Dijkstra akan melakukan pengembangan pencarian dari satu titik ke titik lain dan ke titik selanjutnya tahap demi tahap.
2. 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) 2.
3. Set semua node yang belum dilalui  dan set node awal sebagai “Node keberangkatan”
4. Dari node keberangkatan, pertimbangkan node tetangga yang belum dilalui dan hitung jaraknya dari titik keberangkatan. Jika jarak ini lebih kecil dari jarak sebelumnya (yang telah terekam sebelumnya) hapus data lama, simpan ulang data jarak dengan jarak yang baru
5. Saat kita selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah dilalui sebagai “Node dilewati”. Node yang dilewati tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.
6. Set “Node belum dilewati” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan ulangi langkah e

 

Algoritma A* 

Algoritma A* (A Star / A Bintang) Algoritma -  A* (dibaca "A bintang"/"A star") adalah algoritma  pencarian graf/pohon yang mencari jalur dari satu titik awal ke sebuah titik akhir yang telah ditentukan. Algoritma A* menggunakan pendekatan heuristik h(x)  yang memberikan peringkat ke tiap-tiap titik x dengan  cara memperkirakan rute terbaik yang dapat dilalui dari titik tersebut. Setelah itu tiap-tiap titk x tersebut dicek  satu-persatu berdasarkan urutan yang dibuat dengan  pendekatan heuristik tersebut. Maka dari itulah algoritma A* adalah contoh dari best-first search. Algoritma ini pertama kali ditemukan pada tahun 1968 oleh Peter Hart, Nils Nilsson dan Bertram Raphael. Dalam tulisan mereka, algoritma ini dinamakan algoritma A. Penggunaan algoritma ini dengan fungsi heuristik yang tepat dapat memberikan hasil yang optimal, maka algoritma inipun disebut A*. Beberapa terminologi dasar yang terdapat pada algoritma ini adalah starting point, simpul (nodes), A, open list, closed list, harga (cost), halangan (unwalkable).

• Starting point adalah sebuah terminologi posisi awal sebuah benda.
• A adalah simpul yang sedang dijalankan algortima pencarian jalan terpendek.
•  Simpul adalah petak-petak kecil sebagai representasi  dari areapathfinding. Bentuknya dapat berupa persegi, lingkaran, maupun segitiga.
• open list adalah tempat menyimpan data simpul yang mungkin diakses dari starting point maupun simpul yang sedang dijalankan.
• Closed list adalah tempat menyimpan data simpul sebelum A yang juga merupakan bagian dari jalur terpendek yang telah berhasil didapatkan.
• Harga (F) adalah nilai yang diperoleh dari penjumlahan nilai G, jumlah nilai tiap simpul dalam jalur terpendek dari starting point ke A, dan H, jumlah nilai perkiraan dari sebuah simpul ke simpul tujuan.
• Simpul tujuan yaitu simpul yang dituju.
• Rintangan adalah sebuah atribut yang menyatakan bahwa sebuah simpul tidak dapat dilalui oleh A.

Prinsip algoritma ini adalah mencari jalur terpendek dari sebuah simpul awal (starting point) menuju simpul tujuan dengan memperhatikan harga (F) terkecil.

A* memperhitungkan cost dari current state ke tujuan denga fungsi heuristic, Algoritma ini juga mempertimbangkan cost yang telah ditempuh selama ini dari initial state ke current state. Jadi jika ada jalan yang telah ditempuh sudah terlalu panjang dan ada jalan lain yang cost-nya lebih kecil tetapi memberikan posisi yang sama dilihat dari goal, jalan yang lebih pendek yang akan dipilih.

 

 

REFERENSI :

https://mti.binus.ac.id/2017/11/28/algoritma-dijkstra/ 

http://mursids.blogspot.com/2009/12/algoritma-koloni-semut-aco.html 

http://jeyegzcorner.blogspot.com/2014/07/algoritma-a-star-bintang-algoritma.html