Algoritma HS (Harmony Search)

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

Algoritma HS (Harmony Search) 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 tingkah laku pemain musik dalam memainkan musik. Masing-masing pemain musik dengan alat musik tersendiri akan saling memainkan nada-nada sampai akhirnya ditemukan kecocokan nada yang dimainkan atau disebut sebagai alunan nada yang harmoni antara satu sama lain. Dalam kasus ini, nada adalah posisi, dan nilai harmoni adalah nilai fungsi yang sedang dicari.



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 (harmoni)
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 5.000 kali

Const jumlahIterasi As Integer = 5000

* Tentukan jumlah pemain musik yang akan memainkan musik
Nilai yang direkomendasikan adalah 1 sampai dengan 100 dengan nilai default adalah 30
Diasumsikan dalam kasus ini, jumlah pemain musik adalah 30 orang

Const jumlahPemainMusik As Integer = 30

* Tentukan probabilitas pemilihan nilai dari memori Harmoni
Nilai yang direkomendasikan adalah 0.7 sampai dengan 0.99 dengan nilai default adalah 0.9
Diasumsikan dalam kasus ini, nilai probabilitas adalah 0.95

Const probPemilihanDariMemoriHarmoni = 0.95

* Tentukan probabilitas untuk melakukan penyesuaian pitch
Penyesuaian pitch adalah proses pengeseran nada untuk menemukan nilai harmoni yang lebih baik
Nilai yang direkomendasikan adalah 0.1 sampai dengan 0.5 dengan nilai default adalah 0.3
Diasumsikan dalam kasus ini, rasio penyesuaian pitch adalah 0.3

Const probPenyesuaianPitch = 0.3

* Tentukan nilai bandwidth yaitu nilai maksimum yang diperbolehkan pada saat proses penyesuaian pitch
Nilai yang direkomendasikan adalah 0.001 * posisi minimal sampai dengan 0.01 * posisi maksimal
Diasumsikan dalam kasus ini, bandwidth yang digunakan adalah 0.005

Const bandwidth = 0.005


Langkah-langkah penggunaan algoritma ini adalah

* Lakukan proses pencarian harmoni terbaik
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 1 – 2)

Dim posisiTerbaik() As Double = HS(dimensi, minPosisi, maksPosisi, jumlahIterasi, _
								   jumlahPemainMusik, probPemilihanDariMemoriHarmoni, probPenyesuaianPitch, bandwidth)

Memasuki perhitungan pada fungsi HS

* Inisialisasi para pemain musik yang digunakan sebanyak parameter jumlah pemain musik

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

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

1a. Beri nada acak pada masing-masing pemain musik sebanyak jumlah dimensi
Kemudian hitung nilai fungsi pada harmoni tersebut
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

