Mengimplementasikan Algoritma Hill Climbing untuk AI di Python

Algoritma hill climbing adalah salah satu algoritma optimasi paling awal dan paling sederhana dalam kecerdasan buatan dan ilmu komputer. Algoritma ini termasuk dalam kategori yang disebut algoritma pencarian lokal (local search), yang menemukan solusi dengan melakukan perbaikan bertahap.

Nama algoritma ini berasal dari analogi yang membantu: bayangkan seorang pendaki dengan mata tertutup mencoba mencapai puncak bukit. Karena ia tidak dapat melihat seluruh lanskap, ia hanya bisa merasakan tanah di sekitarnya. Pada setiap langkah, ia bergerak ke arah mana pun yang menanjak. Ini mencerminkan cara kerja algoritma — ia mengevaluasi solusi di sekitar dan bergerak secara iteratif menuju yang lebih baik, berupaya menemukan solusi optimal (puncak bukit).

Dalam artikel ini, kita akan membahas algoritma hill climbing secara mendalam, variasinya, dan cara mengimplementasikannya di Python. Jika Anda baru di AI, pastikan untuk memeriksa jalur keterampilan AI Fundamentals untuk mempelajari dasar-dasarnya. 

Apa itu Algoritma Hill Climbing dalam AI?

Hill climbing adalah cara sederhana bagi komputer untuk memecahkan masalah dengan mencari jawaban terbaik, seperti pendaki yang mencoba mencapai puncak gunung. Dalam kecerdasan buatan (AI), kita sering perlu menemukan solusi terbaik di antara banyak pilihan. Ini disebut optimasi.

Bayangkan mencoba menemukan titik tertinggi saat bermain permainan “panas dan dingin.” Dalam permainan ini, Anda hanya bisa memeriksa apakah Anda menjadi “lebih hangat” (lebih baik) atau “lebih dingin” (lebih buruk) saat bergerak. Hill climbing bekerja dengan cara yang sama — ia melihat solusi di sekitar dan bergerak menuju yang lebih baik.

Begini cara kerjanya dalam langkah sederhana:

1. Mulai dengan solusi apa pun yang mungkin
2. Lihat solusi di sekitarnya
3. Jika solusi terdekat lebih baik, pindah ke sana
4. Ulangi langkah 2–3 hingga tidak ada solusi yang lebih baik ditemukan

Sebagai contoh, jika Anda mencoba mengajarkan robot untuk berjalan, Hill Climbing mungkin:

• Mulai dengan gerakan kaki acak
• Mencoba gerakan yang sedikit berbeda
• Mempertahankan gerakan yang membantu robot berjalan lebih baik
• Mengulang hingga menemukan pola berjalan terbaik

Walau hill climbing tidak selalu menjadi metode paling canggih dalam AI, ini adalah batu loncatan penting yang membantu kita memahami bagaimana komputer dapat memecahkan masalah secara mandiri, serupa dengan algoritma minimax.

Jenis-jenis Algoritma Hill Climbing

Ada tiga jenis utama algoritma hill climbing, masing-masing dengan caranya sendiri untuk mencari solusi terbaik:

1. Simple hill climbing

Simple hill climbing seperti mengambil langkah baik pertama yang Anda temukan. Dalam versi ini:

• Algoritma melihat solusi terdekat satu per satu
• Segera setelah menemukan solusi yang lebih baik, ia mengambilnya
• Ia tidak memeriksa opsi lain
• Ini cepat tetapi bisa melewatkan solusi yang lebih baik yang sedikit lebih jauh

2. Steepest-ascent hill climbing

Versi ini lebih teliti daripada simple hill climbing:

• Ia melihat SEMUA solusi terdekat sebelum bergerak
• Memilih opsi terbaik dari semua yang ditemukan
• Memakan waktu lebih lama tetapi biasanya menemukan solusi yang lebih baik
• Ini seperti memeriksa setiap jalur dengan saksama sebelum melangkah

3. Stochastic hill climbing

Jenis ini menambahkan beberapa keacakan agar pencarian lebih fleksibel:

• Alih-alih selalu memilih solusi terbaik, ia secara acak memilih dari opsi yang lebih baik
• Solusi yang lebih baik memiliki peluang lebih tinggi untuk dipilih
• Keacakan ini membantu menghindari terjebak di posisi buruk
• Ini seperti sesekali mengambil jalur berbeda untuk melihat ke mana arahnya

