Algoritma EAO (Earthworm Algorithm Optimization)

Algoritma EAO (Earthworm Algorithm 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 dari hewan cacing tanah (Earthworm) dalam berkembang biak. Normalnya cara berkembang biak adalah dengan cara perkawinan antara 2 induk, tetapi ada spesies tertentu yang dapat berkembang biak tanpa perkawinan, yaitu induk yang menghasilkan anak yang mirip dengan induk tersebut. Kedua sistem berkembang biak ini akan diterapkan sebagai inti pemecahan dari 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 500 kali

Const jumlahIterasi As Integer = 500

* Tentukan ukuran populasi yang digunakan dalam perhitungan
Diasumsikan dalam kasus ini, ukuran populasi yang digunakan adalah 40

Const ukuranPopulasi As Integer = 40

* Tentukan jumlah populasi elit
Nantinya dalam setiap perulangan, butterfly elit akan dimasukkan untuk menggantikan butterfly dengan nilai terburuk
Diasumsikan dalam kasus ini, jumlah populasi elit adalah 2

Const jumlahPopulasiElit As Integer = 2

* Tentukan alpha, yaitu faktor kemiripan
Nantinya nilai ini akan digunakan dalam perhitungan reproduksi pertama dari earthworm
Diasumsikan dalam kasus ini, nilai alpha adalah 0.98

Const alpha As Double = 0.98

* Tentukan beta dan gamma, yaitu rasio proporsi populasi pertama yang digunakan untuk menghitung populasi sebenarnya
Nantinya dalam setiap perulangan, proporsi didapatkan dengan cara perkalian antara beta dan gamma
Diasumsikan dalam kasus ini, nilai beta adalah 1 dan nilai gamma adalah 0.9

Const beta As Double = 1
Const gamma As Double = 0.9

* Tentukan probabilitas crossover dan mutasi yang terjadi pada saat melakukan reproduksi
Diasumsikan dalam kasus ini, probabilitas crossover adalah 1 dan probabilitas mutasi adalah 0.3

Const probCrossover As Double = 1
Const probMutasi 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 – 5)

Dim posisiTerbaik() As Double = EAO(dimensi, minPosisi, maksPosisi, jumlahIterasi, ukuranPopulasi, _
									jumlahPopulasiElit, alpha, beta, gamma, probCrossover, probMutasi)

Memasuki perhitungan pada fungsi EAO

* Inisialisasi para earthworm yang digunakan sebanyak ukuran populasi

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

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

1a. Beri posisi acak pada masing-masing earthworm sebanyak jumlah dimensi
dan pastikan tidak ada posisi earthworm yang sama antara satu dengan yang lain

Dim isUnik As Boolean = False
Dim tmpPosisi(dimensi - 1) As Double

