Algoritma Hill Climbing 2

Algoritma Hill Climbing adalah salah satu algoritma optimasi yang dapat digunakan untuk pengambilan keputusan. Contoh yang dibahas kali ini adalah mengenai pencarian posisi dengan pengembalian nilai fungsi maksimal.
Algoritma ini cukup populer karena sangat mudah untuk dipahami dan diimplementasikan, tetapi dari segi akurasi masih kalah dibandingkan dengan Algoritma Tabu Search, atau yang jauh lebih kompleks lagi adalah Algoritma SA (Simulated Annealing). Sehingga untuk mendapatkan hasil yang lebih baik, lebih disarankan untuk menggunakan Simulated Annealing atau algoritma optimasi lainnya.

Diasumsikan ada sebaran titik 2 dimensi antara -2 sampai dengan 2
Fungsi yang diketahui adalah fungsi Himmelblau, dengan rumus f(x, y) = (x^2+y-11)^2 + (x+y^2-7)^2
Tentukan posisi dimana fungsi tersebut mengembalikan nilai maksimal

Fungsi Himmelblau adalah salah satu fungsi yang dapat digunakan untuk mengoptimasi suatu permasalahan. Fungsi ini memiliki sebuah nilai maksimum pada x = -0.270845, and y = -0.923039 dengan nilai fungsi sebesar f(x,y) = 181.617, dengan asumsi bahwa rentang minimal dan maksimal dari sebaran titik adalah -2 sampai dengan 2

Grafik fungsi Himmelblau yang normal, atau untuk sebaran titik tak terbatas adalah sebagai berikut.

Sedangkan Grafik fungsi Himmelblau untuk sebaran titik dengan rentang minimal -2 dan maksimal 2 adalah sebagai berikut.

Dapat dilihat bahwa pada gambar tersebut, didapatkan area dengan titik tertinggi (berwarna merah) berada pada area x = -0, and y = -1, dimana titik tersebut mengembalikan nilai fungsi tertinggi. Oleh sebab itu digunakan algoritma ini untuk mencari titik di area berwarna merah tersebut.

Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan jumlah iterasi yang digunakan dalam perhitungan
Diasumsikan dalam kasus ini, jumlah iterasi adalah 50 kali

Const jumlahIterasi As Integer = 50

* Tentukan posisi minimal dan maksimal dari fungsi yang akan dihitung
Jika tidak ada batasan posisi, tentu saja posisi yang mendekati tak terhingga akan terpilih karena akan mengembalikan nilai fungsi yang sangat besar
Diasumsikan dalam kasus ini, posisi minimal adalah -2, dan posisi maksimal adalah +2

Const minPosisi As Double = -2
Const maksPosisi As Double = +2

Langkah-langkah penggunaan algoritma ini adalah

* Lakukan perhitungan dibawah ini sebanyak jumlah iterasi (poin 1 – 3)

Dim iterasi As Integer = 0
While iterasi < jumlahIterasi
	iterasi += 1
	. . .

1. Tentukan posisi acak yang digunakan sebagai posisi awal mula

Dim posisi(1) As Double
For i As Integer = 0 To posisi.Length - 1
	posisi(i) = (maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi
Next

2. Hitung nilai fungsi dari posisi acak ini
Jika nilai fungsi ini lebih baik dari nilai fungsi terbaik,
maka ambil posisi acak ini sebagai posisi terbaik

Dim nilaiFungsi As Double = HitungNilaiFungsi(posisi(0), posisi(1))
If nilaiFungsi > nilaiFungsiTerbaik Then
	For i As Integer = 0 To posisiTerbaik.Length - 1
		posisiTerbaik(i) = posisi(i)
	Next

	nilaiFungsiTerbaik = nilaiFungsi
End If

* Gunakan fungsi ini untuk menghitung nilai fungsi dengan rumus:
f(x, y) = (x ^ 2 + y - 11) ^ 2 + (x + y ^ 2 - 7) ^ 2

Public Function HitungNilaiFungsi(x1 As Double, y As Double) As Double
	Dim hasil As Double = Math.Pow(x1 * x1 + y - 11, 2) + Math.Pow(x1 + y * y - 7, 2)
	Return hasil
End Function

3. Lakukan perhitungan pada masing-masing dimensi posisi (poin 3a - 3c)

For i As Integer = 0 To posisi.Length - 1
. . .

3a. Di setiap perulangan dimensi, kembalikan posisi menjadi posisi semula
dan beri nilai fungsi untuk posisi baru dengan nilai yang sangat kecil

For j As Integer = 0 To tmpPosisi.Length - 1
	posisi(j) = tmpPosisi(j)
Next
Dim nilaiFungsiBaru As Double = Double.MinValue

3b. Tentukan nilai acak yang digunakan sebagai penambah / pengurang sebuah dimensi dalam posisi

Dim nilaiAcak As Double = rnd.NextDouble() / 10

3c. Lakukan penambahan nilai sebuah dimensi dalam posisi secara terus menerus sampai nilai fungsi yang dihitung tidak lebih baik dari nilai fungsi terbaik (poin 3c1)

3c1. Lakukan perulangan selama nilai fungsi pada posisi baru kurang dari nilai fungsi terbaik (poin 3c1a - 3c1c)

Do
	. . .
Loop Until nilaiFungsiBaru < nilaiFungsiTerbaik

3c1a. Tambahkan nilai acak pada sebuah dimensi dalam posisi

posisi(i) += nilaiAcak

3c1b. Apabila nilai posisi baru melebihi batas nilai minimal dan maksimal posisi,
maka kembalikan nilai posisi nya agar kembali dalam rentang nilai posisi yang diperbolehkan

If posisi(i) < minPosisi Then
	posisi(i) = minPosisi
ElseIf posisi(i) > maksPosisi Then
	posisi(i) = maksPosisi
End If

3c1c. Hitung nilai fungsi untuk posisi yang baru
Jika nilai fungsi ini lebih baik dari nilai fungsi terbaik,
maka ambil posisi baru ini sebagai posisi terbaik

nilaiFungsiBaru = HitungNilaiFungsi(posisi(0), posisi(1))
If nilaiFungsiBaru > nilaiFungsiTerbaik Then
	For j As Integer = 0 To posisiTerbaik.Length - 1
		posisiTerbaik(j) = posisi(j)
	Next

	nilaiFungsiTerbaik = nilaiFungsiBaru
End If

Hasil akhir adalah: (klik untuk perbesar gambar)

Dapat dilihat bahwa hasil akhir perhitungan tidak sama dengan x = -0.270845, and y = -0.923039, tetapi hanya mendekati posisi tersebut. Disinilah kelemahan algoritma ini seperti yang sudah dijelaskan sebelumnya. Untuk mendapatkan hasil yang lebih baik, lebih disarankan untuk menggunakan Simulated Annealing atau algoritma optimasi lainnya.

Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:

Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.