Setiap jenis memiliki keunggulannya masing-masing dan lebih cocok untuk berbagai jenis masalah. Simple hill climbing cepat namun dasar, steepest-ascent teliti namun lebih lambat, dan stochastic menambahkan keacakan yang membantu agar tidak mudah terjebak.

Cara Kerja Algoritma Hill Climbing

Algoritma hill climbing bekerja dengan melakukan perbaikan kecil selangkah demi selangkah hingga menemukan solusi terbaik yang dapat dicapainya. Mari kita uraikan cara kerjanya ke dalam bagian-bagian utama.

1. Memulai

Setiap algoritma hill climbing membutuhkan titik awal. Anggap saja seperti memilih dari mana memulai pendakian di gunung. Anda bisa mulai secara acak, atau menggunakan pengetahuan tentang masalah untuk memilih titik awal yang baik. 

Tempat Anda memulai sangat berpengaruh — pilih tempat yang baik, Anda bisa menemukan solusi terbaik dengan cepat. Pilih tempat yang buruk, Anda mungkin terjebak di bukit kecil alih-alih menemukan puncak gunung.

Sebagai contoh, dalam melatih jaringan saraf, titik awal berarti memilih bobot awal untuk koneksi antar neuron. Anda bisa menginisialisasi bobot ini secara acak, yang mirip dengan memulai pendakian di titik acak di gunung. Atau Anda bisa menggunakan teknik seperti inisialisasi Xavier yang memilih bobot awal yang cerdas berdasarkan struktur jaringan. 

Inisialisasi yang baik membantu jaringan belajar lebih cepat dan menemukan solusi yang lebih baik, sedangkan inisialisasi yang buruk bisa membuat jaringan terjebak pada akurasi rendah yang tidak pernah membaik.

2. Melihat solusi di sekitar

Setelah algoritma memulai pencarian, ia mengevaluasi solusi tetangga yang mirip dengan posisi saat ini. Anggap saja seperti menjelajah sekitar dengan langkah-langkah kecil. Misalnya, jika Anda mencoba mengoptimalkan rute pengiriman antar kota, dan rute saat ini adalah [A -> B -> C -> D], algoritma akan menelaah rute serupa seperti [A -> B -> D -> C] atau [A -> C -> B -> D] untuk melihat apakah itu mengurangi total jarak tempuh. Setiap perubahan kecil pada rute mewakili solusi “tetangga” yang berpotensi lebih baik daripada yang sekarang.

Untuk membuat perbandingan ini, algoritma bergantung pada apa yang disebut fungsi objektif — rumus matematis yang memberikan skor atau nilai untuk setiap solusi yang mungkin.

Fungsi ini berfungsi seperti kompas, membantu algoritma memahami arah mana yang mengarah “menanjak” menuju solusi yang lebih baik dan mana yang mengarah “menurun” ke solusi yang lebih buruk. Untuk rute pengiriman, fungsi objektif akan menghitung total jarak tempuh — jarak total yang lebih pendek berarti solusi yang lebih baik. 

Jadi jika rute X menempuh 100 mil dan rute Z 90 mil, rute B akan memiliki skor yang lebih baik (lebih rendah). Algoritma kemudian akan tahu untuk bergerak ke arah solusi yang mirip dengan rute B. Fungsi objektif pada dasarnya mengubah masalah kompleks optimasi rute menjadi angka sederhana yang dapat dibandingkan dan diminimalkan.

3. Memilih langkah berikutnya

Setelah melihat solusi di sekitar, algoritma perlu memutuskan ke mana harus bergerak selanjutnya. Algoritma membandingkan skor solusi terdekat dengan yang saat ini. Jika menemukan solusi yang lebih baik, ia pindah ke sana. Versi hill climbing yang berbeda membuat pilihan ini dengan cara berbeda:

• Versi sederhana mengambil solusi lebih baik pertama yang ditemukannya
• Versi yang teliti memeriksa semua solusi terdekat sebelum memilih yang terbaik
• Versi acak kadang memilih solusi yang bukan paling baik, yang dapat membantu menghindari kebuntuan

4. Mengetahui kapan harus berhenti

Algoritma perlu mengetahui kapan harus berhenti mencari solusi yang lebih baik. Biasanya, ia berhenti ketika salah satu hal berikut terjadi:

1. Tidak dapat menemukan solusi yang lebih baik di sekitar
2. Sudah berjalan terlalu lama
3. Telah menemukan solusi yang cukup baik

