Hill climbing (algoritma)

Dalam analisis numerik, hill climbing 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, 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, yang tidak selalu merupakan solusi terbaik yang mungkin di antara semua solusi yang mungkin di ruang pencarian. Contoh algoritma yang dapat menyelesaikan masalah optimasi konveks dengan menggunakan algoritma hill climbing, antara lain adalah algoritma simpleks untuk pemrograman linier dan pencarian biner. 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. 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 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. 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.