Algoritma Hill Climbing: Pengertian, Karakteristik, dan Jenis-Jenisnya

Algoritma hill-climbing merupakan salah satu algoritma dalam bidang AI yang meningkatkan nilainya secara terus-menerus hingga mencapai solusi puncak.

Algoritma ini digunakan untuk mengoptimalkan masalah matematika dan aplikasi kehidupan nyata lainnya seperti marketing dan job scheduling.

Artikel ini akan membahas secara lebih rinci mengenai algoritma hill-climbing, mulai dari pengertian, karakteristik, hingga jenis-jenisnya. Yuk, simak!

Daftar Isi

Pengertian Algoritma Hill Climbing

Algoritma hill-climbing adalah algoritma pencarian lokal yang bergerak terus menerus ke atas hingga tercapai solusi terbaik. Algoritma ini akan berakhir ketika puncak solusi tercapai.

Algoritma Hill Climbing: Pengertian, Karakteristik, dan Jenis-Jenisnya

Algoritma hill-climbing memiliki node yang terdiri dari dua bagian: state dan value. Algoritma ini dimulai dengan keadaan yang tidak optimal (dasar bukit) dan meningkatkan keadaan ini hingga prasyarat tertentu terpenuhi. Fungsi heuristik digunakan sebagai dasar untuk prasyarat ini.

Proses peningkatan berkelanjutan dari state iterasi saat ini dapat disebut sebagai climbing. Karena itu algoritme ini disebut sebagai algoritme hill-climbing.

Tujuan algoritma hill-climbing adalah untuk mencapai keadaan optimal yang merupakan peningkatan dari keadaan yang ada.

Ketika state saat ini ditingkatkan, algoritma akan melakukan perubahan tambahan lebih lanjut ke state yang ditingkatkan.

Proses ini akan berlanjut sampai solusi puncak tercapai. Keadaan puncak tidak dapat mengalami perbaikan lebih lanjut.

Karakteristik Algoritma Hill Climbing

Algoritma hill climbing memiliki beberapa fitur atau karakteristik sebagai berikut:

1. Menggunakan pendekatan berbasis algoritma greedy

Karakteristik ini membuat algoritma hill climbing bergerak ke arah fungsi cost yang optimal. Hal ini karena pendekatan berbasis algoritma greedy memungkinkan algoritma untuk menetapkan nilai lokal minimal (local minima) atau nilai lokal maksimal (local maxima).

2. Tidak memiliki mekanisme backtracking

Algoritma hill climbing hanya bekerja pada state saat ini dan state penerusnya. Algoritma tidak menyimpan nilai state sebelumnya sehingga mekanisme backtracking tidak dimungkinkan untuk dilakukan.

3. Merupakan variasi dari algoritma generate and test

Adapun mekanisme umpan balik yang ada pada algoritma hill climbing adalah variasi atau pengembangan dari teknik generate and test.

Mekanisme umpan balik ini akan membantu algoritma untuk menentukan arah dari pergerakan (apakah akan naik atau turun).

4. Perubahan yang dilakukan bersifat inkremental

Algoritma hill climbing mengembangkan solusi masalah dengan perubahan yang bersifat inkremental.

Inkremental berarti perubahan yang dilakukan berkembang sedikit demi sedikit secara teratur hingga tercapai solusi terbaik.

State Space Diagram pada Algoritma Hill Climbing

State space diagram adalah representasi grafis dari state dan fungsi pengoptimalan. Jika fungsi tujuan adalah sumbu y, kita bertujuan untuk menetapkan local maxima dan global maxima.

Jika fungsi cost mewakili sumbu ini, kita bertujuan untuk menetapkan local minima dan global minima.

Diagram di bawah ini menunjukkan state-space diagram sederhana. Fungsi objektif (objective function) ditunjukkan pada sumbu y, sedangkan ruang keadaan (state-space) diwakili sumbu x.

State space diagram pada algoritma Hill Climbing

Sumber: javatpoint.com

State space diagram terdiri dari berbagai wilayah yang dapat dijelaskan sebagai berikut:

Local maximum: Local maximum adalah solusi yang melampaui solusi atau state tetangga lainnya tetapi bukan solusi terbaik.
Global maximum: Merupakan solusi terbaik yang dicapai oleh algoritma
Current state: adalah keadaan yang ada atau sekarang.
Flat local maximum: Merupakan daerah datar di mana solusi tetangga mencapai nilai yang sama.
Shoulder: Merupakan dataran tinggi yang ujungnya menjulur ke atas.

Jenis-jenis Algoritma Hill Climbing

Algoritma hill climbing memiliki beberapa jenis, di antaranya:

1. Simple hill climbing

Simple hill climbing merupakan jenis hill climbing yang hanya mengevaluasi status node tetangga pada satu waktu dan memilih yang pertama yang mengoptimalkan cost saat ini dan menetapkannya sebagai state terkini.

Algoritma jenis ini hanya memeriksa satu state penerusnya, dan jika ternyata lebih baik dari state saat ini, maka pindahkan yang lain dalam state yang sama.

Algoritma ini memiliki karakteristik sedikit memakan waktu namun solusi kurang optimal dan solusi tidak terjamin

2. Steepest-Ascent hill climbing

Algoritma steepest-Ascent hill climbing merupakan variasi dari simple hill climbing. Algoritma ini memeriksa semua node tetangga dari state saat ini dan memilih satu node tetangga yang paling dekat dengan state tujuan.

Algoritma jenis ini menghabiskan lebih banyak waktu karena mencari banyak node tetangga.

3. Stochastic hill climbing

Stochastic hill climbing tidak memeriksa semua node tetangganya sebelum bergerak. Sebaliknya, algoritma pencarian ini memilih satu node tetangga secara acak dan memutuskan apakah akan memilihnya sebagai state saat ini atau memeriksa state lain.

Kegunaan Algoritma Hill Climbing

Algoritma hill-climbing dapat diterapkan pada area berikut:

1. Marketing

Algoritme hill climbing dapat membantu marketing manager untuk mengembangkan rencana pemasaran terbaik.

Algoritma ini banyak digunakan dalam menyelesaikan masalah Travelling-Salesman, dimana algoritma ini dapat membantu dengan mengoptimalkan jarak yang ditempuh dan meningkatkan waktu tempuh anggota tim penjualan. Algoritme membantu menetapkan minima lokal secara efisien.

2. Robotika

Hill climbing berguna dalam pengoperasian robotika yang efektif. Algoritma ini meningkatkan koordinasi berbagai sistem dan komponen dalam robot.

3. Job scheduling

Algoritma hill climbing juga telah diterapkan dalam job scheduling di mana sumber daya sistem dialokasikan untuk tugas yang berbeda dalam sistem komputer.

Job scheduling dicapai melalui migrasi pekerjaan dari satu node ke node tetangga. Teknik hill climbing membantu menentukan rute migrasi yang tepat.

Penutup

Demikianlah penjelasan lengkap mengenai algoritma hill climbing. Semoga informasi yang disajikan di artikel ini dapat bermanfaat dan menambah khazanah pengetahuan kita.

Apabila Anda suka dengan artikel seperti ini Anda dapat mengunjungi rubrik Kecerdasan Buatan atau membaca artikel lainnya mengenai "Perbedaan Informed Search dan Uninformed Search".

Salam!

Referensi:

Trivusi