JURNAL TEKNIK ITS Vol. 1, (Sept, 2012) ISSN: 2301-9271
A-211
Implementasi Algoritma Particle Swarm untuk Menyelesaikan Sistem Persamaan Nonlinear Ardiana Rosita, Yudhi Purwananto dan Rully Soelaiman Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS) Jl. Arief Rahman Hakim, Surabaya 60111 E-mail:
[email protected]
Abstrak—Penyelesaian sistem persamaan nonlinear merupakan salah satu permasalahan yang sulit pada komputasi numerik dan berbagai aplikasi teknik. Beberapa metode telah dikembangkan untuk menyelesaikan sistem persamaan ini dan metode Newton merupakan metode yang paling sering digunakan. Namun metode ini memerlukan perkiraan solusi awal dan memilih perkiraan solusi awal yang baik untuk sebagian besar sistem persamaan nonlinear tidaklah mudah. Pada makalah ini, algoritma Particle Swarm yang diusulkan oleh Jaberipour dan kawan-kawan[1] diimplementasikan. Algoritma ini merupakan pengembangan dari algoritma Particle Swarm Optimization (PSO). Algoritma ini meyelesaikan sistem persamaan nonlinear yang sebelumnya telah diubah menjadi permasalahan optimasi. Uji coba dilakukan terhadap beberapa fungsi dan sistem persamaan nonlinear untuk menguji kinerja dan efisiensi algoritma. Berdasarkan hasil uji coba, beberapa fungsi dan sistem persamaan nonlinear telah konvergen pada iterasi ke 10 sampai 20 dan terdapat fungsi yang konvergen pada iterasi ke 200. Selain itu, solusi yang dihasilkan algoritma Particle Swarm mendekati solusi eksak. Kata Kunci—fungsi, persamaan nonlinear.
optimasi,
particle
swarm,
sistem
I. PENDAHULUAN
S
ISTEM persamaan nonlinear adalah sistem persamaan yang terdiri dari satu atau lebih persamaan nonlinear. Sistem persamaan ini merupakan permasalahan dasar matematika yang banyak dijumpai di berbagai bidang ilmu alam seperti fisika, kimia, komputasi mesin, dan lainnya. Sistem persamaan nonlinear sangat sulit untuk diselesaikan, terlebih pada komputasi numerik dan berbagai aplikasi teknik. Terdapat banyak metode maupun algoritma yang dikembangkan untuk menyelesaikan sistem persamaan nonlinear. Apabila dibandingkan dengan semua metode yang ada, metode Newton merupakan metode yang paling sering digunakan pada penyelesaian sistem persamaan nonlinear. Namun metode ini memiliki beberapa kekurangan, yaitu tingkat konvergensi dan hasilnya sangat bergantung pada perkiraan awal solusi. Algoritma akan gagal apabila pemilihan nilai perkiraan solusi awal tidak tepat, sedangkan menentukan perkiraan solusi awal yang baik pada sebagian besar sistem persamaan nonlinear tidaklah mudah. Oleh karena itu, dibutuhkan sebuah metode baru yang mampu mengatasi permasalahan tersebut.
Pada makalah ini algoritma optimasi particle swarm yang diusulkan oleh Jaberipour et al.[1] diimplementasikan. Algoritma optimasi Particle Swarm baru ini merupakan pengembangan dari algoritma optimasi yang terkenal, yaitu algoritma Particle Swarm Optimization (PSO) dasar[2]. Algoritma Particle Swarm yang diusulkan oleh Jaberipour menyelesaikan sistem persamaan nonlinear yang sebelumnya telah diubah menjadi bentuk permasalahan optimasi, dalam hal ini adalah minimasi. Dengan menggunakan algoritma ini, diharapkan hasil penyelesaian yang didapat efisien dengan rata-rata konvergensi yang tinggi. II. ALGORTIMA PARTICLE SWARM UNTUK MENYELESAIKAN SISTEM PERSAMAAN NONLINEAR Pada makalah ini algoritma optimasi particle swarm digunakan untuk menyelesaikan sistem persamaan nonlinear. Sebelum membahas lebih lanjut tentang algoritma, langkah awal yang dilakukan adalah sistem persamaan nonlinear diubah menjadi permasalahan optimasi. Bentuk sistem persamaannya sebagai berikut :
f 1 ( x1 , x 2 ,..., x n ) 0 f 2 ( x1 , x 2 ,..., x n ) 0 : f m ( x1 , x 2 ,..., x n ) 0.
(1)
Agar dapat menggunakan metode optimasi global, sistem persamaan (1) diubah menjadi fungsi kuadratik sebagai berikut: m
F ( x) f i 2 ( x).
(2)
i 1
Untuk menyelesaikan sistem persamaan nonlinear sama dengan meminimalkan fungsi (2). A. Algoritma Particle Swarm Optimization (PSO) Algoritma Particle Swarm Optimization (PSO) adalah teknik optimasi berdasarkan populasi yang terinspirasi oleh perilaku sosial dari pergerakan burung atau ikan (bird flocking atau fish schooling). PSO sebagai alat optimasi menyediakan prosedur pencarian berbasis populasi dimana masing-masing individu yang disebut partikel mengubah posisi mereka terhadap waktu. Pada sistem PSO, masing-masing partikel terbang mengitari ruang pencarian multi dimensional
JURNAL TEKNIK ITS Vol. 1, (Sept, 2012) ISSN: 2301-9271
A-212
Gambar. 1. Visualisasi perubahan posisi populasi saat mencari posisi terbaik
(multidimensional search space) dan menyesuaikan posisinya berdasarkan pengalaman pribadinya dan pengalaman partikel di sebelahnya. Visualisasi pergerakan populasi dalam mencari posisi terbaik ditampilkan pada Gambar 1. Dari penjelasan di atas dapat dikatakan bahwa algoritma PSO menggabungkan metode pencarian lokal (local search) dengan metode pencarian global (global search)[3]. Tiap partikel memiliki posisi xi = (xi1, xi2, ..., xiN) dan kecepatan vi = (vi1, vi2, ..., viN) pada ruang pencarian berdimensi N, dimana i menyatakan partikel ke-i dan N menyatakan dimensi ruang pencarian atau jumlah variabel yang belum diketahui pada sistem persamaan nonlinear. Inisialisasi algoritma PSO dimulai dengan menetapkan posisi awal partikel secara acak (solusi) dan kemudian mencari nilai optimal dengan memperbarui posisinya. Seperti yang telah dijelaskan di atas, setiap iterasi masing-masing partikel memperbarui posisinya mengikuti dua nilai terbaik, yaitu solusi terbaik yang telah didapat oleh masing-masing partikel (pbest) dan solusi terbaik pada populasi (gbest). Setelah mendapatkan dua nilai terbaik, posisi dan kecepatan partikel diperbarui dengan menggunakan persamaan berikut :
vki wvik c1r1 ( pbestik xik ) c2 r2 ( gbest k xik ) xik 1 xik vik 1
(3)
dimana vik adalah kecepatan partikel ke i pada iterasi ke k, dan
xik adalah solusi (posisi) partikel ke i pada iterasi ke k. c1, c2 adalah konstanta positif, dan r1, r2 adalah dua variabel acak terdistribusi uniform antara 0 sampai 1. Pada persamaan di atas, w adalah bobot inersi yang menunjukkan pengaruh perubahan kecepatan dari vektor lama ke vektor yang baru. B. Algoritma Particle Swarm yang diusulkan oleh Jaberipour Algoritma PSO biasanya konvergen dengan cepat saat pencarian awal dan semakin lama semakin melambat. Selain itu, variabel w, c1, dan c2 merupakan faktor kritis yang mempengaruhi konvergensi algoritma PSO[4],[5]. Untuk mengatasi permasalahan tersebut maka penulis mengimplementasikan algoritma baru yaitu algoritma Particle Swarm yang diusulkan oleh Jaberipour dan kawan-kawan. Perbedaan utama antara algoritma ini dengan algoritma Particle Swarm dasar yaitu pada saat memperbarui masing-
masing partikel. Pada algoritma ini, posisi dan kecepatan partikel diperbarui dengan menggunakan persamaan sebagai berikut :
vik 1 (2r1 0.5)vik (2r2 0.5)( pbest ik xik ) (2r3 0.5)( gbest k xik )
w
k 1
(4)
(2r4 0.5)( gbest pbest ) k
k i
( 2r5 0.5)( gbest k xik )
x ik 1 pbest ik ( 2 r6 0 .5) v ik 1 (2r7 0.5) w k 1
(5)
dimana r1, r2, r3, r4, r5, r6, dan r7 adalah variabel nilai acak antara 0 dan 1. Langkah-langkah algoritma Particle Swarm yang diusulkan oleh Jaberipour ditunjukkan sebagai berikut : 1. Inisialisasi populasi dan kecepatan secara acak 2. Menghitung nilai fitness masing-masing partikel dan menentukan pbest dan gbest. Nilai fitness awal dari masing-masing pbesti sama dengan nilai fitness posisi awal partikel 3. Mengubah kecepatan partikel dengan menggunakan persamaan (4) 4. Memindahkan masing-masing partikel ke posisi yang baru menggunakan persamaan (5) 5. Membandingkan nilai fitness masing-masing partikel dengan pbest. Apabilai nilai fitness partikel ke i lebih kecil daripada nilai fitness pbesti, maka nilai pbesti digantikan oleh partikel ke i. Nilai pbesti kemudian disimpan pada matriks Mmxn, dimana m adalah jumlah partikel dan n menunjukkan jumlah variabel yang belum diketahui 6. Nilai pbesti terburuk diantara partikel terbaik pada matriks M dipilih sebagai pworsti 7. Memilih secara acak salah satu komponen pworsti, yaitu l, dan memperbarui nilainya dengan persamaan berikut : f ( pworst i ) pworst i , l new (6) pworst i , l pworst i , l (2r8 0.5) xU (l ) xL (l ) dimana r8 adalah nilai acak antara 0 dan 1, xU adalah batas atas dan xL adalah batas bawah dari tiap variabel. Pada beberapa kasus persamaan (6) terlalu rumit untuk diselesaikan. Untuk mengatasi permasalahan tersebut, finite differencing adalah sebuah algoritma yang digunakan untuk menghitung perkiraan turunan yang terinspirasi oleh
JURNAL TEKNIK ITS Vol. 1, (Sept, 2012) ISSN: 2301-9271
A-213
teorema Taylor. Perkiraan turunan dengan nilai akurasi tinggi dapat ditentukan dengan menggunakan persamaan central difference, yaitu sebagai berikut : f ( x Eei ) f ( x Eei ) f (7) ( x) xi 2E dimana f adalah fungsi objektif, ei adalah unit vektor dari pworsti, dan E bernilai 10-8. Oleh karena itu persamaan (6) dapat diperbaiki sebagai berikut : f ( pworst i Eei ) f ( pworst i Eei ) cd 2 E ( xU (l ) x L (l ))
yang sering digunakan untuk menguji kinerja algoritma optimasi. Data masukan lebih detail ditunjukkan pada Tabel 1.
pworst inew pworst i ,l ( 2r8 0.5)cd ,l
(8)
8. Membandingkan nilai fitness pworsti baru dengan nilai fitness pworst. Apabila nilai fitness pworsti baru lebih kecil daripada pworst, maka nilai pworsti digantikan oleh pworsti baru. Nilai pbesti baru kemudian disimpan pada matriks M 9. Nilai pbesti terbaik di antara semua partikel dipilih sebagai gbest. Kembali ke langkah 3 dan ulangi sampai konvergen. III. UJI COBA A. Data Uji Coba Data masukan utama yang dibutuhkan untuk proses uji coba adalah sistem persamaan nonlinear dan beberapa fungsi umum
Uji Coba
1
Skenario A B C D E
Tabel 1. Data Uji Coba Fungsi/Sistem Persamaan Nonlinear Fungsi Rastrigin Fungsi Objektif Sinus Fungsi Powell Quartic Fungsi Six-Hump Camelback Fungsi Rosenbrock
B. Skenario Uji Coba Uji coba penyelesaian sistem persamaan nonlinear dengan menggunakan algoritma Particle Swarm yang diusulkan oleh Jaberipour terbagi menjadi 3 skenario. Masing-masing skenario mempunyai tujuan yang berbeda. Berikut ditunjukkan penjelesan masing-masing uji coba : 1. Data masukan yang digunakan pada skenario uji coba pertama adalah fungsi umum yang sering digunakan untuk menguji kinerja algoritma optimasi. Tujuan pengujian ini tentu saja untuk mengetahui kinerja dari algoritma Particle Swarm. 2. Data masukan yang digunakan pada skenario uji coba kedua adalah sistem persamaan nonlinear. Tujuan pengujian ini adalah mengetahui efisiensi algoritma dalam menyelesaikan sistem persamaan nonlinear 3. Masing-masing skenario uji coba menggunakan jumlah partikel yang berbeda-beda, yaitu 100, 200, 500, dan 1000 partikel. Hal ini bertujuan untuk mengetahui hubungan antara jumlah partikel yang digunakan dengan solusi yang diperoleh. C. Hasil dan Analisis Uji Coba Pada uji coba pertama, pengujian dilakukan terhadap lima fungsi objektif. Hal ini dilakukan untuk mengetahui kinerja Tabel 3. Perbandingan hasil uji coba pertama Skenario
f1 (x) (3 5x1 )x1 1 2x2 0 A
f 2 (x) (3 5xi )xi 1 xi1 2xi1 0 i 2,....,9 f3 (x) (3 5x10 )x10 1 x9 0 x 42 x 4 x 6 0.75 0 4 1 x1x 2 x 2 0.405e 1.405 0
A
x1
B
x3
x4x6 1.5 0 2
x 4 0.605e (1 x 3 ) 0.395 0 2
x2x6 1.5 0 2 x 6 x1x 5 0 x5
x 1x 2 x 2x1 5 x 1x 2 x 3 85
2 C
B
x 13 x 2x 3 x 3x 2 60 x 1x 3 x 3x1 x 2 0 3 x 1 5, 2 x 2 4, 0.5 x 3 2.
e x1 8 x1 sin( x 2 ) 0 2
D
x1 x 2 1 0 ( x3 1) 3 0 3x1 cos( x 2 x3 ) 0.5 0
E
x12 625 x 22 0.25 0 e x1x2 2 x3
F
C
(10 3) 0 3
x13 3 x1 x 22 1 0 3 x12 x 2 x 23 1 0
D
E
Nilai
Hasil Uji Coba
Hasil Eksak
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 f(x) x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 f(x) x1 x2 x3 x4 f(x) x1 x2 f(x) x1 x2 f(x)
0.0031 -0.0024 -0.0005 0.0013 0.0034 -0.0029 0.0014 0.0012 -0.0056 -0.0000 0.0000 5.3621 5.3622 5.3630 5.3626 5.3622 5.3623 5.3621 5.3603 5.3678 5.3494 -12.1597 -0.0003 0.0000 0.0000 0.0000 0.0000 -0.0898 0.7126 -1.0316 1.0000 1.0000 0.0000
0 0 0 0 0 0 0 0 0 0 0 5.3623 5.3624 5.3621 5.3633 5.3627 5.3625 5.3624 5.3622 5.3627 5.3616 -12.15982 0 0 0 0 0 -0.08984 0.71266 -1.0316285 1 1 0
Iterasi Konvergensi
15
200
10
15
10
JURNAL TEKNIK ITS Vol. 1, (Sept, 2012) ISSN: 2301-9271
A-214
Tabel 2. Perbandingan hasil uji coba kedua Skenario
A
B
C
D
E
F
Nilai x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x1 x2 x3 x4 x5 x6 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2
Hasil Uji Coba -0.1060 0.3171 0.8061 -0.0875 -0.0582 0.4479 0.7058 0.0794 0.2780 0.7688
Hasil Jaberipur dkk
Iterasi Konvergensi
-0.3820 -0.4380 -0.4459 -0.4469 -0.4469 -0.4463 -0.4441 -0.4361 -0.4078 -0.3095
50
-0.9496 0.9676 -1.0488 0.9378 -1.0265 0.9728
-1 1 -1 1 -1 1
20
4 3 1
4 3 1
10
0.1755 0.8244 1.0005
0.1756 atau 0.7042 0.8244 atau 0.2957 1
15
0.5000 -0.0000 -0.5236
0.5 0 -0.5236
10
-0.2905 1.0842
-0.2905 atau -0.7937 1.0842 atau -0.7937
15
algoritma Particle Swarm dalam mencari solusi yang optimal. Hasil pengujian yang terbaik dibandingkan dengan hasil eksak dari masing-masing fungsi. Pengujian dianggap berhasil apabila hasil uji coba yang didapat sama atau mendekati hasil eksak fungsi. Perbandingan hasil uji coba pertama dengan hasil eksak fungsi ditunjukkan pada Tabel 2. Berdasarkan data tabel tersebut hasil pengujian skenario pertama, kedua, dan ketiga mendekati atau hampir sama dengan solusi eksak fungsinya, sedangkan hasil skenario keempat dan kelima memiliki nilai yang sama persis dengan solusi eksak fungsinya. Oleh karena
Gambar. 3. Grafik perbandingan antara jumlah partikel yang digunakan dengan hasil akhir yang didapat pada uji coba kedua
itu dapat disimpulkan bahwa algoritma Particle Swarm yang diusulkan oleh Jaberipour memiliki kinerja yang baik dalam mencari solusi yang optimal. Uji coba yang kedua dilakukan terhadap enam sistem persamaan nonlinear yang berbeda. Pengujian ini bertujuan untuk mengetahui efisiensi algoritma Particle Swarm yang diusulkan oleh Jaberipour dalam menyelesaikan sistem persamaan nonlinear. Hasil pengujian terbaik dibandingkan dengan hasil yang didapat oleh Jaberipur dkk. Perbandingan hasil uji coba keduan dengan hasil Jaberipour et al. ditampilkan pada Tabel 3. Berdasarkan data tabel tersebut, hasil akhir skenario pertama dan kedua mendekati hasil yang didapatkan oleh Jaberipour et al. sedangkan hasil akhir skenario ketiga, keempat, kelima, dan keenam sama persis dengan hasil Jaberipour. Berdasarkan data hasil terbaik pada Tabel 2 dan Tabel 3, algoritma Particle Swarm yang diusulkan oleh Jaberipour pada penyelesaian beberapa fungsi telah konvergen pada iterasi ke 10 sampai 20, namun ada fungsi yang konvergen pada iterasi ke 200. Berdasarkan hasil tersebut dapat disimpulkan bahwa algoritma Particle Swarm yang diusulkan oleh Jaberipour efisien dalam menyelesaikan sistem persamaan nonlinear. Masing-masing skenario pada uji coba pertama dan kedua menggunakan jumlah partikel yang berbeda-beda. Hal ini dilakukan untuk mengetahui hubungan antara jumlah partikel yang digunakan dengan hasil akhir yang didapat. Grafik hubungan antara jumlah partikel dengan nilai akhir fungsi f(x) pada uji coba pertama ditampilkan pada Gambar 2, sedangkan grafik hubungan untuk uji coba kedua ditampilkan pada Gambar 3. Berdasarkan gambar tersebut, hasil akhir yang didapat dengan menggunakan jumlah partikel yang berbeda tidak jauh berbeda. Oleh karena itu disimpulkan bahwa jumlah partikel yang digunakan tidak mempengaruhi hasil akhir.
IV. KESIMPULAN
Gambar. 2. Grafik perbandingan antara jumlah partikel yang digunakan dengan hasil akhir yang didapat pada uji coba pertama
Berdasarkan sistem yang telah dibuat beserta serangkaian uji coba yang telah dilakukan, maka dapat ditarik kesimpulan sebagai berikut :
JURNAL TEKNIK ITS Vol. 1, (Sept, 2012) ISSN: 2301-9271 1.
2.
3.
4.
Algoritma Particle Swarm yang diusulkan oleh Jaberipour dapat digunakan untuk menyelesaikan sistem persamaan nonlinear. Algoritma Particle Swarm yang diusulkan oleh Jaberipour memiliki kinerja yang baik dalam mencari solusi yang optimal. Hal ini dibuktikan dengan hasil uji coba pertama, solusi yang didapat mendekati solusi eksak masing-masing fungsinya. Berdasarkan hasil pengujian terbaik dari masing-masing skenario uji coba, penyelesaian beberapa fungsi dengan algoritma Particle Swarm yang diusulkan oleh Jaberipour telah konvergen pada iterasi ke 10 sampai iterasi ke 20. Namun, terdapat penyelesaian fungsi yang konvergen pada iterasi ke 200. Jumlah partikel yang digunakan oleh algoritma Particle Swarm dengan nilai minimal 100 partikel tidak mempengaruhi hasil akhir yang didapatkan. DAFTAR PUSTAKA
[1]
[2]
[3] [4]
[5]
Jaberipour Majid, Khorram Esmaile, Karimi Behrooz, “Particle swarm algorithm for solving systems of nonlinear equations,” Elsevier Computers and Mathematics with Applications ScienceDirect (2011) 566-576. J. Kennedy, R.C. Eberhart, “Particle swarm optimization,” IEEE International Conference on Neural Networks, IEEE Service Center, Piscataway, NJ, 1942-1948. C. K. Mohan. E. Ozcan. Particle Swarm Optimization Homepage. Available: http://www.cis.syr.edu/~mohan/pso/ R. Eberhart, Y. Shi, “Comparing inertia weight and constriction factors in particle swarm optimization,” in: Proceeding of the 2000 Congress on Evol. Comput. (2000) 84-88. A. El-Gallad, M. El-Hawary, A. Sallam, A. Kalas, “Enhancing the particle swarm optimizer via proper parameters selection,” IEEE Canadian Conference on Electr. Comput. Eng. (2002) 792-797.
A-215
