Algoritma LSA (Locust Search Algorithm)

Entri ini telah di terbitkan di Algoritma Optimasi dan telah ditandai .net algoritma locust search algorithm lsa vb visual basic on sebesar

Algoritma LSA (Locust 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.



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

Sedangkan Grafik fungsi Himmelblau untuk sebaran titik dengan rentang minimal -2 dan maksimal 2 adalah sebagai berikut.
Grafik Himmelblau -2sd2
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 100 kali

Const jumlahIterasi As Integer = 100

* Tentukan jumlah locust yang digunakan
Diasumsikan dalam kasus ini, jumlah locust adalah 20 locust

Const jumlahLocust As Integer = 20

* Tentukan banyak populasi locust yang diperhitungkan pada saat fase sosial
Diasumsikan dalam kasus ini, siklus adalah 10

Const jumlahChannel As Integer = 10

* Tentukan delta sebagai radius dari posisi sementara pada saat fase sosial
Diasumsikan dalam kasus ini, delta adalah 0.3

Const delta As Double = 0.3

* Tentukan faktor atraksi dan faktor jarak pada saat perpindahan posisi berdasarkan faktor sosial
Diasumsikan dalam kasus ini, faktor atraksi adalah 0.6 dan faktor jarak adalah 15

Const faktorAtraksi As Double = 0.6
Const faktorJarak As Integer = 15


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 – 3)

Dim posisiTerbaik() As Double = LSA(dimensi, minPosisi, maksPosisi, jumlahIterasi, jumlahLocust, _
									populasiLocustSaatFaseSosial, delta, faktorAtraksi, faktorJarak)

Memasuki perhitungan pada fungsi LSA

* Inisialisasi locust yang digunakan sebanyak parameter jumlah locust

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

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

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

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

2. Urutkan Locust berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)

Array.Sort(daftarLocust)

* Lakukan proses pencarian posisi terbaik

3. Lakukan proses perhitungan sebanyak jumlah iterasi (poin 3a – 3c)

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

* Inisialisasi populasi sementara untuk digunakan dalam perhitungan fase sosial

Dim tmpDaftarLocust(jumlahLocust / 2 - 1) As Locust
For i As Integer = 0 To jumlahLocust / 2 - 1
	tmpDaftarLocust(i) = New Locust(dimensi)
Next

3a. Lakukan proses fase sosial (poin 3a1 - 3a5)

3a1. Lakukan perhitungan pada locust terbaik dengan jumlah adalah setengah populasi
Kemudian lakukan pencarian locust dengan memperhitungkan urutan locust terbaik

For i As Integer = 0 To jumlahLocust / 2 - 1
	For j As Integer = 0 To populasiLocustSaatFaseSosial - 1
		For k As Integer = 0 To dimensi - 1
		. . .

3a2. Hitung posisi yang baru menggunakan sistem distribusi uniform acak
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

tmpDaftarLocust(j).posisi(k) = HitungDistribusiUniformAcak(rnd, daftarLocust(j).posisi(k) - (delta / (k + 1)), daftarLocust(j).posisi(k) + (delta / (k + 1)))

* Gunakan fungsi ini untuk menghitung distribusi uniform acak antara interval min dan maks

Public Function HitungDistribusiUniformAcak(ByVal rnd As Random, ByVal min As Double, ByVal maks As Double) As Double
	Dim min2 As Double = min / 2
	Dim maks2 As Double = maks / 2
	Dim mu As Double = min2 + maks2
	Dim sig As Double = maks2 - min2

	Dim rndUniform As Double = mu + sig * (2 * rnd.NextDouble - 1)
	Return rndUniform
End Function

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

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

3a4. Kemudian Hitung nilai fungsi dari posisi yang baru

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

3a5. Jika locust sementara ini memiliki nilai fungsi yang lebih baik dari locust awal, maka ambil posisi locust ini menggantikan posisi locust awal
Jika nilai fungsi terbaik pada locust tersebut ternyata lebih baik dari nilai fungsi secara umum, maka ambil posisi terbaik locust tersebut sebagai posisi terbaik

If tmpDaftarLocust(i).nilaiFungsi > daftarLocust(i).nilaiFungsi Then
	Array.Copy(tmpDaftarLocust(i).posisi, daftarLocust(i).posisi, dimensi)
	daftarLocust(i).nilaiFungsi = tmpDaftarLocust(i).nilaiFungsi

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

3b. Lakukan proses perhitungan untuk mendapatkan faktor sosial dari masing-masing dimensi
faktor sosial dihitung dengan memperhitungkan posisi locust dengan posisi terbaik, serta menggunakan faktor atraksi dan faktor jarak

Dim faktorSosial(dimensi - 1) As Double
For i As Integer = 0 To jumlahLocust - 1
	For k As Integer = 0 To dimensi - 1
		Dim r As Double = Math.Sqrt(PosisiTerbaik(k) ^ 2 + daftarLocust(i).posisi(k) ^ 2)
		Dim ri As Double = PosisiTerbaik(k) - daftarLocust(i).posisi(k)
		Dim sr As Double = (faktorAtraksi * Math.Exp(-r / faktorJarak)) - Math.Exp(-r)

		Dim si As Double = sr * (ri / r)
		If k = 1 Or PosisiTerbaik(k) = daftarLocust(i).posisi(k) Then si = 0
		faktorSosial(k) += si
	Next
Next

For k As Integer = 0 To dimensi - 1
	faktorSosial(k) *= Math.Exp(-((5 * (k))) / 1)
Next

3c. Lakukan proses perpindahan posisi berdasarkan faktor sosial (poin 3c1 - 3c5)

3c1. Lakukan perhitungan pada semua locust yang bukan merupakan locust terbaik

For i As Integer = 1 To jumlahLocust - 1
	If i <> idxTerbaik Then
		For k As Integer = 1 To dimensi - 1
		. . .

3c2. Hitung posisi yang baru menggunakan faktor sosial dari masing-masing dimensi

faktorSosial(k) /= (Math.Abs(faktorSosial(k)) + EPSILON)
tmpPosisiBaru(k) = faktorSosial(k) * (daftarLocust(i).posisi(k) - PosisiTerbaik(k)) + (0.1 * rnd.NextDouble)

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

If tmpPosisiBaru(k) < minPosisi Then
	tmpPosisiBaru(k) = minPosisi
ElseIf tmpPosisiBaru(k) > maksPosisi Then
	tmpPosisiBaru(k) = maksPosisi
End If

3c4. Kemudian Hitung nilai fungsi dari posisi yang baru

Dim tmpNilaiFungsiBaru As Double = hitungNilaiFungsi(tmpPosisiBaru)

3c5. Jika locust sementara ini memiliki nilai fungsi yang lebih baik dari locust awal, maka ambil posisi locust ini menggantikan posisi locust awal
Jika nilai fungsi terbaik pada locust tersebut ternyata lebih baik dari nilai fungsi secara umum, maka ambil posisi terbaik locust tersebut sebagai posisi terbaik

If tmpNilaiFungsiBaru > daftarLocust(i).nilaiFungsi Then
	Array.Copy(tmpPosisiBaru, daftarLocust(i).posisi, dimensi)
	daftarLocust(i).nilaiFungsi = tmpNilaiFungsiBaru

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

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

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

    'Gunakan fungsi ini untuk melakukan clone pada locust
    Public Function Clone() As Object Implements ICloneable.Clone
        Dim hasilClone As Locust = TryCast(Me.MemberwiseClone(), Locust)
        hasilClone.posisi = DirectCast(posisi.Clone(), Double())
        Return hasilClone
    End Function
End Class


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd151


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:

Download Now!



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.

Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *