Algoritma LSA (Lightning Search Algorithm) 2

Algoritma LSA (Lightning Search Algorithm) 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 terinspirasi dari fenomena petir pada alam. Algoritma ini menggunakan konsep partikel proyektil yang bergerak sangat cepat, dan juga bagian dari Algoritma Gradient Descent dalam menentukan arah plus minus dari proyektil tersebut.

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

Const jumlahCrow As Integer = 15

* Tentukan jumlah channel yang digunakan
Nantinya channel akan digunakan dalam proses eliminasi individu yang paling buruk
Diasumsikan dalam kasus ini, jumlah channel adalah 10 channel

Const jumlahChannel As Integer = 10

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 = LSA(dimensi, minPosisi, maksPosisi, jumlahIterasi, jumlahIndividu, _
									jumlahChannel)

Memasuki perhitungan pada fungsi LSA

* Inisialisasi individu yang digunakan sebanyak parameter jumlah individu

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

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

1a. Beri posisi acak pada masing-masing individu 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
	daftarIndividu(i).posisi(k) = (maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi
Next k
daftarIndividu(i).nilaiFungsi = hitungNilaiFungsi(daftarIndividu(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

1b. Ambil posisi individu terbaik sebagai posisi terbaik sementara

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

* Lakukan proses pencarian posisi terbaik (poin 2)

2. Inisialisasi variabel arah yang digunakan dalam perhitungan
Beri nilai acak antara nilai 1, -1, atau 0

Dim arah(dimensi - 1) As Integer
For i As Integer = 0 To dimensi - 1
	Dim r As Double = rnd.NextDouble

	If r > 0.5 Then
		arah(i) = 1
	ElseIf r < 0.5 Then
		arah(i) = -1
	Else
		arah(i) = 0
	End If
Next

3. Lakukan proses perhitungan sebanyak jumlah iterasi (poin 3a - 3g)

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

3a. Simpan nilai individu yang digunakan dalam perhitungan

Dim daftarIndividuBaru() As Individu = daftarIndividu.Clone

3b. Tambahkan nilai 1 pada nilai channel
Jika nilai channel sudah sama dengan jumlah channel,
maka lakukan eliminasi individu dengan nilai fungsi terendah, dan ganti dengan individu dengan nilai fungsi tertinggi

channel += 1
If channel >= jumlahChannel Then
	Array.Sort(daftarIndividuBaru)
	daftarIndividuBaru(daftarIndividuBaru.Length - 1) = daftarIndividuBaru(0).Clone
	channel = 0
End If

3c. Lakukan pencarian nilai fungsi tertinggi dan terendah pada daftar individu

Array.Sort(daftarIndividuBaru)
Dim nilaiFungsiTertinggi As Double = daftarIndividuBaru(0).nilaiFungsi
Dim nilaiFungsiTerendah As Double = daftarIndividuBaru(daftarIndividuBaru.Length - 1).nilaiFungsi

3d. Lakukan perhitungan pada masing-masing dimensi (poin 3d1 - 3d2)

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

3d1. Hitung nilai posisi sementara dengan rumus
pos = pos + arah(i) * 0.005 * (maksPos - minPos)
Kemudian hitung nilai fungsi pada posisi ini

Dim tmpIndividu As Individu = daftarIndividuBaru(0).Clone
tmpIndividu.posisi(i) += arah(i) * 0.005 * (maksPosisi - minPosisi)
tmpIndividu.nilaiFungsi = hitungNilaiFungsi(tmpIndividu.posisi)

3d2. Jika nilai fungsi pada posisi sementara ini lebih tinggi dari nilai fungsi tertinggi,
maka nilai arah adalah positif (+1),
selain itu, maka nilai arah adalah negatif (-1)

If tmpIndividu.nilaiFungsi > nilaiFungsiTertinggi Then
	arah(i) = arah(i)
Else
	arah(i) = -arah(i)
End If

3e. Hitung nilai energi yang dihasilkan pada perulangan ini
energi = 2.05 - 2 * exp(-5 * (T-t) / T)

Dim energi As Double = 2.05 - 2 * Math.Exp(-5 * (jumlahIterasi - iterasi) / jumlahIterasi)

3f. Lakukan perhitungan pada masing-masing individu (poin 3f1 - 3f5)

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

3f1. Lakukan perhitungan pada masing-masing dimensi
Hitung jarak dengan rumus
dist = pos - pos terbaik

Dim jarak(dimensi - 1) As Double
For j As Integer = 0 To dimensi - 1
	jarak(j) = daftarIndividu(i).posisi(j) - daftarIndividuBaru(0).posisi(j)
Next

3f2. Lakukan perhitungan pada masing-masing dimensi (poin 3f2a - 3f2d)

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

3f2a. Tentukan apakah posisi individu pada masing-masing dimensi adalah sama dengan posisi individu terbaik

Dim isSama As Boolean = True
For k As Integer = 0 To dimensi - 1
	If daftarIndividu(i).posisi(k) <> daftarIndividuBaru(0).posisi(k) Then
		isSama = False
		Exit For
	End If
Next

3f2b. Jika posisi individu tersebut sama dengan posisi individu terbaik,
maka hitung posisi sementara dengan rumus:
pos sementara = pos + arah * distnormacak(0, energi)

If isSama Then
	tmpIndividu2.posisi(j) = daftarIndividu(i).posisi(j) + arah(j) * Math.Abs(HitungDistribusiNormalAcak(rnd, 0, energi))
	. . .

* Gunakan fungsi ini untuk menghitung distribusi normal acak
Sehingga nilai yang berada ditengah-tengah akan memiliki kemungkinan muncul yang lebih banyak,
dan nilai yang berada dibagian ujung akan memiliki kemungkinan muncul yang lebih sedikit

Public Function HitungDistribusiNormalAcak(ByVal rnd As Random, Optional ByVal mean As Double = 0, Optional ByVal stdDev As Double = 1) As Double
	Dim u1 As Double = rnd.NextDouble()
	Dim u2 As Double = rnd.NextDouble()
	Dim rndStdNormal As Double = Math.Sqrt(-2.0 * Math.Log(u1)) * Math.Sin(2.0 * Math.PI * u2) 'random normal(0,1)
	Dim rndNormal As Double = mean + stdDev * rndStdNormal                                    ' random normal(mean, stdDev^2)
	Return rndNormal
End Function

3f2c. Jika kondisi diatas tidak terpenuhi, maka lakukan perhitungan berikut
jika nilai jarak kurang dari 0, maka hitung posisi sementara dengan rumus:
pos sementara = pos + distexpacak(abs(jarak))
jika nilai nilai jarak lebih dari 0, maka hitung posisi sementara dengan rumus:
pos sementara = pos - distexpacak(jarak)

. . .
Else
	If jarak(j) < 0 Then
		tmpIndividu2.posisi(j) = daftarIndividu(i).posisi(j) + HitungDistribusiEksponensialAcak(Math.Abs(jarak(j)), rnd)
	ElseIf jarak(j) > 0 Then
		tmpIndividu2.posisi(j) = daftarIndividu(i).posisi(j) - HitungDistribusiEksponensialAcak(jarak(j), rnd)
	End If
End If

* 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

3f2d. Jika posisi individu tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut

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

3f3. Hitung nilai fungsi pada individu tersebut

tmpIndividu2.nilaiFungsi = hitungNilaiFungsi(tmpIndividu2.posisi)

3f4. Jika nilai fungsi pada posisi sementara ternyata lebih baik dari nilai fungsi individu tersebut,
maka ambil posisi sementara menggantikan posisi individu tersebut

If tmpIndividu2.nilaiFungsi > daftarIndividu(i).nilaiFungsi Then
	daftarIndividu(i) = tmpIndividu2.Clone
	. . .

3f4a. Jika nilai acak kurang dari 1 persen, maka lakukan proses focking (poin 3f4a1 - 3f4a3)

If rnd.NextDouble < 0.01 Then
. . .

3f4a1. Hitung nilai posisi focking dengan rumus:
pos = (maksPos + minPos - pos sementara)

Dim tmpIndividu3 As New Individu(dimensi)
For j As Integer = 0 To dimensi - 1
	tmpIndividu3.posisi(j) = maksPosisi + minPosisi - tmpIndividu2.posisi(j)
Next

3f4a2. Hitung nilai fungsi pada individu tersebut

tmpIndividu3.nilaiFungsi = hitungNilaiFungsi(tmpIndividu3.posisi)

3f4a3. Jika nilai fungsi pada posisi focking ternyata lebih baik dari nilai fungsi individu tersebut,
maka ambil posisi focking menggantikan posisi individu tersebut

If tmpIndividu3.nilaiFungsi > daftarIndividu(i).nilaiFungsi Then
	daftarIndividu(i) = tmpIndividu3.Clone
End If

3f5. Jika nilai fungsi terbaik pada individu tersebut ternyata lebih baik dari nilai fungsi secara umum,
maka ambil posisi terbaik individu tersebut sebagai posisi terbaik

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

3g. Jika nilai fungsi tertinggi sudah sama dengan nilai fungsi terendah, maka hentikan perulangan karena nilai terbaik sudah ditemukan

If nilaiFungsiTertinggi = nilaiFungsiTerendah Then
	Console.WriteLine("Perhitungan dihentikan pada iterasi ke " & iterasi)
	Exit Do
End If

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

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

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