ISSN : 2407 - 6511
SWARM GENETIC ALGORITHM, SUATU HIBRIDA DARI ALGORITMA GENETIKA DAN PARTICLE SWARM OPTIMIZATION Taufan Mahardhika1 1
Prodi S1 Kimia, Sekolah Tinggi Analis Bakti Asih 1
[email protected]
Abstrak Swarm Genetic Algorithm (SGA) merupakan suatu hibrida dari Algoritma Genetika (AG) dan Particle Swarm Optimization (PSO). SGA menggunakan proses seleksi, perkawinan dan mutasi yang diadopsi dari AG untuk menciptakan generasi baru. Pertumbuhan setiap individu dalam generasi dalam SGA dipengaruhi oleh faktor perubahan individu, individu terbaik dan faktor sosial yang diadopsi dari PSO. Berdasarkan percobaan yang dilakukan diperoleh bahwa SGA ini lebih baik daripada AG namun SGA ini sebanding dengan PSO. Kata kunci : Swarm Genetic Algorithm, Algoritma Genetika, Particle Swarm Optimization. 1.Pendahuluan Metode heuristic yang berkembang hingga saat ini adalah Evolutionary Computation, Simulated Annealing, Tabu Search, Algoritma Genetik (AG), Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO) dan lain-lain. Metode heuristic yang menjanjikan adalah Algoritma Genetika dan PSO untuk dapat menyelesaikan permasalahan optimasi sebagaimana diutarakan Deepa dan Sugumaran dalam papernya[1]. Berikut adalah perbandingan AG dan PSO yang dikemukakan Li dkk. [4] Item pembanding Operator Kemampuan pencarian global Implementasi Terjebak di lokal optimum Efisiensi komputasi Kecepatan optimasi Kompleksitas algoritma Konvergensi
Tabel 1. Perbandingan AG dan PSO Algoritma Genetika Particle Swarm Optimization code, seleksi, cross over, mutasi Inertia, kognitif, sosial Tinggi Rendah Sukar Sederhana Jarang Sering Rendah Tinggi Rendah Tinggi Tinggi Rendah Sulit Mudah
Dari perbandingan yang dilakukan oleh Li dkk. menjadi inspirasi untuk mencoba mengkombinasikan AG dan PSO sehingga terciptalah Swarm Genetic Algorithm (SGA) ini. 2.Algoritma Genetika (AG) Algoritma genetik (AG) dikemukakan oleh Goldberg [2] adalah suatu teknik pencarian heuristik yang meniru proses seleksi alam. Pada metode ini suatu populasi dari kandidat solusi (yang disebut individu) akan dihitung nilai kecocokannya (fitnes) lalu dievolusi menuju solusi yang lebih baik. Elemen dasar dari AG ini adalah pengkodean, seleksi, perkawinan (cross over) dan mutasi. Algoritma genetika diawali dengan pencarian secara random sejumlah individu yang nantinya akan digabungkan dalam suatu populasi. Dari setiap populasi akan dihitung nilai fitnes yang dimiliki oleh setiap individu. Semakin baik nilai fitnes dari individu maka akan memiliki peluang yang besar untuk tergabung dalam populasi selanjutnya. Setiap individu memiliki nilai gen yang biasanya berupa bilangan biner. Gen dari setiap individu akan dilakukan modifikasi (dapat berupa kombinasi atau mutasi) untuk dapat bergabung di populasi selanjutnya. Populasi baru yang merupakan kumpulan modifikasi individu sebelumnya akan digunakan untuk iterasi selanjutnya untuk membentuk populasi yang lebih baik. Hal ini dilakukan terus menerus hingga nilai fitnes yang diharapkan terpenuhi. 3.Particle Swarm Optimization (PSO)
31
ISSN : 2407 - 6511 Particle Swarm Optimization (PSO) [1] merupakan metode komputasi untuk mengoptimasi permasalahan dengan menggunakan teknik ableive dalam memperbaiki kualitas kandidat dari solusi. Ide sederhana dari PSO adalah model matematika dan simulasi dalam pencarian makanan oleh sekawanan burung (partikel). Dalam ruang berdimesi hingga setiap partikel dalam sekawanan bergerak menuju titik optimal dengan menambahkan suatu kecepatan dari posisinya. Kecepatan dipengaruhi oleh tiga komponen yakni momentum inersia, kognitif dan sosial. Komponen inersia menunjukan perilaku burung untuk terbang dalam arah sebelumnya. Komponen kognitif dari model memberikan informasi posisi terbaik burung tersebut dan komponen sosial merupakan posisi terbaik dari burung yang ada dalam kawanannya. 4.Swarm Genetic Algorithm (SGA) Hibrida adalah turunan yang dihasilkan dari perkawinan antara dua jenis yang berlainan. Swarm Genetic Algorithm (SGA) adalah suatu hasil hibrida dari AG dan PSO. Cara kerja SGA adalah a) Pemilihan n individu secara acak, kumpulan n individu ini disebut sebagai generasi pertama. b) Setiap individu mencari (menseleksi) pasangan hidup dari generasinya sehingga tercapat n/2 pasangan. c) Setiap pasangan menjadi orang tua dan melahirkan 2 anak (proses cross over) sehingga menghasilkan n anak dari n/2 pasangan. d) Dari n anak tersebut dimungkinkan terjadi mutasi gen. e) Pertumbuhan n anak dipengaruhi oleh 3 faktor yakni Inertia, keinginan anak untuk berubah/bergerak, Kognitif, faktor orang tua (the best personal) dan Sosial, faktor tokoh terbaik dalam lingkungannya (the best grup) f) n anak tumbuh menjadi individu yang mungkin menjadi calon orang tua g) kumpulan n individu ini disebut sebagai generasi ke-2 h) Generasi kedua ini melakukan proses perulangan tahap ke-b hingga mencapai generasi terakhir.
5.Percobaan AG, PSO, SGA Kami melakukan percobaan untuk membandingkan kinerja dari GA vs PSO vs SGA untuk mencari nilai minimum dari 3 fungsi yang kami pilih dari paper Digalakis dan Margaritis [2] 𝑓 = 100(𝑥 − 𝑥 ) + 1(1 − 𝑥 ) (1) 𝑓 = 200 + 𝑓 =1+
(𝑥 − 10 cos(2𝜋𝑥 )) (2) 𝑥 − 4000
cos
𝑥 √𝑖
(3)
dengan menggunakan 30 individu awal yang sama untuk ketiga metode, dilakukan proses regenerasi hingga generasi ke-24. Percobaan ini kami lakukan hingga 100 kali pengulangan. 5.1 Hasil Pengujian pada 𝒇𝟏
32
ISSN : 2407 - 6511
Gambar 1. Hasil pengujian ketiga metode pada f1 Tabel 2. Nilai optimal 𝑓 dari 100 percobaan AG PSO SGA Terbaik 0.0000 0.0000 0.0000 Rata-rata 0.2498 0.2375 0.1799 Standar deviasi 0.6436 0.2832 0.2461 PSO.
Dari tabel 2 di atas dapat disimpulkan bahwa SGA ini menghasilkan nilai yang sama dengan AG dan
33
ISSN : 2407 - 6511 5.2 Hasil Pengujian pada 𝒇𝟐
Gambar 2. Hasil pengujian ketiga metode pada f2 Tabel 3. Nilai optimal 𝑓 dari 100 percobaan AG PSO SGA Terbaik 98.1013 58.4186 57.9142 Rata-rata 153.2354 121.3304 95.6834 Standar deviasi 22.8962 18.7212 20.1061 Dari tabel 3 di atas dapat disimpulkan bahwa SGA ini menghasilkan nilai yang lebih baik dibandingkan AG dan PSO.
34
ISSN : 2407 - 6511 5.3 Hasil Pengujian pada 𝒇𝟑
Gambar 15. Hasil pengujian ketiga metode pada f3 Tabel 4. Nilai optimal 𝑓 dari 100 percobaan AG PSO SGA Terbaik 5.3545 1.9320 1.3267 Rata-rata 22.6371 4.8053 6.5428 Standar 12.5799 1.2331 4.5908 deviasi Dari tabel 4 di atas dapat disimpulkan bahwa SGA ini menghasilkan nilai yang lebih baik dibandingkan AG. Dari 100 kali percobaan SGA dengan PSO dapat disimpulkan kedua metode ini menghasilkan nilai optimal f3 yang sama. Namun dari 100 kali percobaan ini SGA dapat menghasilkan nilai yang lebih baik dari PSO.
35
ISSN : 2407 - 6511 6.
Kesimpulan
Dari fungsi pertama SGA, GA dan PSO menghasilkan nilai yang sama. Di fungsi kedua SGA menghasilkan nilai yang lebih baik daripada GA dan PSO. Di fungsi ketiga SGA menghasilkan nilai yang sama dengan PSO namun lebih baik daripada GA. Jadi SGA ini adalah metode yang lebih baik daripada GA dan PSO. Namun SGA ini sama baiknya dengan PSO untuk fungsi tertentu. Daftar Pustaka: [1] [2] [3] [4]
Deepa, S. N., G. Sugumaran, “MPSO based Model Order Formulation Technique for SISO Continuous Systems”, World Academy of Science, Engineering and Technology 75, 2011 O Digalakis, J. G., dan Margaritis, K. G., “On B enchmarking Functions for Genetic Algorithms,” Int. J. Computer Math., Vol. 00, 2000 Goldberg, D.E., “Genetic Algorithms in Search, Optimization, and Machine Learning”, AddisonWesley, 1989 Li, Zhijie, Xiangdong Liu, Xiaodong Duan, dan Feixue Huang, "Comparative Research on Particle Swarm Optimization and Genetic Algorithm" Computer and Information Science Volume 3 No. 1, February, 2010
36
