Algoritma CBBO (Chaotic Biogeography-based Optimization): Chaotic Selection


Algoritma CBBO (Chaotic Biogeography-based 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 merupakan variasi dari BBO (Biogeography-based Optimization), dimana dalam kasus ini akan digunakan sistem Chaotic untuk mencegah kesalahan perhitungan hasil akhir karena beberapa sebab seperti penyimpulan yang terlalu cepat atau perhitungan yang terjebak dalam suatu area tertentu yang bukan merupakan jawaban sebenarnya.
Karena pada algoritma ini terdapat 3 macam proses, yaitu proses seleksi, migrasi, dan mutasi, maka proses penerapan sistem Chaotic juga dilakukan secara sendiri-sendiri, yaitu:

  • CBBO (Chaotic Biogeography-based Optimization): Chaotic Selection
  • CBBO (Chaotic Biogeography-based Optimization): Chaotic Migration
  • CBBO (Chaotic Biogeography-based Optimization): Chaotic Mutation
  • CBBO (Chaotic Biogeography-based Optimization): Hybrid
  • , yang merupakan gabungan dari ketiga penerapan sebelumnya

Versi yang dibahas pada kasus ini adalah versi Chaotic Selection, dimana sistem Chaotic hanya diterapkan pada saat proses seleksi saja.



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 25

Const ukuranPopulasi As Integer = 25

* Tentukan rasio individu yang disimpan dalam habitat
Diasumsikan dalam kasus ini, rasio penyimpanan individu adalah 0.2
Kemudian hitung jumlah individu yang disimpan dengan rumus:
nKeep=round(KeepRate*nPop);

Const rasioPenyimpananIndividu As Double = 0.2
Dim jumlahIndividuTersimpan = Math.Round(rasioPenyimpananIndividu * ukuranPopulasi)

* Tentukan alpha, yaitu koefisien untuk menghitung perpindahan individu ke habitat baru
Diasumsikan dalam kasus ini, alpha adalah 0.9

Const alpha As Double = 0.9

* Tentukan probabilitas mutasi individu
Nilai ini nantinya digunakan dalam proses mutasi individu dalam melakukan migrasi
Diasumsikan dalam kasus ini, probabilitas mutasi adalah 0.1

Const probabilitasMutasi 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 – 6)

Dim posisiTerbaik() As Double = CBBO(dimensi, minPosisi, maksPosisi, jumlahIterasi, ukuranPopulasi, _
									 jumlahIndividuTersimpan, alpha, probabilitasMutasi)

Memasuki perhitungan pada fungsi CBBO

* Inisialisasi individu 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 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

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

Array.Sort(populasi)

3. Ambil posisi individu pertama sebagai posisi terbaik sementara

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

4. Hitung parameter rasio emigrasi, yang dilambangkan dengan mu
dan parameter rasio imigrasi, yang dilambangkan dengan lambda
rasio emigrasi memiliki nilai sebanyak ukuran populasi,
dengan nilai awal adalah 0, dan akan bertambah secara konstan sampai mencapai angka 1
sedangkan rasio imigrasi adalah kebalikan dari rasio emigrasi
dengan nilai awal adalah 1, dan akan berkurang secara konstan sampai mencapai angka 0
Kemudian lakukan pencarian nilai minimal dan maksimal dari lambda tersebut

Dim mu(ukuranPopulasi - 1) As Double
Dim lambda(ukuranPopulasi - 1) As Double
Dim lambdaMin As Double = Double.MaxValue
Dim lambdaMaks As Double = Double.MinValue
For i As Integer = 0 To ukuranPopulasi - 1
	lambda(i) = 1 - populasi(i).jumlahIndividuTerpilih / ukuranPopulasi
	mu(i) = populasi(i).jumlahIndividuTerpilih / ukuranPopulasi

	If lambda(i) > lambdaMaks Then lambdaMaks = lambda(i)
	If lambda(i) < lambdaMin Then lambdaMin = lambda(i)
Next

5. Tentukan nilai sigma, yaitu 2 persen dari selisih posisi maksimal dan posisi minimal

Dim sigma As Double = 0.02 * (maksPosisi - minPosisi)

6. Hitung nilai awai probabilitas individu terpilih dalam populasi
Nilai awal untuk masing-masing individu adalah sama, yaitu 1 / ukuran populasi

Dim probPerPopulasi(ukuranPopulasi - 1) As Double
For i As Integer = 0 To ukuranPopulasi - 1
	probPerPopulasi(i) = 1 / ukuranPopulasi
Next

7. Lakukan perhitungan nilai chaos dalam masing-masing iterasi menggunakan teknik Chaotic
teknik mapping yang digunakan adalah teknik lingkaran / Circle

Dim ChaosMap(jumlahIterasi - 1) As Double
Dim tmpMap(jumlahIterasi - 1) As Double
tmpMap(0) = 0.7
ChaosMap(0) = tmpMap(0)

Dim pa As Double = 0.5, pb As Double = 0.2
For i As Integer = 1 To jumlahIterasi - 1
	tmpMap(i) = (tmpMap(i - 1) + pb - (pa / (2 * Math.PI)) * Math.Sin(2 * Math.PI * tmpMap(i - 1)))
	If tmpMap(i) > 1 Then tmpMap(i) -= Math.Truncate(tmpMap(i))
	ChaosMap(i) = tmpMap(i)
Next

* Lakukan proses pencarian posisi terbaik (poin 8)

8. Lakukan proses perhitungan sebanyak jumlah iterasi (poin 8a - 8l)

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

8a. Beri nilai awal populasi yang baru dengan menggunakan posisi dan nilai fungsi dari populasi yang ada
Kemudian hitung nilai jumlah individu terpilih dari masing-masing individu,
yaitu menggunakan angka terurut dari ukuran populasi sampai dengan 1

Dim populasiBaru() As Individu = populasi.Clone
For i As Integer = 0 To ukuranPopulasi - 1
	populasiBaru(i).jumlahIndividuTerpilih = ukuranPopulasi - 1 - i
Next

* Lakukan perhitungan untuk menentukan nilai probabilitas individu terpilih yang sebenarnya (poin 8b - 8c)

8b. Lakukan perulangan sebanyak ukuran populasi (poin 8b1 - 8b3)

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

8b1. Hitung nilai lambda apabila jumlah individu terpilih dikurangi dengan 1
Kemudian hitung nilai lambda apabila jumlah individu terpilih ditambah dengan 1

Dim lambdaMinus As Double = 1 - (populasiBaru(i).jumlahIndividuTerpilih - 1) / ukuranPopulasi
Dim muPlus As Double = (populasiBaru(i).jumlahIndividuTerpilih + 1) / ukuranPopulasi

8b2. Hitung nilai probabilitasi populasi individu tersebut apabila jumlah individu terpilih ditambah dan dikurangi dengan 1

Dim probMinus As Double = 0
Dim probPlus As Double = 0
If i < (ukuranPopulasi - 1) Then
	probMinus = probPerPopulasi(i + 1)
End If
If i > 0 Then
	probPlus = probPerPopulasi(i - 1)
End If

8b3. Hitung nilai probabilitas sementara untuk individu ini.

tmpProb(i) = -(lambda(i) + mu(i)) * probPerPopulasi(i) + lambdaMinus * probMinus + muPlus * probPlus

8c. Lakukan perulangan sebanyak ukuran populasi
Jumlahkan nilai probabilitas awal dengan nilai probabilitas sementara yang sudah dihitung sebelumnya
Jika nilai probabilitas bernilai negatif, maka nilainya dijadikan 0
Kemudian lakukan normalisasi dengan cara membagi nilai tersebut dengan jumlah semua nilai probabilitas

Dim totalProb As Double = 0
For i As Integer = 0 To ukuranPopulasi - 1
	probPerPopulasi(i) += tmpProb(i)
	If probPerPopulasi(i) < 0 Then probPerPopulasi(i) = 0
	totalProb += probPerPopulasi(i)
Next

Dim maksProb As Double = Double.MinValue
For i As Integer = 0 To ukuranPopulasi - 1
	probPerPopulasi(i) /= totalProb
	If probPerPopulasi(i) > maksProb Then maksProb = probPerPopulasi(i)
Next

8d. Tentukan nilai chaos yang digunakan dalam iterasi ini sesuai dengan mapping yang sudah dilakukan sebelumnya

Dim nilaiChaos As Double = ChaosMap(iterasi - 1)

* Memasuki proses seleksi dan migrasi individu (poin 8e)

8e. Lakukan perulangan sebanyak ukuran populasi (poin 8e1 - 8e2)

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

8e1. Hitung nilai skala lambda pada individu ini

Dim skalaLambda As Double = (lambda(i) - lambdaMin) / (lambdaMaks - lambdaMin)

8e2. Lakukan perulangan pada masing-masing dimensi posisi

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

8e2a. Lakukan proses migrasi berikut ini apabila nilai acak kurang dari nilai skala lambda (poin 8e2a1 - 8e2a2)
Karena menggunakan teknik Chaotic Selection, maka nilai acak diganti dengan nilai chaos

If nilaiChaos < skalaLambda Then
. . .

8e2a1. Tentukan habitat tujuan migrasi individu ini
Teknik yang digunakan adalah teknik Seleksi Roulette (Roulette Wheel Selection)
Habitat tujuan ini tidak boleh sama dengan posisi individu yang sedang dihitung

Dim idxHabitatTerpilih As Integer = i
While idxHabitatTerpilih = i
	idxHabitatTerpilih = RouletteWheelSelection(mu, rnd)
End While

* 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, Optional ByVal nilaiChaos As Double = 0) 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 = IIf(nilaiChaos > 0, nilaiChaos, 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

8e2a2. Hitung posisi yang baru dengan rumus:
posisi baru = posisi + alpha * selisih posisi habitat tujuan dengan posisi individu sekarang

populasiBaru(i).posisi(j) = populasi(i).posisi(j) + alpha * (populasi(idxHabitatTerpilih).posisi(j) - populasi(i).posisi(j))

* Memasuki proses mutasi individu (poin 8f - 8g)

8f. Lakukan perulangan sebanyak ukuran populasi
Lakukan perhitungan rasio mutasi untuk masing-masing individu menggunakan nilai proabilitas yang sudah dihitung sebelumnya

Dim rasioMutasi(ukuranPopulasi - 1) As Double
For i As Integer = 0 To ukuranPopulasi - 1
	rasioMutasi(i) = probabilitasMutasi * (1 - probPerPopulasi(i) / maksProb)
Next

8g. Lakukan perulangan pada masing-masing dimensi dari populasi setengah terbaik
Proses mutasi hanya dilakukan pada setengah populasi terbaik ini

For i As Integer = 0 To ukuranPopulasi / 2
	For j As Integer = 0 To dimensi - 1
	. . .

8g1. Lakukan proses mutasi apabila nilai rasio mutasi individu lebih dari nilai acak
posisi baru dihitung dengan rumus:
posisi baru = posisi + sigma * distribusi normal acak

If rasioMutasi(i) > rnd.NextDouble Then
	populasiBaru(i).posisi(j) += sigma * HitungDistribusiNormalAcak(rnd)
End If

* Gunakan fungsi ini untuk menghitung distribusi normal acak
Sehingga nilai yang berada ditengah-tengah akan memiliki kemungkinan muncul yang lebih banyak,
dan nilai yang berada dibagian ujung akan memiliki kemungkinan muncul yang lebih sedikit

Public Function HitungDistribusiNormalAcak(ByVal rnd As Random, Optional ByVal mean As Double = 0, Optional ByVal stdDev As Double = 1) As Double
	Dim u1 As Double = rnd.NextDouble()
	Dim u2 As Double = rnd.NextDouble()
	Dim rndStdNormal As Double = Math.Sqrt(-2.0 * Math.Log(u1)) * Math.Sin(2.0 * Math.PI * u2) 'random normal(0,1)
	Dim rndNormal As Double = mean + stdDev * rndStdNormal                                    'random normal(mean, stdDev^2)
	Return rndNormal
End Function

8h. Lakukan perhitungan pada masing-masing dimensi dalam populasi baru (poin 8h1 - 8h2)

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

8h1. Jika posisi individu yang baru ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut

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

8h2. hitung nilai fungsi pada posisi tersebut

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

8i. Urutkan populasi yang baru berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)

Array.Sort(populasiBaru)

8j. Simpan individu terbaik dari populasi yang lama sebanyak parameter jumlah individu tersimpan
Kemudian ganti individu lainnya sesuai dengan individu terbaik pada populasi yang baru

For i As Integer = jumlahIndividuTersimpan To ukuranPopulasi - 1
	populasi(i) = populasiBaru(i - jumlahIndividuTersimpan).Clone
Next

8k. Lakukan pengurutan populasi sekali lagi

Array.Sort(populasi)

8l. Jika nilai fungsi individu terbaik ternyata lebih baik dari nilai fungsi secara umum,
maka ambil posisi terbaik individu 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 Individu untuk menampung semua data posisi dan nilai fungsinya. Deklarasi Class Individu adalah sebagai berikut:

Public Class Individu
    Implements IComparable(Of Individu)
    Implements ICloneable

    Public posisi() As Double
    Public nilaiFungsi As Double
	Public jumlahIndividuTerpilih As Integer

    Public Sub New(ByVal dimensi As Integer)
        Me.posisi = New Double(dimensi - 1) {}
        Me.nilaiFungsi = 0.0
        Me.jumlahIndividuTerpilih = 0
    End Sub
	
	. . .
End Class


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd103


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.

Tinggalkan sebuah komentar

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