Apa beda fungsi fitness dan objektif pada pso

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

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

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