Particle swarm optimization

Dalam Ilmu komputasi, Particle Swarm Optimization (biasa disingkat: PSO) adalah sebuah metode komputasi yang mengoptimasi suatu masalah dengan menggunakan metode iteratif untuk memperbaiki suatu kandidat solusi dengan ukuran kualitas tertentu. Cara PSO dalam menyelesaikan masalah tersebut adalah dengan menggunakan sebuah populasi yang berisi kandidat-kandidat solusi yang disebut sebagai partikel, dan kemudian menggerakkan partikel-partikel tersebut di dalam ruang pencarian berdasarkan rumus sederhana dalam penentuan posisi dan kecepatan (velocity) tiap partikel. Pergerakan setiap partikel dalam ruang pencarian ini tidak hanya dipengaruhi oleh posisi lokal terbaik yang saat ini diketahui oleh partikel tersebut (local best known position), tetapi pergerakannya juga dipandu menuju posisi terbaik dalam ruang pencarian secara keseluruhan, yang diperbarui seiring dengan ditemukannya posisi yang lebih baik oleh partikel lain. Hal ini diharapkan dapat menggerakkan kawanan atau gerombolan menuju solusi terbaik.

PSO awalnya dikaitkan dengan Kennedy, Eberhart, dan Shi dan pertama kali dimaksudkam untuk simulasi perilaku sosial, sebagai representasi non natural (stylized representation) dari pergerakan organisme kawanan burung atau gerombolan ikan. Algoritmanya disederhanakan dan diamati untuk melakukan optimasi. Buku karya Kennedy dan Eberhart menjelaskan banyak aspek filosofis dari PSO dan kecerdasan gerombolan. Sebuah survei mendalam mengenai aplikasi PSO dibuat oleh Poli. Baru-baru ini, sebuah kajian komprehensif mengenai karya-karya teoretis dan eksperimental mengenai PSO telah diterbitkan oleh Bonyadi dan Michalewicz.

PSO adalah salah satu algoritma metaheuristik, yang artinya PSO hanya membuat sedikit atau bahkan tidak ada asumsi apapun mengenai masalah yang dioptimalkan dan mampu menelusuri ruang kandidat solusi yang sangat luas. Selain itu, PSO tidak menggunakan gradien dari masalah yang sedang dioptimalkan, yang berarti PSO tidak mengharuskan masalah pengoptimalan merupakan fungsi terdiferensialkan sebagaimana yang diharuskan dalam metode pengoptimalan klasik, seperti penurunan gradien dan metode quasi-newton. Meskipun begitu, PSO, sebagaimana algoritma metaheuristik lainnya, tidak dapat menjamin untuk menemukan solusi optimal global.

 Algoritma 
Varian dasar dari algoritma PSO bekerja dengan menggunakan sebuah populasi (disebut kawanan atau gerombolan) dari kandidat solusi (disebut partikel). Partikel-partikel tersebut bergerak di dalam ruang pencarian mengikut pada beberapa rumus sederhana. Pergerakan partikel dipandu oleh posisi terbaik (local best known position) mereka sendiri dan posisi terbaik seluruh kawanan dalam ruang pencarian. Ketika posisi yang lebih baik ditemukan, posisi terseut akan memandu pergerakan kawanan. Proses ini akan terus diulang dan diharapkan, tetapi tidak menjamin; solusi yang memuaskan akan ditemukan di akhir iterasi.

Secara formal, misalkan f: ℝn → ℝ adalah fungsi biaya yang akan diminimalkan. Fungsi ini mengambil satu kandidat solusi sebagai parameter dalam bentuk vektor baris dari bilangan riil dan menghasilkan keluaran sebuah bilangan riil yang menunjukkan nilai fungsi objektif dari kandidat solusi yang diberikan. Nilai gradien dari f tidak diketahui. Tujuan dari permasalahan ini adalah menemukan sebuah solusi a yang mana f(a) ≤ f(b) untuk semua b di dalam ruang pencarian solusi, yang berarti a adalah minimal global.

