Algoritma EHO (Elephant Herding Optimization)

Entri ini telah di terbitkan di Algoritma Optimasi dan telah ditandai .net algoritma eho elephant herding optimization vb visual basic on sebesar

Algoritma EHO (Elephant Herding 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 maksimal.
Algoritma ini meniru tingkah laku dari hewan gajah (Elephant) dalam bermigrasi. Biasanya gajah akan bermigrasi secara berkelompok, yang dalam kasus ini disebut dengan clan. Masing-masing clan akan bermigrasi sambil menjaga anggota clan agar tidak terpisah. Sistem migrasi ini kemudian diterapkan sebagai inti pemecahan dari permasalahan optimasi



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 500 kali

Const jumlahIterasi As Integer = 500

* Tentukan ukuran populasi yang digunakan dalam perhitungan
Diasumsikan dalam kasus ini, ukuran populasi yang digunakan adalah 40

Const ukuranPopulasi As Integer = 40

* Tentukan jumlah kelompok dalam populasi, yang disebut juga sebagai clan
Diasumsikan dalam kasus ini, jumlah clan adalah 5 clan

Const jumlahClan As Integer = 5

* Tentukan jumlah populasi elit
Nantinya dalam setiap perulangan, butterfly elit akan dimasukkan untuk menggantikan butterfly dengan nilai terburuk
Diasumsikan dalam kasus ini, jumlah populasi elit adalah 2

Const jumlahPopulasiElit As Integer = 2

* Tentukan nilai alpha dan beta sebagai parameter untuk digunakan dalam proses penyesuaian posisi elephant dalam clan
Diasumsikan dalam kasus ini, nilai alpha adalah 0.5 dan nilai beta adalah 0.1

Const alpha As Double = 0.5
Const beta As Double = 0.1


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

Dim posisiTerbaik() As Double = EHO(dimensi, minPosisi, maksPosisi, jumlahIterasi, ukuranPopulasi, _
									jumlahClan, jumlahPopulasiElit, alpha, beta)

Memasuki perhitungan pada fungsi EHO

* Inisialisasi para elephant yang digunakan sebanyak ukuran populasi

1. Lakukan perulangan sebanyak ukuran populasi (poin 1a – 1b)

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

1a. Beri posisi acak pada masing-masing elephant sebanyak jumlah dimensi
dan pastikan tidak ada posisi elephant yang sama antara satu dengan yang lain

Dim isUnik As Boolean = False
Dim tmpPosisi(dimensi - 1) As Double

While Not isUnik
	isUnik = True

	For k As Integer = 0 To dimensi - 1
		tmpPosisi(k) = (maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi
	Next k

	For j As Integer = 0 To i - 1
		For jd As Integer = 0 To dimensi - 1
			If populasi(j).posisi(jd) = tmpPosisi(jd) Then
				isUnik = False
			Else
				isUnik = True
				Exit For
			End If
		Next
		If Not isUnik Then Exit For
	Next
End While

For k As Integer = 0 To dimensi - 1
	populasi(i).posisi(k) = tmpPosisi(k)
Next

1b. Hitung nilai fungsi pada posisi tersebut
Penjelasan tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

populasi(i).nilaiFungsi = hitungNilaiFungsi(populasi(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 populasi berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)

Array.Sort(populasi)

3. Ambil posisi elephant pertama sebagai posisi terbaik sementara

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

4. Lakukan pencatatan jumlah elephant dalam masing-masing clan
Untuk memudahkan perhitungan, maka sebaiknya digunakan nilai yang tidak memiliki sisa pembagian

Dim jumlahElephantPerClan(jumlahClan - 1) As Integer
For i As Integer = 0 To jumlahClan - 1
	jumlahElephantPerClan(i) = ukuranPopulasi / jumlahClan
Next

* Lakukan proses pencarian posisi terbaik (poin 5)

5. Lakukan proses perhitungan sebanyak jumlah iterasi (poin 5a – 5h)

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

5a. Simpan populasi elephant elit untuk dimasukkan ke dalam populasi pada generasi berikutnya

Dim populasiElit(jumlahPopulasiElit - 1) As Elephant
For i As Integer = 0 To jumlahPopulasiElit - 1
	populasiElit(i) = populasi(i).Clone
Next

5b. Lakukan pembagian populasi ke dalam masing-masing clan
Elephant yang terbaik akan menjadi nilai awal dalam masing-masing clan, dan selanjutnya elephant akan dimasukkan kedalam masing-masing clan

Dim idxPopulasi As Integer = 0
Dim idxElephantPerClan As Integer = 0
Dim daftarClan(jumlahClan - 1)() As Elephant
For i As Integer = 0 To jumlahClan - 1
	daftarClan(i) = New Elephant(jumlahElephantPerClan(i) - 1) {}
Next

While idxPopulasi < ukuranPopulasi
	For i As Integer = 0 To jumlahClan - 1
		daftarClan(i)(idxElephantPerClan) = populasi(idxPopulasi).Clone
		idxPopulasi += 1
	Next

	idxElephantPerClan += 1
End While

* Berikut adalah proses update posisi elephant dalam masing-masing clan (poin 5c)

5c. lakukan perulangan sebanyak populasi yang ada

While idxPopulasi < ukuranPopulasi
. . .

5c1. Lakukan perulangan seanyak jumlah clan yang ada

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

5c1a. Lakukan perhitungan pada masing-masing dimensi
Hitung nilai posisi yang baru dengan rumus:
posisi baru = posisi lama + alpha * (posisi elephant terbaik dalam clan - posisi elephant terpilih dalam clan) * nilai acak
Kemudian jumlahkan selisih dari posisi baru dan posisi lama

Dim delta As Double = 0
For j As Integer = 0 To dimensi - 1
	daftarClanBaru(i)(idxElephantPerClan).posisi(j) = daftarClan(i)(idxElephantPerClan).posisi(j) _
		+ alpha * (daftarClan(i)(0).posisi(j) - daftarClan(i)(idxElephantPerClan).posisi(j)) * rnd.NextDouble

	delta += daftarClanBaru(i)(idxElephantPerClan).posisi(j) - daftarClan(i)(idxElephantPerClan).posisi(j)
Next

5c1b. Jika tidak ada perubahan antara posisi baru dan posisi lama,
maka hitung nilai rata-rata posisi elephant pada clan tersebut
Kemudian posisi baru dihitung dengan rumus:
posisi baru = beta * rata-rata posisi

If delta = 0 Then
	Dim rata2posisi(dimensi - 1) As Double
	For j As Integer = 0 To jumlahElephantPerClan(i) - 1
		For k As Integer = 0 To dimensi - 1
			rata2posisi(k) += daftarClan(i)(j).posisi(k)
		Next
	Next

	For j As Integer = 0 To dimensi - 1
		rata2posisi(j) /= jumlahElephantPerClan(i)
		daftarClanBaru(i)(idxElephantPerClan).posisi(j) = beta * rata2posisi(j)
	Next
End If

5d. Lakukan proses pemisahan elephant pada posisi terakhir pada masing-masing clan
nilai posisi yang digunakan adalah nilai acak sesuai dengan batasan dimensi pada masing-masing posisi

For i As Integer = 0 To jumlahClan - 1
	For j As Integer = 0 To dimensi - 1
		daftarClanBaru(i)(daftarClanBaru(i).Length - 1).posisi(j) = (maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi
	Next
Next

* Berikut adalah proses evaluasi posisi elephant pada semua clan (poin 5e)

5e. Lakukan perhitungan pada masing-masing clan (poin 5e1 - 5e4)

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

5e1. Jika terdapat elephant pada posisi yang sama,
maka elephant dengan indeks yang lebih tinggi akan diganti posisinya dengan posisi acak
Kemudian akan dilakukan pengecekan lagi agar tidak ada elephant pada posisi yang sama

Dim isUnik As Boolean = False

While Not isUnik
	isUnik = True
	Dim idxTerakhir As Integer = -1
	For j As Integer = 0 To jumlahElephantPerClan(i) - 1
		For k As Integer = 0 To j - 1
			For jd As Integer = 0 To dimensi - 1
				If daftarClanBaru(i)(j).posisi(jd) = daftarClanBaru(i)(k).posisi(jd) Then
					isUnik = False
				Else
					isUnik = True
					Exit For
				End If
			Next

			If Not isUnik Then Exit For
		Next

		If Not isUnik Then
			idxTerakhir = j
			Exit For
		End If
	Next

	If Not isUnik Then
		For jd As Integer = 0 To dimensi - 1
			daftarClanBaru(i)(idxTerakhir).posisi(jd) = (maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi
		Next
	End If
End While

5e2. Jika posisi elephant tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut

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

5e3. Kemudian hitung nilai fungsi pada posisi tersebut

daftarClanBaru(i)(j).nilaiFungsi = hitungNilaiFungsi(daftarClanBaru(i)(j).posisi)

5e4. Lakukan proses pengurutan clan tersebut berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)

Array.Sort(daftarClanBaru(i))

5f. Lakukan penggabungan data dari masing-masing clan menjadi populasi semula
Kemudian urutkan populasi berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)

idxPopulasi = 0
For i As Integer = 0 To jumlahClan - 1
	For j As Integer = 0 To jumlahElephantPerClan(i) - 1
		populasi(idxPopulasi) = daftarClanBaru(i)(j).Clone
		idxPopulasi += 1
	Next
Next

Array.Sort(populasi)

5g. Masukkan elephant elit untuk menggantikan elephant dengan nilai terburuk (terendah)
Kemudian lakukan pengurutan populasi sekali lagi

For i As Integer = 0 To jumlahPopulasiElit - 1
	populasi(populasi.Length - 1 - i) = populasiElit(i).Clone
Next

Array.Sort(populasi)

5h. Jika nilai fungsi elephant terbaik ternyata lebih baik dari nilai fungsi secara umum,
maka ambil posisi terbaik elephant tersebut sebagai posisi terbaik

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

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

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

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


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd95


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 *