Saat algoritma bekerja, ia biasanya mengikuti pola. Pada awalnya, ia menemukan solusi yang lebih baik dengan cepat, seperti mengambil langkah besar menanjak. Lalu, ia melambat saat mendekati puncak, membuat perbaikan kecil hingga akhirnya berhenti. 

Terkadang jalurnya mulus dan lurus, tetapi kadang juga rumit dengan banyak naik turun.

Keunggulan dan Keterbatasan Hill Climbing dalam AI

Mari kita lihat apa yang membuat hill climbing berguna dan masalah apa yang mungkin Anda temui saat menggunakannya.

Keunggulan

Hill climbing adalah salah satu algoritma optimasi yang paling mudah dipahami dan diprogram. Prinsipnya sederhana: “Jika sesuatu lebih baik, pergilah ke sana.” Ini membuatnya menjadi titik awal yang bagus untuk menyelesaikan banyak masalah.

Ketika masalahnya sederhana, hill climbing dapat menemukan solusi yang baik dengan cepat. Ia tidak membuang waktu menjelajahi setiap kemungkinan solusi — ia hanya mengikuti jalur yang menanjak.

Algoritma ini tidak memerlukan banyak memori atau daya pemrosesan. Ia hanya perlu mengingat posisinya dan melihat solusi terdekat, sehingga praktis untuk banyak masalah dunia nyata.

Keterbatasan

Tentu saja, seperti metode apa pun, ada beberapa kekurangan potensial: 

1. Terjebak di bukit kecil

Masalah terbesar dengan hill climbing adalah dapat terjebak pada apa yang kita sebut “maksimum lokal” — ini seperti bukit kecil ketika sebenarnya ada gunung di dekatnya. Setelah algoritma mencapai puncak bukit kecil, ia berhenti karena segala sesuatu di sekitarnya lebih rendah, meskipun mungkin ada solusi yang jauh lebih baik di tempat lain.

2. Masalah tanah datar

Terkadang algoritma berada di tanah datar (disebut plateau), di mana semua solusi terdekat sama baiknya. Bayangkan mencoba menemukan titik tertinggi saat berjalan di lapangan sepak bola yang rata — sulit mengetahui ke arah mana harus pergi!

3. Masalah punggungan

Bayangkan mencoba berjalan di atas puncak punggungan gunung yang sempit. Algoritma bisa membuang waktu berzigzag ke kiri dan kanan melintasi punggungan alih-alih bergerak maju ke puncak. Ini terjadi karena setiap langkah ke samping terlihat sama baiknya dengan tetap di jalur.

4. Titik awal sangat menentukan

Tempat Anda memulai dapat sangat memengaruhi seberapa baik algoritma bekerja. Ini seperti memulai pendakian — mulai dari tempat yang salah, Anda mungkin tidak pernah menemukan puncak tertinggi.

Keterbatasan ini tidak berarti hill climbing adalah pilihan buruk — ini hanya berarti kita perlu berhati-hati tentang kapan dan bagaimana menggunakannya. Terkadang, kita bisa mengombinasikannya dengan teknik lain untuk mengatasi masalah ini, yang akan kita bahas di bagian berikutnya.

Strategi untuk Mengatasi Keterbatasan

Saat menggunakan hill climbing, kita dapat memakai beberapa strategi cerdas untuk menyelesaikan masalah yang dibahas sebelumnya. Mari kita telusuri dua pendekatan utama yang membantu membuat hill climbing bekerja lebih baik.

Random-restart hill climbing

Salah satu cara terbaik untuk menghindari terjebak di bukit kecil adalah mencoba mendaki dari titik awal yang berbeda. Pendekatan ini disebut random-restart hill climbing, dan bekerja persis seperti namanya — jika Anda buntu, mulailah lagi di tempat baru.

Bayangkan mencoba menemukan gunung tertinggi di jajaran pegunungan berkabut. Jika Anda mulai mendaki bukit pertama yang ditemukan dan mencapai puncaknya, Anda mungkin melewatkan gunung yang jauh lebih tinggi di dekatnya. Namun jika Anda bisa “teleportasi” ke tempat berbeda dan mulai mendaki lagi, Anda akan memiliki peluang lebih besar untuk akhirnya menemukan puncak tertinggi.

