Optimasi kawanan partikel
Dalam ilmu komputer, optimasi gerombolan partikel (PSO) adalah metode komputasi yang bertujuan untuk meningkatkan kandidat solusi secara berulang dengan mempertimbangkan ukuran kualitas tertentu. Metode ini memecahkan masalah dengan memanipulasi populasi kandidat solusi, yang disebut partikel, dan memindahkan partikel-partikel tersebut dalam ruang pencarian berdasarkan rumus matematika sederhana yang menggambarkan posisi dan kecepatan partikel. Pergerakan setiap partikel dipengaruhi oleh posisi lokalyang paling terkenal, namun juga diarahkan ke posisi paling terkenal di ruang pencarian, yang diperbarui saat partikel lain menemukan posisi yang lebih baik. Tujuannya adalah untuk memimpin kelompok menuju solusi terbaik.
PSO awalnya dikaitkan dengan Kennedy, Eberhart dan Shi dan pada awalnya dimaksudkan untuk mensimulasikan perilaku sosial, mewakili pergerakan organisme dalam kawanan burung atau gerombolan ikan.Algoritma tersebut kemudian disederhanakan dan diamati untuk melakukan optimasi. Buku Kennedy dan Eberhart menjelaskan banyak aspek filosofis PSO dan badan intelijen mafia. Poli melakukan survei komprehensif terhadap permintaan PSO. Baru-baru ini, Bonyadi dan Michalewicz menerbitkan tinjauan komprehensif karya teoretis dan eksperimental tentang PSO.
PSO bersifat metaheuristik karena membuat sedikit atau tidak ada asumsi mengenai masalah yang sedang dioptimalkan dan dapat mencari solusi yang mungkin dalam ruang yang sangat luas. Selain itu, PSO tidak menggunakan gradien dari masalah yang sedang dioptimalkan, sehingga masalah optimasi tidak perlu dapat dibedakan, seperti yang disyaratkan oleh metode optimasi klasik seperti metode penurunan gradien dan metode quasi-Newton. Namun perlu diperhatikan bahwa metaheuristik seperti PSO tidak menjamin akan ditemukannya solusi optimal.
Pemlihan Parameter
Pemilihan parameter PSO mempunyai pengaruh yang signifikan terhadap kinerja optimasi. Oleh karena itu, penelitian tentang pemilihan parameter PSO yang mencapai kinerja optimal menjadi fokus utama. Untuk menghindari divergensi (“ledakan”), bobot inersia harus kurang dari 1. Dua parameter lainnya dapat diturunkan dengan menggunakan pendekatan restriktif atau dipilih secara bebas, namun analisis menyarankan wilayah konvergensi untuk membatasinya pada nilai-nilai tipikal. berada dalam kisaran [1,3].Parameter PSO juga dapat dioptimalkan menggunakan pengoptimal overlay lainnya, sebuah konsep yang dikenal sebagai meta-optimasi, atau bahkan disempurnakan selama optimasi, misalnya dengan menggunakan logika fuzzy.Pemilihan parameter PSO juga dapat disesuaikan untuk skenario optimasi yang berbeda.
Lingkungan dan Topologi
Topologi gerombolan mendefinisikan subset partikel yang dapat bertukar informasi dengan setiap partikel. Versi dasar dari algoritma ini menggunakan topologi global sebagai struktur komunikasi cluster. Topologi ini memungkinkan semua partikel untuk berkomunikasi dengan partikel lainnya, sehingga seluruh gerombolan berbagi posisi terbaik yang sama (g) dari satu partikel. Namun, pendekatan ini dapat mengakibatkan kawanan ternak terjebak dalam kondisi minimum lokal. Oleh karena itu,topologi berbeda digunakan untuk mengontrol aliran informasi antar partikel.
Misalnya, dalam topologi lokal, sebuah partikel hanya berbagi informasi dengan subset partikel, di mana subset tersebut adalah subset geometris, seperti "m partikel terdekat", atau subset sosial, yaitu sekelompok partikel yang tidak bergantung pada semua jarak.Dalam kasus seperti ini, varian PSO dianggap yang terbaik secara lokal (dibandingkan dengan varian global dari PSO dasar).Topologi cluster yang umum digunakan adalah ring dimana setiap partikel hanya memiliki dua tetangga, namun terdapat banyak partikel lain di dalam cluster. Topologi belum tentu statis dan upaya telah dilakukan untuk menciptakan topologi adaptif seperti SPSO, APSO, Stochastic Star, TRIBES, Cyber Swarm dan C-PSO.Dengan menggunakan topologi ring, PSO dapat mencapai paralelisme pada tingkat generasi, sehingga secara signifikan meningkatkan kecepatan evolusi.
Cara Kerja Bagian Dalam
Cara kerja algoritma PSO memiliki pemikiran yang berbeda tentang mengapa dan bagaimana hal itu dapat dioptimalkan.Pandangan umum di kalangan peneliti adalah bahwa perilaku gerombolan bervariasi antara eksplorasi, yang melibatkan pencarian di wilayah ruang pencarian yang lebih luas, dan eksploitasi, yang merupakan pencarian berorientasi lokal untuk mendapatkan titik optimal terdekat (mungkin lokal).
Aliran pemikiran ini telah menjadi konsep umum sejak awal PSO. Aliran pemikiran ini berpendapat bahwa algoritma PSO dan parameternya harus dipilih sedemikian rupa sehingga dapat menyeimbangkan eksplorasi dan eksploitasi untuk menghindari konvergensi dini ke optimal lokal sekaligus memastikan tingkat konvergensi yang baik. Keyakinan ini menjadi dasar dari banyak varian PSO.Sebaliknya, aliran pemikiran lain berfokus pada pemahaman perilaku gerombolan PSO dan bagaimana pengaruhnya terhadap kinerja pengoptimalan aktual, khususnya untuk ruang pencarian berdimensi lebih tinggi dan masalah pengoptimalan yang dapat terputus-putus, berisik, dan bervariasi terhadap waktu. Aliran pemikiran ini mencari algoritma dan parameter PSO yang berkinerja baik dalam konteks eksplorasi dan eksploitasi, terlepas dari interpretasi perilaku kawanan. Studi-studi ini telah mengarah pada penyederhanaan algoritma PSO.
Konvergensi
Dalam konteks OSP, konvergensi memiliki dua arti utama. Pertama, konvergensi himpunan solusi terjadi ketika semua partikel berkumpul pada suatu titik di ruang pencarian, yang mungkin optimal atau tidak. Analisis konvergensi urutan solusi telah memberikan pedoman untuk memilih parameter PSO untuk menghindari divergensi kawanan partikel. Meskipun ada kritik terhadap penyederhanaan analisis yang berlebihan, penelitian menunjukkan bahwa penyederhanaan tersebut tidak berdampak pada batas konvergensi.Kedua, konvergensi menuju optimal lokal terjadi ketika posisi terbaik atau paling terkenal dari kawanan mendekati permasalahan optimal lokal tanpa mempertimbangkan perilaku kawanan secara keseluruhan.
Analisis konvergensi terhadap optimum lokal menunjukkan bahwa PSO memerlukan modifikasi tertentu untuk memastikan ditemukannya optimum lokal. Meskipun penentuan kemampuan konvergensi masih bergantung pada hasil empiris, upaya sedang dilakukan untuk mengembangkan strategi “pembelajaran ortogonal” untuk meningkatkan kinerja PSO secara keseluruhan. Tujuan dari strategi ini adalah untuk mendorong konvergensi global yang lebih cepat, solusi berkualitas lebih tinggi, dan ketahanan yang lebih besar. Namun,penelitian ini tidak memberikan bukti teoretis apa pun yang mendukung klaim tersebut.
Mekanisme Adaptif
Tanpa memerlukan keseimbangan antara konvergensi (“eksploitasi”) dan divergensi (“eksplorasi”), mekanisme adaptif dapat diterapkan. Optimasi kawanan partikel adaptif (APSO) memberikan efisiensi pencarian yang lebih baik daripada PSO standar. APSO dapat melakukan pencarian global di seluruh ruang pencarian dengan kecepatan konvergensi yang lebih cepat, memungkinkan kontrol otomatis terhadap bobot inersia, koefisien percepatan, dan parameter algoritmik lainnya pada waktu proses.ini sekaligus meningkatkan efektivitas dan efisiensi pencarian. Selain itu, APSO juga dapat bertindak berdasarkan partikel terbaik global untuk meninggalkan optimal lokal.Meskipun APSO memperkenalkan parameter algoritme baru, tidak diperlukan kompleksitas desain atau implementasi tambahan.Selain itu, PSO dapat secara efisien mengatasi masalah optimasi komputasi intensif dengan memanfaatkan mekanisme evaluasi kesesuaian skala-adaptif.
Varian
Banyak varian bahkan dari algoritma PSO dasar yang dimungkinkan. Misalnya, ada beberapa metode untuk menginisialisasi partikel dan kecepatan, seperti memulai dari kecepatan nol, serta berbagai pendekatan untuk buffering kecepatan, memperbarui pi dan g hanya setelah seluruh gerombolan diperbarui, dan seterusnya. Beberapa pilihan ini dan dampaknya terhadap kinerja telah dibahas dalam literatur.
Peneliti terkemuka telah mengembangkan serangkaian implementasi standar sebagai dasar untuk menguji kinerja teknik peningkatan sekaligus memperkenalkan PSO ke komunitas pengoptimalan yang lebih luas. Keberadaan standar algoritme yang terkenal dan didefinisikan secara ketat memberikan titik perbandingan berharga yang dapat digunakan di seluruh penelitian untuk menguji kemajuan baru dengan lebih baik.Salah satu standar terbaru adalah Standar PSO 2011 (SPSO-2011).
Hibridisasi
Untuk meningkatkan kinerja pengoptimalan, varian PSO baru dan lebih canggih terus diperkenalkan. Terdapat tren tertentu dalam penelitian ini, termasuk pengembangan metode optimasi hybrid yang menggabungkan PSO dengan pengoptimal lainnya. Contoh pendekatan ini antara lain menggabungkan PSO dengan optimasi berbasis biogeografi dan mengintegrasikan metode pembelajaran yang efektif. Tujuan pengembangan varian ini adalah untuk mencapai peningkatan kinerja lebih lanjut dalam proses optimasi dengan menggabungkan keunggulan PSO dengan sifat positif metode optimasi lainnya. Pendekatan ini membuka peluang eksplorasi dan penggunaan yang lebih efisien dalam bidang pencarian solusi.
Mengurangi Kovergensi Dini
Tren penelitian lainnya adalah upaya untuk mengurangi konvergensi dini, yang mengindikasikan stagnasi optimasi. Beberapa pendekatan yang digunakan antara lain membalikkan atau menghentikan pergerakan partikel PSO. Selain itu, strategi lain untuk mengatasi konvergensi prematur adalah dengan menggunakan multiple-swarm (multi-swarm optimizer). Pendekatan multi-swarm juga dapat digunakan untuk mengimplementasikan optimasi multi-tujuan. Selain itu, terdapat kemajuan dalam penyesuaian parameter perilakuPSO selama proses optimasi.Semua ini merupakan upaya untuk meningkatkan ketahanan algoritme terhadap konvergensi dini dan meningkatkan kinerja pengoptimalan pada masalah yang kompleks dan dinamis.
Penyederhanaan
Aliran pemikiran lainnya adalah bahwa PSO harus disederhanakan sebanyak mungkin tanpa mengorbankan kinerjanya, sebuah konsep yang sering disebut sebagai “Occam's Razor.” Kennedy awalnya mengusulkan penyederhanaan PSO, dan penelitian selanjutnya menunjukkan bahwa menyederhanakan PSO meningkatkan kinerja pengoptimalan, mempermudah penyesuaian parameter, dan menjaga konsistensi kinerja di berbagai masalah pengoptimalan.
Argumen untuk menyederhanakan PSO mencakup keyakinan bahwa efektivitas metaheuristik hanya dapat ditunjukkan secara empiris melalui eksperimen komputasi pada sejumlah masalah optimasi yang terbatas. Sulit untuk membuktikan bahwa metaheuristik seperti PSO benar, sehingga meningkatkan risiko kesalahan dalam deskripsi dan implementasinya. Misalnya, varian algoritma genetika menunjukkan potensi besar tetapi kemudian ditemukan cacat karena optimasi pencariannya bias terhadapnilai serupa untuk berbagai dimensi dalam ruang pencarian.Penyederhanaan PSO juga berlaku untuk inisialisasi cepat. Variasi PSO Bare Bones yang diusulkan oleh James Kennedy pada tahun 2003 tidak memerlukan penggunaan kecepatan sama sekali. Varian lain yang lebih sederhana adalah Accelerated Particle Swarm Optimization (APSO), yang juga tidak memerlukan kecepatan dan dapat mempercepat konvergensi di banyak aplikasi. Kode demo APSO sederhana tersedia.
Pengoptimalan Multi-Tujuan
PSO juga telah berhasil diterapkan pada masalah multiobjektif dimana perbandingan fungsi objektif memperhitungkan dominasi Pareto dalam gerak partikel PSO. Dalam konteks ini, solusi yang tidak didominasi disimpan sedemikian rupa sehingga mendekati front Pareto dan memberikan alternatif optimal yang mencakup solusi yang tidak dapat dilampaui satu sama lain dalam konteks fungsi tujuan yang berbeda.
Disadur dari: en.wikipedia.org