Algoritma Random Search: ASSRS (Adaptive Step Size Random Search)

Algoritma Random Search 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 memiliki beberapa variasi yaitu:

• FSSRS (Fixed Step Size Random Search)
• OSSRS (Optimum Step Size Random Search)
• ASSRS (Adaptive Step Size Random Search)
• ORSSRS (Optimized Relative Step Size Random Search)

Variasi yang dibahas kali ini adalah variasi ASSRS (Adaptive Step Size Random Search). Akan terdapat 2 radius, yaitu radius normal dan radius yang lebih besar. Solusi akan dihitung berdasarkan nilai acak dalam masing-masing radius. Radius normal akan menjadi radius yang lebih besar jika memenuhi syarat tertentu, dan radius yang lebih besar akan diperkecil apabila memenuhi syarat tertentu. Proses tersebut dilakukan sampai jumlah perulangan telah terpenuhi.

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 dimensi permasalahan dalam sebuah solusi
Diasumsikan dalam kasus ini, dimensi bernilai 2 karena ada 2 dimensi yang akan dicari solusinya yaitu x dan y

Const dimensi As Integer = 2

* 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

* Tentukan jumlah iterasi yang digunakan dalam perhitungan
Diasumsikan dalam kasus ini, jumlah iterasi adalah 10.000 kali

Const jumlahIterasi As Integer = 10000

* Tentukan radius tetap dalam setiap kali pergeseran posisi
Semakin rendah nilai radius tetap, maka semakin akurat hasil yang didapatkan
Diasumsikan dalam kasus ini, radius tetap adalah 1 persen dari rentang posisi yang diperbolehkan

Dim radius As Double = 0.01 * (maksPosisi - minPosisi)

Langkah-langkah penggunaan algoritma ini adalah

* Lakukan proses pencarian posisi terbaik
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 1 – 2)

Dim posisiTerbaik() As Double = ASSRS(dimensi, minPosisi, maksPosisi, jumlahIterasi, radius)

Memasuki perhitungan pada fungsi ASSRS

1. Tentukan 2 buah radius yang digunakan dalam perhitungan
Radius yang lebih kecil bernilai sama dengan parameter radius
Radius yang lebih besar dapat bernilai terserah, dalam kasus ini digunakan nilai 1.5 kali dari parameter radius

Dim radiusKecil As Double = radius
Dim radiusBesar As Double = radius * 1.5

2. Tentukan batas maksimal dari banyaknya perulangan yang tidak menghasilkan nilai yang lebih baik
Jika perulangan sudah melebihi nilai ini, nantinya kedua radius diatas akan diperkecil wilayahnya
Diasumsikan dalam kasus ini, batas maksimal tidak ada perubahan adalah 100 kali perulangan

Const maksTidakAdaPerubahan As Integer = 100

3. Tentukan batas selisih minimal antara nilai terbaik yang sedang dihitung dan nilai terbaik secara umum
Jika selisihnya lebih dari nilai ini, nantinya kedua radius diatas akan diperbesar wilayahnya
Diasumsikan dalam kasus ini, batas selisih minimal adalah 1

Const epsilonNilaiFungsi As Double = 1

4. Tentukan nilai acak sebanyak jumlah dimensi
Kemudian hitung nilai fungsi pada posisi tersebut
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

