Perbedaan Metode Greedy, A* dan Simulated Annealing Lengkap dan Terbaru

Skema Umum dalam algoritma greedy :

1. Himpunan kandidat, himpunan ini berisi elemen elemen pembentuk solusi.
2. Himpunan solusi, himpunan ini dipilih untuk sebagai solusi dari persoalan.
3. Fungsi seleksi, fungsi ini digunakan untuk memilih kandidat yang mungkin mencapai pada solusi optimal.
4. Fungsi kelayakan,  Fungsi ini digunakan untuk memerika apakah suatu kandidat bisa memberikan solusi yang layak atau tidak.
5. Fungsi solusi, fungsi ini untuk membalikkai nilai boolean atau true false.
6. Fungsi Objektif, fungsi ini untuk mengoptimalkan solusi.

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 :

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.

• 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* 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.

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 :

f(n) = g(n) + h(n)

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.

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.

 

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.

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

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.

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

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 :

1. 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
2. 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
3. Kemudian lakukan iterasi maksimun dengan jumlah iterasi adalah
   

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) :

Waktu perjalanan ( t) :

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.

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 :

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 :

f(n) = h(n) + h(n)

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.

• https://bellavira.blogspot.com/2017/10/pencarian-berbentuk-heuristic-search.html