Hill climbing (algoritma)

Dalam analisis numerik, hill climbing (lit: pendakian bukit) merupakan teknik optimasi matematis yang termasuk dalam keluarga algoritma pencarian lokal. Ia adalah algoritma iteratif yang dimulai dengan menginisiasi solusi sembarang untuk suatu masalah, kemudian mencoba menemukan solusi yang lebih baik dengan melakukan perubahan inkremental pada solusi tersebut. Jika perubahan tersebut menghasilkan solusi yang lebih baik, maka perubahan inkremental lainnya akan dilakukan pada solusi yang baru, dan begitu seterusnya hingga tidak ada lagi perbaikan yang dapat ditemukan.

Sebagai contoh, hill climbing dapat diterapkan pada masalah penjualan keliling. Sangat mudah untuk menemukan solusi awal yang dapat mengunjungi semua kota, tetapi kemungkinan solusi tersebut akan sangat buruk (tinggi biaya), jika dibandingkan dengan solusi optimal. Algoritma ini dimulai dengan solusi seperti itu dan melakukan perbaikan kecil terhadap solusi tersebut, seperti menukar urutan dua kota. Secara bertahap, rute yang jauh lebih pendek bisa ditemukan.

Hill climbing mampu menemukan solusi optimal, khususnya untuk masalah optimasi konvex, sedangkan untuk permasalahan lain, hill climbing hanya akan menemukan optimum lokal (solusi yang tidak dapat diperbaiki dengan konfigurasi tetangga manapun), yang tidak selalu merupakan solusi terbaik yang mungkin (optimum global) di antara semua solusi yang mungkin di ruang pencarian. Contoh algoritma yang dapat menyelesaikan masalah optimasi konveks (atau cembung) dengan menggunakan algoritma hill climbing, antara lain adalah algoritma simpleks untuk pemrograman linier dan pencarian biner.^[1] ^:253 Untuk menghindari terjebak dalam optimum lokal, dapat digunakan pendekatan, seperti restart, yaitu pencarian lokal berulang, atau dengan skema yang lebih kompleks berdasarkan iterasi, seperti iterasi pencarian lokal, atau berdasarkan memori, seperti reactive search optimizatiom dan pencarian tabu), atau dengan modifikasi stokastik tanpa penggunaan memori (seperti simulated annealing).

Simplisitas relatif algoritma ini menjadikannya pilihan awal yang populer di antara algoritma optimasi. Algoritma ini telah digunakan secara luas dalam kecerdasan buatan, seperti untuk mendapatkan kondisi tujuan (goal state) dari node awal yang mana terdapat beberapa pilihan yang berbeda untuk node berikutnya dan node awal yang digunakan dalam algoritma terkait. Meskipun terdapat algoritma yang lebih canggih, seperti simulated annealing atau pencarian tabu yang mungkin memberikan hasil yang lebih baik, tetapi dalam beberapa situasi, hill climbing dapat berfungsi sama baiknya. Hill climbing sering kali dapat memberikan hasil yang lebih baik, dibandingkan dengan algoritma lain ketika jumlah waktu yang tersedia terbatas untuk melakukan pencarian, seperti pada sistem real-time, selama jumlah inkrementasi yang kecil umumnya konvergen pada solusi yang baik (solusi optimal atau pendekatan yang mendekati). Di sisi lain, salah satu algoritma pengurutan, bubble sort dapat dilihat sebagai algoritma hill climbing, sebab setiap pertukaran elemen yang berdekatan akan mengurangi jumlah pasangan elemen yang tidak terurut), tetapi pendekatan ini jauh dari efisien, bahkan untuk N yang kecil sekalipun, karena jumlah pertukaran yang dibutuhkan akan bertambah secara kuadratik.

Hill climbing termasuk dalam anytime algorithm atau algoritma yang dapat digunakan kapan saja, sebab ia dapat mengembalikan solusi yang valid. Bahkan, ketika diinterupsi kapan saja sebelum eksekusi algoritma tersebut berakhir.

Deskripsi matematis

Hill climbing berupaya untuk memaksimalkan (atau meminimalkan) fungsi target $f(\mathbf {x} )$ , dengan $\mathbf {x}$ adalah sebuah vektor nilai kontinu dan/atau diskrit. Di setiap iterasi, hill climbing akan menyesuaikan satu elemen dalam $\mathbf {x}$ dan menentukan apakah perubahan tersebut meningkatkan nilai $f(\mathbf {x} )$ . (Perhatikan bahwa ini berbeda dengan metode penurunan gradien, yang menyesuaikan semua nilai di dalamnya $\mathbf {x}$ pada setiap iterasi sesuai dengan gradien bukit). Dengan hill climbing, perubahan apa pun yang meningkatkan $f(\mathbf {x} )$ akan diterima, dan proses akan terus berlanjut hingga tidak ditemukan perubahan yang meningkatkan nilai $f(\mathbf {x} )$ . Kemudian $\mathbf {x}$ dikatakan “optimal secara lokal”.

Dalam ruang vektor diskrit, setiap nilai yang mungkin untuk $\mathbf {x}$ dapat divisualisasikan sebagai sebuah simpul pada suatu graf. Hill climbing akan mengikuti graf dari simpul ke simpul, selalu meningkatkan (atau menurunkan) nilai $f(\mathbf {x} )$ secara lokal, hingga maksimum lokal (atau minimum lokal) $x_{m}$ tercapai.