Begini cara kerjanya: Pertama, jalankan algoritma hill climbing biasa hingga mentok. Alih-alih menyerah, simpan solusi terbaik yang ditemukan lalu mulai lagi di titik acak baru. Terus lakukan ini untuk beberapa percobaan, dan pada akhirnya, pilih solusi terbaik dari semua percobaan.

Keunggulan random-restart adalah sederhana namun efektif. Setiap kali mulai ulang memberi Anda peluang baru untuk menemukan puncak tertinggi. Walau memakan waktu lebih lama dibanding hill climbing biasa, pendekatan ini jauh lebih mungkin menemukan solusi terbaik.

Simulated annealing

Meskipun secara teknis bukan hill climbing, simulated annealing adalah variasi cerdas yang membantu menyelesaikan banyak masalah hill climbing. Metode ini terinspirasi dari bagaimana logam didinginkan dan mengeras dalam pengerjaan logam. Saat logam didinginkan perlahan, atom-atomnya menemukan posisi yang lebih baik, membuat logam lebih kuat.

Dalam pendekatan ini, algoritma terkadang menerima solusi yang lebih buruk dengan sengaja, terutama di awal. Seiring waktu, ia menjadi lebih selektif terhadap solusi yang diterima. Ini seperti bola yang memantul di permukaan bergelombang — pada awalnya, ia punya cukup energi untuk melompati bukit, tetapi saat energinya berkurang, ia menetap di tempat yang baik.

Begini cara kerjanya: Pada awalnya, algoritma mungkin menerima solusi yang lebih buruk daripada yang sekarang dengan probabilitas yang cukup tinggi. Probabilitas ini bergantung pada dua hal: seberapa jauh lebih buruk solusi baru dan berapa lama algoritma telah berjalan. Seiring waktu, algoritma menjadi semakin kecil kemungkinannya untuk menerima solusi yang lebih buruk, dan akhirnya bertindak lebih mirip Hill Climbing biasa.

Kekuatan utama simulated annealing adalah dapat keluar dari bukit kecil dan area datar, terutama di awal pencarian. Dengan sesekali menerima solusi yang lebih buruk, ia dapat:

• Melompat keluar dari maksimum lokal (bukit kecil)
• Melewati plateau (area datar)
• Menavigasi punggungan (puncak sempit)
• Menjelajahi lebih banyak ruang solusi

Sebagai contoh, bayangkan Anda mencoba menata furnitur di ruangan untuk memaksimalkan ruang. Memindahkan kursi mungkin sementara membuat ruangan lebih sempit, tetapi bisa memungkinkan Anda memindahkan barang lain ke posisi yang jauh lebih baik. Simulated annealing bersedia mencoba susunan yang sementara lebih buruk, terutama di awal proses, untuk menemukan susunan keseluruhan yang terbaik.

Strategi ini menunjukkan bahwa terkadang cara terbaik untuk menyelesaikan masalah bukan selalu mengambil langkah yang tampak jelas. Dengan menambahkan unsur keacakan dan “kekacauan” yang terkontrol, kita sering dapat menemukan solusi yang lebih baik daripada selalu mengambil jalur lurus.

Mengimplementasikan Algoritma Hill Climbing Sederhana di Python

Sekarang setelah kita memahami cara meningkatkan hill climbing dengan strategi seperti random-restart dan simulated annealing, mari kita terapkan pada masalah finansial nyata: optimasi portofolio.

Optimasi portofolio membantu investor memutuskan bagaimana membagi uang mereka di berbagai investasi. Saat membangun portofolio, investor ingin meraih imbal hasil setinggi mungkin sambil menjaga risiko tetap rendah. Menemukan keseimbangan ini rumit — ibarat mencari resep sempurna dengan banyak bahan.

Pada tahun 1952, seorang ekonom bernama Harry Markowitz menemukan cara cerdas untuk menyelesaikan masalah ini. Ia menunjukkan bahwa investor dapat mengurangi risiko dengan mencampur investasi yang tidak bergerak naik turun bersamaan. Ini disebut diversifikasi — mirip dengan tidak menaruh semua telur dalam satu keranjang.

Saat membangun portofolio, kita perlu menghitung tiga hal utama:

• Berapa banyak uang yang kita harapkan untuk diperoleh (Expected Return)
• Seberapa berisiko investasinya (Portfolio Risk)
• Apakah potensi keuntungan sebanding dengan risikonya (Risk-Adjusted Return)

Hill Climbing cocok untuk masalah ini karena perubahan kecil dalam pembagian uang biasanya menghasilkan perubahan kecil dalam kinerja portofolio. Bayangkan sebuah bukit halus di mana setiap titik merepresentasikan cara berbeda untuk menginvestasikan uang Anda. Titik yang lebih tinggi menunjukkan pilihan investasi yang lebih baik.

Untuk menemukan portofolio yang baik menggunakan Hill Climbing, kita akan:

1. Mulai dengan campuran investasi acak
2. Mencoba campuran yang sedikit berbeda untuk melihat apakah hasilnya lebih baik
3. Terus membuat perbaikan kecil hingga kita tidak bisa menemukan opsi yang lebih baik
4. Menggunakan campuran terbaik yang kita temukan

Dengan menggunakan hill climbing seperti ini, kita dapat membantu investor menemukan portofolio yang lebih baik di antara jutaan kombinasi yang mungkin. Ini seperti memiliki asisten cerdas yang dapat dengan cepat menguji berbagai campuran investasi untuk menemukan yang menyeimbangkan risiko dan imbal hasil dengan baik.

Pertama, mari kita definisikan fungsi objektif, yaitu ukuran kinerja portofolio yang menyeimbangkan ekspektasi imbal hasil terhadap risiko. Fungsi ini menerima daftar bobot portofolio sebagai masukan dan mengembalikan skor, di mana skor lebih tinggi menunjukkan portofolio yang lebih baik.

def objective_function(state):
   """
   Portfolio optimization objective function that maximizes expected returns while minimizing risk.
   The state represents portfolio weights for different assets.

   Args:
       state (list): List of portfolio weights for different assets (should sum to 1)

   Returns:
       float: Portfolio score combining returns and risk
   """
   # Expected annual returns for assets (example values)
   expected_returns = [0.1, 0.12, 0.18, 0.1, 0.15]  # 8%, 12%, etc.

   # Risk (volatility) for each asset
   volatilities = [0.1, 0.2, 0.3, 0.2, 0.2]  # 10%, 20%, etc.

   # Validate input length matches expected returns/volatilities
   if len(state) != len(expected_returns):
       return float("-inf")  # Return worst possible score for invalid states

   # Calculate expected portfolio return
   portfolio_return = sum(w * r for w, r in zip(state, expected_returns))

   # Calculate portfolio risk (simplified, not using covariance matrix)
   portfolio_risk = sum(w * v for w, v in zip(state, volatilities))

   # Penalize if weights don't sum to 1 (invalid portfolio)
   weight_sum_penalty = abs(sum(state) - 1) * 100

   # Penalize negative weights (no short selling)
   negative_weight_penalty = sum(abs(min(0, w)) for w in state) * 100

   # Combine return and risk with risk aversion factor of 2
   # Higher score is better: maximize return, minimize risk and penalties
   score = (
       portfolio_return
       - 2 * portfolio_risk
       - weight_sum_penalty
       - negative_weight_penalty
   )

   return score

Fungsi objective_function di atas membantu kita mengevaluasi seberapa baik suatu portofolio investasi. Mari kita uraikan cara kerjanya:

Pertama, fungsi ini menerima daftar angka yang merepresentasikan persentase uang yang ingin kita investasikan pada berbagai aset (seperti saham atau obligasi). Misalnya, jika kita memiliki lima aset, kita mungkin menginvestasikan 20% pada masing-masing.

Fungsi ini menggunakan dua informasi penting:

1. Expected returns: Berapa banyak uang yang kita harapkan dari setiap aset (misalnya 8% atau 12% per tahun)
2. Volatilities: Seberapa berisiko setiap aset — angka yang lebih tinggi berarti nilai aset lebih tidak dapat diprediksi perubahannya (seperti kripto)

Fungsi kemudian:

• Menghitung total ekspektasi imbal hasil portofolio dengan mengalikan ekspektasi imbal hasil setiap aset dengan porsi investasi pada aset tersebut
• Menentukan total risiko dengan melihat volatilitas masing-masing aset
• Memeriksa apakah persentase investasi berjumlah 100% (harus demikian!)
• Memastikan kita tidak mencoba menjual aset yang tidak kita miliki (tidak ada persentase negatif)

Terakhir, fungsi menggabungkan semua informasi ini menjadi satu skor. Skor yang lebih tinggi berarti portofolio yang lebih baik. Skor meningkat dengan imbal hasil yang lebih tinggi tetapi menurun dengan risiko yang lebih tinggi. Skor juga menjadi jauh lebih buruk jika persentase tidak berjumlah 100% atau jika kita mencoba menggunakan persentase negatif.