While Not isUnik
	isUnik = True

	For k As Integer = 0 To dimensi - 1
		tmpPosisi(k) = (maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi
	Next k

	For j As Integer = 0 To i - 1
		For jd As Integer = 0 To dimensi - 1
			If populasi(j).posisi(jd) = tmpPosisi(jd) Then
				isUnik = False
			Else
				isUnik = True
				Exit For
			End If
		Next
		If Not isUnik Then Exit For
	Next
End While

For k As Integer = 0 To dimensi - 1
	populasi(i).posisi(k) = tmpPosisi(k)
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

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

Array.Sort(populasi)

3. Ambil posisi earthworm pertama sebagai posisi terbaik sementara

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

* Lakukan proses pencarian posisi terbaik (poin 4)

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

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

4a. Simpan populasi earthworm elit untuk dimasukkan ke dalam populasi pada generasi berikutnya

Dim populasiElit(jumlahPopulasiElit - 1) As MonarchButterfly
For i As Integer = 0 To jumlahPopulasiElit - 1
	populasiElit(i) = populasi(i).Clone
Next

4b. Tentukan nilai beta yang sebenarnya, yaitu nilai beta dikalikan dengan gamma
Nilai beta ini akan semakin menurun seiring dengan banyaknya iterasi yang sudah dilakukan

beta *= gamma

4c. Simpan populasi ini sebagai populasi sebelum dilakukan perhitungan
Nantinya populasi ini akan digunakan dalam perhitungan mutasi
Kemudian hitung juga jumlah semua posisi pada masing-masing dimensi

Dim populasiSebelumnya(ukuranPopulasi - 1) As Earthworm
Dim totalPosisi(dimensi - 1) As Double
For i As Integer = 0 To ukuranPopulasi - 1
	populasiSebelumnya(i) = populasi(i).Clone

	For j As Integer = 0 To dimensi - 1
		totalPosisi(j) += populasiSebelumnya(i).posisi(j)
	Next
Next

4d. Lakukan perhitungan pada masing-masing populasi (poin 4d1 - 4d5)

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

* Berikut adalah perhitungan reproduksi jenis pertama, yaitu seekor earthworm akan menghasilkan earthworm lain yang mirip dengan dirinya (poin 4d1)

4d1. Lakukan perhitungan reproduksi jenis pertama
Tingkat kemiripan earthworm yang baru ditentukan dengan parameter alpha yang sudah ditentukan sebelumnya

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

* Berikut adalah perhitungan reproduksi jenis kedua, yaitu 2 ekor induk earthworm akan menghasilkan 2 anak earthworm (poin 4d2 - 4d4)

4d2. Tentukan nilai indeks acak dalam populasi

Dim idxPopulasiAcak As Integer = Math.Round((ukuranPopulasi - 1) * rnd.NextDouble + 0.5)

4d3. Jika indeks populasi yang sedang dihitung masih kurang dari jumlah populasi elit,
maka nilai posisi sementara diambil dari populasi dengan indeks acak yang sudah ditentukan sebelumnya

If i < jumlahPopulasiElit Then
	For j As Integer = 0 To dimensi - 1
		tmpPosisi(j) = populasi(idxPopulasiAcak).posisi(j)
	Next
	. . .

4d4. Jika kondisi tersebut tidak terpenuhi, maka lakukan perhitungan berikut (poin 4d4a - 4d4c)

. . .
Else
. . .

4d4a. Tentukan indeks acak kedua untuk dijadikan sebagai induk kedua
Oleh sebab itu, nilai indeks acak kedua tidak boleh sama dengan indeks acak pertama
teknik yang digunakan adalah teknik Seleksi Roulette (Roulette Wheel Selection)
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Dim idxPopulasiAcak2 As Integer = idxPopulasiAcak
While idxPopulasiAcak2 = idxPopulasiAcak
	idxPopulasiAcak2 = RouletteWheelSelection(populasi, rnd)
	If idxPopulasiAcak2 = -1 Then idxPopulasiAcak2 = 1
End While

* Gunakan fungsi ini untuk melakukan teknik Seleksi Roulette (Roulette Wheel Selection)
Nilai yang lebih baik akan memiliki kemungkinan yang lebih besar untuk terpilih
Dalam kasus ini, nilai yang dibandingkan adalah nilai fungsi dari masing-masing earthworm

Public Function RouletteWheelSelection(ByVal populasi() As Earthworm, ByVal rnd As Random) As Integer
	Dim bobot(populasi.Length - 1) As Double
	Dim totalBobot As Double = 0
	For i As Integer = 0 To bobot.Length - 1
		totalBobot += 1 / populasi(i).nilaiFungsi
		bobot(i) = totalBobot
	Next

	Dim probabilitasKumulatif As Double = rnd.NextDouble * totalBobot
	Dim idxTerpilih As Integer = -1
	For i As Integer = 0 To bobot.Length - 1
		If bobot(i) > probabilitasKumulatif Then
			idxTerpilih = i
			Exit For
		End If
	Next

	Return idxTerpilih
End Function

4d4b. Catat induk pertama dan kedua yang telah didapatkan dari posisi acak
Langkah ini hanya digunakan untuk mempermudah pembacaan skrip saja

Dim induk1 As Earthworm = populasi(idxPopulasiAcak).Clone
Dim induk2 As Earthworm = populasi(idxPopulasiAcak2).Clone

4d4c. Lakukan proses crossover antara posisi dari induk pertama dan kedua
Catat hasil crossover sebagai hasil posisi sementara yang ditemukan

For j As Integer = 0 To dimensi - 1
	Dim nilaiAcak As Double = rnd.NextDouble
	If probCrossover > nilaiAcak Then
		tmpPosisi(j) = IIf(nilaiAcak > 0.5, induk1.posisi(j), induk2.posisi(j))
	Else
		tmpPosisi(j) = IIf(nilaiAcak > 0.5, induk2.posisi(j), induk1.posisi(j))
	End If
Next

4d5. Hitung posisi sebenarnya dari masing-masing earthworm dengan rumus:
posisi baru = beta * populasi1 + (1 - beta) * posisi sementara
Kemudian hitung nilai fungsi pada posisi tersebut

For j As Integer = 0 To dimensi - 1
	populasi(i).posisi(j) = beta * populasiPertama(i).posisi(j) + (1 - beta) * tmpPosisi(j)
Next

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

4e. Lakukan pengurutan populasi berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)
Pengurutan ini dimaksudkan agar populasi elit tidak mengalami proses mutasi,
yang akan dilakukan pada proses dibawah ini

