Algoritma Moth Optimizer

Algoritma Moth 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 Moth dalam navigasi pada saat terbang. Moth akan selalu bergerak mengelilingi sumber cahaya yang menurutnya paling menarik / terang. Jika terdapat sumber cahaya lain yang lebih menarik, maka Moth akan mengganti arah terbangnya menuju sumber cahaya tersebut. Demikian seterusnya sampai Moth tidak lagi menemukan sumber cahaya yang lebih menarik dan tetap akan terbang mengelilingi sumber cahaya terbaik sampai akhir hidupnya.

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 jumlah Moth yang digunakan
Diasumsikan dalam kasus ini, jumlah Moth adalah 30 Moth

Const jumlahMoth 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 – 4)

Dim posisiTerbaik() As Double = MO(dimensi, minPosisi, maksPosisi, jumlahIterasi, jumlahMoth)

Memasuki perhitungan pada fungsi MO

* Inisialisasi para Moth yang digunakan sebanyak parameter jumlah Moth

1. Lakukan perulangan sebanyak jumlah Moth (poin 1a)

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

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

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

1b. Hitung nilai fungsi pada posisi tersebut

daftarMoth(i).nilaiFungsi = hitungNilaiFungsi(daftarMoth(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 Moth berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)

Array.Sort(daftarMoth)

3. Ambil posisi Moth pertama sebagai posisi terbaik sementara

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

* Lakukan proses pencarian posisi terbaik

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

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

4a. Lakukan perhitungan ini pada saat perulangan dijalankan pertama kalinya (poin 4a1)

If iterasi = 1 Then
. . .

4a1. Tentukan posisi cahaya yang ada
Diasumsikan nilai awal adalah sama dengan nilai pada masing-masing moth

For i As Integer = 0 To jumlahMoth - 1
	daftarCahaya(i) = daftarMoth(i).Clone
Next

4b. Lakukan perhitungan ini pada setiap kali perulangan selain perulangan pertama kali (poin 4b1 - 4b3)

. . .
Else
. . .

4b1. Lakukan penggabungan data antara posisi moth dan cahaya yang ada

Dim daftarGabungan(jumlahMoth * 2 - 1) As Moth
For i As Integer = 0 To daftarMoth.Length - 1
	daftarGabungan(i) = daftarMothSebelumnya(i).Clone
	daftarGabungan(jumlahMoth + i) = daftarCahaya(i).Clone
Next

4b2. Urutkan posisi gabungan berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)

Array.Sort(daftarGabungan)

4b3. Ambil posisi-posisi dengan nilai tertinggi sebagai posisi cahaya yang baru

For i As Integer = 0 To jumlahMoth - 1
	daftarCahaya(i) = daftarGabungan(i).Clone
Next

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

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

4d. Simpan posisi moth sebelum dilakukan perhitungan setelah ini

For i As Integer = 0 To daftarMoth.Length - 1
	daftarMothSebelumnya(i) = daftarMoth(i).Clone
Next

4e. Tentukan jumlah cahaya yang digunakan
Jumlah cahaya pada awalnya akan sama dengan parameter jumlah moth, dan akan berkurang seiring banyaknya iterasi yang telah dilakukan

Dim jumlahCahaya As Integer = jumlahMoth - iterasi * ((jumlahMoth - 1) / jumlahIterasi)

4f. Tentukan konstanta a, b, dan t untuk digunakan dalam perhitungan posisi moth yang baru
Konstanta a akan bernilai awal -1, dan akan berkurang seiring banyaknya iterasi yang telah dilakukan
Sedangkan konstanta b memiliki nilai 1

Dim a As Double = -1 + iterasi * ((-1) / jumlahIterasi)
Dim b As Integer = 1

4g. Lakukan perhitungan sebanyak dimensi pada masing-masing posisi moth (poin 4g1 - 4g5)

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

4g1. Hitung jarak absolut antara posisi moth dengan posisi cahaya terpilih

Dim jarakMenujuCahaya As Double = Math.Abs(daftarCahaya(i).posisi(j) - daftarMoth(i).posisi(j))

4g2. Hitung nilai acak t menggunakan konstanta a yang sudah ditentukan sebelumnya

Dim t As Double = (a - 1) * rnd.NextDouble + 1

4g3. Hitung posisi moth yang baru
* Dalam kasus adanya sebuah sumber cahaya, moth akan bergerak menuju sumber cahaya dengan cara mengelilingi cahaya tersebut
Jika terdapat beberapa sumber cahaya yang ada disekitar moth, maka arah terbang moth tersebut akan dipengaruhi oleh beberapa sumber cahaya tersebut

daftarMoth(i).posisi(j) = jarakMenujuCahaya * Math.Exp(b * t) * Math.Cos(t * 2 * Math.PI) + daftarCahaya(IIf(i <= jumlahCahaya, i, jumlahCahaya)).posisi(j)

4g4. Jika posisi moth tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut

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

4g5. Hitung nilai fungsi pada posisi moth yang baru

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

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

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

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

[sdm_download id="2418" fancy="0"]

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.