For i As Integer = 0 To dimensi - 1
	posisi(i) = (maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi
Next i
nilaiFungsi = hitungNilaiFungsi(posisi)

* Gunakan fungsi ini untuk menghitung nilai fungsi yang diinginkan
Fungsi yang diketahui adalah fungsi Himmelblau, 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

5. Catat posisi dan nilai fungsi tersebut sebagai posisi dan nilai terbaik sementara

Array.Copy(posisi, posisiTerbaik, dimensi)
nilaiFungsiTerbaik = nilaiFungsi

* Lakukan proses pencarian posisi terbaik

6. Lakukan proses perhitungan sebanyak jumlah iterasi (poin 6a – 6d)

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

6a. Lakukan perhitungan pada masing-masing dimensi untuk mendapatkan nilai acak sementara pada perulangan ini (poin 6a1 - 6a4)

For i As Integer = 0 To dimensi - 1
. . .

6a1. Hitung nilai minimal dan maksimal radius kecil pada posisi terbaik

Dim minRadiusKecil As Double = posisiTerbaik(i) - radiusKecil
Dim maksRadiusKecil As Double = posisiTerbaik(i) + radiusKecil

6a2. Jika nilai radius tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut

If minRadiusKecil < minPosisi Then minRadiusKecil = minPosisi
If maksRadiusKecil > maksPosisi Then maksRadiusKecil = maksPosisi

6a3. Tentukan nilai acak yang berada dalam rentang radius kecil posisi terbaik

posisiBaru(0)(i) = (maksRadiusKecil - minRadiusKecil) * rnd.NextDouble() + minRadiusKecil

6a4. Lakukan proses diatas (poin 6a1 - 6a3) pada radius besar

Dim minRadiusBesar As Double = posisiTerbaik(i) - radiusBesar
Dim maksradiusBesar As Double = posisiTerbaik(i) + radiusBesar

If minRadiusBesar < minPosisi Then minRadiusBesar = minPosisi
If maksradiusBesar > maksPosisi Then maksradiusBesar = maksPosisi

posisiBaru(1)(i) = (maksradiusBesar - minRadiusBesar) * rnd.NextDouble() + minRadiusBesar

6b. Hitung nilai fungsi pada posisi yang baru
Ada 2 nilai fungsi yang dihitung, yaitu untuk nilai acak dalam radius kecil dan besar

Dim nilaiFungsiBaru(1) As Double
For i As Integer = 0 To nilaiFungsiBaru.Length - 1
	nilaiFungsiBaru(i) = hitungNilaiFungsi(posisiBaru(i))
Next

6c. Tentukan nilai fungsi terbaik diantara 2 nilai fungsi tersebut

Dim nilaiFungsiBaruTerbaik As Double = Double.MinValue
Dim idxNilaiFungsiBaruTerbaik As Integer = -1
If nilaiFungsiBaru(0) > nilaiFungsiBaru(1) Then
	nilaiFungsiBaruTerbaik = nilaiFungsiBaru(0)
	idxNilaiFungsiBaruTerbaik = 0
Else
	nilaiFungsiBaruTerbaik = nilaiFungsiBaru(1)
	idxNilaiFungsiBaruTerbaik = 1
End If

6d. Jika nilai fungsi terbaik yang baru lebih baik dari nilai fungsi terbaik secara umum,
maka lakukan perhitungan berikut (poin 6d1 - 6d2)

If nilaiFungsiBaruTerbaik > nilaiFungsiTerbaik Then
	. . .

6d1. Jika nilai fungsi pada radius besar lebih baik dari nilai fungsi terbaik secara umum,
dan selisihnya lebih dari batas minimal selisih,
maka radius kecil akan diperbesar menjadi radius besar
dan lakukan hitung ulang untuk radius besar yang baru

If idxNilaiFungsiBaruTerbaik = 1 AndAlso nilaiFungsiBaruTerbaik - nilaiFungsiTerbaik > epsilonNilaiFungsi Then
	radiusKecil = radiusBesar
	radiusBesar = radiusKecil * 1.5
End If

6d2. Ambil posisi yang baru sebagai posisi terbaik

Array.Copy(posisiBaru(idxNilaiFungsiBaruTerbaik), posisiTerbaik, dimensi)
nilaiFungsiTerbaik = nilaiFungsiBaruTerbaik

6e. Jika diantara 2 nilai fungsi tidak ada yang lebih baik dari nilai fungsi terbaik secara umum,
maka hitung sudah berapa kali keadaan ini terjadi
Jika jumlah kejadian sudah melebihi batas maksimal tidak ada perubahan,
maka radius besar akan diperkecil menjadi radius kecil
dan lakukan hitung ulang untuk radius kecil yang baru

. . .
Else
	tidakAdaPerubahan += 1

	If tidakAdaPerubahan > maksTidakAdaPerubahan Then
		radiusBesar = radiusKecil
		radiusKecil = radiusKecil / 2
		tidakAdaPerubahan = 0
	End If

Hasil akhir adalah: (klik untuk perbesar gambar)

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.