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, zMasing-masing dimensi memiliki sebuah konstanta dan batas rentang titik yang dapat digunakanContoh data pada masing-masing dimensi adalah sebagai berikut
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
* Tentukan jumlah partikel yang digunakan dalam perhitungan
Diasumsikan dalam kasus ini, jumlah partikel yang digunakan adalah 10 partikel
* Tentukan jumlah iterasi yang digunakan oleh setiap partikel untuk melakukan proses
Diasumsikan dalam kasus ini, jumlah iterasi yang digunakan adalah 100 kali
* Tentukan total posisi yang harus dicapaiSemua 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 prosesDiasumsikan dalam kasus ini nilai minimal dan nilai maksimal adalah 10% dari masing-masing batas nilai pada tiap-tiap dimensiSebagai 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 NextLangkah-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
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
1c. Inisialisasi nilai kecepatan semua partikel awal dengan nilai kecepatan acak
1d. Hitung nilai fitness dari posisi acak tersebutKarena 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 partikelRumus 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 Function1e. Lakukan pengecekan nilai fitness,
Jika nilai fitness ini lebih baik dari nilai fitness umum, maka ambil posisi acak ini sebagai posisi terbaik umum
2. Tentukan bobot inertia (w), bobot kognitif (c1), dan bobot sosial (c2)Nilai acuan untuk masing-masing variabel dapat dilihat di //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.494453. Lakukan proses pencarian posisi terbaik sebanyak jumlah perulangan (poin 3a – 3f)
3a. Lakukan perulangan untuk setiap partikelCari 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
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
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
3d. Hitung nilai fitness untuk posisi yang baru
posisiBaru.CopyTo(partikelTerpilih.posisi, 0) fitnessBaru = CariFitness(posisiBaru) partikelTerpilih.fitness = fitnessBaru3e. 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 If3f. 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 ClassHasil 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.