Algoritma GWO (Grey Wolf Optimizer)

Algoritma GWO (Grey Wolf Optimizer) 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 meniru tingkah laku dari spesies Grey Wolf dalam berburu. Proses utama Grey Wolf dalam berburu secara berkelompok dikonversi ke dalam bentuk matematika dan digunakan untuk memecahkan permasalahan optimasi.

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 100 kali

Const jumlahIterasi As Integer = 100

* Tentukan jumlah grey wolf yang digunakan
Diasumsikan dalam kasus ini, jumlah grey wolf adalah 30 grey wolf

Const jumlahWolf As Integer = 30

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 = GWO(dimensi, minPosisi, maksPosisi, jumlahIterasi, jumlahWolf)

Memasuki perhitungan pada fungsi GWO

* Inisialisasi para grey wolf yang digunakan sebanyak parameter jumlah wolf

1. Lakukan perulangan sebanyak jumlah wolf (poin 1a – 1b)

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

1a. Beri posisi acak pada masing-masing grey wolf sebanyak jumlah dimensi
Kemudian hitung nilai fungsi pada posisi tersebut
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

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

* 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

1b. Jika nilai posisi acak ini lebih baik dari nilai fungsi terbaik,
maka ambil posisi tersebut sebagai posisi terbaik sementara

If nilaiFungsi(i) > nilaiFungsiTerbaik Then
	nilaiFungsiTerbaik = nilaiFungsi(i)
	Array.Copy(daftarPosisi(i), PosisiTerbaik, dimensi)
	indeksPosisiTerbaik = i
End If

* Lakukan proses pencarian posisi terbaik

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

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

2a. Lakukan perhitungan pada masing-masing grey wolf (poin 2a1 - 2a6)

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

2a1. Lakukan perhitungan pada masing-masing posisi grey wolf tersebut
Jika posisi pada perhitungan sebelumnya ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut

For j As Integer = 0 To daftarPosisi(i).Length - 1
	If daftarPosisi(i)(j) < minPosisi Then
		daftarPosisi(i)(j) = minPosisi
	ElseIf daftarPosisi(i)(j) > maksPosisi Then
		daftarPosisi(i)(j) = maksPosisi
	End If
Next

2a2. Hitung nilai fungsi pada posisi tersebut

Dim nilaiFungsiBaru As Double = hitungNilaiFungsi(daftarPosisi(i))

2a3. Jika nilai fungsi yang baru lebih baik dari nilai alpha,
maka ambil posisi tersebut sebagai posisi alpha terbaik

If nilaiFungsiBaru > nilaiAlpha Then
	nilaiAlpha = nilaiFungsiBaru
	PosisiAlpha = daftarPosisi(i)
End If

2a4. Jika nilai fungsi yang baru kurang dari nilai alpha tetapi lebih baik dari nilai beta
maka ambil posisi tersebut sebagai posisi beta terbaik

If nilaiFungsiBaru < nilaiAlpha AndAlso nilaiFungsiBaru > nilaiBeta Then
	nilaiBeta = nilaiFungsiBaru
	PosisiBeta = daftarPosisi(i)
End If

2a5. Jika nilai fungsi yang baru kurang dari nilai alpha dan beta tetapi lebih baik dari nilai delta
maka ambil posisi tersebut sebagai posisi delta terbaik

If nilaiFungsiBaru < nilaiAlpha AndAlso nilaiFungsiBaru < nilaiBeta AndAlso nilaiFungsiBaru > nilaiDelta Then
	nilaiDelta = nilaiFungsiBaru
	PosisiDelta = daftarPosisi(i)
End If

2a6. Jika nilai alpha sementara ternyata lebih baik dari nilai fungsi secara umum,
maka ambil posisi alpha sebagai posisi terbaik

If nilaiAlpha > nilaiFungsiTerbaik Then
	Array.Copy(PosisiAlpha, PosisiTerbaik, dimensi)
	nilaiFungsiTerbaik = nilaiAlpha
End If

2b. Tentukan nilai a
Nilai a akan memiliki nilai awal 2 dan akan menurun secara bertahap menuju angka 0 sebanyak jumlah iterasi

Dim a As Double = 2 - 2 / jumlahIterasi

2c. Lakukan perhitungan pada pada masing-masing posisi grey wolf yang ada (poin 2c1 - 2c4)

For i As Integer = 0 To daftarPosisi.Length - 1
	For j As Integer = 0 To daftarPosisi(i).Length - 1
	. . .

2c1. Lakukan perhitungan untuk menghitung nilai X_Alpha (poin 2c1a - 2c1e)

2c1a. Tentukan 2 nilai acak untuk digunakan dalam perhitungan

Dim r1 As Double = rnd.NextDouble
Dim r2 As Double = rnd.NextDouble

2c1b. Hitung nilai A alpha dengan rumus A1=2*a*r1-a

Dim A_Alpha As Double = 2 * a * r1 - a

2c1c. Hitung nilai C alpha dengan rumus C1=2*r2

Dim C_Alpha As Double = 2 * r2

2c1d. Hitung nilai D alpha dengan rumus D_alpha=abs(C1*posisiAlpha(j)-daftarPosisi(i,j))

Dim D_Alpha As Double = Math.Abs(C_Alpha * PosisiAlpha(j) - daftarPosisi(i)(j))

2c1e. Hitung nilai X alpha dengan rumus X1=posisiAlpha(j)-A1*D_alpha;

Dim X_Alpha As Double = PosisiAlpha(j) - A_Alpha * D_Alpha

2c2. Lakukan perhitungan yang sama (poin 2c1) untuk menghitung nilai X beta

r1 = rnd.NextDouble
r2 = rnd.NextDouble

Dim A_Beta As Double = 2 * a * r1 - a
Dim C_Beta As Double = 2 * r2
Dim D_Beta As Double = Math.Abs(C_Beta * PosisiAlpha(j) - daftarPosisi(i)(j))
Dim X_Beta As Double = PosisiAlpha(j) - A_Beta * D_Beta

2c3. Lakukan perhitungan yang sama (poin 2c1) untuk menghitung nilai X delta

r1 = rnd.NextDouble
r2 = rnd.NextDouble

Dim A_Delta As Double = 2 * a * r1 - a
Dim C_Delta As Double = 2 * r2
Dim D_Delta As Double = Math.Abs(C_Delta * PosisiAlpha(j) - daftarPosisi(i)(j))
Dim X_Delta As Double = PosisiAlpha(j) - A_Delta * D_Delta

2c4. Hitung nilai posisi yang baru dengan rumus daftarPosisi(i,j)=(X1+X2+X3)/3

daftarPosisi(i)(j) = (X_Alpha + X_Beta + X_Delta) / 3

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. Ini adalah salah satu kelemahan algoritma ini, dan hasil akhir tetap tidak akan berubah meskipun jumlah iterasi telah ditambah. Untuk mendapatkan hasil yang lebih baik, lebih disarankan untuk menggunakan 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.