Fungsi ini akan membantu kita menemukan campuran investasi terbaik menggunakan algoritma hill climbing berikutnya. Jika Anda belum sepenuhnya memahami fungsi objektif, tidak masalah — intinya adalah fungsi ini memberi tahu kita seberapa baik suatu campuran investasi, dan kita akan menggunakannya untuk menemukan kombinasi yang semakin baik.

Sekarang, mari kita definisikan fungsi baru untuk menghasilkan keadaan portofolio tetangga dengan membuat penyesuaian kecil pada bobot.

def get_neighbors(state):
   """
   Generates neighboring states by making small adjustments to portfolio weights

   Args:
       state (list): Current portfolio weights

   Returns:
       list: List of neighboring portfolio weight configurations
   """
   neighbors = []
   step_size = 0.01  # Small adjustment to weights (1%)

   for i in range(len(state)):
       for j in range(len(state)):
           if i != j:
               # Transfer weight from asset i to asset j
               neighbor = state.copy()
               if neighbor[i] >= step_size:  # Only transfer if enough weight available
                   neighbor[i] -= step_size
                   neighbor[j] += step_size
                   neighbors.append(neighbor)

   return neighbors

Fungsi get_neighbors adalah bagian penting dari algoritma hill climbing kita yang menghasilkan alokasi portofolio serupa dengan membuat penyesuaian kecil pada bobot portofolio saat ini. Begini cara kerjanya:

Untuk setiap pasangan aset dalam portofolio, fungsi ini membuat alokasi portofolio baru dengan memindahkan sebagian kecil (1%) dari satu aset ke aset lainnya. Misalnya, jika kita memiliki lima aset, ia akan mencoba:

• Memindahkan 1% dari Aset 1 ke Aset 2
• Memindahkan 1% dari Aset 1 ke Aset 3
• Memindahkan 1% dari Aset 1 ke Aset 4
• Memindahkan 1% dari Aset 1 ke Aset 5
• Memindahkan 1% dari Aset 2 ke Aset 1 dan seterusnya untuk semua pasangan yang mungkin.

Fungsi ini menyertakan pemeriksaan keamanan untuk memastikan kita hanya mentransfer bobot jika aset sumber memiliki alokasi yang cukup (setidaknya 1%). Ini mencegah bobot negatif, yang tidak masuk akal dalam portofolio nyata.

Setiap penyesuaian kecil ini menciptakan “tetangga” — alokasi portofolio yang sangat mirip dengan yang sekarang tetapi sedikit berbeda. Algoritma hill climbing kemudian akan mengevaluasi para tetangga ini untuk menemukan alokasi portofolio yang lebih baik.

Ukuran langkah 1% memberikan keseimbangan yang baik antara menjelajahi berbagai alokasi dan melakukan perubahan yang terkontrol. Ukuran langkah yang lebih besar bisa melewatkan solusi optimal, sementara yang lebih kecil akan membuat pencarian terlalu lambat.

Sekarang, mari kita implementasikan algoritma hill climbing sederhana:

def simple_hill_climbing(initial_state, max_iterations=1000):
   """
   Implements Simple Hill Climbing algorithm
  
   Args:
       initial_state (list): Starting point for the algorithm
       max_iterations (int): Maximum number of iterations to prevent infinite loops
  
   Returns:
       tuple: (best_state, best_value) found by the algorithm
   """
   current_state = initial_state
   current_value = objective_function(current_state)
  
   for _ in range(max_iterations):
       # Get neighboring states
       neighbors = get_neighbors(current_state)
      
       # Flag to check if we found a better neighbor
       found_better = False
      
       # Check neighbors one by one (Simple Hill Climbing)
       for neighbor in neighbors:
           neighbor_value = objective_function(neighbor)
          
           # If we find a better neighbor, move to it immediately
           if neighbor_value > current_value:
               current_state = neighbor
               current_value = neighbor_value
               found_better = True
               break
      
       # If no better neighbor was found, we've reached a peak
       if not found_better:
           break
  
   return current_state, current_value

Fungsi ini mulai dari keadaan awal dan bergerak secara iteratif ke keadaan tetangga yang lebih baik hingga mencapai maksimum lokal atau jumlah iterasi maksimum.

Fungsi ini menerima dua parameter:

• initial_state: Titik awal untuk optimasi, direpresentasikan sebagai daftar nilai
• max_iterations: Parameter keamanan untuk mencegah loop tak berujung, bawaan 1000 iterasi

Algoritma bekerja sebagai berikut:

1. Mulai pada initial_state dan menghitung nilai fungsi objektifnya
2. Untuk setiap iterasi, algoritma:

• Menghasilkan keadaan tetangga menggunakan get_neighbors()
• Mengevaluasi setiap tetangga satu per satu
• Segera setelah menemukan tetangga yang lebih baik (nilai objektif lebih tinggi), ia berpindah ke keadaan tersebut
• Jika tidak ada tetangga yang lebih baik, algoritma telah mencapai maksimum lokal dan berhenti

Fungsi mengembalikan sepasang nilai berisi:

• Keadaan terbaik yang ditemukan (daftar nilai)
• Nilai fungsi objektif untuk keadaan tersebut

Varian “sederhana” dari hill climbing ini bersifat rakus (greedy) — ia berpindah ke tetangga lebih baik pertama yang ditemukannya alih-alih mengevaluasi semua tetangga untuk menemukan yang terbaik. Walau ini membuatnya lebih cepat, ia bisa melewatkan solusi yang lebih baik yang bisa ditemukan jika lebih teliti.

Algoritma ini berguna untuk menemukan optimum lokal tetapi dapat terjebak pada maksimum lokal ini, sehingga berpotensi melewatkan maksimum global. Terlepas dari keterbatasan ini, ia tetap populer karena kesederhanaan dan efisiensinya.

Mari kita uji pada contoh portofolio:

# Example usage
initial_state = [0.15, 0.25, 0.1, 0.3, 0.2]
best_state, best_value = simple_hill_climbing(initial_state)
print(f"Initial State: {initial_state}")
print(f"Best State Found: {best_state}")
print(f"Best Value: {best_value}")

[OUT]:

Initial State: [0.15, 0.25, 0.1, 0.3, 0.2]
Best State Found: [0.9700000000000006, 0.009999999999999913, 1.0408340855860843e-17, 0.009999999999999858, 0.009999999999999969]
Best Value: -0.1053000000000444

Keluaran menunjukkan hasil algoritma hill climbing kita saat mengoptimasi portofolio. Dimulai dari bobot acak untuk lima aset, algoritma menemukan seperangkat bobot baru yang memperbaiki nilai fungsi objektif. Meski solusi ini lebih baik daripada portofolio awal, kemungkinan ini hanya optimum lokal karena algoritma berhenti pada puncak pertama yang ditemukannya.

Aplikasi Hill Climbing dalam AI

Algoritma Hill Climbing memiliki aplikasi praktis di banyak bidang kecerdasan buatan dan pembelajaran mesin. Mari kita telusuri beberapa aplikasi kunci:

1. Optimasi model machine learning

Hill climbing membantu menyetel model machine learning dalam beberapa cara:

• Pemilihan fitur: Menemukan subset fitur terbaik untuk model
• Penyetelan hiperparameter: Mengoptimalkan parameter model seperti learning rate atau kedalaman pohon
• Pelatihan jaringan saraf: Menyetel bobot dan arsitektur jaringan
• Kompresi model: Mengurangi ukuran model sambil mempertahankan kinerja

Sebagai contoh, saat memilih fitur untuk model prediktif, Hill Climbing dapat mulai dengan semua fitur dan secara iteratif menghapus atau menambahkannya berdasarkan kinerja model. Ini membantu menemukan himpunan fitur optimal yang menyeimbangkan akurasi model dengan kompleksitas.

2. Robotika dan perencanaan lintasan

Dalam robotika, hill climbing membantu dalam:

• Perencanaan gerak: Menemukan lintasan efisien di ruang fisik
• Optimasi sudut sendi: Menentukan posisi optimal untuk lengan robot
• Penempatan sensor: Mengoptimalkan penempatan sensor untuk cakupan maksimal
• Manajemen baterai: Mengoptimalkan pola konsumsi daya

Robot vacuum mungkin menggunakan hill climbing untuk menemukan lintasan pembersihan yang efisien, terus menyesuaikan rutenya berdasarkan cakupan ruangan dan daya baterai.

3. Pemrosesan bahasa alami

NLP mencakup aplikasi:

