Algoritma BSA (Bird Swarm Algorithm)


Algoritma BSA (Bird Swarm 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.



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

Const jumlahBird As Integer = 20

* Tentukan parameter koefisien akselerasi kognitif c1, koefisien akselerasi sosial c2, koefisien kewaspadaan langsung a1, koefisien kewaspadaan tidak langsung a2 sebagai parameter untuk menghitung perpindahan posisi
Diasumsikan dalam kasus ini, c1 dan c2 bernilai 1.5, dan a1 dan a2 bernilai 1

Const c1 As Double = 1.5
Const c2 As Double = 1.5
Const a1 As Double = 1
Const a2 As Double = 1

* Tentukan waktu siklus untuk melakukan update status dari masing-masing bird
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 = BSA(dimensi, minPosisi, maksPosisi, jumlahIterasi, jumlahBird, _
									c1, c2, a1, a2, waktuSiklus)

Memasuki perhitungan pada fungsi BSA

* Inisialisasi bird yang digunakan sebanyak parameter jumlah bird

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

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

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

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

2. Simpan populasi awal untuk nantinya digunakan dalam perhitungan

Dim daftarBirdAwal(jumlahBird - 1) As Bird
For i As Integer = 0 To jumlahBird - 1
	daftarBirdAwal(i) = daftarBird(i).Clone
Next

* Lakukan proses pencarian posisi terbaik

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

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

* Lakukan perhitungan berikut untuk mengupdate status bird pada populasi

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

3a. Jika memenuhi siklus waktu tersebut, maka semua bird hanya akan memiliki 2 pilihan,
yaitu untuk pergi mencari makanan atau hanya berjaga-jaga saja (poin 3a1 - 3a4)

3a1. Hitung rata-rata posisi pada masing-masing dimensi, dan total nilai fungsi dari semua bird

Dim rata2Posisi(dimensi - 1) As Double
Dim totalNilaiFungsi As Double = 0
For i As Integer = 0 To jumlahBird - 1
	For j As Integer = 0 To daftarBirdAwal(i).posisi.Length - 1
		rata2Posisi(j) += daftarBirdAwal(i).posisi(j)
	Next

	totalNilaiFungsi += daftarBirdAwal(i).nilaiFungsi
Next

For j As Integer = 0 To dimensi - 1
	rata2Posisi(j) /= jumlahBird
Next

3a2. Hitung probabilitas bird untuk mencari makanan

Dim probMencariMakanan As Double = rnd.NextDouble * 0.2 + 0.8

* Lakukan proses perpindahan posisi bird

3a3. Jika nilai acak adalah kurang dari nilai probabilitas mencari makanan
maka bird ini akan melakukan proses pencarian makanan
bird akan bergerak menuju sumber makanan terbaik yang telah ditemukan selama ini
Jika posisi bird tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut
Kemudian Hitung nilai fungsi dari posisi yang baru

If rnd.NextDouble < probMencariMakanan Then
	For j As Integer = 0 To daftarBird(i).posisi.Length - 1
		daftarBird(i).posisi(j) += c1 * rnd.NextDouble * (PosisiTerbaik(j) - daftarBird(i).posisi(j)) _
			+ c2 * rnd.NextDouble * (daftarBirdAwal(i).posisi(j) - daftarBird(i).posisi(j))

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

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

3a4. Jika kondisi di atas tidak terpenuhi,
maka bird ini akan melakukan proses berjaga-jaga saja
bird akan bergerak untuk melindungi sumber makanan dari bird lain
Jika posisi bird tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut
Kemudian Hitung nilai fungsi dari posisi yang baru

. . .
Else
	Dim idxBirdLain As Integer = i
	While i = idxBirdLain
		idxBirdLain = rnd.Next(jumlahBird)
	End While

	For j As Integer = 0 To daftarBird(i).posisi.Length - 1
		daftarBird(i).posisi(j) += rnd.NextDouble * (rata2Posisi(j) - daftarBird(i).posisi(j)) * a1 _
			* Math.Exp(-daftarBirdAwal(i).nilaiFungsi / totalNilaiFungsi * jumlahBird) _
			+ a2 * (rnd.NextDouble * 2 - 1) * (daftarBirdAwal(idxBirdLain).posisi(j) - daftarBird(i).posisi(j)) _
			* Math.Exp(-(daftarBirdAwal(idxBirdLain).nilaiFungsi - daftarBirdAwal(i).nilaiFungsi) / (Math.Abs(daftarBirdAwal(idxBirdLain).nilaiFungsi - daftarBirdAwal(i).nilaiFungsi)) * daftarBirdAwal(idxBirdLain).nilaiFungsi / totalNilaiFungsi * jumlahBird)

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

	daftarBird(i).nilaiFungsi = hitungNilaiFungsi(daftarBird(i).posisi)
End If

3b. Jika iterasi bukan merupakan waktu untuk mengupdate status bird,
maka masing-masing bird akan memiliki 4 pilihan tergantung dari situasi populasi yang ada (poin 3b1 - 3b5)

* Proses tak tertulis yang dilakukan adalah membagi populasi menjadi 2 kelompok tanpa memandang posisi dan nilai fungsinya
Sehingga kelompok 1 berisi bird dengan indeks 1 s/d n/2
dan kelompok 2 berisi bird dengan indeks n/2+1 s/d n

3b1. Cari indeks bird yang memiliki nilai fungsi paling tinggi dan paling rendah

Dim idxMinNilaiFungsi As Integer = -1
Dim idxMaksNilaiFungsi As Integer = -1
Dim minNilaiFungsi As Double = Double.MaxValue
Dim maksNilaiFungsi As Double = Double.MinValue

For i As Integer = 0 To jumlahBird - 1
	If daftarBirdAwal(i).nilaiFungsi < minNilaiFungsi Then
		minNilaiFungsi = daftarBirdAwal(i).nilaiFungsi
		idxMinNilaiFungsi = i
	End If
	If daftarBirdAwal(i).nilaiFungsi > maksNilaiFungsi Then
		maksNilaiFungsi = daftarBirdAwal(i).nilaiFungsi
		idxMaksNilaiFungsi = i
	End If
Next

3b2. 'Tentukan pilihan sesuai situasi populasi yang tersedia
Jika indeks bird dengan nilai fungsi tertinggi dan indeks bird dengan nilai fungsi terendah berada pada kelompok 1, maka termasuk sebagai pilihan 1
Jika indeks bird dengan nilai fungsi tertinggi berada pada kelompok 2 dan indeks bird dengan nilai fungsi terendah berada pada kelompok 1, maka termasuk sebagai pilihan 2
Jika indeks bird dengan nilai fungsi tertinggi berada pada kelompok 1 dan indeks bird dengan nilai fungsi terendah berada pada kelompok 2, maka termasuk sebagai pilihan 3
Jika indeks bird dengan nilai fungsi tertinggi dan indeks bird dengan nilai fungsi terendah berada pada kelompok 2, maka termasuk sebagai pilihan 4

Dim pilihan As Integer = 0
If (idxMinNilaiFungsi < jumlahBird / 2) AndAlso (idxMaksNilaiFungsi < jumlahBird / 2) Then pilihan = 1
If (idxMinNilaiFungsi > jumlahBird / 2) AndAlso (idxMaksNilaiFungsi < jumlahBird / 2) Then pilihan = 2
If (idxMinNilaiFungsi < jumlahBird / 2) AndAlso (idxMaksNilaiFungsi > jumlahBird / 2) Then pilihan = 3
If (idxMinNilaiFungsi > jumlahBird / 2) AndAlso (idxMaksNilaiFungsi > jumlahBird / 2) Then pilihan = 4

3b3. Hitung nilai koefisien posisi untuk digunakan dalam proses perpindahan posisi pada salah satu pilihan

Dim koefisienPosisi As Double = rnd.NextDouble * 0.4 + 0.5

3b4. Jika termasuk dalam pilihan 1 atau pilihan 2, maka lakukan perhitungan berikut (poin 3b4a -3b4c)

If pilihan < 3 Then
. . .

3b4a. Lakukan perpindahan posisi pada semua bird pada kelompok 2 dengan pergerakan secara acak
Jika posisi bird tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut
Kemudian Hitung nilai fungsi dari posisi yang baru

For i As Integer = jumlahBird / 2 To jumlahBird - 1
	For j As Integer = 0 To daftarBird(i).posisi.Length - 1
		daftarBird(i).posisi(j) *= (HitungDistribusiNormalAcak(rnd))

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

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

3b4b. Jika termasuk dalam pilihan 1, maka Lakukan perpindahan posisi bird dengan nilai fungsi terendah dengan pergerakan secara acak
Jika posisi bird tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut
Kemudian Hitung nilai fungsi dari posisi yang baru

If pilihan = 1 Then
	For j As Integer = 0 To daftarBird(idxMinNilaiFungsi).posisi.Length - 1
		daftarBird(idxMinNilaiFungsi).posisi(j) *= (HitungDistribusiNormalAcak(rnd))

		If daftarBird(idxMinNilaiFungsi).posisi(j) < minPosisi Then
			daftarBird(idxMinNilaiFungsi).posisi(j) = minPosisi
		ElseIf daftarBird(idxMinNilaiFungsi).posisi(j) > maksPosisi Then
			daftarBird(idxMinNilaiFungsi).posisi(j) = maksPosisi
		End If
	Next

	daftarBird(idxMinNilaiFungsi).nilaiFungsi = hitungNilaiFungsi(daftarBird(idxMinNilaiFungsi).posisi)
End If

3b4c. Lakukan perhitungan pada semua bird pada kelompok 1
Jika termasuk dalam pilihan 2 dan bukan merupakan bird dengan nilai fungsi terendah,
maka cari bird lain dalam kelompok 2 dan lakukan perpindahan posisi mendekati posisi bird dalam kelompok 2 tersebut
Jika posisi bird tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut
Kemudian Hitung nilai fungsi dari posisi yang baru

For i As Integer = 0 To jumlahBird / 2 - 1
	If pilihan = 2 And idxMinNilaiFungsi <> i Then
		Dim idxBirdLain As Integer = rnd.Next(jumlahBird / 2, jumlahBird)

		For j As Integer = 0 To daftarBird(i).posisi.Length - 1
			daftarBird(i).posisi(j) += (daftarBirdAwal(idxBirdLain).posisi(j) - daftarBird(i).posisi(j) * koefisienPosisi)

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

		daftarBird(i).nilaiFungsi = hitungNilaiFungsi(daftarBird(i).posisi)
	End If
Next

3b5. Jika termasuk dalam pilihan 3 atau pilihan 4, maka lakukan perhitungan berikut (poin 3b5a -3b5c)

3b5a. Lakukan perpindahan posisi pada semua bird pada kelompok 1 dengan pergerakan secara acak
Jika posisi bird tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut
Kemudian Hitung nilai fungsi dari posisi yang baru

For i As Integer = 0 To jumlahBird / 2 - 1
	For j As Integer = 0 To daftarBird(i).posisi.Length - 1
		daftarBird(i).posisi(j) *= (HitungDistribusiNormalAcak(rnd))

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

	daftarBird(i).nilaiFungsi = hitungNilaiFungsi(daftarBird(i).posisi)
Next

3b5b. Jika termasuk dalam pilihan 4, maka Lakukan perpindahan posisi bird dengan nilai fungsi terendah dengan pergerakan secara acak
Jika posisi bird tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut
Kemudian Hitung nilai fungsi dari posisi yang baru

If pilihan = 4 Then
	For j As Integer = 0 To daftarBird(idxMinNilaiFungsi).posisi.Length - 1
		daftarBird(idxMinNilaiFungsi).posisi(j) *= (HitungDistribusiNormalAcak(rnd))

		If daftarBird(idxMinNilaiFungsi).posisi(j) < minPosisi Then
			daftarBird(idxMinNilaiFungsi).posisi(j) = minPosisi
		ElseIf daftarBird(idxMinNilaiFungsi).posisi(j) > maksPosisi Then
			daftarBird(idxMinNilaiFungsi).posisi(j) = maksPosisi
		End If
	Next

	daftarBird(idxMinNilaiFungsi).nilaiFungsi = hitungNilaiFungsi(daftarBird(idxMinNilaiFungsi).posisi)
End If

3b5c. Lakukan perhitungan pada semua bird pada kelompok 2
Jika termasuk dalam pilihan 3 dan bukan merupakan bird dengan nilai fungsi terendah,
maka cari bird lain dalam kelompok 1 dan lakukan perpindahan posisi mendekati posisi bird dalam kelompok 1 tersebut
Jika posisi bird tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut
Kemudian Hitung nilai fungsi dari posisi yang baru

For i As Integer = jumlahBird / 2 To jumlahBird - 1
	If pilihan = 3 And idxMinNilaiFungsi <> i Then
		Dim idxBirdLain As Integer = rnd.Next(jumlahBird / 2 + 1)

		For j As Integer = 0 To daftarBird(i).posisi.Length - 1
			daftarBird(i).posisi(j) += (daftarBirdAwal(idxBirdLain).posisi(j) - daftarBird(i).posisi(j) * koefisienPosisi)

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

		daftarBird(i).nilaiFungsi = hitungNilaiFungsi(daftarBird(i).posisi)
	End If
Next

3c. Lakukan pengecekan nilai fungsi dari setiap bird
Jika ditemukan bird dengan nilai fungsi yang lebih baik dari bird awal, maka ambil posisi bird ini menggantikan posisi bird awal
Jika nilai fungsi terbaik pada bird tersebut ternyata lebih baik dari nilai fungsi secara umum, maka ambil posisi terbaik bird tersebut sebagai posisi terbaik

For i As Integer = 0 To jumlahBird - 1
	If daftarBird(i).nilaiFungsi > daftarBirdAwal(i).nilaiFungsi Then
		daftarBirdAwal(i) = Nothing
		daftarBirdAwal(i) = daftarBird(i).Clone

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

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

Public Class Bird
    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

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


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd150


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 *