Algoritma Hill Climbing: Contoh Perhitungan Optimasi Rute Lengkap

Hill Climbing adalah algoritma optimasi lokal yang memperbaiki solusi secara bertahap dengan berpindah dari solusi saat ini menuju solusi tetangga yang lebih baik. Proses terus dilakukan sampai tidak ditemukan lagi tetangga yang memberikan perbaikan.

Tutorial ini menggunakan contoh optimasi rute Traveling Salesman Problem (TSP) dengan lima kota. Solusi direpresentasikan sebagai urutan kunjungan kota, fungsi objektifnya adalah total jarak rute, dan neighborhood dibentuk menggunakan teknik 2-opt.

Pada contoh ini digunakan varian Steepest-Ascent Hill Climbing dalam konteks minimisasi, yaitu pada setiap iterasi seluruh neighbor diperiksa lalu dipilih neighbor dengan total jarak paling kecil.

---

Daftar Isi

• Pengertian Hill Climbing
• Konsep Dasar Hill Climbing
• Istilah Penting
• Jenis Hill Climbing
• Fungsi Objektif
• Neighborhood
• Kondisi Berhenti
• Masalah Local Optimum
• Contoh Kasus Optimasi Rute
  • #01 Menentukan Kota
  • #02 Menghitung Matriks Jarak
  • #03 Menentukan Solusi Awal
  • #04 Menghitung Nilai Solusi Awal
  • #05 Membentuk Neighbor Iterasi 1
  • #06 Memilih Solusi Terbaik Iterasi 1
  • #07 Membentuk Neighbor Iterasi 2
  • #08 Memilih Solusi Terbaik Iterasi 2
  • #09 Iterasi 3 dan Kondisi Berhenti
  • #10 Hasil Akhir
• Tabel Riwayat Iterasi
• Pseudocode Hill Climbing
• Simple vs Steepest-Ascent Hill Climbing
• Hill Climbing vs Simulated Annealing
• Hill Climbing vs Genetic Algorithm
• Kelebihan dan Kekurangan
• Kapan Hill Climbing Cocok Digunakan?
• Kesalahan Umum Implementasi
• Ringkasan
• FAQ Hill Climbing
• Referensi
• Source Code Hill Climbing

---

Pengertian Hill Climbing

Hill Climbing adalah metode pencarian lokal yang memulai proses dari sebuah solusi awal, kemudian mencoba solusi-solusi di sekitarnya.

Jika ditemukan solusi yang lebih baik:

solusi saat ini
↓
neighbor lebih baik
↓
neighbor menjadi solusi saat ini

Proses tersebut diulang sampai tidak ada neighbor yang lebih baik.

Walaupun istilahnya menggunakan kata climbing, algoritma ini dapat digunakan untuk:

• maksimisasi, atau
• minimisasi.

Pada maksimisasi:

nilai lebih besar = lebih baik

Pada minimisasi:

nilai lebih kecil = lebih baik

Contoh TSP pada artikel ini merupakan masalah minimisasi karena tujuan kita adalah mencari rute dengan total jarak sekecil mungkin.

---

Konsep Dasar Hill Climbing

Alur dasar:

Buat Solusi Awal
↓
Hitung Nilai Objektif
↓
Bentuk Neighbor
↓
Evaluasi Neighbor
↓
Ada Neighbor Lebih Baik?
├── Ya  → pindah ke neighbor terbaik
└── Tidak → berhenti

Hill Climbing tidak menyimpan seluruh ruang pencarian.

Algoritma hanya berfokus pada:

current solution
+
neighbor di sekitar current solution

Karena itu kebutuhan memorinya relatif kecil.

---

Istilah Penting

---

Jenis Hill Climbing

Beberapa varian yang umum:

Simple Hill Climbing

Neighbor diperiksa satu per satu.

Begitu ditemukan neighbor yang lebih baik:

langsung pindah

Tidak harus mencari neighbor terbaik dari seluruh neighborhood.

Steepest-Ascent Hill Climbing

Seluruh neighbor dievaluasi.

Kemudian dipilih:

neighbor terbaik

Pada masalah minimisasi:

Stochastic Hill Climbing

Pemilihan neighbor melibatkan unsur acak.

Neighbor yang lebih baik dapat dipilih secara probabilistik atau secara random dari kandidat yang memenuhi syarat.

