Algoritma IWO (Invasive Weed Optimization)

Entri ini telah di terbitkan di Algoritma Optimasi dan telah ditandai .net algoritma invasive weed optimization iwo vb visual basic on sebesar

Algoritma IWO (Invasive Weed 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 meniru tingkah laku weed atau rumput liar dalam berkembang biak. Dalam dunia pertanian, rumput liar merupakan salah satu tanaman hama yang perlu dibasmi karena dianggap mengganggu pertumbuhan dari tanaman yang sedang ditanam.



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 ukuran populasi minimal dan maksimal yang digunakan dalam perhitungan
Diasumsikan dalam kasus ini, ukuran populasi minimal adalah 10 dan ukuran populasi maksimal adalah 25

Const ukuranPopulasiMinimal As Integer = 10
Const ukuranPopulasiMaksimal As Integer = 25

* Tentukan jumlah bibit minimal dan maksimal dari masing-masing weed
Nantinya dalam setiap perulangan, nilai ini akan digunakan untuk menghitung jumlah bibit yang sebenarnya
Diasumsikan dalam kasus ini, jumlah bibit minimal adalah 0 dan jumlah bibit maksimal adalah 5

Const jumlahBibitMinimal As Integer = 0
Const jumlahBibitMaksimal As Integer = 5

* Tentukan koefisien eksponen, yang digunakan untuk menghitung nilai standar deviasi
Diasumsikan dalam kasus ini, nilai koefisien eksponen adalah 2

Const eksponen As Double = 2

* Tentukan nilai awal dan nilai akhir dari standar deviasi
Sama seperti parameter eksponen, nilai ini digunakan untuk menghitung nilai standar deviasi
Diasumsikan dalam kasus ini, nilai awal standar deviasi adalah 0.5 dan nilai akhir standar deviasi adalah 0.001

Const nilaiAwalStdDev As Double = 0.5
Const nilaiAkhirStdDev As Double = 0.001


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 = IWO(dimensi, minPosisi, maksPosisi, jumlahIterasi, ukuranPopulasiMinimal, ukuranPopulasiMaksimal, _
									jumlahBibitMinimal, jumlahBibitMaksimal, eksponen, nilaiAwalStdDev, nilaiAkhirStdDev)

Memasuki perhitungan pada fungsi IWO

* Inisialisasi para weed yang digunakan sebanyak ukuran populasi

1. Lakukan perulangan sebanyak ukuran populasi (poin 1a – 1c)

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

1a. Beri posisi acak pada masing-masing weed sebanyak jumlah dimensi

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

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

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

1c. Ambil posisi weed terbaik sebagai posisi terbaik sementara

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

* Lakukan proses pencarian posisi terbaik (poin 2)

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

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

2a. Hitung nilai sigma, yaitu nilai standar deviasi untuk perhitungan posisi bibit yang baru
Semakin banyak iterasi yang sudah dilakukan, maka nilai sigma akan semakin rendah,
sehingga posisi bibit yang baru tidak akan berada terlalu jauh dari posisi weed yang baru

Dim sigma As Double = ((jumlahIterasi - iterasi) / (jumlahIterasi - 1)) ^ eksponen * (nilaiAwalStdDev - nilaiAkhirStdDev) + nilaiAkhirStdDev

2b. Hitung nilai fungsi terburuk dan terbaik pada populasi ini
Karena tujuan kasus ini adalah untuk mencari nilai fungsi maksimal,
maka nilai fungsi terburuk adalah nilai fungsi terendah, dan nilai fungsi terbaik adalah nilai fungsi tertinggi

Dim nilaiFungsiPopulasiTerburuk As Double = Double.MaxValue
Dim nilaiFungsiPopulasiTerbaik As Double = Double.MinValue
For i As Integer = 0 To populasi.Length - 1
	If populasi(i).nilaiFungsi < nilaiFungsiPopulasiTerburuk Then nilaiFungsiPopulasiTerburuk = populasi(i).nilaiFungsi
	If populasi(i).nilaiFungsi > nilaiFungsiPopulasiTerbaik Then nilaiFungsiPopulasiTerbaik = populasi(i).nilaiFungsi
Next

* Memasuki proses perhitungan populasi dari masing-masing bibit yang dihasilkan oleh masing-masing weed (poin 2c)

2c. Lakukan perulangan sebanyak ukuran populasi (poin 2c1 - 2c3)

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

2c1. Hitung nilai rasio yang dihasilkan oleh masing-masing weed
Weed dengan nilai fungsi lebih baik akan menghasilkan bibit yang lebih banyak daripada weed yang nilai fungsinya kurang baik

Dim rasioBibit As Double = (populasi(i).nilaiFungsi - nilaiFungsiPopulasiTerburuk) / (nilaiFungsiPopulasiTerbaik - nilaiFungsiPopulasiTerburuk)

2c2. Hitung jumlah bibit yang dihasilkan weed tersebut dengan rumus:
jumlah bibit = bibit minimal + (bibit maksimal - bibit minimal) * rasio
Nilai yang digunakan adalah nilai pembulatan kebawah dari hasil perhitungan tersebut

Dim jumlahBibit = Math.Truncate(jumlahBibitMinimal + (jumlahBibitMaksimal - jumlahBibitMinimal) * rasioBibit)

2c3. Lakukan perhitungan pada masing-masing jumlah bibit yang ada (poin 2c3a - 2c3c)

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

2c3a. Lakukan perhitungan pada masing-masing dimensi posisi bibit
Hitung posisi bibit dengan rumus:
posisi bibit = posisi weed + sigma * distribusi normal acak
Jika posisi bibit ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut

For k As Integer = 0 To BibitBaru.posisi.Length - 1
	BibitBaru.posisi(k) = populasi(i).posisi(k) + sigma * HitungDistribusiNormalAcak(rnd)

	If BibitBaru.posisi(k) < minPosisi Then
		BibitBaru.posisi(k) = minPosisi
	ElseIf BibitBaru.posisi(k) > maksPosisi Then
		BibitBaru.posisi(k) = maksPosisi
	End If
Next

* Gunakan fungsi ini untuk menghitung distribusi normal acak
Sehingga nilai yang berada ditengah-tengah akan memiliki kemungkinan muncul yang lebih banyak,
dan nilai yang berada dibagian ujung akan memiliki kemungkinan muncul yang lebih sedikit

Public Function HitungDistribusiNormalAcak(ByVal rnd As Random, Optional ByVal mean As Double = 0, Optional ByVal stdDev As Double = 1) As Double
	Dim u1 As Double = rnd.NextDouble()
	Dim u2 As Double = rnd.NextDouble()
	Dim rndStdNormal As Double = Math.Sqrt(-2.0 * Math.Log(u1)) * Math.Sin(2.0 * Math.PI * u2) 'random normal(0,1)
	Dim rndNormal As Double = mean + stdDev * rndStdNormal                                    'random normal(mean, stdDev^2)
	Return rndNormal
End Function

2c3b. hitung nilai fungsi pada posisi tersebut

BibitBaru.nilaiFungsi = hitungNilaiFungsi(BibitBaru.posisi)

2c3c. Masukkan bibit tersebut ke dalam populasi bibit baru

populasiBibitBaru.Add(BibitBaru)

2d. Lakukan penggabungan populasi dengan populasi bibit baru

Dim populasiGabungan As New List(Of Weed)()
For i As Integer = 0 To populasi.Length - 1
	populasiGabungan.Add(populasi(i).Clone)
Next
For i As Integer = 0 To populasiBibitBaru.Count - 1
	populasiGabungan.Add(populasiBibitBaru(i).Clone)
Next

2e. Urutkan populasi yang baru berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)

populasiGabungan.Sort()

2f. Jika ukuran populasi gabungan tersebut ternyata lebih dari ukuran populasi maksimal,
maka lakukan pembuangan weed dengan nilai fungsi terburuk sampai ukuran populasi ini sudah tidak melebihi ukuran populasi maksimal

If populasiGabungan.Count > ukuranPopulasiMaksimal Then
	For i As Integer = populasiGabungan.Count - 1 To ukuranPopulasiMaksimal Step -1
		populasiGabungan.RemoveAt(i)
	Next
End If

Dim tmpPopulasi(populasiGabungan.Count - 1) As Weed
For i As Integer = 0 To populasiGabungan.Count - 1
	tmpPopulasi(i) = populasiGabungan(i).Clone
Next
populasi = tmpPopulasi

2g. Jika nilai fungsi weed terbaik ternyata lebih baik dari nilai fungsi secara umum,
maka ambil posisi terbaik weed tersebut sebagai posisi terbaik

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

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

Public Class Weed
    Implements IComparable(Of Weed)
    Implements ICloneable

    Public posisi() As Double
    Public nilaiFungsi As Double

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


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd101


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:

Download Now!



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 *