Algoritma PSO (Particle Swarm Optimization) adalah salah satu algoritma optimasi yang dapat digunakan untuk pengambilan keputusan. Tetapi bisa juga digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian posisi dengan pengembalian nilai fungsi minimal. .
Particle Swarm Optimization adalah teknik optimasi dengan cara menghitung secara terus menerus calon solusi dengan menggunakan suatu acuan kualitas. Algoritma ini mengoptimasi permasalahan dengan cara menggerakan partikel / calon solusi di dalam ruang permasalahan menggunakan fungsi tertentu untuk posisi dan kecepatan dari partikel. Pergerakan partikel dipengaruhi oleh solusi terbaik partikel tersebut, dan solusi terbaik secara umum yang didapatkan dari partikel lain. Sekumpulan partikel ini dinamakan swarm, dan pada akhirnya swarm ini akan bergerak menuju kepada solusi terbaik.
Salah satu pengembangan algoritma ini adalah algoritma MSO (Multi Swarm Optimization), dimana digunakan lebih dari 1 swarm untuk menyelesaikan permasalahan.



Diasumsikan ada sebaran titik 3 dimensi, yaitu dimensi x, y, z
Masing-masing dimensi memiliki sebuah konstanta dan batas rentang titik yang dapat digunakan
Contoh data pada masing-masing dimensi adalah sebagai berikut

Dimensi konstanta batas minimal batas maksimal
x 3.2 10 50
y 3 30 80
z 2.5 50 150

Contoh data awal adalah sebagai berikut:

Dim data(2)() As Double
data(0) = New Double() {3.2, 10, 50}
data(1) = New Double() {3, 30, 80}
data(2) = New Double() {2.5, 50, 150}

Nilai fungsi yang diketahui adalah dengan rumus f(x, y, z) = (kx * x^2) + (ky * y^2) + (kz * z^2)
Tentukan posisi dimana fungsi tersebut mengembalikan nilai minimal
Dengan batasan nilai bahwa x + y + z harus bernilai 210



Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan dimensi permasalahan
Diasumsikan dalam kasus ini, dimensi bernilai 3 karena ada 3 dimensi yang akan dicari solusinya

Const dimensi As Integer = 3

* Tentukan jumlah partikel yang digunakan dalam perhitungan
Diasumsikan dalam kasus ini, jumlah partikel yang digunakan adalah 10 partikel

Const jumlahPartikel As Integer = 10

* Tentukan jumlah iterasi yang digunakan oleh setiap partikel untuk melakukan proses
Diasumsikan dalam kasus ini, jumlah iterasi yang digunakan adalah 100 kali

Const jumlahIterasi As Integer = 100

* Tentukan total posisi yang harus dicapai
Semua solusi yang ditemukan oleh masing-masing individu harus berjumlah sebanyak variabel ini
Diasumsikan dalam kasus ini, total nilai yang harus dicapai adalah 210

Const totalPosisi As Integer = 210

* Tentukan batas kecepatan untuk perpindahan posisi partikel 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 10 dan 50,
Maka nilai minimalnya adalah -(50-10)/10 = -4, dan nilai maksimalnya adalah (50-10)/10 = 4

Dim minKecepatan(dimensi - 1) As Double
Dim maksKecepatan(dimensi - 1) As Double

For i As Integer = 0 To dimensi - 1
	minKecepatan(i) = -(data(i)(2) - data(i)(1)) / 10
	maksKecepatan(i) = (data(i)(2) - data(i)(1)) / 10
Next

Langkah-langkah penggunaan algoritma ini adalah

1. Lakukan Inisialisasi data pada masing-masing partikel

1a. Inisialisasi semua posisi partikel awal dengan posisi acak
Setiap dimensi memiliki batas minimal dan maksimal sendiri-sendiri, sesuai pada isian parameter data

jumlahPosisi = 0
For j As Integer = 0 To posisi.Length - 1
	posisi(j) = rnd.Next(data(j)(1), data(j)(2))
	jumlahPosisi += posisi(j)
Next j

1b. Perlu diingat bahwa jumlah posisi diatas belum tentu sesuai dengan parameter totalPosisi
Oleh karena itu, lakukan penyesuaian posisi agar jumlah posisi selalu bernilai sama dengan parameter totalPosisi

