Algoritma MBO (Monarch Butterfly Optimization)

Algoritma MBO (Monarch Butterfly 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 spesies Monarch Butterfly pada saat bermigrasi ke tempat lain. Spesies ini bermigrasi dalam kelompok, dan biasanya seekor butterfly memiliki kemungkinan untuk berpindah menuju ke kelompok lainnya yang memiliki tujuan yang sama dengan kelompok sebelumnya. Sistem perpindahan ini yang akan digunakan 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 20

Const ukuranPopulasi As Integer = 20

* 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 jumlah maksimal step
Nantinya nilai ini akan digunakan dalam perhitungan skala pada saat proses penyesuaian
Diasumsikan dalam kasus ini, jumlah maksimal step adalah 1

Const maksStep As Double = 1.0

* Tentukan rasio partisi yang digunakan dalam perhitungan
Rasio partisi digunakan untuk membagi kelompok butterfly menjadi 2 kelompok
Diasumsikan dalam kasus ini, rasio partisi yang digunakan adalah 5/12

Const partisi As Double = 5 / 12

* Tentukan batas maksimal rasio penyesuaian butterfly
Nantinya, jika nilai acak lebih dari nilai ini, maka akan dilakukan penyesuaian posisi dari butterfly terpilih
Diasumsikan dalam kasus ini, rasio penyesuaian yang digunakan adalah sama dengan nilai rasio partisi, yaitu 5/12

Const rasioPenyesuaian As Double = 5 / 12

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 = MBO(dimensi, minPosisi, maksPosisi, jumlahIterasi, ukuranPopulasi, _
									jumlahPopulasiElit, maksStep, partisi, rasioPenyesuaian)

Memasuki perhitungan pada fungsi MBO

* Inisialisasi para butterfly yang digunakan sebanyak ukuran populasi

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

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

1a. Beri posisi acak pada masing-masing butterfly sebanyak jumlah dimensi
dan pastikan tidak ada posisi butterfly 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 butterfly pertama sebagai posisi terbaik sementara

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

4. Tentukan jumlah dari masing-masing kelompok butterfly 1 dan 2
Jumlahnya ditentukan dari parameter rasio partisi yang sudah ditentukan sebelumnya

Dim jumlahButterfly1 As Integer = Math.Round(partisi * ukuranPopulasi)
Dim jumlahButterfly2 As Integer = ukuranPopulasi - jumlahButterfly1

* Lakukan proses pencarian posisi terbaik (poin 5)

5. Lakukan proses perhitungan sebanyak jumlah iterasi (poin 5a – 5i)

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

5a. Simpan populasi butterfly 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

5b. Lakukan pembagian populasi ke dalam kelompok butterfly 1 dan 2
Perlu diingat bahwa rasio yang digunakan adalah sesuai dengan parameter rasio partisi
Karena populasi sudah diurutkan sesuai dengan nilai fungsi terbaik, maka butterfly pada kelompok 1 akan memiliki nilai yang lebih baik atau sama dengan kelompok 2

Dim populasiButterfly1(jumlahButterfly1 - 1) As MonarchButterfly
Dim populasiButterfly2(jumlahButterfly2 - 1) As MonarchButterfly
For i As Integer = 0 To ukuranPopulasi - 1
	If i < jumlahButterfly1 Then
		populasiButterfly1(i) = populasi(i).Clone
	Else
		populasiButterfly2(i - jumlahButterfly1) = populasi(i).Clone
	End If
Next

5c. Lakukan pembentukan populasi baru pada kelompok butterfly 1
Posisi pada masing-masing butterfly diambil dari posisi acak dari semua populasi butterfly
Pemilihan posisi tersebut tergantung dari nilai acak dan rasio partisi
Sehingga butterfly pada kelompok dengan rasio partisi yang lebih besar akan lebih memiliki kemungkinan untuk dipilih

Dim tmpPopulasiButterfly1(jumlahButterfly1 - 1) As MonarchButterfly
Dim PopulasiBaruButterfly1(jumlahButterfly1 - 1) As MonarchButterfly
For i As Integer = 0 To jumlahButterfly1 - 1
	tmpPopulasiButterfly1(i) = New MonarchButterfly(dimensi)

	For j As Integer = 0 To dimensi - 1
		If rnd.NextDouble <= partisi Then
			Dim idxPopulasiAcak As Integer = Math.Round((jumlahButterfly1 - 1) * rnd.NextDouble + 0.5)
			tmpPopulasiButterfly1(i).posisi(j) = populasiButterfly1(idxPopulasiAcak).posisi(j)
		Else
			Dim idxPopulasiAcak As Integer = Math.Round((jumlahButterfly2 - 1) * rnd.NextDouble + 0.5)
			tmpPopulasiButterfly1(i).posisi(j) = populasiButterfly2(idxPopulasiAcak).posisi(j)
		End If
	Next

	PopulasiBaruButterfly1(i) = tmpPopulasiButterfly1(i).Clone
Next

5d. Lakukan perulangan pada masing-masing butterfly pada kelompok 1
Jika posisi butterfly 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 jumlahButterfly1 - 1
	For j As Integer = 0 To dimensi - 1
		If PopulasiBaruButterfly1(i).posisi(j) < minPosisi Then
			PopulasiBaruButterfly1(i).posisi(j) = minPosisi
		ElseIf PopulasiBaruButterfly1(i).posisi(j) > maksPosisi Then
			PopulasiBaruButterfly1(i).posisi(j) = maksPosisi
		End If
	Next

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

* Selanjutnya adalah proses penyesuaian posisi butterfly pada kelompok 2
Menurut pengelompokan yang telah dilakukan sebelumnya,
butterfly pada kelompok 2 akan memiliki nilai yang tidak lebih baik daripada butterfly pada kelompok 1
Sehingga perlu dilakukan penyesuaian posisi pada masing-masing posisi butterfly tersebut

5e. Lakukan perulangan pada masing-masing butterfly pada kelompok 2 (poin 5e1 - 5e5)

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

5e1. Hitung nilai skala dengan rumus
skala = maksimal step / (iterasi^2)

Dim skala As Double = maksStep / (iterasi ^ 2)

5e2. Hitung jumlah ukuran step untuk digunakan dalam perhitungan jarak terbang butterfly
Nilai yang digunakan adalah nilai acak yang diambil dalam distribusi secara eksponensial
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Dim ukuranStep As Double = HitungDistribusiEksponensialAcak(2 * jumlahIterasi, rnd)

* Gunakan fungsi ini untuk menghitung distribusi eksponensial acak
Sehingga nilai yang lebih rendah akan memiliki kemungkinan muncul yang lebih banyak,
dan nilai yang lebih tinggi akan memiliki kemungkinan muncul yang lebih sedikit,
dengan rasio perbedaan kemungkinan tersebut akan terlihat secara eksponensial

Public Function HitungDistribusiEksponensialAcak(ByVal mu As Double, ByVal rnd As Random) As Double
	Dim minNilai As Double = 0
	Dim maksNilai As Double = mu * 10

	Dim hasil As Double = maksNilai
	Do
		Dim lambda As Double = 1.0
		Dim u As Double = rnd.NextDouble()
		Dim t As Double = -Math.Log(u) / lambda
		Dim increment As Double = (maksNilai - minNilai) / 6.0
		hasil = minNilai + (t * increment)
		If hasil < maksNilai Then Return hasil
	Loop Until hasil < maksNilai

	Return hasil
End Function

5e3. Hitung nilai deltaX sebagai jarak terbang butterfly
Metode yang digunakan adalah metode Levy
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Dim deltaX() As Double = HitungLevy(ukuranStep, dimensi, rnd)

* Gunakan fungsi ini untuk menghitung jarak terbang
Rumus yang digunakan adalah fungsi Levy, yang dihitung menggunakan distribusi Cauchy

Public Function HitungLevy(ByVal ukuranStep As Double, dimensi As Integer, ByVal rnd As Random) As Double()
	Dim hasil(dimensi - 1) As Double

	For i As Integer = 0 To dimensi - 1
		Dim jumlahFx As Double = 0

		For j As Integer = 0 To ukuranStep - 1
			Dim fx As Double = Math.Tan(Math.PI * rnd.NextDouble)
			jumlahFx += fx
		Next

		hasil(i) = jumlahFx
	Next

	Return hasil
End Function

5e4. Lakukan perhitungan pada masing-masing dimensi yang ada (poin 5e4a - 5e4b)

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

5e4a. Jika nilai acak lebih dari partisi
maka posisi yang digunakan adalah posisi terbaik pada dimensi tersebut

If rnd.NextDouble >= partisi Then
	tmpPopulasiButterfly2(i).posisi(j) = populasi(0).posisi(j)
	. . .

5e4b. Jika kondisi tersebut tidak terpenuhi, maka lakukan perhitungan berikut

. . .
Else
. . .

5e4b1. Tentukan indeks acak pada kelompok butterfly 2
Kemudian ambil posisi dimensi pada butterfly tersebut

Dim idxPopulasiAcak As Integer = Math.Round((jumlahButterfly2 - 1) * rnd.NextDouble + 0.5)
tmpPopulasiButterfly2(i).posisi(j) = populasiButterfly2(idxPopulasiAcak).posisi(j)

5e4b2. Jika nilai acak lebih dari rasio penyesuaian,
maka lakukan penyesuaian posisi dengan rumus:
posisi = posisi + skala * (deltaX - 0.5)

If rnd.NextDouble > rasioPenyesuaian Then
	tmpPopulasiButterfly2(i).posisi(j) += skala * (deltaX(j) - 0.5)
End If

5e5. Posisi butterfly yang baru adalah gabungan dari posisi dimensi yang telah didapatkan sebelumnya

PopulasiBaruButterfly2(i) = tmpPopulasiButterfly2(i).Clone

5f. Lakukan perulangan pada masing-masing butterfly pada kelompok 2
Jika posisi butterfly 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 jumlahButterfly2 - 1
	For j As Integer = 0 To dimensi - 1
		If PopulasiBaruButterfly2(i).posisi(j) < minPosisi Then
			PopulasiBaruButterfly2(i).posisi(j) = minPosisi
		ElseIf PopulasiBaruButterfly2(i).posisi(j) > maksPosisi Then
			PopulasiBaruButterfly2(i).posisi(j) = maksPosisi
		End If
	Next

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

5g. Lakukan penggabungan data antara kedua kelompok butterfly yang sudah diperbaharui
Kemudian urutkan populasi berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)

For i As Integer = 0 To populasi.Length - 1
	If i < jumlahButterfly1 Then
		populasi(i) = PopulasiBaruButterfly1(i).Clone
	Else
		populasi(i) = PopulasiBaruButterfly2(i - jumlahButterfly1).Clone
	End If
Next

Array.Sort(populasi)

5h. Masukkan butterfly elit untuk menggantikan butterfly dengan nilai terburuk (terendah)
Kemudian lakukan pengurutan populasi sekali lagi

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

Array.Sort(populasi)

5i. Jika nilai fungsi butterfly terbaik ternyata lebih baik dari nilai fungsi secara umum,
maka ambil posisi terbaik butterfly 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 MonarchButterfly untuk menampung semua data posisi dan nilai fungsinya. Deklarasi Class MonarchButterfly adalah sebagai berikut:

Public Class MonarchButterfly
    Implements IComparable(Of MonarchButterfly)
    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 MonarchButterflyLain As MonarchButterfly) As Integer Implements IComparable(Of MonarchButterfly).CompareTo
        If Me.nilaiFungsi > MonarchButterflyLain.nilaiFungsi Then
            Return -1
        ElseIf Me.nilaiFungsi < MonarchButterflyLain.nilaiFungsi Then
            Return 1
        Else
            Return 0
        End If
    End Function

    'Gunakan fungsi ini untuk melakukan clone pada masing-masing Monarch Butterfly
    Public Function Clone() As Object Implements ICloneable.Clone
        Dim hasilClone As MonarchButterfly = TryCast(Me.MemberwiseClone(), MonarchButterfly)
        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.