For j As Integer = 0 To dimensi - 1
	daftarHarmoni(i)(j) = (maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi
Next j
nilaiFungsi(i) = hitungNilaiFungsi(daftarHarmoni(i))

* 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. Jika nilai harmoni acak ini lebih baik dari nilai fungsi terbaik,
maka ambil harmoni tersebut sebagai harmoni terbaik sementara

If nilaiFungsi(i) > nilaiFungsiTerbaik Then
	nilaiFungsiTerbaik = nilaiFungsi(i)
	Array.Copy(daftarHarmoni(i), harmoniTerbaik, dimensi)
	indeksharmoniTerbaik = i
End If

* Lakukan proses pencarian harmoni terbaik

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

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

2a. Lakukan perulangan pada masing-masing dimensi permasalahan untuk mendapatkan nilai harmoni sementara pada iterasi ini (poin 2a1 - 2a2)

For i As Integer = 0 To dimensi - 1

2a1. Tentukan nilai acak antara 0 sampai dengan 1 untuk dibandingkan dengan parameter pemilihan dari memori harmoni
Jika nilai acak ini lebih dari parameter tersebut,
maka nada untuk menyusun harmoni yang baru didapatkan dengan cara pemilihan acak

Dim p As Double = rnd.NextDouble()
If p > probPemilihanDariMemoriHarmoni Then
	harmoniBaru(i) = (maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi
	. . .

2a2. Jika nilai acak diatas kurang dari parameter pemilihan dari memori harmoni,
maka lakukan perhitungan berikut (poin 2a2a - 2a2e)

. . .
Else
. . .

2a2a. Tentukan nada untuk menyusun harmoni yang baru,
yang didapatkan dari pemain musik acak pada dimensi yang sedang dihitung

harmoniBaru(i) = daftarHarmoni(rnd.Next(jumlahPemainMusik))(i)

2a2b. Tentukan nilai acak lainnya untuk dibandingkan dengan parameter penyesuaian pitch
Jika nilai acak ini kurang dari parameter tersebut,
maka lakukan proses penyesuaian pitch pada nada tersebut

Dim p2 As Double = rnd.NextDouble()
If p2 < probPenyesuaianPitch Then
. . .

2a2c. Tentukan nilai acak antara -1 sampai dengan 1 sebagai nilai penggeser pitch

Dim nilaiAcak As Double = rnd.NextDouble()
If rnd.NextDouble() < 0.5 Then nilaiAcak *= -1

2a2d. Tentukan nada yang baru setelah dilakukan penyesuaian pitch

Dim tmp As Double = harmoniBaru(i)
tmp += nilaiAcak * bandwidth

2a2e. Jika nada ini masih di dalam batasan yang diperbolehkan,
maka ambil nada ini sebagai nada yang baru

If tmp > minPosisi Then
	harmoniBaru(i) = tmp
ElseIf tmp < maksPosisi Then
	harmoniBaru(i) = tmp
End If

2b. Hitung nilai fungsi pada harmoni yang baru

Dim nilaiFungsiBaru As Double = hitungNilaiFungsi(harmoniBaru)

2c. Cari nilai fungsi terburuk dari pemain musik yang ada

Dim nilaiFungsiTerburuk As Double = daftarHarmoni(0)(dimensi)
Dim idxNilaiFungsiTerburuk As Integer = 0
For i As Integer = 0 To jumlahPemainMusik - 1
	If daftarHarmoni(i)(dimensi) < nilaiFungsiTerburuk Then
		nilaiFungsiTerburuk = daftarHarmoni(i)(dimensi)
		idxNilaiFungsiTerburuk = i
	End If
Next

2d. Jika nilai fungsi harmoni baru lebih dari nilai fungsi terburuk,
maka gantikan harmoni terburuk dengan harmoni yang baru

If nilaiFungsiBaru > nilaiFungsiTerburuk Then
	Array.Copy(harmoniBaru, daftarHarmoni(idxNilaiFungsiTerburuk), dimensi)
	daftarHarmoni(idxNilaiFungsiTerburuk)(dimensi) = nilaiFungsiBaru
End If

2e. Cari nilai fungsi terbaik dari pemain musik yang ada

Dim nilaiFungsiTerbaikBaru As Double = daftarHarmoni(0)(dimensi)
Dim idxNilaiFungsiTerbaik As Integer = 0
For i As Integer = 0 To jumlahPemainMusik - 1
	If daftarHarmoni(i)(dimensi) > nilaiFungsiTerbaikBaru Then
		nilaiFungsiTerbaikBaru = daftarHarmoni(i)(dimensi)
		idxNilaiFungsiTerbaik = i
	End If
Next

2f. Jika nilai fungsi pada poin sebelumnya lebih baik dari nilai fungsi secara umum,
maka ambil harmoni yang baru sebagai harmoni terbaik

If nilaiFungsiTerbaikBaru > nilaiFungsiTerbaik Then
	Array.Copy(daftarHarmoni(idxNilaiFungsiTerbaik), harmoniTerbaik, dimensi)
	nilaiFungsiTerbaik = nilaiFungsiTerbaikBaru
End If


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd87


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 *