Tutorial ini menggunakan Steepest-Ascent Hill Climbing karena seluruh neighbor dibandingkan pada setiap iterasi.

---

Fungsi Objektif

Fungsi objektif digunakan untuk mengukur kualitas solusi.

Pada TSP:

dengan perjalanan kembali ke kota awal:

Keterangan:

• \(R\) = sebuah rute,
• \(r_i\) = kota ke-\(i\),
• \(d(a,b)\) = jarak antara kota \(a\) dan \(b\).

Tujuannya:

Artinya semakin kecil total jarak, semakin baik solusi.

---

Neighborhood

Neighbor merupakan solusi yang diperoleh dari perubahan kecil terhadap solusi sekarang.

Pada contoh ini digunakan operator 2-opt.

Contoh rute:

A → B → D → E → C → A

Jika bagian:

D → E → C

dibalik, dapat diperoleh:

A → B → C → E → D → A

Setiap pembalikan segmen menghasilkan neighbor baru.

Kota A dipertahankan sebagai kota awal agar representasi rute lebih mudah dibandingkan.

---

Kondisi Berhenti

Hill Climbing berhenti jika:

tidak ada neighbor yang lebih baik

Untuk minimisasi:

Jika kondisi tersebut terjadi, current solution dianggap sebagai local optimum terhadap neighborhood yang digunakan.

Kondisi berhenti tambahan dapat berupa:

• maksimum iterasi,
• batas waktu,
• target objective tertentu,
• atau tidak terjadi perbaikan selama beberapa iterasi.

---

Masalah Local Optimum

Hill Climbing tidak menjamin selalu menemukan global optimum.

Algoritma dapat berhenti pada:

Local Optimum

Solusi lebih baik daripada seluruh neighbor terdekat, tetapi belum tentu terbaik secara global.

Plateau

Banyak neighbor mempunyai nilai objektif yang sama.

Ridge

Arah menuju solusi lebih baik tidak dapat dicapai dengan move sederhana yang digunakan.

Ilustrasi:

       Global optimum
            /\
           /  \
      /\  /    \
     /  \/      \
 Local optimum

Jika algoritma berada di local optimum, ia tidak akan berpindah ke solusi yang lebih buruk walaupun perpindahan tersebut mungkin diperlukan untuk mencapai global optimum.

Beberapa strategi yang dapat digunakan:

• random restart,
• stochastic move,
• simulated annealing,
• tabu search,
• atau mengubah definisi neighborhood.

---

Contoh Kasus Optimasi Rute

Sebuah kurir harus mengunjungi lima kota:

A
B
C
D
E

Kurir harus:

1. mulai dari A,
2. mengunjungi seluruh kota satu kali,
3. kembali ke A,
4. mencari total jarak yang minimum.

---

#01 Menentukan Kota

Koordinat:

Jarak Euclidean:

Contoh A ke B:

---

#02 Menghitung Matriks Jarak

Hasil pembulatan dua desimal:

Karena jarak menggunakan Euclidean Distance:

sehingga matriks bersifat simetris.

---

#03 Menentukan Solusi Awal

Gunakan rute awal:

A → B → D → E → C → A

Representasi:

[A, B, D, E, C]

Perjalanan kembali:

C → A

tetap dihitung pada fungsi objektif.

---

#04 Menghitung Nilai Solusi Awal

Rute:

A → B → D → E → C → A

Komponen jarak:

Total:

Jadi current solution:

A-B-D-E-C-A

dengan objective:

---

#05 Membentuk Neighbor Iterasi 1

Gunakan 2-opt dengan kota A tetap sebagai posisi awal.

Dari:

A-B-D-E-C-A

diperoleh enam neighbor.

Sebelum melihat hasil terbaik:

Current = 26.56

Neighbor dengan total jarak minimum adalah:

N5 = A-B-C-E-D-A

dengan:

Karena:

maka solusi diperbarui.

---

#06 Memilih Solusi Terbaik Iterasi 1

Current solution baru:

A → B → C → E → D → A

Total jarak:

Maka:

Perbaikan:

Persentase penurunan:

---

#07 Membentuk Neighbor Iterasi 2

Current:

A-B-C-E-D-A

Neighbor:

Neighbor terbaik:

A-B-C-D-E-A

dengan:

Karena:

maka solusi diperbarui lagi.

---

#08 Memilih Solusi Terbaik Iterasi 2

