Dutormasi.com –Pada kesempatan kali ini kita akan membahas mengenai perbedaan antara metode pencarian greedy search, metode pencarian A* dan juga metode pencarian simulated Annealing. Disini kita akan membahas tentang definisi dan pengertiannya, algoritma dan prinsip kerja metode, contoh kasus serta sumber dan perbedaan dan persamaan dari metode yang diatas.
Maka sebab itu postingan ini mungkin akan sedikit panjang, karena disini saya akan membahasnya sekaligus. Oleh sebab itu anda harus membacanya secara teliti agar bisa memahami dan menangkap materinya dengan mudah.
Metode Pencarian Greedy Search
1. Definisi dan Pengertian Metode Greedy Search
Metode pencarian greedy search adalah salah satu metode yang digunakan untuk memecahkan suatu masalah optimasi yang seperti persoalan yang menuntut pencarian optimum atau optimal, algoritma serta membentuk solusi langkah perlangkahnya.
Nilai maksimum nya tersebut sementara ini dikenal dengan istilah local maximum dan kebanyakan kasus algoritma greedy ini tidak akan menghasilkan silusi yang mendekati nilai optimum dalam bentuk cukup cepat.
2. Prinsip Utama Algoritma greedy
Prinsip utama dari algoritma greedy ialah “take what you can get now!” yang maksudnya adalah setiap langkah pada algoritma greedy akan diambil keputusan yang paling optimal untuk langkah tersebut tanpat dulu memerhatikan konsekuensi pada tahap selanjutnya.
Contohnya seperti ini jika menggunakan algoritma greedy untuk menempatkan komponen papan sirkuit, maka saat komponen diubah tataletak nya dan dan dipasang lagi makan komponen tersebut tidak bisa lagi dipindahkan. Maka dinamakanlah solusinya tersebut dengan optimum lokal.
Selain itu contoh masalah sehari hari yang menggunakan konsep greeady adalah :
- Bermain kartu remi
- Memilih prodi atau jurusan di perkuliahan
- Mencari jalur dekat dari panam ke rumbai (lokasi pekanbaru)
- Memilih jenis investasi atau penanaman modal
Skema Umum dalam algoritma greedy :
- Himpunan kandidat, himpunan ini berisi elemen elemen pembentuk solusi.
- Himpunan solusi, himpunan ini dipilih untuk sebagai solusi dari persoalan.
- Fungsi seleksi, fungsi ini digunakan untuk memilih kandidat yang mungkin mencapai pada solusi optimal.
- Fungsi kelayakan, Fungsi ini digunakan untuk memerika apakah suatu kandidat bisa memberikan solusi yang layak atau tidak.
- Fungsi solusi, fungsi ini untuk membalikkai nilai boolean atau true false.
- Fungsi Objektif, fungsi ini untuk mengoptimalkan solusi.
3. Contoh Kasus Metiode Greedy
Contohnya kita memilki peta sebagai berikut :
Maka gambar peta diatas bisa kita lihat bahwa titik titik jalur perjalanan yang telah didapatkan dari representasikan dengan menggunakan graph atau biasa disebut dengan graph berarah. Untuk itu kita langsung buat saja graph yang telah didapati dari peta diatas :
Untuk mendapatkan jarak optimal atau tecepat dari A ke B. algoritma greddy akan menjalankan langkah berikut ini :
- Mengkunjungi 1 titik graph dan akan mengambil seluruh titik dari yang dikunjungi sampai titik sekarang
- Mencari local maximum ke titik selanjutnya
- Menandai graph sekarang sebagai graph yang telah di kunjungi, lalu pindah ke local maximum yang sudah ditentukan.
- Kembali ke langkah satu sampai titik didapatkan.
Jika mengaplikasikan ke langkah langkah graph A ke B sebelumnya maka akan mendapatkan pergerakan seperti ini :
1. Start dari titik awal yaitu A, dan ambil seluruh titik yang dapat dikunjungi.
2. local maximum nya adalah titik C karena jarak nya yang paling dekat.
3. Tandailah A sebagai titik yang sudah dikunjungi dan pindah ke titik C.
4. Kemudian ambil seluruh yang bisa dilalui dari titik C.
5. Local maximum yang didapatkan adalah titik D karena jaraknya adalah 6
6. Kemudian tandai titik C sebagai titik yang sudah dikunjungi dan pindah ke titik D.
7. Karena dititik D cuman hanya 1 jalur perjalanan saja maka tinggal mengikuti saja.
Dengan menggunakan algoritma greedy dari graph yang diatas, maka didapatkan lah hasil akhir dari graph nya. Maka Jalur terpendek yang didapatkan adalah A-C-D-E-F-B. Namun sebenernya jalur terpendeknya adalah A-G-E-F-B yang mana algoritma greedy tidak selamanya memberikan solusi yang optimal karena local maximum setiap langkahnya tanpa memerhatikan solusi dari keseluruhan. Inilah contoh gambar yang memperlihatkan algoritma greedy yang kurang memberikan solusi optimal.
Teteapi perlu anda ketahui bahwa dikasus umum, kebanyakan algoritma greedy ini memberikan cukup baik dengan kompelsitas waktu yang cepat. Sehingga algoritma greedy sering digunakan untuk menyelesaikan permasalahan yang komplekes dengan memerlukan kecepatan jawaban.
Sumber yang didapatkan :
- https://bertzzie.com/knowledge/analisis-algoritma/Greedy.html
- https://www.it-jurnal.com/pengertian-algoritma-greedy/
- https://tugasanalgo4blog.wordpress.com/2016/12/04/algoritma-greedy/
Metode Pencarian A*
1. Definisi dan Pengertian Metode Pencarian A*
Metode pencarian A* ini atau biasa dibaca dengan A bintang atau A star merupakan algoritma pencarian graph atau pohon yang mana mencari jalur dari satu titik awal ke titik ahir yang telah ditentukan. Algoritma A* ini menggabungkan nilai g(n) dan nilai h(n) untuk mencari beberapa jenis jalan yang akan dilalui kendaraan.
Dengan cara tersebut maka akan bisa memperkirakan rute terbaik untuk dilalui dan tiap tiap titik tersebut akan dicek satu persatu berdasarkan urutan pemdekatan heurstik dan itulah algortma A* dari best first search.
2. Algoritma dan Prinsip Kerja Metode Pencarian A*
Prinsip algoritma metode A* ini adalah algoritma komputer secara luas untuk mencari jalur dan grafik melintang, proses plotting sebuah jalur melintang secara efisien ke titik titik disebut dengan node. Selain itu prinsi algoritma A* ini juga bisa disebut mencari jalur terpendek dari sebuah titik awal dan menuju ke titik tujan dengan memperhatikan harga terkecil.
Oleh sebab itu lah metode ini mempertimbangkan cost yang akan ditempuh selama ini dan intital state ke current state. Notasi yang dipakai pada algoritma A* adalah sebagai berikut :
Keterangannya adalah :
1. f(n) adlaah biaya estimasi terendah
2. g(n) adalah biaya dari node awal ke node n
3. h(n) adalah perkiraan biaya dari node n ke node akhir.
Algoritma A* memiliki 2 senarai yaitu Open dan closed. Untuk Open adalah list yang akan dugunakan untuk menyimpan simpul simpul yang akan dibangkitkan dan nilai heuristiknya telah dihitung tetapi belum dipilih sebagai simpul yang terbaik. Closed adalah list untuk menyimpan simpul simpul yang pernah terpilih sebagai simpul yang terbaik sehingga peliamh terpilih telah ditutup.
3. Contoh kasus Metode A*
Diberi suatu kasus seperti gambar dibawah ini yaitu jika ada seseorang pengendara akan pergi berkeliling dari pontianak menuju ke melawi hingga kembali lagi ke pontianak. Manakah rute yang optimal/tercepat untuk dilalui seorang pengendara.
A = Pontianak ( 2,14)
B = Singkawang (14,19)
C = Sintang (38,15)
D = Sanggau (32,4)
E = Melawi (13,5)
PEMBAHASAN :
Hal yang pertama dilakukan adalah menentukan nilai dari h'(n) dengan memakai rumus dua titik :
Maka didapatlah perhitungannya sebagai berikut :
A ke B = (2,14), (14,19) = 13
A ke C = (2,14), (38,15) = 36,01
A ke D = (2,14), (32,4) = 31,62
A ke E = (2,14) , (13,5) = 14,21
B ke A = (14,19), (2,14) = 13
B ke C =(14,19), (38,15) = 24,33
B ke D = (14,19), (32,4) = 23,43
B ke E = (14,19), (13,5) = 14,04
C ke A = (38,15), (1,14) = 36,01
C ke B = (38,15), (14,19) = 24,33
C ke D = (38,15), (32,4) = 12,43
C ke E = (38,15), (13,5) = 26,93
D ke A = (32,4), (1,14) = 31,62
D ke B = (32,4), (14,19) = 23,43
D ke C = (32,4), (38,15) = 12,53
D ke E = (32,4), (13,5) = 19,03
E ke A = (13,5), (1,14) = 14,21
E ke B = (13,5), (14,19) = 14,04
E ke C = (13,5), (38,15) = 26,93
E ke D = (13,5), (32,4) = 19,03
Kemudian mencari nilai f(n). g(n) didapat dari mengukur suatu jarak antara point 1 je point lainnya kemudian selanjutnya bisa mencari nilai f(n) dengan rumus f(n) = h'(n) + g(n).
Didapatlah perhitungan sebagai berikut :
A ke B = 13 + 18 = 31
A ke C = 36,01 + 37 = 73,01
A ke D = 31,62 + 40 = 71,62
A ke E = 14,21 + 20 = 34,21
B ke A = 13 + 18 = 31
B ke C = 24,33 + 29 = 53,33
B ke D = 23,43 + 34 = 57,43
B ke E = 14,04 + 16 = 30,04
C ke A = 36,01 + 37 = 73,01
C ke B = 24,33 + 29 = 53,33
C ke D = 12,43 + 17 = 29,43
C ke E = 26,93 + 35 = 61,93
D ke A = 31,62 + 40 = 71,62
D ke B = 23,43 + 34 = 57,43
D ke C = 2,53 + 17 = 29,43
D ke E = 19,03 + 20 = 39,03
E ke A = 14,21 + 20 = 34,21
E ke B = 14,04 + 16 = 30,04
E ke C = 26,93 + 35 = 61,93
E ke D = 19,03 + 20 = 39,03
Setelah mendapatkan nilai f(n) kita bisa menggambarkan rute perjalanan dengan pemilihan rute nilai terkecil.
Darier gambar diatas bisa disimpulkan bahwa rute yang optimat// tercepat dari metode ini adalah A-B-E-D-C-A.
Sumber yang didapatkan adalah :
- https://www.researchgate.net/publication/323599865_PENERAPAN_METODE_A_PADA_APLIKASI_PENCARIAN_JALUR_TERPENDEK_PENGIRIMAN_BARANG_APPLICATION_OF_A_METHOD_IN_SEARCHING_APPLICATIONS_THE_SHORTEST_PATH_OF_SHIPPING_GOODS
- https://www.academia.edu/13206772/IMPLEMENTASI_DAN_ANALISIS_PENGGUNAAN_ALGORITMA_A_STAR_DENGAN_PRIORITAS_PADA_PEMILIHAN_RUTE_LINTAS_KENDARAAN
- https://media.neliti.com/media/publications/235453-penerapan-algoritma-a-star-menggunakan-g- fa0b1902.pdf
- https://clocariusedu.blogspot.com/2017/11/penjelasan-algoritma-A-star-beserta-contoh.html
Metode Simlulated Annealing
1. Definisi dan Pengertian Metode Simulalted Annealing
Metode ini dikembangkan dari sebuah analogi yang diproses pada pendinginan cairan logam sehingga membentuk kristal yang bernama annealing. Annealing ini merupakan teknik yang bernama metalurgi yang menggunakan ilmu penjadwalan pendinginan untuk bisa menghasilkan efisiensi penggunaan energi yang optimal sehinnga bisa menghasilkan logam.
Sehingga bisa disebut metode simulated annealing ini merupakan sebuah metode pencarian yang memanfaatkan teori probabilitas dalam mencari global minimum untuk suatu permasalahan dari optimasi. Metode ini biasanya digunakan untuk variabel yang bersifat categorical. Target nya adalah menemukan solusi yang bagus sehingga bisa diterima untuk mencari solusi yang terbaik
2. Algoritma dan Prinsip Kerja Metode Simulated Annealing
Algoritma dari simlulated annealing ini mampu digunakan untuk menyelesaikan TSP atau travelling Salesman Problem. Travelling Salesman Problem (TSP) adalah masalah seorang salesman yang ingin mengunjungi tempat dan akan kembali lagi ketempat asalanya tersebut tepat pada satu kaoi sehingga diprolehlah jarak yang terpendek.
Contohnya adalah pengiriman barang, pengiriman surat, dan masalah transportasi biaya perjalanan dalam bidang transportasi darat juga merupakan dari konsep TSP dengan biaya yang dikeluarkan dan perjalanan yang sedekat/ tercepat mungkin.
3. Contoh Kasus Metode Simulated Annealing
Ada seorang salesman PT.XX yang betugas untuk mengecek ketersediaan suku cadang. Kemudian salesman tersebut akan berpedian dimulai dari pos awal yaitu XX A.Yani(0) ke pos Sei. Raya(1), pos Adisucipto(2), pos Siantan (3), pos Gajah Mada (4) dan pos Kota Baru (5). Lalu salesman ini haru kembali lagi kepos awanya yaitu XX A. Yani. Pos pos manakah yang harus dikunjungi satu kali dan rute yang diambil tidak boleh dilalui lebih dari satu kali karena untuk meminimumkan biaya dan jarak jauh tempuh
PEMBAHASANNYA :
Tabel 3 di bawah ini akan memnunjukan biaya yang diberikan dalam ribu rupiah, maka jarak yang ditempuh dengan satuan kilometer dan waktu dalam menit secara kerseluruhan perjalanan seorang salesman PT.XX seperti gamabar 1 diatas.
Langkah langkah yang bisa dilakukan untuk mengoptimalkan biaya jarak dan waktu perjalan salesman tersebut adalah :
- Menentukan rute awal secara random, rute awal dengan solusi rute 0-1-2-3-4-5-0 dengan 0 sebagai titik awal dari perjalanan salesman PT XX. Maka biaya transportasi yang diberikan adalah (c) = 10+12+18+14+12+12 =78.
Jarak yang ditempuh (d) = 3+6+12+7+5+5 =38
Waktu perjalanan (t) = 12+25+45+30+20+18=150
- Kemudian tentukan T awal yaitu Ti = a x zc dengan i = 1, a =0,95 dan zc adalah biaya, jarak dan waktu tempuh rute awal yang dilalui salesman PT.XX secara random.
Biaya Transportasi (c) = T1 = 0,95 x 78 = 74,10
Jarak yang ditempuh (d) = T1 = 0,95 x 150 = 36,10
Waktu Perjalanan (t) = T1 = 0,95 x 150 =142,50
- Kemudian lakukan iterasi maksimun dengan jumlah iterasi adalah
Iterasi 1
Langkah yang dilakukan yaitu membangkitkan suatu bilangan acak untuk menentukan ke kota 1, 2, 3 ,4 pada range [0,1]
00 – 0,24 = rute perjalanan awal menuju kota 1
0,25 – 0,49 = rute perjalanan awal menuju kota 2
0,50 – 0,74 = rute perjalanan awal menuju kota 3
0,75 – 0,99 = rute perjalanan awal menuju kota 4
Maka bilangan random yang akan dibangkitkan adalah r = 0,00125 yang terletak pada kota 1. Selanjutnya kita bisa membangkitkan lagi suatu bilangan random untuk menentukan kota 2, 4 dan kota 5 pada range [0,1] :
00 – 0,32 = rute perjalanan awal menuju kota 2
0,33 – 0,65 = rute perjalanan awal menuju kota 4
0,66 – 0,98 = rute perjalanan awal menuju kota 5
Bilangan random ini akan dibangkitkan adalah r = 0,00125 yang terletak pada kota 2. Maka selanjutnya bisa kita menukarkan antara kota 1 dan kota 2 sehingga diproleh rute : 0 – 2 – 1 – 3 – 4 – 5- 0
Biaya Transportasi (c) = 013 + 12 +16 + 14 + 12 + 12 = 79
Jarak yang ditempuh (d) = 7 + 6 + 10 + 7 + 5 + 5 = 40
Waktu Perjalanan (t) = 24 + 25 + 38 + 30 + 20 + 18 = 155
Karena Zn > Zc maka ditetapkan rute beru sebagai rute dengan probabilitas persamaan yaitu :
Biaya transportasi yang diberikan ( c) :
Jarak yang ditempuh (d) :
Krena r < p oleh sebab itu rute baru dapat ditetapkan sebagai rute sekarang. Insialisasi TI+1 = a x Yi sesuai dengan annealing schedule dengan T2 = 0,95 X T1.
Biaya Transportasi (c) = T2 = 0,95 x 74,10 = 70,40
Jarak yang ditempuh (d) = T2 = 0,95 x 36,10 = 34,30
Waktu Perjalanan (t) = T2 = 0,95 x 142,50 =135, 38
Untuk perhitungan iterasi 2 sampai iterasi 60 menggunakan perhitungan saya sama seperti dengan iterasi 1 dengan rute seperti salaseman tersebut.
Dengan perhitungan tabel 4 diatas maka dapat dilihat bahwa hasil iterasi SA menunjukanan minimum biaya perjalanan pada rute yaitu rute 0 – 3 – 4 – 5 – 2 – 1 – 0 dengan biaya perjalanan Rp. 77.000 jarak tempuh 39km dan waktu perjalanan 157 menit atau 2 jam 37 menit.
Sumber yang didapatkan adalah :
- https://docplayer.info/37078527-Aplikasi-simulated-annealing-untuk-menyelesaikan-travelling-salesman-problem.html
- https://yudiagusta.wordpress.com/2009/11/10/simulated-annealing/
- https://core.ac.uk/download/pdf/304760293.pdf
Perbedaan metode Greedy, A* dan Simulated Annealing
Metode greedy ini seperti halnya dengan algoritma best first search yang mempunyai sebuh fungsi untuk menjadi acuan kelayakan dari sebuah sumpul yaitu fungsi evaluasi f(n). Kemudian juga tergantung pada cost yang sebenarnya dari sebuah simpul yaitu g(n) dan fungsi evaluasi hanya tergantung pada fungsi heuristic h(n) yang mengestimasikan ke arah benar. Matematis dungsi evaluasi dari greedy search diberikan oleh :
f(n) = h(n)
Kemudian algoritma A star adalah algoritma yang dapat menggabungkan dijkstra dan algoritma dari greedy best first search . Yaitu menghitung biaya yang diperlukan dalam perjlanan dan simpul ke simpul lainnya. Secara matematis nilai fungsi evaluasi heuristic adalah sebuah simpul algoritma * yang diberikan oleh :
Dengan keterangan sebagai berikut :
g(n) adalah biaya dari simpul awal ke simpul n
h(n) adalah estimasi biaya dari simpul n ke simpul tujuan
Sementara untuk metode simulated annealing berbeda dengan kedua metode yang diatas yang mana SA ini adalah algoritma optimasi yang mensimulasikan proses annelaing dai materi yang terdiri dari butir kristal atau logam.
Sumber yang didapatkan adalah :
- https://bellavira.blogspot.com/2017/10/pencarian-berbentuk-heuristic-search.html
Nah begitulah penjelasan mengenai metode greedly, A* dan simulated Annealing. Semoga anda bisa memahaminya dengan jelas yaaa. Jika ada pertanyaan yang bagi anda membingungkan anda bisa bertanya kepada saya pada menu contact di footer bawah ini.
Semoga bermanfaat postingan ini. Sekian dan terima kasih. Salam Dutormasi !.