Array.Sort(populasi)

* Berikut adalah proses mutasi menggunakan metode mutasi Cauchy (poin 4f)

4f. Lakukan perhitungan pada semua populasi selain populasi elit (poin 4f1 - 4f2)

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

4f1. Tentukan nilai acak antar 0 sampai dengan 1
Jika nilai acak tersebut kurang dari probabilitas mutasi,
maka hitung bobot pada masing-masing dimensi dengan rumus:
bobot = total posisi dimensi / ukuran populasi

For j As Integer = 0 To dimensi - 1
	If probMutasi > rnd.NextDouble Then
		bobotCauchy(j) = totalPosisi(j) / ukuranPopulasi
	End If
Next

4f2. Hitung nilai posisi yang baru dengan rumus:
posisi baru = (bobot + posisi terbaik) / 2

For j As Integer = 0 To dimensi - 1
	populasi(i).posisi(j) = (bobotCauchy(j) + PosisiTerbaik(j)) / 2
Next

4g. Lakukan perulangan pada masing-masing earthworm
Jika posisi earthworm tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut
Kemudian hitung nilai fungsi pada posisi tersebut

For i As Integer = 0 To ukuranPopulasi - 1
	For j As Integer = 0 To dimensi - 1
		If populasi(i).posisi(j) < minPosisi Then
			populasi(i).posisi(j) = minPosisi
		ElseIf populasi(i).posisi(j) > maksPosisi Then
			populasi(i).posisi(j) = maksPosisi
		End If
	Next

	populasi(i).nilaiFungsi = hitungNilaiFungsi(populasi(i).posisi)
Next

4h. Jika terdapat earthworm pada posisi yang sama,
maka earthworm dengan indeks yang lebih tinggi akan diganti posisinya dengan posisi acak
Kemudian akan dilakukan pengecekan lagi agar tidak ada earthworm pada posisi yang sama

For i As Integer = 0 To jumlahPopulasiElit - 1
	populasi(populasi.Length - 1 - i) = populasiElit(i).Clone
Next

For i As Integer = 0 To ukuranPopulasi - 1
	Dim isUnik As Boolean = False

	While Not isUnik
		isUnik = True
		Dim idxTerakhir As Integer = -1

		For j As Integer = 0 To i - 1
			For jd As Integer = 0 To dimensi - 1
				If populasi(i).posisi(jd) = populasi(j).posisi(jd) Then
					isUnik = False
				Else
					isUnik = True
					Exit For
				End If
			Next

			If Not isUnik Then
				idxTerakhir = i
				Exit For
			End If
		Next

		If Not isUnik Then
			For jd As Integer = 0 To dimensi - 1
				populasi(idxTerakhir).posisi(jd) = (maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi
			Next
		End If
	End While
Next

4i. Lakukan pengurutan populasi lagi pada posisi yang baru

Array.Sort(populasi)

4j. Jika nilai fungsi earthworm terbaik ternyata lebih baik dari nilai fungsi secara umum,
maka ambil posisi terbaik earthworm tersebut sebagai posisi terbaik

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

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

Public Class Earthworm
    Implements IComparable(Of Earthworm)
    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

    'Gunakan fungsi ini untuk melakukan pengurutan dari nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)
    Public Function CompareTo(ByVal EarthwormLain As Earthworm) As Integer Implements IComparable(Of Earthworm).CompareTo
        If Me.nilaiFungsi > EarthwormLain.nilaiFungsi Then
            Return -1
        ElseIf Me.nilaiFungsi < EarthwormLain.nilaiFungsi Then
            Return 1
        Else
            Return 0
        End If
    End Function

    'Gunakan fungsi ini untuk melakukan clone pada masing-masing Earthworm
    Public Function Clone() As Object Implements ICloneable.Clone
        Dim hasilClone As Earthworm = TryCast(Me.MemberwiseClone(), Earthworm)
        hasilClone.posisi = DirectCast(posisi.Clone(), Double())
        Return hasilClone
    End Function
End Class

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.