Algoritma Random Search: FSSRS (Fixed 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 FSSRS (Fixed Step Size Random Search). Pencarian acak dilakukan dari posisi terbaik yang memiliki nilai radius yang tetap. 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.
Grafik Himmelblau

Sedangkan Grafik fungsi Himmelblau untuk sebaran titik dengan rentang minimal -2 dan maksimal 2 adalah sebagai berikut.
Grafik Himmelblau -2sd2
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

* 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

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

* 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


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)

Memasuki perhitungan pada fungsi FSSRS

1. 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

* 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

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

* Lakukan proses pencarian posisi terbaik

3. Lakukan proses perhitungan sebanyak jumlah iterasi (poin 3a – 3c)

3a. Lakukan perhitungan pada masing-masing dimensi untuk mendapatkan nilai acak sementara pada perulangan ini (poin 3a1 – 3a3)

3a1. Hitung nilai minimal dan maksimal radius pada posisi terbaik

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

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

3b. Hitung nilai fungsi pada posisi yang baru

3c. Jika nilai fungsi pada poin sebelumnya lebih baik dari nilai fungsi secara umum,
maka ambil posisi yang baru sebagai posisi terbaik


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd88


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.

Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *