Algoritma CSO (Chicken Swarm Optimization)

Entri ini telah di terbitkan di Algoritma Optimasi dan telah ditandai .net algoritma chicken swarm optimization cso vb visual basic on sebesar

Algoritma CSO (Chicken Swarm 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.



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

Const jumlahIterasi As Integer = 100

* Tentukan jumlah Chicken yang digunakan
Diasumsikan dalam kasus ini, jumlah chicken adalah 20 chicken

Const jumlahChicken As Integer = 20

* Tentukan persentase ayam jantan, ayam betina, dan calon induk betina daripada jumlah populasi
Diasumsikan dalam kasus ini, persentase ayam jantan adalah 0.15, ayam betina adalah 0.7, dan induk betina adalah 0.5

Const persentaseJantan As Double = 0.15
Const persentaseBetina As Double = 0.7
Const persentaseIndukBetina As Double = 0.5

* Tentukan waktu siklus untuk melakukan update status dari masing-masing chicken
Diasumsikan dalam kasus ini, waktu siklus adalah 10

Const waktuSiklus As Integer = 10


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

Dim posisiTerbaik() As Double = CSO(dimensi, minPosisi, maksPosisi, jumlahIterasi, jumlahChicken, _
									persentaseJantan, persentaseBetina, persentaseIndukBetina, waktuSiklus)

Memasuki perhitungan pada fungsi CSO

* Hitung jumlah ayam jantan, jumlah ayam betina, jumlah anak ayam, dan jumlah induk betina dalam populasi

Dim jumlahJantan As Integer = Math.Round(persentaseJantan * jumlahChicken)
Dim jumlahBetina As Integer = Math.Round(persentaseBetina * jumlahChicken)
Dim jumlahAnak As Integer = jumlahChicken - jumlahJantan - jumlahBetina
Dim jumlahIndukBetina As Integer = Math.Round(persentaseIndukBetina * jumlahBetina)

* Inisialisasi chicken yang digunakan sebanyak parameter jumlah chicken

1. Lakukan perulangan sebanyak jumlah chicken (poin 1a – 1c)

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

1a. Beri posisi acak pada masing-masing Chicken 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
	daftarChicken(i).posisi(k) = (maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi
Next k
daftarChicken(i).nilaiFungsi = hitungNilaiFungsi(daftarChicken(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. Simpan indeks masing-masing chicken sebelum nantinya dilakukan proses pengurutan

daftarChicken(i).idxAwal = i

1c. Ambil posisi Chicken terbaik sebagai posisi terbaik sementara

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

2. Simpan populasi awal untuk nantinya digunakan dalam perhitungan

Dim daftarChickenAwal(jumlahChicken - 1) As Chicken
For i As Integer = 0 To jumlahChicken - 1
	daftarChickenAwal(i) = daftarChicken(i).Clone
Next

* Lakukan proses pencarian posisi terbaik

3. Lakukan proses perhitungan sebanyak jumlah iterasi (poin 3a – 3e)

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

3a. Lakukan perhitungan berikut untuk mengupdate status chicken pada populasi (poin 3a1 - 3a3)
Ini merupakan simulasi dari perkembangan populasi chicken
Tentu saja akan ada ayam yang mati, kemudian anak ayam menjadi induk jantan / betina, dan memiliki pasangan dan anak ayam sendiri

If (iterasi = 1) Or (iterasi Mod waktuSiklus = 0) Then
. . .

3a1. Lakukan pengurutan populasi sehingga populasi akan terurut dari ayam terbaik sampai pada ayam terburuk
Asumsi yang digunakan adalah ayam jantan akan selalu lebih baik dari ayam betina, dan ayam betina selalu lebih baik dari anak ayam
Sehingga pengurutan dilakukan untuk menentukan ayam mana saja yang termasuk ayam jantan, ayam betina, dan anak ayam

Array.Sort(daftarChickenAwal)

* Dengan menggunakan asumsi sebelumnya maka
indeks pertama s/d jumlah jantan adalah ayam jantan
indeks jumlah jantan s/d jumlah jantan + jumlah betina adalah ayam betina
indeks sisanya adalah anak ayam

3a2. Untuk masing-masing induk betina, tentukan indeks ayam jantan sebagai pasangan induk betina

For i As Integer = 0 To jumlahBetina - 1
	daftarIdxPasanganInduk(i) = rnd.Next(jumlahJantan)
Next

3a3. Untuk masing-masing anak ayam, tentukan indeks induk betina sebagai induk dari anak ayam

For i As Integer = 0 To jumlahAnak - 1
	daftarIdxInduk(i) = rnd.Next(jumlahJantan, jumlahJantan + jumlahBetina)
Next

3b. Lakukan perhitungan untuk mengupdate posisi ayam jantan (poin 3b1 - 3b4)

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

3b1. Tentukan indeks jantan selain indeks yang sedang dihitung

Dim idxJantanLain As Integer = i
While i = idxJantanLain
	idxJantanLain = rnd.Next(jumlahJantan)
End While

3b2. Hitung nilai selisih antara nilai fungsi indeks ayam jantan terpilih dengan indeks ayam jantan yang lain

Dim sigma As Double
If daftarChickenAwal(i).nilaiFungsi > daftarChickenAwal(idxJantanLain).nilaiFungsi Then
	sigma = 1
Else
	sigma = Math.Exp((daftarChickenAwal(idxJantanLain).nilaiFungsi - daftarChickenAwal(i).nilaiFungsi) / (Math.Abs(daftarChickenAwal(i).nilaiFungsi)))
End If

3b3. Lakukan perpindahan posisi ayam jantan
Jika posisi Chicken tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut

For j As Integer = 0 To daftarChickenAwal(i).posisi.Length - 1
	daftarChicken(idxAwal).posisi(j) = daftarChickenAwal(i).posisi(j) * (1 + sigma * HitungDistribusiNormalAcak(rnd))

	If daftarChicken(idxAwal).posisi(j) < minPosisi Then
		daftarChicken(idxAwal).posisi(j) = minPosisi
	ElseIf daftarChicken(idxAwal).posisi(j) > maksPosisi Then
		daftarChicken(idxAwal).posisi(j) = maksPosisi
	End If
Next

* 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

3b4. Hitung nilai fungsi dari posisi yang baru

daftarChicken(idxAwal).nilaiFungsi = hitungNilaiFungsi(daftarChicken(idxAwal).posisi)

3c. Lakukan perhitungan untuk mengupdate posisi ayam betina (poin 3c1 - 3c4)

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

3c1. Tentukan indeks jantan selain pasangan dari induk betina
Ini ditujukan bahwa ayam betina mampu mencuri makanan yang didapatkan oleh ayam jantan pada grup lain.

Dim idxPasanganInduk As Integer = daftarIdxPasanganInduk(i)
Dim idxJantanLain As Integer = daftarIdxPasanganInduk(i)
While i = idxJantanLain
	idxJantanLain = rnd.Next(jumlahJantan)
End While

3c2. Hitung paramter c1 dan c2 untuk digunakan dalam perpindahan posisi chicken berikutnya

Dim c1 As Double = Math.Exp((daftarChickenAwal(jumlahJantan + i).nilaiFungsi - daftarChickenAwal(idxPasanganInduk).nilaiFungsi) / (Math.Abs(daftarChickenAwal(jumlahJantan + i).nilaiFungsi)))
Dim c2 As Double = Math.Exp(-daftarChickenAwal(jumlahJantan + i).nilaiFungsi + daftarChickenAwal(idxJantanLain).nilaiFungsi)

3c3. Lakukan perpindahan posisi ayam betina
Jika posisi Chicken tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut

For j As Integer = 0 To daftarChickenAwal(jumlahJantan + i).posisi.Length - 1
	daftarChicken(idxAwal).posisi(j) = daftarChickenAwal(jumlahJantan + i).posisi(j) + (daftarChickenAwal(idxPasanganInduk).posisi(j) - daftarChickenAwal(jumlahJantan + i).posisi(j)) * c1 * HitungDistribusiNormalAcak(rnd) _
		+ (daftarChickenAwal(idxJantanLain).posisi(j) - daftarChickenAwal(jumlahJantan + i).posisi(j)) * c2 * HitungDistribusiNormalAcak(rnd)

	If daftarChicken(idxAwal).posisi(j) < minPosisi Then
		daftarChicken(idxAwal).posisi(j) = minPosisi
	ElseIf daftarChicken(idxAwal).posisi(j) > maksPosisi Then
		daftarChicken(idxAwal).posisi(j) = maksPosisi
	End If
Next

3c4. Hitung nilai fungsi dari posisi yang baru

daftarChicken(idxAwal).nilaiFungsi = hitungNilaiFungsi(daftarChicken(idxAwal).posisi)

3d. Lakukan perhitungan untuk mengupdate posisi anak ayam (poin 3d1 - 3d4)

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

3d1. Tentukan indeks induk betina dari anak ayam tersebut

Dim idxInduk As Integer = daftarIdxInduk(i)

3d2. Hitung nilai kedekatan anak ayam pada masing-masing induk
Karena asumsi yang digunakan adalah anak ayam akan selalu mengikuti induk kemanapun induk pergi

Dim kedekatanAnakPadaInduk As Double = rnd.NextDouble() * 0.4 + 0.5

3d3. Lakukan perpindahan posisi anak ayam
Jika posisi Chicken tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut

For j As Integer = 0 To daftarChickenAwal(jumlahJantan + jumlahBetina + i).posisi.Length - 1
	daftarChicken(idxAwal).posisi(j) = daftarChickenAwal(jumlahJantan + jumlahBetina + i).posisi(j) + (daftarChickenAwal(idxInduk).posisi(j) - daftarChickenAwal(jumlahJantan + jumlahBetina + i).posisi(j)) * kedekatanAnakPadaInduk

	If daftarChicken(idxAwal).posisi(j) < minPosisi Then
		daftarChicken(idxAwal).posisi(j) = minPosisi
	ElseIf daftarChicken(idxAwal).posisi(j) > maksPosisi Then
		daftarChicken(idxAwal).posisi(j) = maksPosisi
	End If
Next

3d4. Hitung nilai fungsi dari posisi yang baru

daftarChicken(idxAwal).nilaiFungsi = hitungNilaiFungsi(daftarChicken(idxAwal).posisi)

3e. Lakukan update populasi chicken awal
Jika ditemukan chicken dengan nilai fungsi yang lebih baik dari chicken awal, maka ambil posisi chicken ini menggantikan posisi chicken awal
Jika nilai fungsi terbaik pada Chicken tersebut ternyata lebih baik dari nilai fungsi secara umum, maka ambil posisi terbaik Chicken tersebut sebagai posisi terbaik

For i As Integer = 0 To jumlahChicken - 1
	If daftarChicken(i).nilaiFungsi > daftarChickenAwal(i).nilaiFungsi Then
		daftarChickenAwal(i) = Nothing
		daftarChickenAwal(i) = daftarChicken(i).Clone

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

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

Public Class Chicken
    Implements IComparable(Of Chicken)
    Implements ICloneable

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

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

    'Gunakan fungsi ini untuk melakukan pengurutan dari nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)
    Public Function CompareTo(ByVal chickenLain As Chicken) As Integer Implements IComparable(Of Chicken).CompareTo
        If Me.nilaiFungsi > chickenLain.nilaiFungsi Then
            Return -1
        ElseIf Me.nilaiFungsi < chickenLain.nilaiFungsi Then
            Return 1
        Else
            Return 0
        End If
    End Function

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


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd149


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 *