Dim selisih As Integer = totalPosisi - jumlahPosisi
Dim idx As Integer = rnd.Next(dimensi)
Dim posisiBaru As Integer = posisi(idx) + selisih
If posisiBaru < data(idx)(1) Then Continue Do
If posisiBaru > data(idx)(2) Then Continue Do
jumlahPosisi = jumlahPosisi - posisi(idx) + posisiBaru
posisi(idx) = posisiBaru

1c. Inisialisasi nilai kecepatan semua partikel awal dengan nilai kecepatan acak

Dim kecepatanAcak(dimensi - 1) As Double
For j As Integer = 0 To kecepatanAcak.Length - 1
	Dim lo As Double = -1.0 * Math.Abs(data(j)(2) - data(j)(1)) / 10
	Dim hi As Double = Math.Abs(data(j)(2) - data(j)(1)) / 10
	kecepatanAcak(j) = (hi - lo) * rnd.NextDouble() + lo
Next j

1d. Hitung nilai fitness dari posisi acak tersebut
Karena tujuan permasalahan adalah mencari nilai minimal, maka semakin rendah nilai fungsi akan semakin baik
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Dim fitness As Double = HitungFitness(posisi, data)

* Gunakan fungsi ini untuk menghitung nilai fitness pada masing-masing partikel
Rumus yang digunakan adalah sesuai dengan rumus yang sudah ditentukan, yaitu
f(x, y, z) = (kx * x^2) + (ky * y^2) + (kz * z^2)

Private Function HitungFitness(ByVal posisi() As Integer, ByVal data()() As Double) As Double
	Dim hasil As Double = 0.0
	For i As Integer = 0 To posisi.Length - 1
		hasil += data(i)(0) * posisi(i) * posisi(i)
	Next i
	Return hasil
End Function

1e. Lakukan pengecekan nilai fitness,
Jika nilai fitness ini lebih baik dari nilai fitness umum, maka ambil posisi acak ini sebagai posisi terbaik umum

If swarm(i).fitness < fitnessTerbaik Then
	fitnessTerbaik = swarm(i).fitness
	swarm(i).posisi.CopyTo(posisiTerbaik, 0)

	indeksPosisiTerbaik = i
End If

2. 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

3. Lakukan proses pencarian posisi terbaik sebanyak jumlah perulangan (poin 3a – 3f)

3a. Lakukan perulangan untuk setiap partikel
Cari kecepatan perpindahan posisi yang baru dengan rumus:
v baru = (w * v skrg) + (c1 * r1 * (posisi terbaik – posisi skrg)) + (c2 * r2 * (posisi umum terbaik – posisi skrg))
Jika kecepatan yang baru ternyata diluar batas minKecepatan dan maksKecepatan pada masing-masing dimensi, maka kembalikan nilainya agar masuk dalam batas kecepatan

For j As Integer = 0 To partikelTerpilih.kecepatan.Length - 1
	r1 = rnd.NextDouble()
	r2 = rnd.NextDouble()

	kecepatanBaru(j) = (w * partikelTerpilih.kecepatan(j)) + (c1 * r1 * (partikelTerpilih.posisiTerbaik(j) - partikelTerpilih.posisi(j))) + (c2 * r2 * (posisiTerbaik(j) - partikelTerpilih.posisi(j)))

	If kecepatanBaru(j) < minKecepatan(j) Then
		kecepatanBaru(j) = minKecepatan(j)
	ElseIf kecepatanBaru(j) > maksKecepatan(j) Then
		kecepatanBaru(j) = maksKecepatan(j)
	End If
Next j

kecepatanBaru.CopyTo(partikelTerpilih.kecepatan, 0)

3b. Lakukan update posisi yang baru dengan cara posisi lama + kecepatan baru
Jika posisi yang baru ternyata diluar batas variabel minX dan maksX (0 – 5), maka kembalikan posisinya agar masuk dalam batas

For j As Integer = 0 To partikelTerpilih.posisi.Length - 1
	posisiBaru(j) = partikelTerpilih.posisi(j) + kecepatanBaru(j)
	If posisiBaru(j) < data(j)(1) Then
		posisiBaru(j) = data(j)(1)
	ElseIf posisiBaru(j) > data(j)(2) Then
		posisiBaru(j) = data(j)(2)
	End If
Next j

3c. Sama seperti perhitungan sebelumnya, jumlah posisi yang baru belum tentu sesuai dengan parameter totalPosisi
Oleh karena itu, lakukan penyesuaian posisi agar jumlah posisi selalu bernilai sama dengan parameter totalPosisi

