HILL CLIMBING

Mendaki bukit ( Hill Climbing )

Dalam ilmu komputer , mendaki bukit adalah optimasi matematika teknik yang dimiliki oleh keluarga pencarian lokal . Meskipun algoritma yang lebih maju bisa memberikan hasil yang lebih baik, dalam beberapa situasi mendaki bukit bekerja sama dengan baik.
Mendaki bukit dapat digunakan untuk memecahkan masalah-masalah yang banyak solusi, beberapa yang lebih baik daripada yang lain. Dimulai dengan solusi (berpotensi miskin) secara acak, dan iteratif membuat perubahan kecil untuk solusi, setiap kali memperbaikinya sedikit. Ketika algoritma tidak bisa melihat perbaikan apapun lagi, itu berakhir. Idealnya, pada titik bahwa solusi saat ini dekat dengan optimal, tetapi tidak menjamin bahwa mendaki bukit itu akan datang dekat dengan solusi optimal.
Misalnya, bukit pendakian dapat diterapkan pada masalah perjalanan salesman . Sangat mudah untuk mencari solusi yang dilihat semua kota tetapi akan sangat miskin dibandingkan dengan solusi optimal. Algoritma ini dimulai dengan solusi tersebut dan membuat perbaikan kecil untuk itu, yaitu switching urutan dua kota yang dikunjungi. Akhirnya, rute yang jauh lebih baik diperoleh.
Mendaki bukit digunakan secara luas dalam kecerdasan buatan , untuk mencapai goal state dari node awal. Pilihan node node berikutnya dan mulai dapat divariasikan untuk memberikan daftar algoritma yang terkait.


Deskripsi Matematika

Mendaki bukit upaya untuk memaksimalkan (atau mengurangi) suatu fungsi f (x), di mana x adalah negara diskrit. Negara-negara ini biasanya diwakili oleh titik dalam grafik , di mana tepi di encode kedekatan kesamaan grafik atau grafikMendaki bukit akan mengikuti grafik dari titik ke titik, selalu meningkat secara lokal (atau penurunan) nilai dari f, sampai maksimum lokal (atau minimum lokal ) x m tercapai. Mendaki bukit juga dapat beroperasi pada ruang terus menerus: dalam hal ini, algoritma ini disebut pendakian gradien (atau keturunan gradien apakah fungsi ini diminimalkan) .*.












Varian

Dalam mendaki bukit sederhana, dekat simpul pertama dipilih, sedangkan di bukit mendaki pendakian terjal dibandingkan semua penerus dan yang paling dekat dengan Kedua bentuk gagal jika tidak ada node lebih dekat, yang mungkin terjadi jika ada maxima lokal dalam ruang pencarian yang tidak solusi. Mendaki pendakian terjal bukit mirip dengan -pertama pencarian yang terbaik , yang mencoba semua ekstensi kemungkinan jalan saat ini bukan hanya satu.
mendaki bukit stokastik tidak memeriksa semua tetangga sebelum memutuskan bagaimana bergerak. Sebaliknya, ia memilih tetangga secara acak, dan memutuskan (berdasarkan jumlah perbaikan di tetangganya itu) apakah untuk pindah ke tetangga yang lain atau untuk memeriksa.

Random-restart mendaki bukit merupakan meta-algoritma dibangun di atas bukit pendakian algoritma. Ia juga dikenal sebagai memanjat bukit shotgun. Ini iteratif tidak bukit-pendakian, setiap kali dengan kondisi awal random x 0. M x terbaik adalah tetap: jika menjalankan baru mendaki bukit menghasilkan m X lebih baik dari keadaan yang tersimpan, menggantikan negara disimpan.

Random-restart hill climbing adalah algoritma sangat efektif dalam banyak kasus. Ternyata sering lebih baik untuk menghabiskan waktu mengeksplorasi ruang CPU, dibandingkan dengan hati-hati mengoptimalkan dari kondisi awal

Masalah

maxima Lokal

Masalah dengan bukit pendakian adalah bahwa ia hanya akan menemukan maxima lokal Kecuali jika heuristik adalah cembung, tidak mungkin mencapai maksimum global. Lain algoritma pencarian lokal mencoba untuk mengatasi masalah ini seperti mendaki bukit stokastik , random walk dan simulated annealing .













ridges

ridge adalah kurva di tempat pencarian yang mengarah ke maksimum, tetapi orientasi punggungan dibandingkan dengan langkah yang tersedia yang digunakan untuk memanjat adalah seperti yang bergerak setiap akan mengarah ke titik yang lebih kecil. Dengan kata lain, setiap titik di punggung bukit terlihat dengan algoritma seperti maksimum lokal, meskipun intinya adalah bagian dari kurva mengarah ke lebih optimal.

Dataran Tinggi

Masalah lain dengan mendaki bukit adalah bahwa dari dataran tinggi, yang terjadi ketika kita sampai di bagian "datar" dari ruang pencarian, yaitu kami memiliki jalan di mana heuristik semua sangat berdekatan. Jenis kerataan dapat menyebabkan algoritma untuk menghentikan kemajuan dan berkeliaran tanpa tujuan.

Pseudocode

Algoritma Hill Climbing

currentNode = startNode;
loop lakukan
L = Tetangga (currentNode);
nextEval =-INF;
nextNode = NULL;
untuk semua x dalam L
if (Tarahan (x) nextEval>)
nextNode = x;
nextEval = Tarahan (x);
jika nextEval <= Tarahan (currentNode)
/ / Node Kembali saat ini tidak ada tetangga lebih baik karena ada
kembali currentNode;
currentNode = nextNode;