Algoritma FAO (Fireworks 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 minimal.
Fireworks Algorithm adalah salah satu teknik optimasi yang digunakan untuk menyelesaikan permasalahan matematika. Algoritma ini dinamakan fireworks karena, pada saat digambarkan pada sebuah graifk 2 dimensi, gambar yang terjadi mirip dengan kembang api yang sedang meledak / menyala di langit.
Diasumsikan ada sebaran titik 3 dimensi, yaitu dimensi x, y, z
Masing-masing dimensi memiliki sebuah konstanta dan batas rentang titik yang dapat digunakan
Contoh data pada masing-masing dimensi adalah sebagai berikut
Dimensi | konstanta | batas minimal | batas maksimal |
---|---|---|---|
x | 3.2 | 10 | 50 |
y | 3 | 30 | 80 |
z | 2.5 | 50 | 150 |
Contoh data awal adalah sebagai berikut:
Dim data(2)() As Double data(0) = New Double() {3.2, 10, 50} data(1) = New Double() {3, 30, 80} data(2) = New Double() {2.5, 50, 150}
Nilai fungsi yang diketahui adalah dengan rumus f(x, y, z) = (kx * x^2) + (ky * y^2) + (kz * z^2)
Tentukan posisi dimana fungsi tersebut mengembalikan nilai minimal
Dengan batasan nilai bahwa x + y + z harus bernilai 210
Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan jumlah kembang api yang digunakan
Diasumsikan dalam kasus ini, akan digunakan kembang api sebanyak 5 buah
Const jumlahFirework As Integer = 5
* Tentukan dimensi permasalahan
Diasumsikan dalam kasus ini, dimensi bernilai 3 karena ada 3 dimensi yang akan dicari solusinya
Const dimensi As Integer = 3
* Tentukan jumlah perulangan dalam perhitungan
Nantinya setiap kembang api akan melakukan perulangan sebanyak ini untuk mencari posisi terbaik
Diasumsikan dalam kasus ini, jumlah perulangan adalah 1000 kali
Const maksEpoch As Integer = 1000
* Tentukan total posisi yang harus dicapai
Semua solusi yang ditemukan oleh kembang api harus berjumlah sebanyak variabel ini
Diasumsikan dalam kasus ini, total nilai yang harus dicapai adalah 210
Const totalPosisi As Integer = 210
Langkah-langkah penggunaan algoritma ini adalah
Lakukan proses pencarian posisi terbaik sebanyak jumlah perulangan
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 1 – 9)
Dim posisiTerbaik() As Integer = prosesPencarianPosisi(jumlahFirework, dimensi, maksEpoch, totalPosisi, data)
Memasuki fungsi prosesPencarianPosisi untuk melakukan pencarian posisi terbaik
1. Tentukan deklarasi variabel yang diperlukan dalam proses pencarian posisi terbaik
jumlahSparkStandar adalah Jumlah spark standar untuk masing-masing firework
jumlahGaussianSpark adalah Jumlah Gaussian spark yang dibuat pada masing-masing perulangan
a adalah konstanta untuk mengontrol jumlah spark minimal pada masing-masing firework
b adalah konstanta untuk mengontrol jumlah spark maksimal pada masing-masing firework
maksAmplitudo adalah maksimum amplitudo (luas area) pada masing-masing firework
Nilai-nilai untuk variabel tersebut adalah nilai-nilai yang direkomendasikan pada jurnal penelitian
Dim jumlahSparkStandar As Integer = jumlahFirework * 10 Const jumlahGaussianSpark As Integer = 5 Const a As Double = 0.04 Const b As Double = 0.8 Const maksAmplitudo As Integer = 40
2. Hitung rata-rata jumlah rentang nilai pada masing-masing dimensi
Digunakan untuk menghitung amplitudo pada setiap perulangan / epoch
Dim rata2Delta = 0.0 For i As Integer = 0 To dimensi - 1 rata2Delta += data(i)(2) - data(i)(1) Next rata2Delta /= dimensi
3. Inisialisasi firework sebanyak parameter jumlahFirework, dan inisialisasi posisi nya sebanyak parameter dimensi
daftarFirework(i) = New Info() daftarFirework(i).posisi = New Integer(dimensi - 1) {}
4. Untuk setiap firework, Beri nilai posisi acak pada setiap dimensi
Setiap dimensi memiliki batas minimal dan maksimal sendiri-sendiri, sesuai pada isian parameter data
jumlahPosisi = 0 For j = 0 To dimensi - 1 daftarFirework(i).posisi(j) = rnd.Next(data(j)(1), data(j)(2)) jumlahPosisi += daftarFirework(i).posisi(j) Next j
5. Perlu diingat bahwa jumlah posisi diatas belum tentu sesuai dengan parameter totalPosisi
Oleh karena itu, lakukan penyesuaian posisi agar jumlah posisi selalu bernilai sama dengan parameter totalPosisi
Dim selisih As Integer = totalPosisi - jumlahPosisi Dim idx As Integer = rnd.Next(dimensi) Dim posisiBaru As Integer = daftarFirework(i).posisi(idx) + selisih If posisiBaru < data(idx)(1) Then Continue Do If posisiBaru > data(idx)(2) Then Continue Do jumlahPosisi = jumlahPosisi - daftarFirework(i).posisi(idx) + posisiBaru daftarFirework(i).posisi(idx) = posisiBaru
6. Hitung nilai fungsi untuk firework pada posisi tersebut
Karena tujuan permasalahan adalah mencari nilai minimal, maka semakin rendah nilai fungsi akan semakin baik
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini
daftarFirework(i).nilaiFungsi = hitungNilaiFungsi(daftarFirework(i).posisi, data)
* Gunakan fungsi ini untuk menghitung nilai fungsi firework tersebut
Rumus yang digunakan adalah sesuai dengan rumus yang sudah ditentukan, yaitu
f(x, y, z) = (kx * x^2) + (ky * y^2) + (kz * z^2)
Private Function hitungNilaiFungsi(ByVal posisi() As Integer, ByVal data()() As Double) As Double Dim hasil As Double = 0.0 For i As Integer = 0 To posisi.Length - 1 hasil += data(i)(0) * posisi(i) * posisi(i) Next i Return hasil End Function
7. Lakukan pengecekan apakah firework ini berada pada posisi terbaik
If daftarFirework(i).nilaiFungsi < nilaiFungsiTerbaik Then nilaiFungsiTerbaik = daftarFirework(i).nilaiFungsi For k As Integer = 0 To dimensi - 1 posisiTerbaik(k) = daftarFirework(i).posisi(k) Next k indeksPosisiTerbaik = i End If
8. Inisialisasi daftar spark sejumlah parameter jumlahFirework
spark adalah percikan yang dimiliki oleh masing-masing firework
Masing-masing firework nantinya akan memiliki jumlah spark yang berbeda-beda tergantung dari nilai fungsi firework tersebut
Dim daftarSpark(jumlahFirework - 1) As List(Of Info) For i = 0 To jumlahFirework - 1 daftarSpark(i) = New List(Of Info)() Next i
9. Lakukan proses pencarian posisi terbaik sebanyak jumlah perulangan (poin 9a – 9f)
9a. Tentukan jumlah spark standar pada masing-masing firework
Firework yang memiliki nilai fungsi terendah (terbaik) akan memiliki jumlah spark lebih dari firework yang memiliki nilai fungsi tertinggi (terburuk)
9a1. Tentukan jumlah spark minimal dan maksimal
Dim minSpark As Integer = CInt(Fix(Math.Round(a * jumlahSparkStandar))) If minSpark < 1 Then minSpark = 1 End If Dim maksSpark As Integer = CInt(Fix(Math.Round(b * jumlahSparkStandar))) If maksSpark > jumlahSparkStandar - (jumlahFirework - 1) * minSpark Then maksSpark = jumlahSparkStandar - (jumlahFirework - 1) * minSpark End If
9a2. Tentukan yMax, yaitu nilai fungsi tertinggi (terburuk) pada semua firework
Dim yMax As Double = daftarFirework(0).nilaiFungsi For i = 1 To daftarFirework.Length - 1 If daftarFirework(i).nilaiFungsi > yMax Then yMax = daftarFirework(i).nilaiFungsi End If Next i
9a3. Tentukan jumlah dari masing-masing selisih yMax dan nilai fungsi pada semua firework
Dim jumlahSelisih As Double = 0.0 For i = 0 To jumlahFirework - 1 jumlahSelisih += yMax - daftarFirework(i).nilaiFungsi Next i
9a4. Tentukan jumlah spark standar pada masing-masing firework
Nilai 0.0000000001 digunakan agar tidak terjadi error pembagian dengan 0
Dim jumlahSpark(jumlahFirework - 1) As Integer For i = 0 To jumlahFirework - 1 jumlahSpark(i) = CInt(Fix(Math.Round(jumlahSparkStandar * (yMax - daftarFirework(i).nilaiFungsi + 0.0000000001) / (jumlahSelisih + 0.0000000001)))) If jumlahSpark(i) < minSpark Then jumlahSpark(i) = minSpark ElseIf jumlahSpark(i) > maksSpark Then jumlahSpark(i) = maksSpark End If Next i
9b. Tentukan amplitudo, yaitu luas area pada masing-masing firework
Nantinya spark akan menempati posisi-posisi di dalam luas area pada masing-masing firework
Firework yang memiliki nilai fungsi terendah (terbaik) akan memiliki amplitudo yang lebih rendah dari firework yang memiliki nilai fungsi tertinggi (terburuk)
Oleh sebab itu, firework yang baik akan memiliki jumlah spark yang lebih banyak dan luas area yang lebih sedikit, sehingga pencarian posisi dapat difokuskan pada area firework ini
9b1. Tentukan yMin, yaitu nilai fungsi terendah (terbaik) pada semua firework
Dim yMin As Double = daftarFirework(0).nilaiFungsi For i = 1 To daftarFirework.Length - 1 If daftarFirework(i).nilaiFungsi < yMin Then yMin = daftarFirework(i).nilaiFungsi End If Next i
9b2. Tentukan jumlah dari masing-masing selisih nilai fungsi dan yMin pada semua firework
jumlahSelisih = 0.0 For i = 0 To jumlahFirework - 1 jumlahSelisih += daftarFirework(i).nilaiFungsi - yMin Next i
9b3. Tentukan batas minimal amplitudo
Semakin lama perhitungan, maka nilai minimal amplitudo akan semakin rendah, sehingga pencarian akan semakin fokus mendekati posisi terbaik
Dim minAmplitudo As Double = 0 Dim ampInit As Double = (rata2Delta) * 0.02 Dim ampFinal As Double = (rata2Delta) * 0.001 minAmplitudo = ampInit - (ampInit - ampFinal) * epoch \ maksEpoch
9b4. Tentukan amplitudo pada masing-masing firework
Nilai 0.0000000001 digunakan agar tidak terjadi error pembagian dengan 0
Dim daftarAmplitudo(jumlahFirework - 1) As Double ' an amplitude for each firework For i = 0 To jumlahFirework - 1 daftarAmplitudo(i) = maksAmplitudo * (daftarFirework(i).nilaiFungsi - yMin + 0.0000000001) / (jumlahSelisih + 0.0000000001) If daftarAmplitudo(i) < minAmplitudo Then daftarAmplitudo(i) = minAmplitudo End If Next i
9c. Bersihkan isian variabel daftar spark, karena jumlah spark akan berubah pada tiap-tiap perulangan
For i = 0 To jumlahFirework - 1 daftarSpark(i).Clear() Next i
9d. Tentukan spark standar untuk masing-masing firework
9d1. Inisialisasi variabel spark sejumlah variabel jumlahSpark untuk firework tersebut
Kemudian beri nilai posisi spark tersebut sesuai dengan posisi firework yang sedang dihitung
Dim spark As New Info() spark.posisi = New Integer(dimensi - 1) {} For k = 0 To dimensi - 1 spark.posisi(k) = daftarFirework(i).posisi(k) Next k
9d2. Tentukan jumlah dimensi yang akan dipilih secara acak
Dim z As Integer = CInt(Fix(Math.Round(dimensi * rnd.NextDouble)))
9d3. Tentukan dimensi acak sejumlah variabel z
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini
Dim daftarDimensiAcak() As Integer = CariDimensiAcak(dimensi, z, epoch)
Gunakan fungsi ini untuk mencari dimensi acak sebanyak parameter z
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini
Private Function CariDimensiAcak(ByVal dimensi As Integer, ByVal z As Integer, ByVal seed As Integer) As Integer() Dim hasil(z - 1) As Integer Dim daftarIndeks(dimensi - 1) As Integer For i = 0 To dimensi - 1 daftarIndeks(i) = i Next i Dim rnd As New Random(seed) For i = 0 To daftarIndeks.Length - 1 Dim ri As Integer = rnd.Next(i, daftarIndeks.Length) Dim tmp As Integer = daftarIndeks(ri) daftarIndeks(ri) = daftarIndeks(i) daftarIndeks(i) = tmp Next i 'Ambil nilai hasil yaitu sejumlah z baris pertama pada daftar indeks For i = 0 To z - 1 hasil(i) = daftarIndeks(i) Next i Return hasil End Function
9d4. Untuk setiap dimensi acak yang terpilih
Tentukan nilai h yaitu jarak acak yang berada pada amplitudo firework tersebut
Kemudian pindahkan posisi spark sesuai dengan nilai h
Dim h As Double = amplitudoI * 2 * rnd.NextDouble - 1 Dim k As Integer = daftarDimensiAcak(ii) spark.posisi(k) += h
9d5. Perlu diingat bahwa apabila nilai posisi baru melebihi batas nilai minimal dan maksimal pada masing-masing dimensi,
maka kembalikan nilai posisi nya agar kembali dalam rentang nilai pada dimensi tersebut
If spark.posisi(k) < data(k)(1) OrElse spark.posisi(k) > data(k)(2) Then spark.posisi(k) = rnd.Next(data(k)(1), data(k)(2)) End If
9d6. Sama seperti perhitungan sebelumnya, jumlah posisi diatas belum tentu sesuai dengan parameter totalPosisi
Oleh karena itu, lakukan penyesuaian posisi agar jumlah posisi selalu bernilai sama dengan parameter totalPosisi
Dim jumlahPosisi As Integer = 0 For k As Integer = 0 To dimensi - 1 jumlahPosisi += spark.posisi(k) Next Do While jumlahPosisi <> totalPosisi Dim selisih As Integer = totalPosisi - jumlahPosisi Dim selisihPerDimensi(dimensi - 1) As Integer Dim idx As Integer = -1 Do While selisih <> 0 idx = rnd.Next(dimensi) If selisih > 0 Then If spark.posisi(idx) + selisihPerDimensi(idx) < data(idx)(2) Then selisihPerDimensi(idx) += 1 selisih -= 1 End If Else If spark.posisi(idx) + selisihPerDimensi(idx) > data(idx)(1) Then selisihPerDimensi(idx) -= 1 selisih += 1 End If End If Loop For k As Integer = 0 To dimensi - 1 Dim posisiBaru As Integer = spark.posisi(k) + selisihPerDimensi(k) If posisiBaru < data(k)(1) Then Continue Do If posisiBaru > data(k)(2) Then Continue Do Next For k As Integer = 0 To dimensi - 1 Dim posisiBaru As Integer = spark.posisi(k) + selisihPerDimensi(k) jumlahPosisi = jumlahPosisi - spark.posisi(k) + posisiBaru spark.posisi(k) = posisiBaru Next Loop
9d7. Hitung nilai fungsi untuk spark ini pada posisi yang baru
Kemudian tambahkan spark ini pada daftar spark
spark.nilaiFungsi = hitungNilaiFungsi(spark.posisi, data) daftarSpark(i).Add(spark)
9d8. Lakukan pengecekan apakah spark ini berada pada posisi terbaik
If spark.nilaiFungsi < nilaiFungsiTerbaik Then nilaiFungsiTerbaik = spark.nilaiFungsi For k = 0 To dimensi - 1 posisiTerbaik(k) = spark.posisi(k) Next k End If
9e. Tentukan Gaussian spark sejumlah variabel jumlahGaussianSpark
Gaussian spark adalah spark non standar, dimana posisi nya akan ditentukan sehingga berada diantara posisi terbaik sementara dan posisi firework acak
9e1. Inisialisasi variabel gaussianSpark sejumlah variabel jumlahGaussianSpark
Kemudian beri nilai posisi spark tersebut sesuai dengan posisi firework acak yang terpilih
Dim gaussianSpark As New Info gaussianSpark.posisi = New Integer(dimensi - 1) {} Dim i As Integer = rnd.Next(0, jumlahFirework) For k = 0 To dimensi - 1 gaussianSpark.posisi(k) = daftarFirework(i).posisi(k) Next k
9e2. Tentukan jumlah dimensi yang akan dipilih secara acak, dan tentukan dimensi acak sejumlah variabel tersebut
Dim z As Integer = CInt(Fix(Math.Round(dimensi * rnd.NextDouble))) Dim daftarDimensiAcak() As Integer = CariDimensiAcak(dimensi, z, epoch)
9e3. Tentukan nilai e yaitu konstanta yang digunakan untuk perhitungan jarak Gaussian spark
Dim u1 As Double = rnd.NextDouble Dim u2 As Double = rnd.NextDouble Dim left As Double = Math.Cos(2.0 * Math.PI * u1) Dim right As Double = Math.Sqrt(-2.0 * Math.Log(u2)) Dim e As Double = left * right
9e4. Untuk setiap dimensi acak yang terpilih
Pindahkan posisi Gaussian spark dengan cara menambahkan dengan (selisih posisi dengan posisi terbaik) dikali e
Dim k As Integer = daftarDimensiAcak(ii) gaussianSpark.posisi(k) = gaussianSpark.posisi(k) + (posisiTerbaik(k) - gaussianSpark.posisi(k)) * e
9e5. Sama seperti perhitungan sebelumnya, apabila nilai posisi baru melebihi batas nilai minimal dan maksimal pada masing-masing dimensi,
maka kembalikan nilai posisi nya agar kembali dalam rentang nilai pada dimensi tersebut
If gaussianSpark.posisi(k) < data(k)(1) OrElse gaussianSpark.posisi(k) > data(k)(2) Then gaussianSpark.posisi(k) = rnd.Next(data(k)(1), data(k)(2)) End If
9e6. Sama seperti perhitungan sebelumnya juga, jumlah posisi diatas belum tentu sesuai dengan parameter totalPosisi
Oleh karena itu, lakukan penyesuaian posisi agar jumlah posisi selalu bernilai sama dengan parameter totalPosisi
Dim jumlahPosisi As Integer = 0 For k As Integer = 0 To dimensi - 1 jumlahPosisi += gaussianSpark.posisi(k) Next Do While jumlahPosisi <> totalPosisi Dim selisih As Integer = totalPosisi - jumlahPosisi Dim selisihPerDimensi(dimensi - 1) As Integer Dim idx As Integer = -1 Do While selisih <> 0 idx = rnd.Next(dimensi) If selisih > 0 Then If gaussianSpark.posisi(idx) + selisihPerDimensi(idx) < data(idx)(2) Then selisihPerDimensi(idx) += 1 selisih -= 1 End If Else If gaussianSpark.posisi(idx) + selisihPerDimensi(idx) > data(idx)(1) Then selisihPerDimensi(idx) -= 1 selisih += 1 End If End If Loop For k As Integer = 0 To dimensi - 1 Dim posisiBaru As Integer = gaussianSpark.posisi(k) + selisihPerDimensi(k) If posisiBaru < data(k)(1) Then Continue Do If posisiBaru > data(k)(2) Then Continue Do Next For k As Integer = 0 To dimensi - 1 Dim posisiBaru As Integer = gaussianSpark.posisi(k) + selisihPerDimensi(k) jumlahPosisi = jumlahPosisi - gaussianSpark.posisi(k) + posisiBaru gaussianSpark.posisi(k) = posisiBaru Next Loop
9e7. Hitung nilai fungsi untuk gaussian spark ini pada posisi yang baru
Kemudian tambahkan gaussian spark ini pada daftar spark
gaussianSpark.nilaiFungsi = hitungNilaiFungsi(gaussianSpark.posisi, data) daftarSpark(i).Add(gaussianSpark)
9e8. Lakukan pengecekan apakah gaussian spark ini berada pada posisi terbaik
If gaussianSpark.nilaiFungsi < nilaiFungsiTerbaik Then nilaiFungsiTerbaik = gaussianSpark.nilaiFungsi For k = 0 To dimensi - 1 posisiTerbaik(k) = gaussianSpark.posisi(k) Next k End If
9f. Tentukan Firework untuk digunakan pada perhitungan berikutnya
Firework pertama yang dipakai adalah spark yang memiliki nilai fungsi terendah (terbaik)
Firework kedua yang dipakai adalah spark yang memiliki nilai fungsi tertinggi (terburuk)
Sisanya adalah menggunakan spark acak dari sisa daftar spark yang sudah ditentukan sebelumnya
9f1. Tentukan Firework pertama dan kedua, sesuai penjelasan diatas
Dim posisiSparkTerbaik(dimensi - 1) As Double Dim nilaiFungsiSparkTerbaik As Double = Double.MaxValue Dim posisiSparkTerburuk(dimensi - 1) As Double Dim nilaiFungsiSparkTerburuk As Double = Double.MinValue For i = 0 To jumlahFirework - 1 Dim j As Integer = 0 Do While j < daftarSpark(i).Count If daftarSpark(i)(j).nilaiFungsi < nilaiFungsiSparkTerbaik Then nilaiFungsiSparkTerbaik = daftarSpark(i)(j).nilaiFungsi For k = 0 To daftarSpark(i)(j).posisi.Length - 1 posisiSparkTerbaik(k) = daftarSpark(i)(j).posisi(k) Next k End If If daftarSpark(i)(j).nilaiFungsi > nilaiFungsiSparkTerburuk Then nilaiFungsiSparkTerburuk = daftarSpark(i)(j).nilaiFungsi For k = 0 To daftarSpark(i)(j).posisi.Length - 1 posisiSparkTerburuk(k) = daftarSpark(i)(j).posisi(k) Next k End If j += 1 Loop Next i 'Posisi Firework pertama adalah spark terbaik For k = 0 To dimensi - 1 daftarFirework(0).posisi(k) = posisiSparkTerbaik(k) Next k daftarFirework(0).nilaiFungsi = nilaiFungsiSparkTerbaik 'Posisi Firework kedua adalah spark terburuk For k = 0 To dimensi - 1 daftarFirework(1).posisi(k) = posisiSparkTerburuk(k) Next k daftarFirework(1).nilaiFungsi = nilaiFungsiSparkTerburuk
9f2. Tentukan Firework acak sisanya, yaitu dari posisi spark acak selain posisi yang sudah dipilih diatas
For i = 2 To jumlahFirework - 1 Dim row As Integer = rnd.Next(0, jumlahFirework) Dim cols As Integer = daftarSpark(row).Count Dim col As Integer = rnd.Next(0, cols) For k = 0 To dimensi - 1 daftarFirework(i).posisi(k) = daftarSpark(row)(col).posisi(k) Next k daftarFirework(i).nilaiFungsi = daftarSpark(row)(col).nilaiFungsi Next i
* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class Titik untuk menampung semua data posisi beserta nilai fungsinya. Deklarasi Class Titik adalah sebagai berikut:
Public Class Titik Public posisi() As Integer Public nilaiFungsi As Double 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.