Algoritma CSO (Cat Swarm Optimization)

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

Algoritma CSO (Cat 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
Digunakan 2 jenis iterasi, yaitu untuk iterasi global dan lokal
Diasumsikan dalam kasus ini, jumlah iterasi global adalah 5 kali dan jumlah iterasi lokal adalah 50 kali

Const jumlahIterasiGlobal As Integer = 5
Const jumlahIterasiLokal As Integer = 50

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

Const jumlahCat As Integer = 20

* Tentukan persentase Cat yang memiliki status Seeker
Nantinya cat akan dibagi menjadi 2 status, yaitu Seeker dan Tracker
Diasumsikan dalam kasus ini, persentase seeker adalah 0.3

Const persentaseSeeker As Double = 0.3

* Tentukan batas kecepatan untuk perpindahan posisi dalam setiap proses
Diasumsikan dalam kasus ini nilai minimal dan nilai maksimal adalah 10% dari masing-masing batas nilai pada tiap-tiap dimensi
Sebagai contoh kasus, apabila nilai minimal dan maksimal dari sebuah dimensi adalah -2 dan 2,
Maka nilai minimalnya adalah -(2-(-2))/10 = -0.4, dan nilai maksimalnya adalah (2-(-2))/10 = 0.4

Dim minKecepatan As Double = (maksPosisi - minPosisi) / 10
Dim maksKecepatan As Double = -(maksPosisi - minPosisi) / 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 CatTerbaik As Cat = CSO(dimensi, minPosisi, maksPosisi, jumlahIterasiGlobal, jumlahIterasiLokal, jumlahCat, _
							persentaseSeeker, minKecepatan, maksKecepatan)

Memasuki perhitungan pada fungsi CSO

1. Tentukan bobot inertia (w), bobot kognitif (c1), dan bobot sosial (c2)
Nilai acuan untuk masing-masing variabel dapat dilihat di http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=00870279
Diasumsikan dalam kasus ini, nilai bobot tersebut akan mengikuti nilai acuan yang sudah ada

Const w As Double = 0.729
Const c1 As Double = 1.49445
Const c2 As Double = 1.49445

2. Hitung jumlah cat dengan status seeker dan tracker
Seeker adalah cat yang mencari posisi baru untuk menemukan solusi yang lebih baik
Tracker adalah cat yang sifatnya berusaha untuk menuju pada cat terbaik

Dim jumlahSeeker As Integer = Math.Round(persentaseSeeker * jumlahCat)
Dim jumlahTracker As Integer = jumlahCat - jumlahSeeker

3. Lakukan perhitungan sebanyak jumlah iterasi global (poin 3a -3d)

For iterasiGlobal As Integer = 0 To jumlahIterasiGlobal - 1
. . .

3a. Tentukan indeks permutasi acak dari daftar cat
Indeks ini nantinya digunakan untuk menentukan status dari cat
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Dim daftarIdxAcak() As Integer = permutasiAcak(jumlahCat)

* Gunakan fungsi ini untuk melakukan permutasi acak sebanyak input nilai

Public Function permutasiAcak(ByVal x As Integer) As Integer()
	Dim hasil(x - 1) As Integer

	'Nilai pertama adalah terurut sesuai urutan loop
	For i = 0 To hasil.Length - 1
		hasil(i) = i
	Next i

	'Teknik pengacakan titik menggunakan Fisher-Yates (Knuth) 
	For i = 0 To hasil.Length - 1
		Dim r As Integer = rnd.Next(i, hasil.Length)
		Dim temp As Integer = hasil(r)
		hasil(r) = hasil(i)
		hasil(i) = temp
	Next i

	Return hasil
End Function

3b. Lakukan inisialisasi Cat yang digunakan sebanyak parameter jumlah Cat (poin 3b1 – 3b4)

3b1. Beri nilai acak untuk posisi dan kecepatan pada masing-masing Cat sebanyak jumlah dimensi
nilai acak ini harus berada di dalam batas yang diperbolehkan

For k As Integer = 0 To dimensi - 1
	daftarCat(i).posisi(k) = (maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi
	daftarCat(i).kecepatan(k) = rnd.NextDouble() - (1 - maksKecepatan)
Next k

3b2. Beri nilai awal untuk status dari cat tersebut
Sehingga populasi akan dibagi menjadi 2, yaitu cat yang berstatus seeker dan cat yang berstatus tracker

For k As Integer = 0 To daftarIdxAcak.Length - 1
	If i = daftarIdxAcak(k) Then
		If k <= jumlahSeeker Then
			daftarCat(i).status = "Seeker"
		Else
			daftarCat(i).status = "Tracker"
		End If
		Exit For
	End If
Next

3b3. Hitung nilai fungsi pada posisi tersebut

daftarCat(i).nilaiFungsi = hitungNilaiFungsi(daftarCat(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

3b4. Ambil posisi Cat terbaik sebagai posisi terbaik sementara

If daftarCat(i).nilaiFungsi > CatTerbaikSementara.nilaiFungsi Then
	CatTerbaikSementara = daftarCat(i).Clone
End If

* Lakukan proses pencarian posisi terbaik

3c. Lakukan proses perhitungan sebanyak jumlah iterasi (poin 3c1 - 3c3)

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

3c1. Lakukan perulangan pada masing-masing Cat (poin 3c1a - 3c1e)

3c1a. Lakukan perhitungan pada masing-masing posisi dimensi cat tersebut
Hitung kecepatan perpindahan posisi yang baru dengan rumus:
v baru = (w * v skrg) + (c2 * r2 * (posisi cat terbaik - posisi cat skrg))
Jika kecepatan yang baru ternyata diluar batas minKecepatan dan maksKecepatan, maka kembalikan nilainya agar masuk dalam batas kecepatan

For j As Integer = 0 To daftarCat(i).posisi.Length - 1
	r1 = rnd.NextDouble()
	r2 = rnd.NextDouble()

	kecepatanBaru(j) = (w * daftarCat(i).kecepatan(j)) + (c2 * r2 * (CatTerbaikSementara.posisi(j) - daftarCat(i).posisi(j)))
	If kecepatanBaru(j) < minKecepatan Then
		kecepatanBaru(j) += maksKecepatan
	ElseIf kecepatanBaru(j) > maksKecepatan Then
		kecepatanBaru(j) += minKecepatan
	End If
Next

3c1b. Jika status cat adalah tracker,
maka tentukan nilai acak
jika nilai acak ini lebih dari fungsi sigmoid dari kecepatan yang baru,
maka posisi cat ini akan berpindah pada cat terbaik sementara

If daftarCat(i).status = "Tracker" Then
	For j As Integer = 0 To daftarCat(i).posisi.Length - 1
		If rnd.NextDouble() < Sigmoid(kecepatanBaru(j)) Then
			daftarCat(i).posisi(j) = CatTerbaikSementara.posisi(j)
		End If
	Next
    . . .

* Gunakan fungsi ini untuk menghitung nilai fungsi Sigmoid, yang diperoleh dengan rumus:
f(x) = 1.0 / (1.0 + Exp(-x))

Private Function Sigmoid(ByVal x As Double) As Double
	If x < -45.0 Then
		Return 0.0
	ElseIf x > 45.0 Then
		Return 1.0
	Else
		Return 1.0 / (1.0 + Math.Exp(-x))
	End If
End Function

3c1c. Jika status cat adalah seeker,
Lakukan update posisi yang baru dengan cara posisi lama + kecepatan baru
Jika posisi yang baru ternyata diluar batas minPosisi dan maksPosisi, maka kembalikan posisinya agar masuk dalam batas

. . .
ElseIf daftarCat(i).status = "Seeker" Then
	For j As Integer = 0 To daftarCat(i).posisi.Length - 1
		daftarCat(i).posisi(j) += kecepatanBaru(j)

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

3c1d. Hitung nilai fungsi pada posisi tersebut

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

3c1e. Jika nilai fungsi cat ini ternyata lebih baik dari nilai fungsi cat terbaik,
maka ambil posisi yang baru sebagai posisi cat terbaik sementara

If daftarCat(i).nilaiFungsi > CatTerbaikSementara.nilaiFungsi Then
	CatTerbaikSementara = daftarCat(i).Clone
End If

3c2. Tentukan indeks permutasi acak dari daftar cat yang baru

Dim daftarIdxAcak2() As Integer = permutasiAcak(jumlahCat)

3c3. Lakukan pengacakan status cat untuk digunakan pada perhitungan berikutnya.

For i As Integer = 0 To jumlahCat - 1
	For k As Integer = 0 To daftarIdxAcak2.Length - 1
		If i = daftarIdxAcak2(k) Then
			If k <= jumlahSeeker Then
				daftarCat(i).status = "Seeker"
			Else
				daftarCat(i).status = "Tracker"
			End If
			Exit For
		End If
	Next
Next

3d. Jika nilai fungsi cat terbaik sementara ternyata lebih baik dari nilai fungsi cat terbaik,
maka ambil posisi cat terbaik sementara sebagai posisi terbaik

If CatTerbaikSementara.nilaiFungsi > CatTerbaik.nilaiFungsi Then
	CatTerbaik = CatTerbaikSementara.Clone
End If

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

Public Class Cat
    Implements ICloneable

    Public posisi() As Double
    Public kecepatan() As Double
    Public status As String
    Public nilaiFungsi As Double

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

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


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd148


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 *