• Ringkasan teks: Mengoptimalkan pemilihan konten ringkasan
• Word embedding: Menyetel representasi vektor kata
• Pengelompokan dokumen: Mengelompokkan dokumen ke dalam grup optimal
• Optimasi mesin pencari: Meningkatkan peringkat hasil pencarian

Misalnya, dalam peringkasan teks, Hill Climbing dapat membantu memilih kalimat yang memaksimalkan informasi sekaligus meminimalkan redundansi.

4. Computer vision Dalam pengolahan citra dan penglihatan komputer

• Segmentasi citra: Menemukan batas optimal antar objek
• Kalibrasi kamera: Menyetel parameter kamera untuk kualitas gambar yang lebih baik
• Deteksi objek: Mengoptimalkan posisi bounding box
• Pencocokan fitur: Menemukan titik yang bersesuaian antar citra

Sebuah sistem pengenalan wajah mungkin menggunakan hill climbing untuk mengoptimalkan penyelarasan fitur wajah selama prapemrosesan.

5. Game AI dan pengambilan keputusan

Hill climbing membantu dalam:

• Optimasi strategi permainan: Menemukan langkah kemenangan dalam permainan papan
• Alokasi sumber daya: Mengoptimalkan distribusi sumber daya dalam permainan strategi
• Perilaku NPC: Meningkatkan pengambilan keputusan karakter non-pemain
• Pembuatan level: Menciptakan level permainan yang seimbang dan menarik

Mesin catur sering menggunakan varian hill climbing untuk mengevaluasi dan mengoptimalkan urutan langkah selama permainan.

6. Bisnis dan operasional

Aplikasi bisnis praktis meliputi:

• Optimasi rantai pasok: Menemukan rute pengiriman yang efisien
• Penjadwalan sumber daya: Mengoptimalkan jadwal staf atau penggunaan mesin
• Manajemen portofolio: Menyeimbangkan portofolio investasi
• Manajemen inventaris: Mengoptimalkan tingkat stok

Perusahaan pengiriman dapat menggunakan hill climbing untuk terus mengoptimalkan rute pengiriman berdasarkan pola lalu lintas dan prioritas paket.

Meskipun hill climbing mungkin tidak selalu menemukan solusi terbaik secara absolut, kesederhanaan dan efisiensinya membuatnya berharga untuk aplikasi dunia nyata ini. Ini sangat berguna ketika:

• Solusi cepat dibutuhkan
• Ruang masalah terlalu besar untuk pencarian menyeluruh
• Solusi perkiraan dapat diterima
• Ruang solusi relatif mulus
• Algoritma dapat dikombinasikan dengan teknik lain untuk hasil yang lebih baik

Kesimpulan

Hill climbing berdiri sebagai algoritma dasar dalam kecerdasan buatan, menawarkan pendekatan yang lugas namun kuat untuk masalah optimasi. 

Melalui pembahasan kita, terlihat bagaimana konsep sederhana bergerak secara iteratif menuju solusi yang lebih baik dapat diterapkan pada tantangan kompleks di machine learning, robotika, pemrosesan bahasa alami, dan operasional bisnis. 

Meskipun algoritma ini memiliki keterbatasan, seperti terjebak pada optimum lokal, strategi seperti random-restart dan simulated annealing telah berkembang untuk mengatasi tantangan ini secara efektif.

Seiring AI terus berkembang, hill climbing tetap relevan bukan hanya sebagai alat praktis, tetapi juga sebagai batu loncatan untuk memahami algoritma optimasi yang lebih kompleks. Sifatnya yang intuitif menjadikannya titik awal yang sangat baik bagi mereka yang memasuki bidang AI, sementara versatilitasnya memastikan penggunaan berkelanjutan dalam aplikasi dunia nyata. 

Baik Anda sedang mengoptimalkan bobot jaringan saraf, merencanakan lintasan robot, atau mengelola portofolio investasi, prinsip-prinsip hill climbing memberikan wawasan berharga tentang bagaimana komputer secara sistematis dapat menemukan solusi yang lebih baik untuk masalah yang menantang.

Jika Anda ingin mempelajari lebih lanjut tentang AI dan algoritma di baliknya, lihat sumber daya kami:

• Memahami Algoritma Pencarian A*
• Mengimplementasikan Algoritma Minimax untuk AI di Python
• Kasus Penggunaan dan Algoritma Machine Learning
• Panduan Algoritma Gradient Boosting
• Track Developing AI Applications
• Track AI Fundamentals