Misalkan S adalah jumlah partikel dalam kawanan yang setiap partikel tersebut memiliki satu nilai posisi xi ∈ ℝn dalam ruang pencarian solusi dan satu nilai kecepatan vi ∈ ℝn. Misal, pi adalah posisi terbaik yang diketahui partikel i dan g adalah posisi terbaik yang diketahui seluruh kawanan. Maka, algoritma PSO dasar yang dapat meminimalkan fungsi biaya adalah, antara lain:


 for setiap partikel i = 1, ..., S do
     Inisialisasi posisi partikel dengan vektor acak berdasarkan distribusi seragam kontinu: xi ~ U(blo, bup)
     Inisialisasi posisi awal partikel menjadi posisi terbaik yang diketahui partikel: pi ← xi
     if f(pi) < f(g) then
         perbarui posisi terbaik seluruh kawanan: g ← pi
     Inisialisasi kecepatan (velocity) partikel: vi ~ U(-|bup-blo|, |bup-blo|)
 while kriteria penghentian belum terpenuhi do:
     for setiap partikel i = 1, ..., S do
         for setiap dimensi d = 1, ..., n do
             Pilih angka acak: rp, rg ~ U(0,1)
             Perbarui kecepatan partikel: vi,d ← w vi,d + φp rp (pi,d-xi,d) + φg rg (gd-xi,d)
         Perbarui posisi partikel: xi ← xi + vi
         if f(xi) < f(pi) then
             Perbarui posisi terbaik yang diketahui partikel: pi ← xi
             if f(pi) < f(g) then
                 Perbarui posisi terbaik seluruh kawanan: g ← pi

Nilai blo dan bup, masing-masing menunjukkan batas bawah dan batas atas dari ruang pencarian. Parameter w adalah bobot inersia.  Sedangkan parameter φp dan φg sering kali disebut sebagai koefisien kognitif dan koefisien sosial.

Kriteria penghentian (termination criterion) dapat berupa maksimum jumlah iterasi yang dilakukan atau suatu solusi fungsi objektif yang memuaskan telah ditemukan. Parameter w, φp, dan φg dipilih oleh praktisi yang ketiganya ini dapat mengontrol perilaku dan kemanjuran algoritma PSO (di bawah).

 Seleksi parameter 

Untuk mencegah divergensi ("ledakan"), bobot inersia harus lebih kecil dari 1. Dua parameter lainnya dapat diturunkan melalui pendekatan pembatasan (constriction approach), atau dapat dipilih secara bebas, tetapi para ahli menganalisis bahwa domain konvergensi dapat digunakan untuk membatasi parameter-parameter tersebut. Nilai-nilai yang umum digunakan adalah .

Parameter PSO juga dapat di-tuning dengan menggunakan pengoptimal lain, sebuah konsep yang dikenal sebagai optimasi-meta, atau bahkan di-tuning selama pengoptimalan, misal, dengan menggunakan logika fuzzy.

Parameter juga telah di-tuning untuk berbagai skenario pengoptimalan.

 Ketetanggaan dan topologi  
Topologi dari kawanan mendefinisikan bagaimana subhimpunan partikel dapat digunakan oleh setiap partikel untuk bertukar informasi. Versi dasar algoritma ini menggunakan topologi global sebagai struktur komunikasi pada kawanan. Topologi ini memungkinkan semua partikel untuk berkomunikasi dengan semua partikel lainnya, sehingga seluruh kawanan berbagi posisi terbaik yang sama g' dari sebuah partikel. Namun, pendekatan ini dapat menyebabkan kawanan terjebak ke dalam minimum lokal,Mendes, R. (2004). Population Topologies and Their Influence in Particle Swarm Performance (Tesis PhD). Universidade do Minho.. Oleh karena itu, topologi yang berbeda telah digunakan untuk mengontrol aliran informasi di antara partikel. Sebagai contoh, pada topologi lokal, partikel-partikel hanya berbagi informasi dengan sebagian kecil partikel. Sebagian kecil ini dapat berupa sebuah geometriSuganthan, Ponnuthurai N. "Particle swarm optimiser with neighbourhood operator." Evolutionary Computation, 1999. CEC 99. Prosiding Kongres 1999 tentang. Vol. 3. IEEE, 1999. - misalnya "partikel terdekat m" - atau, lebih sering, partikel sosial, yaitu sekumpulan partikel yang tidak bergantung pada jarak apa pun. Dalam kasus seperti itu, varian PSO dikatakan sebagai yang terbaik secara lokal (dibandingkan yang terbaik secara global untuk PSO dasar).

