Algoritma MVO (Multi-Verse Optimizer)

Entri ini telah di terbitkan di Algoritma Optimasi dan telah ditandai .net algoritma multi-verse optimizer mvo vb visual basic on sebesar

Algoritma MVO (Multi-Verse 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 menggunakan topik perpindahan posisi alam semesta atau dinamakan dengan universe. Terdapat 2 macam cara perpindahan posisi universe, yaitu melalui proses perpindahan materi dari Whitehole ke Blackhole, dan melalui proses perpindahan berkecepatan cahaya yang dilakukan dalam ruang Wormhole.



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

Const jumlahUniverse As Integer = 20

* Tentukan probabilitas minimal dan maksimal untuk keberadaan Wormhole
Diasumsikan dalam kasus ini, probabilitas minimal adalah 0.2 dan probabilitas maksimal adalah 1

Const probMinimalWormhole As Double = 0.2
Const probMaksimalWormhole As Double = 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 – 2)

Dim posisiTerbaik() As Double = MVO(dimensi, minPosisi, maksPosisi, jumlahIterasi, jumlahUniverse, _
									probMinimalWormhole, probMaksimalWormhole)

Memasuki perhitungan pada fungsi MVO

* Inisialisasi universe yang digunakan sebanyak parameter jumlah universe

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

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

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

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

* Lakukan proses pencarian posisi terbaik (poin 2)

2. Lakukan proses perhitungan sebanyak jumlah iterasi (poin 2a – 2f)

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

2a. Hitung probabilitas terjadinya Wormhole dengan rumus:
p = pmin + iterasi * ((pmaks - pmin) / jumlah iterasi)
Semakin banyak iterasi yang telah dilakukan, maka semakin tinggi kemungkinan Wormhole akan terjadi

Dim probWormhole As Double = probMinimalWormhole + iterasi * ((probMaksimalWormhole - probMinimalWormhole) / jumlahIterasi)

2b. Hitung rasio jarak tempuh dengan rumus:
rasio = 1 - ((iterasi ^ (1/6)) / ((jumlah iterasi ^ (1/6)))
Semakin banyak iterasi yang telah dilakukan, maka semakin rendah rasio jarak tempuh yang dapat dilakukan,
sehingga solusi yang ditemukan sudah tidak dapat lagi berpindah-pindah

Dim rasioJarakTempuh As Double = 1 - ((iterasi ^ (1 / 6)) / (jumlahIterasi ^ (1 / 6)))

2c. Salin data universe sebagai data baru,
Kemudian urutkan data tersebut berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)

Dim tmpDaftarUniverseTerurut(jumlahUniverse - 1) As Universe
For i As Integer = 0 To jumlahUniverse - 1
	tmpDaftarUniverseTerurut(i) = daftarUniverse(i).Clone
Next

Array.Sort(tmpDaftarUniverseTerurut)

2d. Hitung normalisasi nilai fungsi dari data universe yang sudah terurut
Penjelasan tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Dim normalisasiNilaiFungsi() As Double = HitungNormalisasiNilaiFungsi(tmpDaftarUniverseTerurut)

* Gunakan fungsi ini untuk menghitung normalisasi nilai fungsi
Hitung faktor normalisasi dengan rumus (1 / jumlah kuadrat masing-masing nilai fungsi)
Kemudian kalikan masing-masing nilai fungsi dengan faktor normalisasi tersebut

Public Function HitungNormalisasiNilaiFungsi(ByVal daftarUniverse() As Universe) As Double()
	Dim totalKuadrat As Double = 0
	For i As Integer = 0 To daftarUniverse.Length - 1
		totalKuadrat += Math.Pow(daftarUniverse(i).nilaiFungsi, 2)
	Next

	Dim faktorNormalisasi As Double = 1 / Math.Sqrt(totalKuadrat)

	Dim normalisasiNilaiFungsi(daftarUniverse.Length - 1) As Double
	For i As Integer = 0 To daftarUniverse.Length - 1
		normalisasiNilaiFungsi(i) = daftarUniverse(i).nilaiFungsi * faktorNormalisasi
	Next

	Return normalisasiNilaiFungsi
End Function

2e. Ambil universe terbaik dari data terurut ke dalam data universe pertama

daftarUniverse(0) = tmpDaftarUniverseTerurut(0).Clone

* Lakukan proses perhitungan nilai posisi yang baru dari setiap universe (poin 2f)

2f. Lakukan perhitungan pada masing-masing universe (poin 2f1 - 2f4)
perhitungan dimulai dari universe kedua karena universe pertama merupakan universe terbaik yang sudah ditentukan sebelumnya

For i As Integer = 1 To daftarUniverse.Length - 1
. . .

2f1. Tentukan indeks Blackhole untuk digunakan dalam proses perpindahan posisi universe
Universe yang sedang terhitung akan digunakan sebagai posisi Blackhole

Dim idxBlackHole As Integer = i

2f2. Lakukan perhitungan pada masing-masing posisi universe tersebut (poin 2f2a -2f2c)

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

2f2a. Tentukan nilai acak antara 0 sampai dengan 1
Jika nilai acak kurang dari normalisasi nilai fungsi universe tersebut,
maka lakukan proses perpindahan posisi universe (poin 2f2a1 - 2f2a2)

Dim r1 As Double = rnd.NextDouble()
If r1 < normalisasiNilaiFungsi(i) Then
. . .

2f2a1. Tentukan indeks Whitehole untuk digunakan dalam proses perpindahan posisi universe
Teknik yang digunakan adalah teknik Seleksi Roulette (Roulette Wheel Selection)
Jika Whitehole tidak ditemukan, maka gunakan universe terbaik sebagai posisi Whitehole

Dim idxWhiteHole As Integer = RouletteWheelSelection(tmpDaftarUniverseTerurut)
If idxWhiteHole = -1 Then idxWhiteHole = 0

* 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 rasio emigrasi

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

2f2a2. Lakukan perpindahan posisi dari Whitehole ke Blackhole

daftarUniverse(idxBlackHole).posisi(j) = tmpDaftarUniverseTerurut(idxWhiteHole).posisi(j)

2f2b. Tentukan nilai acak antara 0 sampai dengan 1
Jika nilai acak kurang dari probabilitas terjadinya Wormhole,
maka lakukan proses Wormhole (poin 2f2b1)

r1 = rnd.NextDouble
If r1 < probWormhole Then
. . .

2f2b1. Tentukan nilai acak antara 0 sampai dengan 1
Jika nilai acak kurang dari 0.5, maka posisi universe dihitung dengan rumus:
posisi baru = posisi terbaik + rasio jarak tempuh * posisi acak dalam rentang dimensi
Jika nilai acak lebih dari 0.5, maka posisi universe dihitung dengan rumus:
posisi baru = posisi terbaik - rasio jarak tempuh * posisi acak dalam rentang dimensi

If rnd.NextDouble < 0.5 Then
	daftarUniverse(i).posisi(j) = PosisiTerbaik(j) + rasioJarakTempuh * ((maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi)
Else
	daftarUniverse(i).posisi(j) = PosisiTerbaik(j) - rasioJarakTempuh * ((maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi)
End If

2f2c. Jika posisi universe tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut

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

2f3. Hitung nilai fungsi pada universe tersebut

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

2f4. Jika nilai fungsi terbaik pada universe tersebut ternyata lebih baik dari nilai fungsi secara umum,
maka ambil posisi terbaik universe tersebut sebagai posisi terbaik

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

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

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

cmd102


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 *