Dim jumlahPosisi As Integer = 0
For k As Integer = 0 To dimensi - 1
	jumlahPosisi += posisiBaru(k)
Next

Do While jumlahPosisi <> totalPosisi
	Dim selisih As Integer = totalPosisi - jumlahPosisi
	Dim selisihPerDimensi(dimensi - 1) As Integer
	Dim idx As Integer = -1
	Do While selisih <> 0
		idx = rnd.Next(dimensi)
		If selisih > 0 Then
			If posisiBaru(idx) + selisihPerDimensi(idx) < data(idx)(2) Then
				selisihPerDimensi(idx) += 1
				selisih -= 1
			End If
		Else
			If posisiBaru(idx) + selisihPerDimensi(idx) > data(idx)(1) Then
				selisihPerDimensi(idx) -= 1
				selisih += 1
			End If
		End If
	Loop
	For k As Integer = 0 To dimensi - 1
		Dim posBaru As Integer = posisiBaru(k) + selisihPerDimensi(k)
		If posBaru < data(k)(1) Then Continue Do
		If posBaru > data(k)(2) Then Continue Do
	Next
	For k As Integer = 0 To dimensi - 1
		Dim posBaru As Integer = posisiBaru(k) + selisihPerDimensi(k)
		jumlahPosisi = jumlahPosisi - posisiBaru(k) + posBaru
		posisiBaru(k) = posBaru
	Next
Loop

posisiBaru.CopyTo(partikelTerpilih.posisi, 0)

3d. Hitung nilai fitness untuk posisi yang baru

posisiBaru.CopyTo(partikelTerpilih.posisi, 0)
fitnessBaru = CariFitness(posisiBaru)
partikelTerpilih.fitness = fitnessBaru

3e. Jika nilai fitness baru lebih baik dari nilai fitness sebelumnya, maka ambil posisi yang baru sebagai posisi terbaik partikel tersebut

If fitnessBaru > partikelTerpilih.fitnessTerbaik Then
	posisiBaru.CopyTo(partikelTerpilih.posisiTerbaik, 0)
	partikelTerpilih.fitnessTerbaik = fitnessBaru
End If

3f. Jika nilai fitness baru ternyata lebih baik dari nilai fitness umum, maka ambil posisi yang baru sebagai posisi terbaik secara umum

If fitnessBaru > fitnessTerbaik Then
	posisiBaru.CopyTo(posisiTerbaik, 0)
	fitnessTerbaik = fitnessBaru

	Dim s As String = swarm(i).ToString()
	If s <> "" Then
		Console.Write("Partikel " & i & " : ")
		Console.WriteLine(s)
	End If
End If

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class Partikel untuk menampung semua data partikel beserta posisi, kecepatan dan nilai fitnessnya. Deklarasi Class Partikel adalah sebagai berikut:

Public Class Partikel
	Public posisi() As Integer
	Public fitness As Double
	Public kecepatan() As Double

	Public posisiTerbaik() As Integer
	Public fitnessTerbaik As Double

	Public lastString As String = ""

	Public Sub New(ByVal posisi() As Integer, ByVal fitness As Double, ByVal kecepatan() As Double, ByVal posisiTerbaik() As Integer, ByVal fitnessTerbaik As Double)
		Me.posisi = New Integer(posisi.Length - 1) {}
		posisi.CopyTo(Me.posisi, 0)
		Me.fitness = fitness
		Me.kecepatan = New Double(kecepatan.Length - 1) {}
		kecepatan.CopyTo(Me.kecepatan, 0)
		Me.posisiTerbaik = New Integer(posisiTerbaik.Length - 1) {}
		posisiTerbaik.CopyTo(Me.posisiTerbaik, 0)
		Me.fitnessTerbaik = fitnessTerbaik
	End Sub

	Public Overrides Function ToString() As String
		Dim s As String = ""
		s &= "posisi: "
		For i As Integer = 0 To Me.posisi.Length - 1
			s &= Me.posisi(i).ToString("F0") & " "
		Next i
		s &= ", "
		s &= "Fitness = " & Me.fitness.ToString("F2")

		If s <> lastString Then
			lastString = s
			Return s
		Else
			Return ""
		End If
	End Function
End Class

Hasil akhir adalah: (klik untuk perbesar gambar)

cmd25b

Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:

[sdm_download id=”554″ fancy=”0″]



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.