Topologi kawanan yang umum digunakan adalah ring atau cincin, yang masing-masing partikel hanya memiliki dua tetangga, tetapi terdapat topologi lainnya. Topologi ini tidak harus statis. Faktanya, karena topologi terkait dengan diversitas komunikasi partikel, beberapa upaya telah dilakukan untuk membuat topologi adaptif (SPSO,SPSO Particle Swarm Central APSO, Almasi, O. N. and Khooban, M. H. (2017). A parsimonious SVM model selection criterion for classification of real-world data sets via an adaptive population-based algorithm. Neural Computing and Applications, 1-9. https://doi.org/10.1007/s00521-017-2930-y stochastic star,Miranda, V., Keko, H. and Duque, Á. J. (2008). Stochastic Star Communication Topology in Evolutionary Particle Swarms (EPSO). International Journal of Computational Intelligence Research (IJCIR), Volume 4, Number 2, pp. 105-116 TRIBES,Clerc, M. (2006). Particle Swarm Optimization. ISTE (International Scientific and Technical Encyclopedia), 2006 Cyber Swarm,Yin, P., Glover, F., Laguna, M., & Zhu, J. (2011). A Complementary Cyber Swarm Algorithm. International Journal of Swarm Intelligence Research (IJSIR), 2(2), 22-41 dan C-PSO)

Dengan menggunakan topologi cincin, PSO dapat mencapai paralelisme tingkat generasi, yang secara signifikan meningkatkan kecepatan evolusi.

 Proses kerja 
Ada beberapa aliran pemikiran tentang mengapa dan bagaimana algoritma PSO dapat melakukan optimasi.

Keyakinan umum di antara para peneliti adalah bahwa perilaku kawanan bervariasi antara perilaku eksploratif, yaitu mencari wilayah yang lebih luas dari ruang pencarian, dan perilaku eksploitatif, yaitu pencarian yang berorientasi pada lokal sehingga lebih dekat ke optimal (mungkin lokal). Aliran pemikiran ini telah lazim sejak awal PSO. Aliran pemikiran ini berpendapat bahwa algoritma PSO dan parameter-parameternya harus dipilih sedemikian rupa sehingga dapat menyeimbangkan dengan tepat antara eksplorasi dan eksploitasi untuk menghindari konvergensi dini ke suatu optimal lokal, tetapi tetap memastikan tingkat konvergen yang baik ke optimal. Keyakinan ini adalah pendahulu dari banyak varian PSO, lihat di bawah ini.

Aliran pemikiran lainnya adalah bahwa perilaku kawanan PSO tidak dipahami dengan baik dalam hal bagaimana hal tersebut memengaruhi kinerja optimasi yang sebenarnya, terutama untuk ruang pencarian berdimensi lebih tinggi dan masalah optimasi yang mungkin diskontinyu, bising, dan bervariasi terhadap waktu. Aliran pemikiran ini hanya mencoba untuk menemukan algoritma dan parameter PSO yang menghasilkan kinerja yang baik terlepas dari bagaimana perilaku swarm dapat ditafsirkan dalam kaitannya dengan eksplorasi dan eksploitasi. Penelitian-penelitian tersebut telah menghasilkan penyederhanaan algoritma PSO, lihat  di bawah.

 Konvergensi 
Sehubungan dengan PSO, kata konvergensi biasanya mengacu pada dua definisi yang berbeda:

 Konvergensi urutan solusi (alias, analisis stabilitas, konvergen) yang mana semua partikel telah konvergen ke suatu titik di ruang pencarian, yang mungkin atau mungkin bukan merupakan titik optimal,
 Konvergensi ke optimum lokal yang mana semua personal terbaik p' atau, sebagai alternatif, posisi terbaik dari kawanan g', mendekati optimum lokal dari masalah, terlepas dari bagaimana perilaku kawanan tersebut.

Konvergensi dari barisan solusi telah diteliti untuk PSO. Analisis-analisis ini telah menghasilkan panduan untuk memilih parameter PSO yang diyakini dapat menyebabkan konvergensi pada suatu titik dan mencegah divergensi partikel kawanan (partikel-partikel tidak bergerak tanpa batas dan akan berkumpul di suatu tempat). Namun, analisis tersebut dikritik oleh Pedersen karena terlalu menyederhanakan dengan mengasumsikan bahwa kawanan tersebut hanya memiliki satu partikel, tidak menggunakan variabel stokastik, dan titik-titik tariknya, yaitu posisi terbaik partikel p' dan posisi terbaik kawanan g', tetap konstan selama proses pengoptimalan. Namun, hal itu ditunjukkan bahwa penyederhanaan ini tidak memengaruhi batas-batas yang ditemukan oleh penelitian-penelitian ini untuk parameter yang kawanan tersebut konvergen. Upaya yang cukup besar telah dilakukan dalam beberapa tahun terakhir untuk melemahkan asumsi pemodelan yang digunakan selama analisis stabilitas PSO, dengan hasil umum terbaru yang berlaku untuk berbagai varian PSO dan memanfaatkan asumsi pemodelan minimal yang diperlukan.

Konvergensi ke optimum lokal telah dianalisis untuk PSO dalam  dan. Telah terbukti bahwa PSO membutuhkan beberapa modifikasi untuk menjamin ditemukannya optimum lokal.

Ini berarti bahwa menentukan kemampuan konvergensi dari algoritma dan parameter PSO yang berbeda masih bergantung pada hasil empiris. Salah satu upaya untuk mengatasi masalah ini adalah pengembangan strategi "pemelajaran ortogonal" untuk meningkatkan penggunaan informasi yang sudah ada dalam hubungan antara p' dan g', untuk membentuk contoh konvergen utama dan efektif dengan topologi PSO apa pun. Tujuannya adalah untuk meningkatkan kinerja PSO secara keseluruhan, termasuk konvergensi global yang lebih cepat, kualitas solusi yang lebih tinggi, dan robustness yang lebih kuat. Namun, penelitian tersebut tidak memberikan bukti teoretis untuk membuktikan klaim mereka.

 Mekanisme adaptif 
Tanpa memerlukan pertukaran antara konvergensi ('eksploitasi') dan divergensi ('eksplorasi'), sebuah mekanisme adaptif bisa diberlakukan. Adaptive particle swarm optimization (APSO)  memiliki efisiensi pencarian yang lebih baik daripada PSO standar. APSO dapat melakukan pencarian global di seluruh ruang pencarian dengan kecepatan konvergensi yang lebih tinggi. APSO memungkinkan kontrol otomatis terhadap bobot inersia, koefisien akselerasi, dan parameter algoritmik lainnya pada saat proses berjalan, sehingga meningkatkan efektivitas dan efisiensi pencarian secara bersamaan. Selain itu, APSO dapat mengambil tindakan terhadap partikel terbaik secara global untuk keluar dari kemungkinan optima lokal. Namun, APSO akan memperkenalkan parameter algoritma baru, tetapi tidak menambah kompleksitas desain atau implementasi.

Selain itu, melalui pemanfaatan mekanisme evaluasi kecocokan (fitness) skala-adaptif, PSO dapat secara efisien mengatasi masalah optimasi yang mahal secara komputasi.

 Varian 

Banyak variasi dari algoritma PSO, bahkan yang paling dasar sekalipun. Sebagai contoh, ada berbagai cara untuk menginisialisasi partikel dan kecepatan (misalnya, mulai dengan kecepatan nol), cara meredam kecepatan, hanya memperbarui pi dan g setelah seluruh kawanan telah diperbarui, dll. Beberapa pilihan ini dan dampak performa yang mungkin telah dibahas dalam literatur.

Sejumlah implementasi standar telah dibuat oleh peneliti terkemuka, "diciptakan untuk digunakan, baik sebagai dasar untuk pengujian performa perbaikan teknik PSO maupun untuk mewakili PSO kepada komunitas optimisasi yang lebih luas. Memiliki algoritma standar yang terkenal dan secara ketat didefinisikan memberikan titik perbandingan yang berharga yang dapat digunakan di seluruh bidang penelitian untuk menguji kemajuan baru dengan lebih baik." Yang terbaru adalah Standard PSO 2011 (SPSO-2011).

 Hibridisasi 
Varian PSO yang baru dan lebih canggih juga terus diperkenalkan dalam upaya untuk meningkatkan kinerja optimasi. Ada beberapa tren dalam penelitian tersebut; salah satunya adalah membuat metode optimasi hibrida menggunakan PSO yang dikombinasikan dengan pengoptimal lain, mis, menggabungkan PSO dengan optimasi berbasis biogeografi, dan penggabungan metode pemelajaran yang efektif.

 Mengatasi konvergensi prematur
Tren penelitian lain adalah mencoba dan mengatasi konvergensi prematur (yaitu, stagnasi optimasi), misalnya dengan membalikkan atau mengganggu pergerakan partikel PSO, pendekatan lain untuk menangani konvergensi prematur adalah dengan menggunakan kawanan berganda (multi-swarm optimization). Pendekatan multi-swarm juga dapat digunakan untuk mengimplementasikan optimasi multi-objektif. Terakhir, ada perkembangan dalam mengadaptasi parameter perilaku PSO selama pengoptimalan.

 Penyederhanaan 
Aliran pemikiran lainnya adalah bahwa PSO harus disederhanakan sebanyak mungkin tanpa mengganggu kinerjanya; konsep umum yang sering disebut sebagai pisau cukur Occam. Penyederhanaan PSO pada awalnya disarankan oleh Kennedy dan telah diteliti secara lebih ekstensif, yang terlihat bahwa kinerja optimasi meningkat, dan parameter lebih mudah disetel serta berkinerja lebih konsisten di berbagai masalah optimasi.

Argumen lain yang mendukung penyederhanaan PSO adalah bahwa metaheuristik hanya dapat dibuktikan kemanjurannya secara empiris dengan melakukan eksperimen komputasi dengan jumlah masalah optimasi yang terbatas. Ini berarti metaheuristik seperti PSO tidak dapat dibuktikan kebenarannya dan hal ini meningkatkan risiko terjadinya kesalahan dalam deskripsi dan implementasinya. Sebuah contoh yang baik dari hal ini  menyajikan varian yang menjanjikan dari algoritma genetika (metaheuristik populer lainnya), tetapi kemudian ditemukan cacat karena sangat bias dalam pencarian optimasi terhadap nilai yang sama untuk dimensi yang berbeda dalam ruang pencarian, yang kebetulan merupakan optimal dari masalah tolok ukur yang dipertimbangkan. Bias ini disebabkan oleh kesalahan pemrograman, dan sekarang telah diperbaiki.

Inisialisasi kecepatan mungkin memerlukan input tambahan. Varian Bare Bones PSO telah diusulkan pada tahun 2003 oleh James Kennedy, dan sama sekali tidak perlu menggunakan kecepatan.

Varian lain yang lebih sederhana adalah optimasi kawanan partikel yang diakselerasi (accelerated particle swarm optimization, APSO),X. S. Yang, S. Deb dan S. Fong, Accelerated particle swarm optimization and support vector machine for business optimization and applications, NDT 2011, Springer CCIS 136, pp. 53-66 (2011). yang juga tidak perlu menggunakan velocity dan dapat mempercepat konvergensi di banyak aplikasi. Tersedia kode demo sederhana dari APSO.

 Optimasi multi-objektif  
PSO juga telah diterapkan pada masalah multi-objektif, yang mana perbandingan fungsi objektifnya mempertimbangkan dominansi Pareto ketika menggerakkan partikel PSO dan solusi yang tidak terdominasi disimpan untuk mendekati front pareto.

 Biner, diskrit, dan kombinatorial 
Karena persamaan PSO yang diberikan di atas bekerja pada bilangan riil, metode yang umum digunakan untuk menyelesaikan masalah diskrit adalah memetakan ruang pencarian diskrit ke domain kontinu, menerapkannya ke PSO klasik, dan kemudian memetakan hasilnya.  Pemetaan seperti itu bisa sangat sederhana (misalnya dengan hanya menggunakan nilai pembulatan) atau lebih canggih.Roy, R., Dehuri, S., & Cho, S. B. (2012). A Novel Particle Swarm Optimization Algorithm for Multi-Objective Combinatorial Optimization Problem. 'International Journal of Applied Metaheuristic Computing (IJAMC)', 2(4), 41-57

Namun, perlu dicatat bahwa persamaan pergerakan menggunakan operator yang mengerjakan empat tindakan:
menghitung selisih dua posisi. Hasilnya adalah kecepatan (lebih tepatnya perpindahan)
mengalikan kecepatan dengan koefisien numerik
menambahkan dua kecepatan
menerapkan kecepatan pada suatu posisi

Biasanya posisi dan kecepatan diwakili oleh n bilangan riil, dan operator-operator ini adalah -, *, +, dan lagi +. Namun, semua objek matematika tersebut dapat didefinisikan dengan cara yang sama sekali berbeda, untuk menyelesaikan masalah biner (atau lebih umum lagi masalah diskrit), atau bahkan masalah kombinatorial.Kennedy, J. & Eberhart, RC (1997). A discrete binary version of the particle swarm algorithm, Conference on Systems, Man, and Cybernetics, Piscataway, NJ: IEEE Service Center, pp. 4104-4109 Clerc, M. (2004). Discrete Particle Swarm Optimization, illustrated by the Traveling Salesman Problem, New Optimization Techniques in Engineering, Springer, pp. 219-239Clerc, M. (2005). Binary Particle Swarm Optimisers: toolbox, derivations, and mathematical insights, Open Archive HAL Salah satu pendekatannya adalah dengan mendefinisikan ulang operator-operator yang didasarkan pada himpunan.

 Lihat juga 

 Artificial bee colony algorithm
 Algoritma lebah
 Derivative-free optimization
 Pengoptimalan multi-kawanan
 Filter partikel
 Kecerdasan gerombolan
 Pencarian gerombolan ikan
 Dispersive flies optimisation

 Referensi 
{{Reflist|refs=

Zhang, Wen-Jun; Xie, Xiao-Feng (2003). DEPSO: hybrid particle swarm with differential evolution operator. IEEE International Conference on Systems, Man, and Cybernetics (SMCC), Washington, DC, USA: 3816-3821.

Xie, Xiao-Feng; Zhang, Wen-Jun; Yang, Zhi-Lian (2002). A dissipative particle swarm optimization. Congress on Evolutionary Computation (CEC), Honolulu, HI, USA: 1456-1461.

<ref name="tu04corrections">{{cite journal | first1=Z. | last1=Tu | title=Corrections to "A Robust Stochastic Genetic Algorithm (StGA) for Global Numerical Optimization | last2=Lu | first2=Y. | journal=IEEE Transactions on Evolutionary Computation | year=2008 | volume=12 | issue=6 | pages=781 | doi=10.1109/TEVC.2008.926734| s2cid=2864886 }}</ref>

f

}}

 Pranala luar 

Particle Swarm Central adalah repositori yang bersi informasi terkait PSO. Terdapat beberapa source code'' yang tersedia.
Video singkat yang menayangkan bagaimana PSO mengoptimasi tiga fungsi tolok ukur
Simulasi konvergensi PSO dalam ruang dua dimensi (Matlab).
Aplikasi PSO.

Pranala menuju source code PSO

Category:Metaheuristik
Category:Algoritma evolusioner