Hill climbing (algoritma)

Suatu permukaan yang hanya memiliki satu nilai maksimum. Di sini, teknik hill climbing sangat cocok untuk mengoptimalkan permukaan tersebut, dan akan konvergen ke maksimum global.

Dalam analisis numerik, hill climbing (lit: pendakian bukit) adalah teknik optimasi matematis yang termasuk dalam keluarga pencarian lokal. Ia adalah algoritma iteratif yang dimulai dengan solusi sembarang terhadap suatu masalah, kemudian mencoba untuk menemukan solusi yang lebih baik dengan membuat perubahan bertahap pada solusi tersebut. Jika perubahan tersebut menghasilkan solusi yang lebih baik, maka perubahan tambahan lainnya akan dilakukan pada solusi yang baru, dan 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 mengganti urutan dua kota yang dikunjungi. Pada akhirnya, rute yang jauh lebih pendek bisa didapatkan.

Hill climbing menemukan solusi optimal untuk permasalahan optimasi convex, sedangkan untuk permasalahan lain hill climbing hanya akan menemukan optimum lokal (solusi yang tidak dapat diperbaiki dengan konfigurasi tetangga), yang belum tentu merupakan solusi terbaik (optimum global) dari semua solusi yang mungkin dari ruang pencarian. Contoh algoritma yang dapat menyelesaikan masalah cembung dengan hill climbing, antara lain adalah algoritma simpleks untuk pemrograman linier dan pencarian biner. ^:253 Untuk menghindari terjebak dalam optimum lokal, dapat dengan menggunakan 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. Namun, dalam beberapa situasi, hill climbing juga dapat digunakan. Hill climbing sering kali dapat memberikan hasil yang lebih baik, dibandingkan dengan algoritma lain ketika jumlah waktu yang tersedia untuk melakukan pencarian terbatas, seperti pada sistem real-time. Hal tersebut dapat terjadi asalkan sejumlah kecil kenaikan biasanya konvergen pada solusi yang baik (solusi optimal atau pendekatan solusi). 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 teratur), 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 matematika

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.

Lihat juga

• Penurunan gradien
• Algoritma serakah
• Tâtonnement
• Pergeseran rata-rata
• Algoritma pencarian A*

Bacaan lanjutan

• Lasry, George (2018). A Methodology for the Cryptanalysis of Classical Ciphers with Search Metaheuristics (PDF). Kassel University Press. ISBN 978-3-7376-0459-8. 

Pranala eksternal

• Hill climbing (algoritma) di Wikibuku