Hill Climbing
Dalam analisis numerik, pendakian bukit merupakan teknik optimasi matematis yang termasuk dalam keluarga pencarian lokal. Ini adalah algoritma berulang yang dimulai dengan solusi sewenang-wenang terhadap suatu masalah dan kemudian mencoba menemukan solusi yang lebih baik dengan membuat perubahan bertahap pada solusi tersebut. Jika suatu perubahan mengarah pada solusi yang lebih baik, perubahan bertahap lainnya akan dilakukan terhadap solusi baru tersebut, dan seterusnya, hingga tidak ada perbaikan lebih lanjut yang dapat ditemukan.
Misalnya mendaki bukit bisa diterapkan pada masalah penjual. Sangat mudah untuk menemukan solusi awal yang mencakup semua kota, namun mungkin akan sangat buruk jika dibandingkan dengan solusi optimal.Algoritme dimulai dengan solusi ini dan melakukan perbaikan kecil pada solusi tersebut, seperti mengubah urutan dua kota yang dikunjungi. Anda mungkin akan menempuh jarak yang jauh lebih pendek.
Hill Climbing menemukan solusi optimal untuk masalah cembung; Untuk permasalahan lainnya, hanya ditemukan local optima (solusi yang tidak dapat diperbaiki oleh konfigurasi tetangga), yang belum tentu merupakan solusi terbaik (global optimum) dari semua kemungkinan solusi (ruang pencarian). Contoh algoritma yang menyelesaikan masalah cembung dengan mendaki bukit antara lain algoritma pemrograman linier simpleks dan algoritma pencarian biner. Untuk menghindari terjebak dengan optimasi lokal, Anda dapat menggunakan restart (yaitu pencarian lokal berulang) atau berbasis iterasi yang lebih kompleks (misalnya pencarian lokal berulang) atau skema berbasis memori (misalnya optimasi pencarian reaktif, dll gunakan pencarian tabu) atau dalam modifikasi stokastik tanpa memori (misalnya simulasi anil).Kesederhanaan relatif dari algoritma ini menjadikannya pilihan pertama yang populer di antara algoritma optimasi. Ini banyak digunakan dalam kecerdasan buatan untuk mencapai suatu keadaan tujuan dari titik awal. Dalam algoritma yang sesuai, opsi berbeda digunakan untuk node berikutnya dan node awal. Meskipun algoritme yang lebih canggih seperti Simulated Annealing atau Tabu Search mungkin memberikan hasil yang lebih baik, penskalaan juga dapat berfungsi dalam beberapa situasi.
Hill Climbing seringkali dapat memberikan hasil yang lebih baik dibandingkan algoritma lain ketika waktu yang tersedia untuk pencarian terbatas, seperti dalam sistem real-time, selama sejumlah kecil perbaikan umumnya mengarah pada solusi yang baik (solusi optimal). .atau pendekatan dekat). Di sisi lain, pengurutan gelembung dapat dilihat sebagai algoritma pendakian (setiap pertukaran elemen yang bertetangga mengurangi jumlah pasangan elemen yang tidak berurutan), namun pendekatan ini jauh dari efisien bahkan untuk N sederhana, karena jumlah pertukaran yang diperlukan meningkat tepat.
Varian
Dalam pendakian yang mudah, node pertama yang terdekat dipilih, sedangkan pada pendakian yang lebih curam, semua penerusnya dibandingkan dan node yang paling dekat dengan solusi dipilih. Kedua bentuk tersebut gagal jika tidak ada simpul terdekat. Hal ini dapat terjadi bila terdapat maksimum lokal dalam ruang pencarian yang bukan merupakan solusi. Mendaki bukit paling curam mirip dengan pencarian terbaik pertama, mencoba semua kemungkinan perluasan jalur saat ini, bukan hanya satu.
Pendakian stokastik tidak memeriksa semua tetangga sebelum memutuskan bagaimana bergerak. Sebaliknya, Anda memilih tetangga secara acak dan memutuskan (berdasarkan jumlah perbaikan yang dilakukan pada tetangga tersebut) apakah akan pindah ke tetangga tersebut atau memeriksa tetangga lainnya.Penurunan koordinat melakukan pencarian garis sepanjang arah koordinat pada titik saat ini di setiap iterasi. Beberapa versi penurunan koordinat secara acak memilih arah koordinat yang berbeda di setiap iterasi.
Masalah Dataran Tinggi
Masalah lain yang terkadang muncul saat mendaki bukit adalah dataran tinggi. Dataran tinggi terjadi ketika ruang pencarian datar, atau cukup datar sehingga nilai yang dikembalikan oleh fungsi tujuan tidak dapat dibedakan dari nilai yang dikembalikan untuk wilayah tetangga karena presisi yang digunakan oleh mesin untuk merepresentasikan nilai tersebut. Dalam kasus seperti itu, pendaki mungkin tidak dapat menentukan arah yang harus dituju dan mungkin menyimpang ke arah yang tidak pernah membawa kemajuan.
Disadur dari: en.wikipedia.org