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)
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.
Leave a Reply