Pendakian bukit (algoritma)

Dalam analisis numerik, pendakian bukit atau dalam bahasa Inggris hill climbing merupakan teknik optimasi matematis yang termasuk dalam keluarga algoritma pencarian setempat. Ia adalah algoritma berulang yang diawali dengan memulakan sembarang solusi untuk suatu masalah, kemudian mencoba menemukan solusi yang lebih baik dengan melakukan perubahan bertambah secara bertahap pada solusi tersebut. Jika perubahan tersebut menghasilkan solusi yang lebih baik, maka perubahan bertambah secara bertahap lainnya akan dilakukan pada solusi yang baru, dan begitu seterusnya hingga tak ada lagi perbaikan yang dapat ditemukan.

Sebagai contoh, pendakian bukit 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, jalur yang jauh lebih pendek bisa ditemukan.

Pendakian bukit mampu menemukan solusi optimal, khususnya untuk masalah optimasi cembung, sedangkan untuk permasalahan lain, pendakian bukit hanya akan menemukan optimum setempat (solusi yang tak 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 cembung dengan algoritma pendakian bukit, antara lain adalah algoritma mufrad untuk pemrograman linier dan pencarian biner.^[1] ^:253 Untuk menghindari terjebak dalam optimum setempat, dapat digunakan pendekatan, seperti memulai ulang, yaitu pencarian setempat berulang, atau dengan skema yang lebih rumit berdasarkan perulangan, seperti perulangan pencarian setempat, atau berdasarkan memori, seperti optimisasi pencarian bereaksi dan pencarian tabu), atau dengan modifikasi stokastik tanpa penggunaan memori (seperti penaruman tersimulasi).

Kesederhanaan 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 simpul awal yang mana terdapat beberapa pilihan yang berbeda untuk simpul berikutnya dan simpul awal yang digunakan dalam algoritma terkait. Walau terdapat algoritma yang lebih canggih, seperti penaruman tersimulasi atau pencarian tabu yang mungkin memberikan hasil yang lebih baik, tetapi dalam beberapa situasi saat pendakian bukit dapat bekerja sama baiknya. Pendakian bukit sering kali dapat memberikan hasil yang lebih baik, dibandingkan dengan algoritma lain ketika jumlah waktu yang tersedia terbatas untuk melakukan pencarian, seperti pada sistem waktu nyata, selama jumlah penambahan bertahap yang kecil umumnya konvergen pada solusi yang baik (solusi optimal atau pendekatan yang mendekati). Di sisi lain, salah satu algoritma pengurutan, pengurutan gelembung dapat dilihat sebagai algoritma pendakian bukit, sebab setiap pertukaran unsur yang berdekatan akan mengurangi jumlah pasangan unsur yang tidak terurut), tetapi pendekatan ini jauh dari efisien, bahkan untuk N yang kecil sekalipun, karena jumlah pertukaran yang dibutuhkan akan bertambah secara kuadratik.

Pendakian bukit termasuk dalam algoritma kapan pun atau algoritma yang dapat digunakan kapan pun, sebab ia dapat mengembalikan solusi yang sah. Bahkan, ketika diganggu kapan pun sebelum penyelenggaraan algoritma tersebut berakhir.

Keterangan matematis

Pendakian bukit berupaya untuk memaksimalkan (atau meminimalkan) fungsi target $f(\mathbf {x} )$ , dengan $\mathbf {x}$ adalah sebuah vektor nilai bersinambung dan/atau berlainan. Di setiap perulangan, pendakian bukit akan menyesuaikan satu unsur 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 perulangan sesuai dengan gradien bukit). Dengan pendakian bukit, 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 setempat”.

Dalam ruang vektor berlainan, 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 setempat, hingga maksimum setempat (atau minimum setempat) $x_{m}$ tercapai.