Algoritma GSS (Golden Section 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 minimal.
Algoritma pencarian ini menggunakan teori Golden Ratio, dimana 2 buah garis / bidang (misalkan a dan b) dikatakan sebagai Golden Ratio apabila rasio ((a + b) / a) sama dengan (a / b). Teori ini akan digunakan dalam algoritma ini, dimana dalam setiap perulangan, akan selalu dicari titik-titik baru yang selalu memenuhi teori Golden Ratio sambil mencari nilai yang paling minimal.
Diasumsikan ada sebaran titik 2 dimensi antara -5 sampai dengan 5
Fungsi yang diketahui adalah fungsi Styblinski-Tang, dengan rumus f(xi) = (1 / 2) * E(xi ^ 4 – 16xi ^ 2 + 5xi)
Tentukan posisi dimana fungsi tersebut mengembalikan nilai minimal
Fungsi Styblinski-Tang adalah salah satu fungsi yang dapat digunakan untuk mengoptimasi suatu permasalahan. Fungsi ini dapat menerima inputan dimensi sebanyak mungkin. Nilai minimum fungsi ini adalah -39.16599 * jumlah dimensi, dan nilai tersebut diperoleh pada posisi -2.903534 pada setiap dimensi yang ada.
Grafik fungsi Styblinski-Tang dengan jumlah dimensi 2 adalah sebagai berikut.
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
Diasumsikan dalam kasus ini, posisi minimal adalah -5, dan posisi maksimal adalah +5
Const minPosisi As Double = -5 Const maksPosisi As Double = +5
Tentukan nilai golden ratio, yang dilambangkan dengan simbol phi
Penjelasan lebih lengkap tentang Golden Ratio dapat dilihat di Golden Ratio
Dim goldenRatio As Double = (1 + Math.Sqrt(5.0)) / 2
Tentukan nilai konjugasi golden ratio, yang dilambangkan dengan simbol Phi
Penjelasan lebih lengkap tentang konjugasi Golden Ratio dapat dilihat di Golden Ratio Conjugate
Dim Phi As Double = goldenRatio - 1
Tentukan epsilon, yaitu batas minimal selisih yang diperbolehkan pada masing-masing perulangan
Apabila perulangan sekarang menghasilkan nilai yang nyaris sama dengan nilai sebelumnya, maka perulangan akan dihentikan
Diasumsikan dalam kasus ini, epsilon adalah 0.000001
Const epsilon As Double = 0.000001
Langkah-langkah penggunaan algoritma ini adalah
1. Tentukan nilai a dan b sebagai nilai awal interval pencarian yang dilakukan
Karena sebaran dimensi berkisar antara -5 sampai dengan +5,
maka nilai awal a adalah nilai posisi minimal, yaitu -5, dan nilai awal b adalah nilai posisi maksimal, yaitu +5
Dim a As Double = minPosisi Dim b As Double = maksPosisi
2. Hitung nilai c dan d sebagai nilai interval yang baru yang akan digunakan pada masing-masing perulangan
Nilai c dihitung dengan rumus c = b – Phi * (b – a)
Nilai d dihitung dengan rumus d = a + Phi * (b – a)
Dim c As Double = b - Phi * (b - a) Dim d As Double = a + Phi * (b - a)
* Jika interval diatas diilustrasikan dalam gambar, maka hasilnya adalah
a----------c----------d----------b
3. Kemudian hitung nilai fungsi untuk nilai c dan d tersebut
Dim nilaiFungsiC As Double = HitungNilaiFungsi(New Double() {c, c})
Dim nilaiFungsiD As Double = HitungNilaiFungsi(New Double() {d, d})
* Gunakan fungsi ini untuk menghitung nilai fungsi dengan rumus:
f(xi) = (1 / 2) * E(xi ^ 4 – 16xi ^ 2 + 5xi)
Public Function HitungNilaiFungsi(x() As Double) As Double Dim hasil As Double = 0 For i As Integer = 0 To x.Length - 1 hasil += Math.Pow(x(i), 4) - 16 * Math.Pow(x(i), 2) + 5 * x(i) Next Return (1 / 2) * hasil End Function
4. Lakukan perhitungan sebanyak jumlah iterasi dan selama selisih perhitungan sekarang dan sebelumnya masih ada (poin 4a – 4c)
Dim iterasi As Integer = 0 While (iterasi < jumlahIterasi) AndAlso (Math.Abs(b - a) > epsilon) iterasi += 1 . . .
4a. Jika nilai fungsi c kurang dari nilai fungsi d, maka:
* Geser d ke b
* Geser c ke d
* Hitung nilai interval yang baru menggunakan rumus c diatas, yaitu c = b – Phi * (b – a)
ilustrasi untuk interval yang baru adalah:
a----------c----------d----------b -> a----------x----------c----------d
If nilaiFungsiC < nilaiFungsiD Then b = d d = c c = b - Phi * (b - a) . . .
4b. Jika nilai fungsi c lebih dari atau sama dengan nilai fungsi d, maka:
* Geser c ke a
* Geser d ke c
* Hitung nilai interval yang baru menggunakan rumus d diatas, yaitu d = a + Phi * (b - a)
ilustrasi untuk interval yang baru adalah:
a----------c----------d----------b -> c----------d----------x----------b
. . . Else a = c c = d d = a + Phi * (b - a) End If
4c. Hitung nilai fungsi yang baru untuk nilai interval c dan d
nilaiFungsiC = HitungNilaiFungsi(New Double() {c, c})
nilaiFungsiD = HitungNilaiFungsi(New Double() {d, d})
5. Jawaban akhir adalah nilai yang lebih rendah antara nilai c dan d
If nilaiFungsiC < nilaiFungsiD Then
Console.WriteLine(vbCrLf & "Posisi terbaik adalah: {0}, {0} dengan nilai fungsi {1}", c.ToString("F4"), nilaiFungsiC.ToString("F6"))
Else
Console.WriteLine(vbCrLf & "Posisi terbaik adalah: {0}, {0} dengan nilai fungsi {1}", d.ToString("F4"), nilaiFungsiD.ToString("F6"))
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.