Algoritma CSA (Crow Search Algorithm) 2

Algoritma CSA (Crow Search 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 meniru tingkah laku dari burung gagak / dalam hal ini dinamakan sebagai Crow dalam melakukan migrasi. Burung gagak akan bermigrasi secara berkelompok dengan cara saling mengejar burung yang lain. Perpindahan posisi dalam proses pengejaran ini akan digunakan sebagai dasar untuk melakukan optimasi

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 jumlah Crow yang digunakan
Diasumsikan dalam kasus ini, jumlah Crow adalah 15 Crow

Const jumlahCrow As Integer = 15

* Tentukan probabilitas kesadaran crow untuk mengejar crow lain
Diasumsikan dalam kasus ini, probabilitas kesadaran crow adalah 0.2

Const probabilitasKesadaran As Double = 0.2

* Tentukan jarak terbang maksimal dari masing-masing crow
Jarak terbang menentukan seberapa cepat nilai akan berubah
Diasumsikan dalam kasus ini, jarak terbang adalah 2

Const jarakTerbang As Double = 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 = CSA(dimensi, minPosisi, maksPosisi, jumlahIterasi, jumlahIndividu, _
									probabilitasKesadaran, jarakTerbang)

Memasuki perhitungan pada fungsi CSA

* Inisialisasi individu yang digunakan sebanyak parameter jumlah individu

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

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

1a. Beri posisi acak pada masing-masing individu 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
	daftarIndividu(i).posisi(k) = (maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi
Next k
daftarIndividu(i).nilaiFungsi = hitungNilaiFungsi(daftarIndividu(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. Ambil posisi individu terbaik sebagai posisi terbaik sementara

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

* Lakukan proses pencarian posisi terbaik (poin 2)

2. Simpan posisi terbaik dari masing-masing crow

Dim daftarCrowTerbaik() As Crow = daftarCrow.Clone

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

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

3a. Tentukan indeks crow acak sebagai indeks tujuan dari masing-masing crow
Dalam perulangan ini, crow akan berusaha untuk mengejar crow lain dengan indeks tersebut

Dim daftarIndeksAcak(jumlahCrow - 1) As Double
For i As Integer = 0 To jumlahCrow - 1
	daftarIndeksAcak(i) = rnd.Next(jumlahCrow)
Next

3b. Lakukan perulangan pada masing-masing posisi dimensi dari crow (poin 3b1 - 3b3)

For i As Integer = 0 To jumlahCrow - 1
	For j As Integer = 0 To daftarCrowBaru(i).posisi.Length - 1
	. . .

3b1. Tentukan nilai acak antara 0 sampai dengan 1
Jika nilai acak tersebut berada diatas nilai probabilitas kesadaran, maka crow ini akan berpindah untuk mengejar crow tujuan
Hitung posisi crow yang baru dengan rumus:
pos baru = pos + jarak terbang * (0..1) * (pos crow terbaik - pos)
Jika nilai acak tersebut tidak berada diatas nilai probabilitas kesadaran, maka crow tidak akan mengejar crow tujuan, dan akan berpindah ke tempat lain secara acak

If rnd.NextDouble > probabilitasKesadaran Then
	daftarCrowBaru(i).posisi(j) = daftarCrow(i).posisi(j) + jarakTerbang * rnd.NextDouble * (daftarCrowTerbaik(daftarIndeksAcak(i)).posisi(j) - daftarCrow(i).posisi(j))
Else
	daftarCrowBaru(i).posisi(j) = (maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi
End If

3b2. Jika posisi Crow tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut

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

3b3. Hitung nilai fungsi pada Crow tersebut

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

3c. Lakukan perhitungan pada masing-masing crow (poin 3c1 - 3c3)

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

3c1. Masukkan posisi baru crow menggantikan posisi crow yang lama

daftarCrow(i) = daftarCrowBaru(i).Clone

3c2. Jika nilai fungsi pada Crow tersebut ternyata lebih baik dari nilai fungsi pada daftar crow terbaik,
maka ambil posisi Crow tersebut sebagai posisi terbaik pada daftar crow terbaik

If daftarCrow(i).nilaiFungsi > daftarCrowTerbaik(i).nilaiFungsi Then
	daftarCrowTerbaik(i) = daftarCrow(i).Clone
End If

3c3. Jika nilai fungsi terbaik pada Crow tersebut ternyata lebih baik dari nilai fungsi secara umum,
maka ambil posisi terbaik Crow tersebut sebagai posisi terbaik

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

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

Public Class Crow
    Implements ICloneable

    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.