Algoritma DEA (Differential Evolution Algorithm) 2

Algoritma DEA (Differential Evolution 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 memiliki kemiripan struktur dengan Algoritma GA (Genetic Algorithm), hanya terdapat perbedaan pada saat proses perhitungan mutasi dan crossover.

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 ukuran populasi yang digunakan dalam perhitungan
Diasumsikan dalam kasus ini, ukuran populasi yang digunakan adalah 25

Const ukuranPopulasi As Integer = 25

* Tentukan nilai minimal dan maksimal beta
Nantinya dalam setiap perulangan, nilai beta dihitung dari nilai acak antara nilai minimal dan maksimal beta
Diasumsikan dalam kasus ini, nilai minimal beta adalah 0.2 dan nilai maksimal beta adalah 0.5

Const minBeta As Double = 0.2
Const maksBeta As Double = 0.5

* Tentukan probabilitas crossover
Nantinya nilai ini digunakan dalam perhitungan pada proses crossover
Diasumsikan dalam kasus ini, probabilitas crossover adalah 0.2

Const probCrossover As Double = 0.2

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 = DEA(dimensi, minPosisi, maksPosisi, jumlahIterasi, ukuranPopulasi, _
									minBeta, maksBeta, probCrossover)

Memasuki perhitungan pada fungsi DEA

* Inisialisasi individu yang digunakan sebanyak ukuran populasi

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

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

1a. Beri posisi acak pada masing-masing individu sebanyak jumlah dimensi

For j As Integer = 0 To dimensi - 1
	populasi(i).posisi(j) = (maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi
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

1c. Ambil posisi individu terbaik sebagai posisi terbaik sementara

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

* Lakukan proses pencarian posisi terbaik (poin 2)

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

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

2a. Lakukan perulangan sebanyak ukuran populasi (poin 2a1 - 2a7)

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

2a1. Beri nilai awal pada posisi X, yaitu sama dengan posisi populasi terpilih

Dim posisiX() As Double = populasi(i).posisi

2a2. Cari 3 indeks populasi acak yang tidak sama satu sama lain dan tidak sama juga dengan indeks populasi terpilih

Dim idxA As Integer = -1, idxB As Integer = -1, idxC As Integer = -1
While (i = idxA Or i = idxB Or i = idxC) Or (idxA = idxB Or idxA = idxC Or idxB = idxC)
	idxA = rnd.Next(ukuranPopulasi)
	idxB = rnd.Next(ukuranPopulasi)
	idxC = rnd.Next(ukuranPopulasi)
End While

* Memasuki perhitungan pada proses mutasi (poin 2a3)

2a3. Lakukan perhitungan sebanyak jumlah dimensi yang ada (poin 2a3a - 2a3c)

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

2a3a. Hitung nilai beta dengan mencari nilai acak antara nilai minimal beta dan maksimal beta

Dim beta As Double = (maksBeta - minBeta) * rnd.NextDouble() + minBeta

2a3b. Hitung posisi Y dengan rumus:
Y = pop(A) + beta * pop(B) - pop(C)

posisiY(j) = populasi(idxA).posisi(j) + beta * populasi(idxB).posisi(j) - populasi(idxC).posisi(j)

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

If posisiY(j) < minPosisi Then
	posisiY(j) = minPosisi
ElseIf posisiY(j) > maksPosisi Then
	posisiY(j) = maksPosisi
End If

* Memasuki perhitungan pada proses crossover (poin 2a4a - 2a4b)

2a4a. Tentukan indeks dimensi acak untuk digunakan dalam perhitungan berikutnya

Dim idxDimensiCrossoverAcak As Integer = rnd.Next(dimensi)

2a4b. Lakukan perhitungan sebanyak jumlah dimensi yang ada
Jika indeks dimensi terpilih sama dengan indeks dimensi acak atau nilai acak kurang dari parameter probabilitas crossover,
maka ambil posisi Y sebagai posisi baru
selain itu ambil posisi X sebagai posisi baru

For j As Integer = 0 To dimensi - 1
	If (j = idxDimensiCrossoverAcak) Or (rnd.NextDouble <= probCrossover) Then
		posisiBaru(j) = posisiY(j)
	Else
		posisiBaru(j) = posisiX(j)
	End If
Next

2a5. Hitung nilai fungsi baru pada posisi tersebut
Penjelasan tentang fungsi ini sudah dijelaskan pada perhitungan sebelumnya

Dim nilaiFungsiBaru = hitungNilaiFungsi(posisiBaru)

2a6. Jika nilai fungsi baru lebih baik dari nilai fungsi populasi terpilih
maka ambil posisi baru untuk menggantikan nilai populasi terpilih

If nilaiFungsiBaru > populasi(i).nilaiFungsi Then
	Array.Copy(posisiBaru, populasi(i).posisi, dimensi)
	populasi(i).nilaiFungsi = nilaiFungsiBaru
End If

2a7. Jika nilai fungsi individu terbaik ternyata lebih baik dari nilai fungsi secara umum,
maka ambil posisi terbaik individu tersebut sebagai posisi terbaik

If nilaiFungsiBaru > nilaiFungsiTerbaik Then
	Array.Copy(posisiBaru, PosisiTerbaik, dimensi)
	nilaiFungsiTerbaik = nilaiFungsiBaru
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
    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.