Algoritma AMO (Amoeba Method Optimization) / Nelder-Mead Method 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.
Amoeba Method Optimization, atau disebut juga dengan Nelder-Mead Method dan Simplex Optimization, adalah metode numerik umum yang digunakan untuk mencari nilai minimal atau maksimal dari sebuah fungsi obyektif pada ruang multi dimensi. Simplex Optimization bekerja dengan cara membentuk segitiga solusi yang dikatakan sebagai solusi terbaik – lainnya – terburuk. Pada setiap perhitungan, segitiga ini akan dihitung sehingga semakin mendekati solusi yang terbaik. Apabila segitiga ini digambar secara berurutan pada setiap perulangan, gerakan segitiga yang terjadi mirip dengan pola gerakan Amoeba.
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.
* Tentukan jumlah Amoeba yang digunakan dalam perhitungan
Jumlah amoeba harus minimal 3 buah, dengan batas maksimal tidak ada
Semakin banyak amoeba yang digunakan, semakin akurat nilai akhirnya, tetapi semakin lama proses perhitungannya
Diasumsikan dalam kasus ini, jumlah amoeba ada 5 buah
Dim jumlahAmoeba As Integer = 5
* 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
Dim minPosisi As Double = -2 Dim maksPosisi As Double = +2
* Tentukan jumlah iterasi yang digunakan dalam perhitungan
Diasumsikan dalam kasus ini, jumlah iterasi adalah 50 kali
Dim jumlahIterasi As Integer = 50
Langkah-langkah penggunaan algoritma ini adalah
1. Inisialisasi nilai awal untuk semua amoeba
Beri posisi acak untuk tiap-tiap amoeba
Kemudian hitung nilai fungsi untuk posisi acak tersebut
Dim amoeba As New Amoeba(jumlahAmoeba, dimensi, minPosisi, maksPosisi, jumlahIterasi)
* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class Amoeba untuk menampung semua data solusi yang diperoleh amoeba tersebut. Deklarasi Class Amoeba adalah sebagai berikut:
Public Class Amoeba
Public jumlahAmoeba As Integer
Public dimensi As Integer
Public daftarSolusi() As Solusi
Public minPosisi As Double
Public maksPosisi As Double
Public alpha As Double 'Koefisien untuk menghitung nilai reflected
Public beta As Double 'Koefisien untuk menghitung nilai contracted
Public gamma As Double 'Koefisien untuk menghitung nilai expanded
Public jumlahIterasi As Integer
Public Sub New(ByVal jumlahAmoeba As Integer, ByVal dimensi As Integer, ByVal minPosisi As Double, ByVal maksPosisi As Double, ByVal jumlahIterasi As Integer)
Me.jumlahAmoeba = jumlahAmoeba
Me.dimensi = dimensi
Me.minPosisi = minPosisi
Me.maksPosisi = maksPosisi
Me.alpha = 1.0 'didapatkan dari teori jurnal penelitian
Me.beta = 0.5 'didapatkan dari teori jurnal penelitian
Me.gamma = 2.0 'didapatkan dari teori jurnal penelitian
Me.jumlahIterasi = jumlahIterasi
Me.daftarSolusi = New Solusi(jumlahAmoeba - 1) {}
For i = 0 To daftarSolusi.Length - 1
daftarSolusi(i) = New Solusi(dimensi, minPosisi, maksPosisi)
Next i
'Perlu diingat bahwa, setelah proses pengurutan maka
'daftarSolusi(0) adalah merupakan posisi terbaik
'daftarSolusi(n-1) adalah merupakan posisi terburuk
Array.Sort(daftarSolusi)
End Sub
. . .
End Class
2. Lakukan proses pencarian posisi terbaik sebanyak jumlah iterasi
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 2a – 2e)
Dim solusi As Solusi = amoeba.ProsesPerhitungan
Sedikit pembahasan sebelum memasuki perhitungan utama
Dalam setiap kali perulangan, metode ini akan mencari nilai centroid, reflected, expanded, contracted
Untuk hal tersebut akan digunakan 4 fungsi tambahan untuk menghitung nilai-nilai tersebut
Penjelasan untuk masing-masing nilai tersebut adalah sebagai berikut:
Gunakan fungsi ini untuk mencari nilai centroid
Centroid adalah nilai rata-rata dari semua posisi kecual posisi terburuk
Public Function Centroid() As Solusi Dim c(dimensi - 1) As Double For i = 0 To jumlahAmoeba - 2 For j = 0 To dimensi - 1 c(j) += daftarSolusi(i).matriks(j) Next j Next i For j = 0 To dimensi - 1 c(j) = c(j) / (jumlahAmoeba - 1) If c(j) < minPosisi Then c(j) = minPosisi ElseIf c(j) > maksPosisi Then c(j) = maksPosisi End If Next j Dim s As New Solusi(c) 'Buat solusi baru pada posisi ini, dan hitung nilai fungsinya Return s End Function
Gunakan 3 fungsi dibawah ini untuk mencari nilai reflected, expanded, contracted
Ilustrasi singkat adalah sebagai berikut:
b----------x----------c----------y----------z
buruk-----------------centroid
Tarik garis lurus antara posisi terburuk dengan posisi centroid
Kemudian tambahkan garis terusan dari posisi centroid sepanjang jarak sebelumnnya
Posisi Reflected berada pada posisi y, dengan jarak (centroid-buruk) * koefisien alpha, dalam contoh ini bernilai 1.0
Posisi Expanded berada pada posisi z, dengan jarak (centroid-buruk) * koefisien gamma, dalam contoh ini bernilai 2.0
Posisi Contracted berada pada posisi x, dengan jarak (centroid-buruk) * koefisien beta, dalam contoh ini bernilai 0.5
Public Function Reflected(ByVal centroid As Solusi) As Solusi Dim r(dimensi - 1) As Double Dim terburuk() As Double = Me.daftarSolusi(jumlahAmoeba - 1).matriks For j = 0 To dimensi - 1 r(j) = ((1 + alpha) * centroid.matriks(j)) - (alpha * terburuk(j)) If r(j) < minPosisi Then r(j) = minPosisi ElseIf r(j) > maksPosisi Then r(j) = maksPosisi End If Next j Dim s As New Solusi(r) Return s End Function Public Function Expanded(ByVal reflected As Solusi, ByVal centroid As Solusi) As Solusi Dim e(dimensi - 1) As Double For j = 0 To dimensi - 1 e(j) = (gamma * reflected.matriks(j)) + ((1 - gamma) * centroid.matriks(j)) If e(j) < minPosisi Then e(j) = minPosisi ElseIf e(j) > maksPosisi Then e(j) = maksPosisi End If Next j Dim s As New Solusi(e) Return s End Function Public Function Contracted(ByVal centroid As Solusi) As Solusi Dim v(dimensi - 1) As Double Dim terburuk() As Double = Me.daftarSolusi(jumlahAmoeba - 1).matriks For j = 0 To dimensi - 1 v(j) = (beta * terburuk(j)) + ((1 - beta) * centroid.matriks(j)) If v(j) < minPosisi Then v(j) = minPosisi ElseIf v(j) > maksPosisi Then v(j) = maksPosisi End If Next j Dim s As New Solusi(v) Return s End Function
Kembali pada proses pencarian posisi terbaik oleh fungsi ProsesPerhitungan (poin 2) yang sudah disebutkan diatas
2a. Hitung nilai centroid, kemudian hitung nilai reflected
Dim centroid As Solusi = Me.Centroid Dim reflected As Solusi = Me.Reflected(centroid)
2b. Jika nilai reflected lebih baik dari nilai solusi terbaik, maka hitung nilai expanded
Jika nilai expanded ternyata lebih baik dari nilai reflected, maka update posisi terburuk dengan posisi expanded
Jika nilai expanded ternyata tidak lebih baik dari nilai reflected, maka update posisi terburuk dengan posisi reflected
If reflected.nilai > daftarSolusi(0).nilai Then
Dim expanded As Solusi = Me.Expanded(reflected, centroid)
If expanded.nilai > daftarSolusi(0).nilai Then
Console.WriteLine("Posisi expanded baru ditemukan: " & expanded.ToString)
UpdatePosisiTerburuk(expanded)
Else
Console.WriteLine("Posisi reflected baru ditemukan: " & reflected.ToString)
UpdatePosisiTerburuk(reflected)
End If
Continue Do
End If
2c. Tentukan apakah nilai reflected ternyata paling buruk (nilai terendah) dari semua nilai selain nilai posisi terburuk
Dim IsTerendahSelainTerburuk As Boolean = True For i = 0 To jumlahAmoeba - 2 If reflected.nilai > daftarSolusi(i).nilai Then 'Ternyata ada yang nilai nya lebih buruk dari nilai reflected IsTerendahSelainTerburuk = False Exit For End If Next i
2d. Jika benar nilai reflected ternyata paling buruk (nilai terendah) dari semua nilai selain nilai posisi terburuk, maka:
– Jika nilai reflected ternyata masih lebih baik dari nilai solusi terburuk, maka update posisi terburuk dengan posisi reflected
– Hitung nilai contracted
– Jika nilai contracted ternyata lebih baik dari nilai solusi terburuk, maka update posisi terburuk dengan posisi contracted
– Jika nilai contracted ternyata tidak lebih baik dari nilai solusi terburuk, maka solusi baru tidak ditemukan
Jika solusi baru tidak ditemukan maka lakukan proses perpindahan semua posisi kecual posisi terbaik
Posisi baru untuk masing-masing posisi adalah setengah jarak dari (posisi terbaik dan posisi tersebut), kemudian hitung nilai fungsi baru untuk masing-masing posisi
If IsTerendahSelainTerburuk Then
If reflected.nilai > daftarSolusi(jumlahAmoeba - 1).nilai Then
UpdatePosisiTerburuk(reflected)
End If
Dim contracted As Solusi = Me.Contracted(centroid)
If contracted.nilai > daftarSolusi(0).nilai Then
Console.WriteLine("Posisi contracted baru ditemukan: " & contracted.ToString)
End If
If contracted.nilai > daftarSolusi(jumlahAmoeba - 1).nilai Then
UpdatePosisiTerburuk(contracted)
Else
For i = 1 To jumlahAmoeba - 1
For j = 0 To dimensi - 1
daftarSolusi(i).matriks(j) = (daftarSolusi(i).matriks(j) + daftarSolusi(0).matriks(j)) / 2.0
daftarSolusi(i).nilai = hitungFungsi(daftarSolusi(i).matriks)
Next j
Next i
Array.Sort(daftarSolusi)
End If
Continue Do
End If
2e. Lakukan perhitungan poin 2a – 2d sebanyak jumlah iterasi
* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class Solusi untuk menampung semua data posisi beserta nilai fungsinya. Deklarasi Class Solusi adalah sebagai berikut:
Public Class Solusi
Implements IComparable(Of Solusi)
Public matriks() As Double 'Posisi
Public nilai As Double 'Nilai fungsi posisi tersebut
Private Shared random As New Random(1)
Public Sub New(ByVal dimensi As Integer, ByVal minPosisi As Double, ByVal maksPosisi As Double)
'Membuat matriks baru dengan nilai posisi acak
Me.matriks = New Double(dimensi - 1) {}
For i = 0 To dimensi - 1
Me.matriks(i) = (maksPosisi - minPosisi) * random.NextDouble + minPosisi
Next i
Me.nilai = hitungFungsi(Me.matriks)
End Sub
Public Sub New(ByVal matriks() As Double)
'Membuat matriks baru dengan nilai posisi tertentu
Me.matriks = New Double(matriks.Length - 1) {}
Array.Copy(matriks, Me.matriks, matriks.Length)
Me.nilai = hitungFungsi(Me.matriks)
End Sub
Public Function CompareTo(ByVal other As Solusi) As Integer Implements IComparable(Of Solusi).CompareTo
If Me.nilai < other.nilai Then
Return 1
ElseIf Me.nilai > other.nilai Then
Return -1
Else
Return 0
End If
End Function
Public Overrides Function ToString() As String
Dim s As String = "["
For i = 0 To Me.matriks.Length - 1
If matriks(i) >= 0.0 Then
s &= " "
End If
s &= " " & matriks(i).ToString("F2")
Next i
s &= "] nilai fungsi = " & Me.nilai.ToString("F4")
Return s
End Function
End Class
Hasil akhir adalah: (klik untuk perbesar gambar)
Dapat dilihat bahwa hasil akhir perhitungan tidak sama dengan x = -0.270845, and y = -0.923039, tetapi sangat mendekati posisi tersebut. Jika ingin mendapatkan jawaban yang lebih mirip lagi, maka silahkan lakukan penambahan jumlah iterasi, dengan resiko bahwa perhitungan yang dilakukan akan semakin lama.
Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:
[sdm_download id=”641″ 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.
