Algoritma WDO (Wind Driven Optimization)


Algoritma WDO (Wind Driven Optimization) 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 terinspirasi dari pergerakan sekumpulan partikel udara yang disebut Air Parcel. Definisi Air parcel secara singkat adalah bagian tubuh imajiner dari udara yang memiliki massa, dan memiliki karakteristik yang membedakan antara 1 dengan yang lain. Air parcel ini akan bergerak menggunakan hukum gerak Newton, dimana hukum ini juga digunakan untuk menjelaskan pergerakan udara dalam ruang atmosfer bumi.



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

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

Const jumlahIterasi As Integer = 500

* Tentukan jumlah Air Parcel yang digunakan
Diasumsikan dalam kasus ini, jumlah Air Parcel adalah 20 Air Parcel

Const jumlahAirParcel As Integer = 20

* Tentukan koefisien alpha, koefisien RT, konstanta gravitasi dan konstanta coriolis yang digunakan dalam perhitungan
Masing-masing nilai ini nantinya akan digunakan untuk menghitung kecepatan air parcel dalam bergerak
Nilai yang digunakan adalah nilai yang direkomendasikan dalam jurnal penelitian

Const alpha As Double = 0.4
Const RT As Double = 3
Const g As Double = 0.2
Const c As Double = 0.4

* Tentukan batas kecepatan air parcel pada saat melakukan pergerakan
Diasumsikan dalam kasus ini, kecepatan maksimal air parcel adalah 0.3

Const batasKecepatan As Double = 0.3


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 = WDO(dimensi, minPosisi, maksPosisi, jumlahIterasi, jumlahAirParcel, _
									alpha, RT, g, c, batasKecepatan)

Memasuki perhitungan pada fungsi WDO

* Inisialisasi Air Parcel yang digunakan sebanyak parameter jumlah Air Parcel

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

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

1a. Beri posisi dan kecepatan acak pada masing-masing Air Parcel sebanyak jumlah dimensi

For k As Integer = 0 To dimensi - 1
	daftarAirParcel(i).posisi(k) = (maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi
	daftarAirParcel(i).kecepatan(k) = (batasKecepatan - -batasKecepatan) * rnd.NextDouble() + -batasKecepatan
Next k

1b. Hitung nilai fungsi pada posisi tersebut
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

daftarAirParcel(i).nilaiFungsi = hitungNilaiFungsi(daftarAirParcel(i).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

2. Urutkan Air Parcel berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)

Array.Sort(daftarAirParcel)

3. Ambil posisi Air Parcel pertama sebagai posisi terbaik sementara

Array.Copy(daftarAirParcel(0).posisi, PosisiTerbaik, dimensi)
nilaiFungsiTerbaik = daftarAirParcel(0).nilaiFungsi

* Lakukan proses pencarian posisi terbaik (poin 4)

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

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

4a. Lakukan perhitungan pada masing-masing air parcel

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

* Memasuki proses perhitungan kecepatan yang baru (poin 4a1)

4a1. Lakukan perhitungan pada masing-masing dimensi

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

4a1a. Tentukan kecepatan acak untuk digunakan dalam perhitungan selanjutnya

tmpKecepatan(j) = daftarAirParcel(i).kecepatan(rnd.Next(dimensi))

4a1b. Hitung kecepatan baru dengan rumus:
v baru = (1-a)*v - (g*pos) + abs(1-1/i)*((bestpos-pos)*RT) + (c*tmpV/i)

daftarAirParcel(i).kecepatan(j) = (1 - alpha) * daftarAirParcel(i).kecepatan(j) _
	- (g * daftarAirParcel(i).posisi(j)) _
	+ Math.Abs(1 - 1 / (i + 1)) * ((PosisiTerbaik(j) - daftarAirParcel(i).posisi(j)) * RT) _
	+ (c * tmpKecepatan(j) / (i + 1))

4a1c. Jika kecepatan tersebut ternyata diluar batas kecepatan yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut

If daftarAirParcel(i).kecepatan(j) < -batasKecepatan Then
	daftarAirParcel(i).kecepatan(j) = -batasKecepatan
ElseIf daftarAirParcel(i).kecepatan(j) > batasKecepatan Then
	daftarAirParcel(i).kecepatan(j) = batasKecepatan
End If

* Memasuki proses perhitungan posisi yang baru (poin 4a2)

4a2. Lakukan perhitungan pada masing-masing dimensi

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

4a2a. Hitung posisi baru dengan rumus:
pos = pos + v
daftarAirParcel(i).posisi(j) += daftarAirParcel(i).kecepatan(j)

daftarAirParcel(i).posisi(j) += daftarAirParcel(i).kecepatan(j)

4a2b. Jika posisi Air Parcel tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut

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

4a2c. Hitung nilai fungsi pada Air Parcel tersebut

daftarAirParcel(i).nilaiFungsi = hitungNilaiFungsi(daftarAirParcel(i).posisi)

4b. Urutkan daftar air parcel yang baru berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)

Array.Sort(daftarAirParcel)

4c. Jika nilai fungsi terbaik pada Air Parcel pertama ternyata lebih baik dari nilai fungsi secara umum,
maka ambil posisi terbaik Air Parcel tersebut sebagai posisi terbaik

If daftarAirParcel(0).nilaiFungsi > nilaiFungsiTerbaik Then
	Array.Copy(daftarAirParcel(0).posisi, PosisiTerbaik, dimensi)
	nilaiFungsiTerbaik = daftarAirParcel(0).nilaiFungsi
	. . .
End If

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class AirParcel untuk menampung semua data posisi, kecepatan, dan nilai fungsinya. Deklarasi Class AirParcel adalah sebagai berikut:

Public Class AirParcel
    Implements IComparable(Of AirParcel)

    Public posisi() As Double
    Public kecepatan() As Double
    Public nilaiFungsi As Double

    Public Sub New(ByVal dimensi As Integer)
        Me.posisi = New Double(dimensi - 1) {}
        Me.kecepatan = New Double(dimensi - 1) {}
        Me.nilaiFungsi = 0.0
    End Sub
	
	. . .
End Class


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd108


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 *