Rute:

A → B → C → D → E → A

Perhitungan:

Total:

Perbaikan dari iterasi sebelumnya:

---

#09 Iterasi 3 dan Kondisi Berhenti

Current solution:

A-B-C-D-E-A

Seluruh neighbor:

Nilai current:

Neighbor terbaik juga memiliki:

tetapi tidak lebih kecil.

Kondisi:

terpenuhi.

Karena tidak ada perbaikan, proses berhenti.

---

#10 Hasil Akhir

Rute hasil Hill Climbing:

A → B → C → D → E → A

Total jarak:

Rute awal:

Pengurangan jarak:

Persentase perbaikan:

Jadi Hill Climbing mengurangi total jarak sekitar:

23.31%

dibanding solusi awal pada contoh ini.

Untuk dataset kecil ini, enumerasi seluruh kemungkinan rute menunjukkan bahwa nilai 20.37 juga merupakan global optimum. Namun hal tersebut bukan jaminan umum Hill Climbing. Pada masalah lain algoritma dapat berhenti di local optimum.

---

Tabel Riwayat Iterasi

Alur:

26.56
  ↓
22.33
  ↓
20.37
  ↓
STOP

Nilai objective terus menurun karena masalah ini merupakan minimisasi.

---

Pseudocode Hill Climbing

input:
    initial_solution

current =
    initial_solution

current_value =
    objective(current)

while true:

    neighbors =
        generate_neighbors(current)

    best_neighbor =
        neighbor dengan
        objective terkecil

    best_value =
        objective(best_neighbor)

    if best_value
       < current_value:

        current =
            best_neighbor

        current_value =
            best_value

    else:

        break

return current, current_value

Untuk maksimisasi, operator pembanding diubah menjadi:

best_value > current_value

---

Simple vs Steepest-Ascent Hill Climbing

Pada contoh artikel, seluruh neighbor 2-opt dihitung sebelum dipilih satu solusi.

---

Hill Climbing vs Simulated Annealing

Simulated Annealing dapat menerima move yang lebih buruk dengan probabilitas tertentu sehingga mempunyai peluang keluar dari local optimum.

---

Hill Climbing vs Genetic Algorithm

Hill Climbing cocok ketika dibutuhkan algoritma optimasi sederhana dengan neighborhood yang mudah dibentuk.

---

Kelebihan dan Kekurangan

Kelebihan Hill Climbing

• Implementasi sederhana.
• Mudah dipahami.
• Tidak membutuhkan banyak memori.
• Dapat memperoleh solusi lebih baik dengan cepat.
• Fleksibel untuk berbagai jenis representasi solusi.
• Cocok sebagai local search.
• Dapat digabung dengan metode optimasi lain.

Kekurangan Hill Climbing

• Dapat terjebak local optimum.
• Tidak menjamin global optimum.
• Hasil bergantung pada solusi awal.
• Hasil bergantung pada definisi neighborhood.
• Dapat menghadapi plateau.
• Tidak menerima solusi sementara yang lebih buruk pada bentuk standar.
• Perlu strategi tambahan untuk eksplorasi ruang solusi lebih luas.

---

Kapan Hill Climbing Cocok Digunakan?

Hill Climbing cocok digunakan ketika:

• fungsi objektif dapat dihitung;
• solusi dapat dimodifikasi menjadi neighbor;
• ruang solusi terlalu besar untuk enumerasi penuh;
• solusi mendekati optimum sudah cukup;
• dibutuhkan algoritma sederhana;
• atau Hill Climbing digunakan sebagai local improvement.

Contoh penerapan:

• optimasi rute,
• penjadwalan,
• penempatan fasilitas,
• optimasi urutan pekerjaan,
• feature selection,
• puzzle,
• optimasi parameter diskrit,
• dan berbagai masalah combinatorial optimization.

---

Kesalahan Umum Implementasi

1. Tidak mendefinisikan objective dengan jelas

Untuk TSP:

lebih kecil = lebih baik

Jika implementasi justru memilih nilai terbesar, algoritma bergerak ke arah yang salah.

2. Lupa menghitung perjalanan kembali

Rute:

A-B-C-D-E

belum lengkap.

Harus dihitung:

E-A

3. Neighborhood terlalu sempit

Jika move terlalu terbatas, algoritma lebih mudah terjebak.

4. Menganggap hasil pasti global optimum

Hill Climbing adalah local search.

Hasil akhir hanya menjamin bahwa tidak ada neighbor yang lebih baik berdasarkan neighborhood yang digunakan.

5. Tidak menghentikan proses ketika tidak ada perbaikan

Jika solusi dengan nilai sama terus diterima tanpa mekanisme pencegah, algoritma dapat berpindah bolak-balik pada plateau.

6. Tidak menyimpan solusi terbaik

Pada implementasi yang lebih kompleks, simpan:

best_solution
best_value

agar hasil terbaik tidak hilang.

7. Menggunakan solusi awal yang sama terus-menerus

Jika masalah memiliki banyak local optimum, gunakan random restart untuk mencoba beberapa initial solution.

---

Ringkasan

Kasus:

Optimasi rute 5 kota

Solusi awal:

A-B-D-E-C-A

Total:

Iterasi pertama:

A-B-C-E-D-A

Total:

Iterasi kedua:

A-B-C-D-E-A

Total:

Iterasi berikutnya tidak menemukan neighbor yang lebih baik.

Hasil:

Perbaikan dari solusi awal:

Inti Hill Climbing:

Mulai dari satu solusi
↓
Cari neighbor
↓
Pilih yang lebih baik
↓
Ulangi
↓
Berhenti saat tidak ada perbaikan

---

FAQ Hill Climbing

Apa itu Hill Climbing?

Hill Climbing adalah algoritma local search yang memperbaiki solusi secara iteratif dengan berpindah ke neighbor yang lebih baik.

Apakah Hill Climbing termasuk algoritma optimasi?

Ya. Hill Climbing digunakan untuk mencari solusi yang lebih baik berdasarkan fungsi objektif.

Apakah Hill Climbing hanya untuk maksimisasi?

Tidak. Hill Climbing dapat digunakan untuk maksimisasi maupun minimisasi.

Apa itu neighbor?

Neighbor adalah solusi yang diperoleh melalui perubahan kecil dari solusi saat ini.

Apa itu neighborhood?

Neighborhood adalah seluruh kumpulan neighbor yang dapat dihasilkan dari current solution.

Apa itu 2-opt?

2-opt adalah operator yang membalik suatu segmen pada rute. Teknik ini banyak digunakan sebagai neighborhood untuk optimasi rute.

Apa itu local optimum?

Local optimum adalah solusi yang lebih baik dibanding seluruh neighbor-nya, tetapi belum tentu terbaik dari seluruh ruang solusi.

Apakah Hill Climbing menjamin global optimum?

Tidak.

Mengapa contoh ini mendapatkan global optimum?

Karena untuk dataset kecil pada contoh, hasil 20.37 kebetulan sama dengan nilai terbaik dari seluruh rute yang mungkin. Hal ini bukan sifat yang selalu terjadi.

Apa perbedaan Simple dan Steepest-Ascent Hill Climbing?

Simple Hill Climbing mengambil neighbor pertama yang lebih baik, sedangkan Steepest-Ascent mengevaluasi seluruh neighbor lalu memilih yang terbaik.

Bagaimana mengurangi risiko local optimum?

Beberapa cara:

• random restart,
• mengubah initial solution,
• memperluas neighborhood,
• stochastic hill climbing,
• simulated annealing,
• atau hybrid optimization.

Apakah Hill Climbing cocok untuk TSP?

Bisa sebagai local search. Untuk TSP besar, Hill Climbing biasanya digunakan untuk memperbaiki rute awal daripada menjamin solusi global optimum.

Apakah solusi awal memengaruhi hasil?

Ya. Solusi awal yang berbeda dapat membawa algoritma ke local optimum yang berbeda.

Apa fungsi objective function?

Objective function memberikan nilai numerik untuk membandingkan kualitas antar-solusi.

Kapan algoritma berhenti?

Umumnya ketika tidak ada neighbor yang menghasilkan perbaikan atau batas iterasi telah tercapai.

---

Referensi

1. Russell, S. J., & Norvig, P. (2021). Artificial Intelligence: A Modern Approach. Fourth Edition. Pearson.
2. Aarts, E., & Lenstra, J. K. (2003). Local Search in Combinatorial Optimization. Princeton University Press.
3. Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1985). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley.

---

Source Code Hill Climbing

Berikut source code yang menggunakan algoritma Hill Climbing pada RumahSourceCode.