Algoritma Antlion Optimizer 2

Algoritma Antlion 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 Antlion dalam berburu mangsa. Dalam kasus ini akan digunakan semut sebagai mangsa dari Antlion. Antlion pada awalnya akan berada pada suatu tempat dan membuat jebakan lubang pasir. Semut yang berada pada tepian lubang pasir akan terpeleset jatuh ke dalam lubang dan menjadi mangsa dari Antlion. Kemudian Antlion akan berpindah tempat dan membuat jebakan untuk menangkap semut lain. Demikian seterusnya Antlion akan berpindah-pindah tempat sambil membuat jebakan menuju ke tempat semut yang memiliki nilai paling baik.

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

Const jumlahAntlion 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 – 2)

Dim posisiTerbaik() As Double = AO(dimensi, minPosisi, maksPosisi, jumlahIterasi, jumlahAntlion)

Memasuki perhitungan pada fungsi AO

* Inisialisasi para antlion yang digunakan sebanyak parameter jumlah antlion

1. Lakukan perulangan sebanyak jumlah antlion (poin 1a – 1b)

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

1a. Beri posisi acak pada masing-masing antlion sebanyak jumlah dimensi
Kemudian hitung nilai fungsi pada posisi tersebut
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

For k As Integer = 0 To dimensi - 1
	daftarAntlion(i).posisi(k) = (maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi
Next k
daftarAntlion(i).nilaiFungsi = hitungNilaiFungsi(daftarAntlion(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 antlion berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)

Array.Sort(daftarAntlion)

3. Ambil posisi antlion pertama sebagai posisi terbaik sementara

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

* Lakukan proses pencarian posisi terbaik

4. Lakukan proses perhitungan sebanyak jumlah iterasi (poin 4a – 4e)
Iterasi dimulai dari angka 2 karena iterasi pertama adalah inisialisasi nilai acak pada poin sebelumnya

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

4a. Lakukan perhitungan sebanyak jumlah semut yang ada
Perulangan ini digunakan untuk mengupdate posisi semut sebagai mangsa dari antlion (poin 4a1 - 4a4)

For i As Integer = 0 To daftarSemut.Length - 1
. . .

4a1. Tentukan antlion acak yang digunakan dalam perhitungan ini, dengan menggunakan teknik Seleksi Roulette (Roulette Wheel Selection)
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Dim idxRoulette As Integer = RouletteWheelSelection(daftarAntlion)
If idxRoulette = -1 Then idxRoulette = 1

* 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 Antlion

Public Function RouletteWheelSelection(ByVal daftarAntlion() As Antlion) As Integer
	Dim bobot(daftarAntlion.Length - 1) As Double
	Dim totalBobot As Double = 0
	For i As Integer = 0 To bobot.Length - 1
		totalBobot += 1 / daftarAntlion(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

4a2. Lakukan perhitungan untuk mendapatkan posisi acak disekitar antlion terpilih dan antlion terbaik
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 4a2a - 4a2g)

Dim posisiAcakDisektarAntlion() As Double = CariPosisiAcak(dimensi, minPosisi, maksPosisi, jumlahIterasi, daftarAntlion(idxRoulette).posisi, iterasi)
Dim posisiAcakDisektarAntlionTerbaik() As Double = CariPosisiAcak(dimensi, minPosisi, maksPosisi, jumlahIterasi, PosisiTerbaik, iterasi)

Memasuki perhitungan pada fungsi CariPosisiAcak

4a2a. Lakukan inisialisasi posisi minimal dan maksimal sebanyak jumlah dimensi

Dim minPos(posisi.Length - 1) As Double
Dim maksPos(posisi.Length - 1) As Double
For i As Integer = 0 To posisi.Length - 1
	minPos(i) = minPosisi
	maksPos(i) = maksPosisi
Next

4a2b. Lakukan perhitungan untuk mendapatkan nilai rasio
Nilai rasio tergantung dari banyaknya iterasi yang sudah dilakukan
Semakin mendekati iterasi akhir, maka nilai rasio akan semakin besar

Dim rasio As Double = 1
If iterasi > jumlahIterasi * 0.1 Then
	rasio = 1 + 100 * (iterasi / jumlahIterasi)
ElseIf iterasi > jumlahIterasi * 0.5 Then
	rasio = 1 + 1000 * (iterasi / jumlahIterasi)
ElseIf iterasi > jumlahIterasi * 0.75 Then
	rasio = 1 + 10000 * (iterasi / jumlahIterasi)
ElseIf iterasi > jumlahIterasi * 0.9 Then
	rasio = 1 + 100000 * (iterasi / jumlahIterasi)
ElseIf iterasi > jumlahIterasi * 0.95 Then
	rasio = 1 + 1000000 * (iterasi / jumlahIterasi)
End If

4a2c. Lakukan perhitungan untuk mendapatkan posisi minimal dan maksimal yang baru, sesuai dengan rasio yang sudah dihitung sebelumnya

For i As Integer = 0 To posisi.Length - 1
	minPos(i) /= rasio
	maksPos(i) /= rasio
Next

4a2d. Tentukan nilai acak antara 0 sampai dengan 1
Jika nilai acak tersebut dibawah 0.5, maka posisi minimal yang baru adalah posisi tersebut ditambah dengan posisi antlion terpilih
Jika nilai acak tersebut diatas 0.5, maka posisi minimal yang baru adalah posisi tersebut dikali -1 kemudian ditambah dengan posisi antlion terpilih

Dim r As Double = rnd.NextDouble
If r < 0.5 Then
	For i As Integer = 0 To posisi.Length - 1
		minPos(i) += posisi(i)
	Next
Else
	For i As Integer = 0 To posisi.Length - 1
		minPos(i) = -minPos(i) + posisi(i)
	Next
End If

4a2e. Tentukan nilai acak antara 0 sampai dengan 1
Jika nilai acak tersebut diatas 0.5, maka posisi maksimal yang baru adalah posisi tersebut ditambah dengan posisi antlion terpilih
Jika nilai acak tersebut dibawah 0.5, maka posisi maksimal yang baru adalah posisi tersebut dikali -1 kemudian ditambah dengan posisi antlion terpilih

r = rnd.NextDouble
If r >= 0.5 Then
	For i As Integer = 0 To posisi.Length - 1
		maksPos(i) += posisi(i)
	Next

Else
	For i As Integer = 0 To posisi.Length - 1
		maksPos(i) = -maksPos(i) + posisi(i)
	Next
End If

4a2f. Lakukan perhitungan pada masing-masing dimensi yang ada untuk menghitung posisi acak (poin 4a2f1 - 4a2f2)

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

4a2f1. Lakukan perhitungan sebanyak jumlah iterasi yang dilakukan (poin 4a2f1a - 4a2f1b)

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

4a2f1a. Tentukan nilai acak antara -1 atau 1,
Kemudian catat nilai tersebut dan total dengan nilai-nilai sebelumnya

r = rnd.NextDouble
Dim p As Integer = IIf(r > 0.5, 1, -1)
X(j + 1) = p
totalP += p

4a2f1b. Tentukan juga nilai paling minimal dan maksimal dari total nilai tersebut

If minX > totalP Then minX = totalP
If maksX < totalP Then maksX = totalP

4a2f2. Hitung nilai posisi acak sebagai jawaban akhir

posisiAcak(i) = (X(iterasi - 1) - minX) * (maksPos(i) - minPos(i)) / (maksX - minX) + minPos(i)

4a3. Lakukan perhitungan pada masing-masing dimensi yang ada (poin 4a3a - 4a3b)

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

4a3a. Posisi pada masing-masing dimensi adalah rata-rata dari posisi acak disekitar antlion terpilih dan antlion terbaik

daftarSemut(i).posisi(j) = (posisiAcakDisektarAntlion(j) + posisiAcakDisektarAntlionTerbaik(j)) / 2

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

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

4a4. Hitung nilai fungsi pada posisi tersebut

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

4b. Lakukan penggabungan antara posisi antlion dan semut yang ada

Dim daftarGabungan(jumlahAntlion * 2 - 1) As Antlion
For i As Integer = 0 To daftarAntlion.Length - 1
	daftarGabungan(i) = daftarAntlion(i).Clone
	daftarGabungan(jumlahAntlion + i) = daftarSemut(i).Clone
Next

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

Array.Sort(daftarGabungan)

4d. Jika nilai fungsi terbaik pada posisi gabungan ternyata lebih baik dari nilai fungsi secara umum,
maka ambil posisi terbaik pada posisi gabungan sebagai posisi terbaik

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

4e. Ambil posisi-posisi dengan nilai tertinggi sebagai posisi antlion yang baru
* Jika posisi semut ternyata lebih baik dari posisi antlion,
maka dapat disimpulkan bahwa antlion akan bergerak ke tempat semut untuk membuat jebakan penangkap semut
semut yang tertangkap akan mati, dan antlion akan menunggu semut lain, sampai nantinya akan ditemukan semut lain yang berada pada posisi yang lebih baik

For i As Integer = 0 To daftarAntlion.Length - 1
	daftarAntlion(i) = daftarGabungan(i).Clone
Next

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

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

    . . .
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.