PENYELESAIAN PERMASALAHAN OPTIMASI CONSTRAINED NONLINEAR DENGAN PARTICLE SWARM OPTIMIZATION Yudhi Purwananto1, Rully Soelaiman1, dan Bambang Santoso.1 1
Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS), Surabaya, 60111, Indonesia E-mail :
[email protected]
Abstraksi Particle Swarm Optimization (PSO) merupakan teknik optimasi stokastik berbasiskan populasi yang terinspirasi oleh tingkah laku sosial kawanan burung atau ikan untuk menyelesaikan permasalahan-permasalahan optimasi. Dalam PSO, solusi yang mungkin, yang disebut partikel, terbang melewati ruang permasalahan dengan mengikuti nilai optimum partikel pada saat itu. Pada Tugas Akhir ini, algoritma PSO digunakan untuk menyelesaikan constrained nonlinear optimization problems (CNOPs). Untuk menyelesaikan permasalahan tersebut, digunakan strategi mempertahankan solusi-solusi yang mungkin untuk memenuhi batasan-batasan. PSO dimulai dengan sekelompok solusi yang mungkin dan sebuah fungsi yang digunakan untuk mengecek apakah solusi baru yang didapat memenuhi semua batasan-batasan. Dua belas CNOPs diuji dengan algoritma PSO. Dari hasil penelitian menunjukkan bahwa PSO merupakan solusi yang efektif dan umum dalam menyelesaikan sebagian besar permasalahan optimasi nonlinear dengan batasan-batasan pertidaksamaan nonlinear. Pada Tugas Akhir ini, juga dibandingkan antara algoritma PSO dengan algoritma genetika. Dari hasil penelitian menunjukkan bahwa algoritma PSO lebih cepat dan powerful dibandingkan dengan algoritma genetika. Hal ini disebabkan, algoritma PSO mampu mendapatkan nilai optimum fungsi dengan iterasi yang jauh lebih sedikit dibandingkan dengan algoritma genetika. Kata kunci: particle swarm, optimization technique, nonlinear programming, evolutionary computation, constrained optimization. 1. Pendahuluan Selama lebih dari satu dekade belakangan ini, penelitian penting telah dilakukan pada CNOPs (Constrained Nonlinear Optimization Problems). Permasalahan optimasi nonlinear sangat kompleks dan tidak dapat diprediksi. Sehingga solusi deterministik untuk CNOPs sangat tidak mungkin.
Hal ini memberikan kesempatan berkembangnya algoritma evolusioner. Pada tahun-tahun belakangan ini, beberapa algoritma evolusioner telah diusulkan untuk permasalahan optimasi nonlinear. Michalewicz memberikan gambaran dari algoritma-algoritma tersebut. Pada paper ini, beberapa pendekatan komputasi evolusioner diteliti dan sekumpulan uji kasus optimasi numerik dilakukan. Salah satu algoritma untuk CNOPs adalah Particle Swarm Optimization (PSO). PSO adalah teknik komputasi evolusioner yang dikembangkan oleh Kennedy dan Eberhart. PSO menggunakan teknik perhitungan evolusioner: 1. PSO diinisialisasi dengan sekumpulan solusi acak 2. PSO mencari solusi yang optimum dengan memperbarui generasi 3. Perkembangan populasi berdasarkan pada generasi sebelumnya Dalam PSO, solusi potensial, yaitu partikel, terbang melewati ruang permasalahan dengan mengikuti partikel yang optimal saat ini. PSO telah terbukti efektif untuk banyak permasalahan optimasi. Banyak penelitian telah dilakukan dalam area ini. Namun CNOPs merupakan area baru untuk PSO. 2. Dasar Teori 2.1 Latar Belakang PSO Sekelompok ilmuwan telah menciptakan simulasi komputer dari berbagai interpretasi pergerakan organisme-organisme di dalam sebuah kawanan burung atau ikan. Khususnya, Reynolds (Reynolds, 1987) dan Heppner dan Grenander (Heppner and Grenander, 1990) yang menggambarkan simulasi kawanan burung. Reynolds terkesan dengan keindahan pergerakan kawanan burung, dan Heppner, seorang ahli ilmu hewan, tertarik dalam menemukan aturan dasar yang memungkinkan sejumlah besar burung untuk berkumpul secara serempak, seringkali mengubah arah secara tibatiba, berpencar, dan berkumpul kembali. Sebagai ahli sosio biologi, E.O.Wilson (Wilson, 1975) menulis dalam referensinya mengenai
kawanan ikan, yaitu “Dalam teori sedikitnya anggota individu dalam kawanan tersebut dapat mengambil keuntungan dari penemuan dan pengalaman sebelumnya dari semua anggota lainnya dalam kawanan tersebut selama pencarian makanan. Keuntungan ini jelas melebihi kerugian dari persaingan dalam mencari makanan, sewaktuwaktu sumber makanan tersebar dalam potongan kecil yang tidak dapat diprediksi”. Pernyataan ini menyatakan bahwa pertukaran informasi sosial di antara individu menawarkan sebuah keuntungan evolusioner. Hipotesa ini adalah dasar dari pengembangan Particle Swarm Optimization (PSO). 2.2 Algoritma PSO Particle Swarm Optimization (PSO) adalah teknik optimasi stokastik berbasiskan populasi yang dikembangkan oleh Dr. Eberhart dan Dr. Kennedy pada tahun 1995, yang terinspirasi oleh tingkah laku sosial kawanan burung atau ikan. Di dalam PSO, setiap solusi adalah sebuah titik dalam ruang pencarian dan mungkin dapat dianggap sebagai seekor burung. Burung akan menemukan makanannya melalui usahanya sendiri dan kerja sama sosial dengan burung-burung lain di sekitarnya[8]. Seandainya ada skenario seperti ini: suatu kawanan burung mencari makanan secara acak di sebuah area. Hanya ada satu potong makanan di area pencarian tersebut. Semua burung tidak tahu di mana makanan tersebut. Namun mereka mengetahui seberapa jauh makanan itu pada setiap iterasi. Jadi strategi terbaik untuk menemukan makanan itu adalah dengan cara mengikuti burung yang terdekat dengan makanan tersebut[7]. Setiap anggota di dalam kawanan mengadaptasi pola pencariannya dengan belajar dari pengalamannya sendiri dan pengalaman anggota yang lain. Burung tadi direpresentasikan sebagai partikel dalam algoritma. Setiap partikel merepresentasikan sebuah solusi potensial yang berupa sebuah titik di dalam ruang pencarian. Global optimum dianggap sebagai lokasi dari makanan[8]. Semua partikel mempunyai nilai fitness yang dievaluasi oleh fungsi yang dioptimasi dan juga kecepatan (velocity)[7]. Nilai fitness dan kecepatan (velocity) digunakan untuk mengatur arah terbang sesuai dengan pengalaman terbaik kawanan untuk mencari global optimum (gbest) di dalam ruang solusi D -dimensi dengan cara mengikuti partikel optimum pada saat itu dan memperbarui generasigenerasinya. Partikel-partikel tersebut terbang melewati ruang permasalahan D -dimensi dengan belajar dari pengalaman-pengalaman terbaik semua
partikel. Oleh karena itu, partikel-partikel tersebut mempunyai sebuah kecenderungan untuk terbang menuju area pencarian yang lebih baik pada serangkaian pembelajarannya di dalam proses pencarian tersebut[8]. Setiap partikel menyimpan jejak koordinatnya dalam ruang permasalahan yang sehubungan dengan solusi terbaik (nilai fitness) yang telah dicapai sejauh ini. Nilai fitness juga disimpan. Koordinat terbaik yang dicapai sebuah partikel saat tercapainya nilai fitness terbaik pada saat itu disebut sebagai pbest. Sedangkan koordinat terbaik yang dicapai partikel mana pun dalam suatu wilayah tetangga di dalam populasi (subset of the swarm) partikel disebut local best (lbest). Pada saat sebuah partikel mengambil semua populasi sebagai tetanggaan topologikalnya, maka koordinat terbaiknya disebut global best (gbest). Konsep PSO adalah, di setiap langkah waktunya (iterasi/generasi) mengubah kecepatan (mengakselerasi) dari setiap partikel menuju lokasi pbest dan lbest-nya (untuk varian PSO local version). Akselerasi dipengaruhi syarat yang acak dengan dibangkitkannya sejumlah angka acak secara terpisah untuk akselerasi menuju lokasi pbest (dan lbest). Setelah menemukan kedua nilai terbaik tersebut (pbest dan gbest), partikel kembali lagi memperbarui kecepatan (v) dan posisinya (x) [7]. Pembaharuan partikel diselesaikan dengan persamaan berikut ini. Persamaan (2.1) menghitung kecepatan baru untuk tiap partikel (solusi potensial) berdasarkan pada kecepatan sebelumnya ( Vid ), lokasi partikel dimana nilai fitness terbaik telah dicapai ( p id atau pBest), dan lokasi populasi global ( p gd ,gBest untuk versi global atau p ld , lBest untuk versi lokal) atau local neighborhood pada algoritma versi lokal dimana nilai fitness terbaik telah dicapai. Persamaan (2.2) memperbarui posisi tiap partikel pada ruang solusi. Dua bilangan acak c1 dan c 2 dibangkitkan sendiri. Penggunaan berat inersia w telah memberikan performa yang meningkat pada sejumlah aplikasi. Vid w Vid c1 rand () ( pid xid ) c2 rand () ( pgd xid ) x id x id V id
(2.1) (2.2)
Vid adalah kecepatan partikel, xid adalah posisi
partikel saat ini (solusi). Posisi dari setiap partikel diperbarui setiap generasi, hal ini dengan menambahkan vektor kecepatan ke vektor posisi sebagaimana persamaan (2.1) di atas. Sedangkan rand () adalah bilangan acak antar 0 s/d 1. c1 dan c 2 adalah faktor pembelajaran yang secara berturutturut merepresentasikan sebuah komponen kognitif dan sebuah komponen sosial, yang secara berturutturut mempengaruhi seberapa besar pbest dan gbest
partikel mempengaruhi pergerakannya. Biasanya c1 = c 2 = 2 [7]. w adalah berat inersia yang digunakan untuk menyeimbangkan antara kemampuan pencarian global dan pencarian lokal. Biasanya, berat inersia yang bagus adalah kurang sedikit dari satu.
4.
Metode Hibrid Lainnya Tabel 1. Dua Belas Uji Kasus Optimasi Constrained Nonlinear
Func
Dim
Type
G1 G2 G3 G4 G5 G6 G7 G8 G9 G10 G11 G12
13 K K 5 4 2 10 2 7 8 2 3
Quadratic Nonlinear Polynomial Quadratic Cubic Cubic Quadratic Nonlinear Polynomial Linear Quadratic Quadratic
2.3 Pengaturan Parameter PSO Ukuran populasi PSO ditetapkan 20 agar dapat mempercepat waktu penghitungan. Hal ini dikarenakan selama inisialisasi, semua partikel harus berada pada ruang yang mungkin. Jadi inisialisasi memerlukan waktu proses yang lebih panjang jika ukuran populasi terlalu besar. Bagaimanapun juga untuk kasus yang kompleks, ukuran populasi yang besar lebih direkomendasikan. Dalam PSO, tidak banyak parameter-parameter yang perlu diatur. Hanya beberapa parameterparameter berikut ini yang perlu diatur: kecepatan maksimum Vmax , berat inersia w , konstanta pembelajaran kognitif dan konstanta c1 pembelajaran sosial c 2 . Kecepatan maksimum Vmax ditetapkan sesuai jarak dinamis partikel. Berat inersia w ditetapkan [0.5 + (Rnd/2.0)]. Konstanta pembelajaran c1 dan c 2 ditetapkan 1.49445. 2.4 Constrained Nonlinear Optimation Problems (CNOPs) PSO telah terbukti efektif untuk banyak permasalahan optimasi. Banyak penelitian telah dilakukan dalam area ini. Namun CNOPs merupakan area baru untuk PSO. Constrained Nonlinear Optimization Problems dapat didefiniskan sebagai berikut Optimalkan f (x ) , x ( x1 , x 2 ,...x n ) N Dimana g j ( x ) 0 untuk j 1,..., p h j (x) 0
untuk j q 1,..., m Ada 3 komponen dasar, yaitu: kelompok variabel, fungsi yang dioptimasi, dan kelompok constraint yang mengelompokkan variabel yang mungkin. Tujuannya adalah mencari nilai variabel yang mengoptimalkan fungsi sekaligus memenuhi constraint. Selama beberapa tahun terakhir ini, beberapa metode diusulkan untuk menangani constraint dengan algoritma genetika untuk permasalahan parameter optimasi. Metode-metode ini dikelompokkan (Michalewicz and Schoenauer, 1996) ke dalam empat kategori: 1. Metode Berdasarkan Pada Mempertahankan Solusi-Solusi yang Mungkin 2. Metode Berdasarkan Pada Fungsi-Fungsi Penalti (Penalty Functions) 3. Metode Berdasarkan Pada Suatu Pencarian Untuk Solusi-Solusi Yang Mungkin
Relative size of feasible space 0.0111% 99.8474% <0.0001% 52.1230% <0.0001% 0.0066% 0.0003% 0.8250% 0.5121% 0.0010% <0.0000% -
LI
NE
NI
9 0 0 0 2 0 3 0 0 3 0 -
0 0 1 0 3 0 0 0 0 0 1 -
0 2 0 6 0 2 5 2 4 3 0 -
* LI: Linear Inequalities, NE: Nonlinear Equations, NI: Nonlinear Inequalities Deskripsi dari 12 uji kasus, G1 G12 untuk permasalahan optimasi constrained nonlinear adalah sebagai berikut:
Minimize 4 13 G1( x ) 5 x1 5 x2 5 x3 5 x4 5i 1 xi 2 i 5 xi
batasan-batasannya: 2 x1 2 x 2 x10 x11 10 ,
8 x1 x10 0 , , 2 x1 2 x3 x10 x12 10 8 x 2 x11 0 , 2 x 2 2 x 3 x11 x12 10 , 8 x 3 x12 0 , 2 x 4 x 5 x10 0 , 2 x 6 x7 x11 0 , 2 x8 x 9 x12 0 , di mana: 0 x i 1 , i 1,...,9 , 0 xi 100 , i 10,11,12 , 0 x13 1 .
Solusi: x * (1,1,1,1,1,1,1,1,1,3,3,3,1) , G1( x * ) 15
Maximize G 2( x )
n
n
i 1 cos 4 ( xi ) 2i1 cos 2 ( xi )
,
n ix 2 i 1 i
batasan-batasannya: n
i 1 xi 0.75 ,
n
i 1 xi 7.5n ,
di mana: 0 xi 10 untuk 1 i n . Solusi: untuk n 20 , G 2( x ) 0.8036 .
Maximize n G 3( x ) ( n ) n .i 1 xi ,
di mana: n
i 1 xi 2 1
dan 0 xi 1 untuk 1 i n .
1
Solusi: ( x i ,..., x n )
,...,
n
3 x1 6 x2 12( x9 8) 2 7 x10 0 ,
1 , G 3( x ) 1 . n
0.5( x1 8) 2 2( x2 4) 2 3 x5 2 x6 30 0 ,
di mana:
Minimize
G4(x) 5.3578547x32 0.8356891x1x 5 37.293239x1 40792.141 ,
10.0 xi 10.0 , i 1,...,10 .
Solusi:
0.0022053x3 x5 92 ,
x * ( 2.171996, 2.363683,8.773926,5.095984,0.9906548, 1.430574,1.321644,9.828726,8.280092,8.375927) , G 7( x * ) 24.3062091
90 80.51249 0.0071317x2 x5 0.0029955x1 x2
batasan-batasannya: 0 85.334407 0.0056858x2 x5 0.0006262x1x4
2
sin 3 ( 2x1 ). sin( 2x2 ) G8( x ) , x13.( x1 x2 )
0.0021813x3 110 , 20 9.300961 0.0047026 x3 x5 0.0012547 x1x3
0.0019085x3 x4 25 ,
di mana: 78 x1 102 , 33 x 2 45 , 27 xi 45 untuk i 3,4,5 Solusi: x * (78.0,33.0,29.995,45.0,36.776) , * G 4( x ) 30665.5 .
Minimize
G 5( x ) 3 x1 0.000001x13 2 x2 0.000002 / 3 x23 ,
batasan-batasannya: x1 2 x 2 1 0 , 1 x1 ( x 2 4) 2 0 ,
di mana: 0 x1 10 dan 0 x 2 10 . Solusi: G8( x * ) 0.1 .
batasan-batasannya: x 4 x 3 0.55 0 , x 3 x 4 0.55 0 1000 sin( x3 0.25) 1000 sin( x4 0.25) 894.8 x1 0 1000 sin( x3 0.25) 1000 sin( x3 x4 0.25) 894 .8 x2 0
Maximize
Minimize
G 9( x ) ( x1 10) 2 5( x2 12) 2 x34 3( x4 11) 2 10 x5 6 7 x6 2 x7 4 4 x6 x7 10 x6 8 x7 ,
batasan-batasannya: 127 2 x1 2 3 x 2 4 x 3 4 x 4 2 5 x5 0 ,
1000 sin( x4 0.25) 1000 sin( x4 x3 0.25) 1294.8 0
di mana:
282 7 x1 3 x 2 10 x3 2 x 4 x 5 0 ,
0 x i 1200 , i 1,2 , 0.55 xi 0.55 , i 3,4 . * Solusi x (679.9453,1026.067,0.1188764,0.3962336) G 5( x * ) 5126.4981 .
196 23x1 x 2 2 6 x 6 2 8 x 7 0 ,
4 x1 2 x 2 2 3x1 x 2 2 x 3 2 5 x 6 11x 7 0 ,
di mana: 10.0 xi 10.0 , i 1,...,7 .
Minimize
Solusi:
G 6( x ) ( x1 10)3 ( x2 20)3 ,
x * ( 2.330499,1.951372, 0.4775414, 4.365726, 0.6244870, 1.038131,1.594227) , * G 9( x ) 680.6300573 .
batasan-batasannya: ( x1 5)2 ( x2 5) 2 100 0 ,
( x1 6) 2 ( x2 5) 2 82.81 0 ,
di mana:
13 x1 100 dan 0 x2 100 . Solusi: x * (14.095,0.84296) , G 6( x * ) 6961.81381.
batasan-batasannya:
Minimize
G 7 ( x ) x12 x2 2 x1x2 14 x1 16 x2 ( x3 x10 ) 2
Minimize
G10( x ) x1 x 2 x 3 ,
1 0.0025 ( x 4 x 6 ) 0 , 1 0.0025 ( x 5 x 7 x 4 ) 0 ,
1 0.01( x8 x 5 ) 0 ,
4( x4 5) ( x5 3) 2( x6 1) 5 x7
x1 x6 833.33252 x 4 100 x1 83333 .333 0
7( x8 11) 2 2( x9 10) 2 ( x10 7) 2 45 ,
x 2 x 7 1250 x 5 x 2 x 4 1250 x 4 0
2
2
2
2
batasan-batasannya: 105 4 x1 5 x2 3 x7 9 x8 0 ,
3( x1 2) 2 4( x2 3) 2 2 x32 7 x4 120 0 , 10 x1 8 x2 17 x7 2 x8 0 ,
x12 2( x2 2) 2 2 x1 x2 14 x5 6 x6 0 , 8 x1 2 x2 5 x9 2 x10 12 0 ,
5 x12 8 x2 ( x3 6) 2 2 x4 40 0 ,
x 3 x8 1250000 x3 x 5 2500 x5 0
di mana: 100 x1 10000 , 1000 xi 10000 , i 2,3 ,
10 xi 1000 , i 4,...8 .
Solusi:
x * (579.3167,1359.943,5110.071,182.0174, 295.5985, 217.9799,286.4162,395.5979) , G10( x * ) 7049.330923 .
Minimize
G11( x ) x12 ( x 2 1) 2 ,
batasan-batasannya: x 2 x1 2 0
dimana: 1 x i 1 , i 1,2 . Solusi: x * ( 0.70711,0.5) , G11( x * ) 0.75000455 .
Maximize
G12( x ) (100 ( x1 5) 2 ( x2 5) 2 ( x3 5) 2 ) / 100 ,
batasan-batasannya:
Ada 2 modifikasi dibandingkan dengan PSO mulamula: 1. Selama inisialisasi, semua pertikel diinisialisasi berulang-ulang sampai memenuhi semua constraint. 2. Selama menghitung nilai pBest dan gBest, hanya posisi dalam ruang yang mungkin yang dihitung. Algoritma di atas adalah versi global. Untuk versi lokal, hanya ada 1 perbedaan. Sebagai gantinya mencari gBest, setiap partikel mencari nilai yang berdekatan terbaik (lBest) untuk mengupdate kecepatan yang baru.
( x1 p) 2 ( x 2 q) 2 ( x3 r ) 2 0.25
untuk p, q, r 1,3,5,7,9 di mana: 0 x i 10 (1 i 3) .
3. Desain Uji Coba
Solusi: x * (5,5,5) , G12( x * ) 1 . 2.5 The Modified PSO Algorithm Untuk CNOPs, metode PSO yang semula perlu dimodifikasi agar memenuhi constraints. Beberapa ide dari metode penanganan constraints dapat digunakan. Metode yang paling langsung adalah metode berdasarkan pada mempertahankan solusisolusi yang mungkin. Untuk mencari optimum dalam ruang yang mungkin, tiap partikel mencari seluruh ruang tetapi hanya menyimpan jejak solusisolusi yang mungkin. Dan untuk mempercepat proses ini, semua partikel diinisialisasi sebagai solusi-solusi yang mungkin. Berikut ini adalah algoritmanya:
Pada tabel 1, ada tiga kasus yang memiliki batasanbatasan persamaan nonlinear, yaitu G3, G5, G11. Dalam metode PSO, semua solusi yang diinisialisasi secara acak perlu ditempatkan pada ruang yang mungkin. Jadi untuk batasan-batasan persamaan tersebut, hampir tidak mungkin untuk membangkitkan sekelompok solusi yang mungkin secara acak. Ada beberapa teknik untuk mengeliminisasi batasan-batasan persamaan tersebut. Salah satunya dengan menggunakan penggantian langsung untuk menghilangkan batasan-batasan tersebut, sebagai berikut:
Fungsi G3, Maximize n n G 3( x ) ( n 1 ) n 1 .i 1 x i .(1 i 1 x i 2 ) ,
batasan-batasannya: n
FOR setiap partikel { DO { Inisialisasi partikel } Selama partikel berada dalam ruang yang mungkin (memenuhi batasan-batasan) } DO { FOR setiap partikel { Hitung nilai fitness IF nilai fitness lebih baik daripada nilai fitness terbaik yang disimpan (pBest) AND partikel berada dalam ruang yang mungkin, SET nilai saat ini sebagai pBest yang baru } Pilih partikel dengan nilai fitness terbaik di antara semua partikel sebagai gBest FOR tiap partikel { Hitung kecepatan partikel menggunakan persamaan (2.1) Perbarui posisi partikel menggunakan persamaan (2.2) } } WHILE iterasi maksimum/kriteria error minimum belum tercapai
Gambar 1. Pseudo Code Modified PSO
i 1 xi 2 1
di mana: 0 xi 1 untuk 1 i n 1 Fungsi G11 Minimize G11( x ) x1 2 ( x1 1) 2 , di mana: 1 xi 1 , untuk i 1 .
Untuk setiap fungsi, dimensi ditetapkan sesuai dengan permasalahan constrained nonlinear. Ada 3 uji coba yang dilakukan. Uji coba yang pertama, ukuran populasi sebanyak 20, kecuali fungsi G1 (ukuran populasi 50) dan jumlah iterasi sebanyak 200 kecuali fungsi G7 dan G10 (2000 iterasi). Uji coba yang kedua, ukuran populasi sebanyak 20, kecuali fungsi G1 (ukuran populasi 50) dan jumlah iterasi sebanyak 500, kecuali fungsi G7 dan G10 (5000 iterasi). Sedangkan uji coba ketiga (khusus untuk fungsi G2), menggunakan parameter yang berbeda-beda mengenai jumlah partikel dan jumlah iterasi, yaitu ukuran populasi = 20, 50, 200, 500 dan iterasi untuk masing-masing ukuran populasi adalah 5000, 10000, dan 20000. Algoritma yang digunakan adalah algoritma PSO versi global. Semua algoritma dijalankan selama 20 kali untuk mendapatkan hasil akhir dari gbestval tiap iterasi
tiap fungsi, nilai terburuk (worst) gbestval tiap fungsi, nilai terbaik (best) gbestval tiap fungsi, dan nilai rata-rata (average) gbestval tiap fungsi.
Tabel 4. Hasil PSO pada eksperimen 3 (Fungsi G2) (Nilai optimum 0.8936) Ukuran Pop
4. Hasil dan Pembahasan 20
Tabel 2, tabel 3, dan tabel 4 berikut ini menunjukkan nilai terburuk (worst) gbestval, nilai terbaik (best) gbestval, dan nilai rata-rata (average) gbestval tiap fungsi. Tabel 2 menunjukkan hasil PSO pada eksperimen 1 (200 iterasi), tabel 3 menunjukkan hasil PSO pada eksperimen 2 (500 iterasi), sedangkan tabel 4 menunjukkan hasil PSO pada eksperimen 3 (fungsi G2). Tabel 5 menunjukkan perbandingan antara algoritma PSO dan algoritma genetika dalam mencari nilai optimum fungsi. Warna merah menunjukkan nilai yang lebih bagus di antara kedua algoritma. Tabel 2. Hasil PSO pada eksperimen 1 (Global, populasi 20, 200 iterasi, 20 kali running) Uji kasus G3 dijalankan dengan k=10 variabel Func G1* G3 G4 G5 G6 G7** G8 G9 G10** G11 G12
Type Min Max Min Min Min Min Max Min Min Min Max
Optimum -15 1.0 -30665.5 5126.4981 -6961.8 24.306 0.09583 680.63 7049.33 0.75 1.0
Worst -14.3662 0.9906 -30256 -6885.2 27.1285 0.0958 681.3693 9120.4 0.75 1
Best -14.6821 0.9990 -30655 -6954.1 24.3580 0.0958 680.6643 7326.4 0.75 1
Average -14.5456 0.9953 -30555 -6930.1 25.5715 0.0958 680.9282 8131.2 0.75 1
* Ukuran populasi 50 ** Iterasi maksimum diubah menjadi 2000
50
200
500
Func G1* G3 G4 G5 G6 G7** G8 G9 G10** G11 G12
Type Min Max Min Min Min Min Max Min Min Min Max
Optimum -15 1.0 -30665.5 5126.4981 -6961.8 24.306 0.09583 680.63 7049.33 0.75 1.0
Worst -14.5543 0.9969 -30278 -6954.1 26.8426 0.0958 681.0724 9101.4 0.75 1
Best -14.7093 0.9998 -30659 -6961.7 24.3337 0.0958 680.6496 7132.1 0.75 1
* Ukuran populasi 50 ** Iterasi maksimum diubah menjadi 5000
Average -14.6373 0.9986 -30592 -6960.5 25.0955 0.0958 680.7408 7996.7 0.75 1
Worst 0.2868 0.2698 0.2596 0.4774 0.3376 0.3987 0.5174 0.5699 0.4445 0.7245 0.6580 0.6034
Best 0.7051 0.7313 0.7368 0.7772 0.7682 0.7623 0.8019 0.7930 0.8108 0.8108 0.8108 0.8108
Average 0.4866 0.4887 0.4621 0.5891 0.5714 0.5860 0.7143 0.7135 0.7305 0.7814 0.7635 0.7485
Tabel 5. Perbandingan Algoritma PSO dan GA Func
Type
Optimum
G1 G3 G4 G5 G6 G7**** G8 G9 G10**** G11 G12
Min Max Min Min Min Min Max Min Min Min Max
-15 1.0 -30665.5 5126.4981 -6961.8 24.306 0.09583 680.63 7049.33 0.75 1.0
* ** *** ****
Tabel 3. Hasil PSO pada eksperimen 2 (Global, populasi 20, 500 iterasi, 20 kali running) Uji kasus G3 dijalankan dengan k=10 variabel
Max iterasi 5000 10000 20000 5000 10000 20000 5000 10000 20000 5000 10000 20000
PSO 500* -14.7093 0.9998 -30659 -6961.7 24.3337 0.0958 680.6496 7132.1 0.75 1
GA 20000** -14.7864 0.9997 -30664.5 -6952.1 24.620 0.0958 680.91 7147.9 0.75 1***
Hasil dari tabel 4.3, 500 iterasi Hasil dari Koziel et al.,[5], 20000 iterasi Untuk G12, GA menggunakan 500 iterasi Maksimum iterasi diubah menjadi 5000
Eksperimen 1 (200 iterasi)
Tabel 2 menunjukkan hasil dari eksperimen pertama (200 iterasi). Tabel ini menunjukkan bahwa untuk sebelas uji kasus CNOPs, PSO berhasil mendapatkan nilai optimum atau mendekati optimum dalam 200 iterasi, kecuali untuk kasus G5, yang tidak dapat diselesaikan karena persamaan batasan-batasannya.
Eksperimen 2 (500 iterasi)
Tabel 3 menunjukkan hasil dari eksperimen kedua (500 iterasi). Tabel ini menunjukkan bahwa untuk sebelas uji kasus CNOPs, PSO berhasil mendapatkan nilai optimum atau mendekati optimum dalam 500 iterasi, kecuali untuk kasus G5, yang tidak dapat diselesaikan karena persamaan batasan-batasannya. Pada eksperimen ini, PSO mendapatkan hasil-hasil yang lebih baik dibandingkan dengan eksperimen kedua. Namun waktu yang dibutuhkan untuk mendapatkan nilai optimum fungsi lebih lama dibandingkan dengan eksperimen kedua.
Eksperimen 3 (fungsi G2)
PSO tidak dapat menemukan nilai optimum yang terbaik dengan pengaturan seperti pada eksperimen 1 dan 2. Untuk itu, dicoba variasi pengaturan jumlah populasi dan jumlah maksimum iterasi yang digunakan. PSO berhasil mendapatkan nilai optimum dengan jumlah populasi yang besar. Hasilnya dapat dilihat pada tabel 4.
[4]
[6]
Perbandingan Algoritma PSO dan GA
Tabel 5 adalah perbandingan hasil uji coba terbaik dalam 20x eksekusi untuk agoritma PSO (500 iterasi) dengan algoritma genetika (20000 iterasi). Tabel ini menunjukkan bahwa PSO mendapatkan hasil yang lebih baik atau serupa dengan iterasi yang jauh lebih sedikit dibandingkan dengan algoritma genetika. 5. Kesimpulan Berdasarkan uji coba dan evaluasi terhadap perangkat lunak yang dibangun, dapat diambil kesimpulan sebagai berikut: 1. Algoritma PSO mampu menyelesaikan sebagian besar permasalahan optimasi dengan constraint. 2. Dibandingkan dengan algoritma genetika, algoritma PSO memiliki beberapa keunggulan, di antaranya: algoritma PSO sederhana (tidak banyak parameterparameter yang diatur), algoritma PSO jauh lebih cepat dalam mendapatkan nilai optimum. Paper ini hanya menunjukkan langkah pertama dalam penelitian untuk menyelesaikan permasalahan optimasi constrained nonlinear dengan menggunakan particle swarm optimization (PSO). Agar berguna dalam aplikasi praktis, kemampuan PSO dalam menyelesaikan permasalahan optimasi constrained nonlinear yang lebih komplek lagi, akan perlu untuk dibuktikan. 6. Daftar Pustaka [1] Eberhart, R. C. and Kennedy, J. “A new optimizer using particle swarm theory”, Proceedings of the Sixth International Symposium on Micro Machine and Human Science. Nagoya, Japan, pp 39-43, 1995. [2] Kennedy, J. dan Eberhart, R. C. “Particle swarm optimization” Proceedings of IEEE International Conference on Neural Networks. Piscataway, NJ, IEEE service center.pp. 19421948, 1995. [3] Shi, Y. and Eberhart, R. C. “A modified particle swarm optimizer”, Proceedings of the
[5]
[7]
[8]
IEEE International Conference on Evolutionary Computation., Piscataway, NJ, IEEE Press. pp. 69-73, 1998. Kennedy, J., Eberhart, R. C., and Shi, Y., Swarm intelligence, San Fransisco: Morgan Kaufmann Publisher, 2001. Koziel, S. and Michalewicz, Z., “Evolutionary Algorithms, Homomorphous Mappings, and Constrained Parameter Optimization”. Evolutionary Computation, vol. 7, no. 1. pp. 19-44, 1999. Michalewicz, Z. and Schoenauer, M., “Evolutionary Algorithms for Constrained Parameter Optimization Problems”, Evolutionary Computation, vol. 4, no. 1, pp. 132, 1996. Hu , Xiaohui. 2006. “PSO Tutorial”,
. Liang, Jing J., Qin, A. Kai., Suganthan, Ponnuthurai Nagaratnam, dan Baskar, S., “Evaluation of Comprehensive Learning Particle Swarm Optimizer “. LNCS 3316,:230235, 2004.
