Metoda roje částic

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 14. prosince 2015; kontroly vyžadují 13 úprav .

Metoda roje částic (PSM) je numerická optimalizační metoda , která nevyžaduje znát přesný gradient optimalizované funkce.

MFR byla prokázána Kennedym , Eberhartem a Sheou [1] [2] a původně měla napodobovat sociální chování . Algoritmus byl zjednodušen a bylo zjištěno, že je vhodný pro provádění optimalizací. Kniha Kennedyho a Eberharta [3] popisuje mnohé z filozofických aspektů MFR a tzv. swarm intelligence . Rozsáhlý výzkum aplikací MFR provádí Poly [4] [5]. MFR optimalizuje funkci udržováním populace možných řešení, nazývaných částice, a pohybem těchto částic v prostoru roztoku podle jednoduchého vzorce. Pohyby podléhají principu nejlepší polohy nalezené v tomto prostoru, která se neustále mění, když částice najdou výhodnější polohy.

Algoritmus

Nechť je cílová funkce minimalizována, tj. počet částic v roji, z nichž každá je spojena se souřadnicí v prostoru řešení a rychlostí . Nechť je také nejznámější poloha částice s indexem a je nejznámější stav roje jako celku. Pak je obecná forma metody roje částic následující. $f: \mathbb{R}^n \to \mathbb{R}$ $S$ ${\textbf {x}}_{i}\in \mathbb {R} ^{n}$ ${\textbf {v}}_{i}\in \mathbb {R} ^{n}$ ${\textbf {p}}_{i}$ $i$ ${\textbf {g))$

Pro každou částici udělejte: $i=1,\ldots ,S$
- Vygenerujte počáteční polohu částice pomocí náhodného vektoru s vícerozměrným rovnoměrným rozdělením , kde a jsou dolní a horní hranice prostoru řešení. ${\textbf {x}}_{i}\sim U({\textbf {b}}_{lo},{\textbf {b}}_{up})$ ${\textbf {b}}_{lo}$ ${\textbf {b}}_{up}$
- Přiřaďte nejznámější pozici částice její počáteční hodnotě: . ${\textbf {p}}_{i}\gets {\textbf {x}}_{i}$
- Pokud , pak aktualizujte nejznámější stav roje: . $f({\textbf {p}}_{i})<f({\textbf {g}})$ ${\textbf {g}}\gets {\textbf {p}}_{i}$
- Přiřaďte hodnotu rychlosti částice: . ${\textbf {v}}_{i}\sim U(-({\textbf {b}}_{up}-{\textbf {b}}_{lo}),({\textbf { b))_{up}-{\textbf {b}}_{lo}))$
Dokud není splněno kritérium zastavení (například dosažení daného počtu iterací nebo požadované hodnoty cílové funkce), opakujte:
- Pro každou částici udělejte: $i=1,\ldots ,S$
  - Generujte náhodné vektory . ${\textbf {r}}_{p},{\textbf {r}}_{g}\sim U(0,1)$
  - Aktualizace rychlosti částic: , kde operace znamená násobení po komponentech . ${\textbf {v}}_{i}\gets \omega {\textbf {v}}_{i}+\phi _{p}{\textbf {r}}_{p}\odot ( {\textbf {p}}_{i}-{\textbf {x}}_{i})+\phi _{g}{\textbf {r}}_{g}\odot ({\textbf {g ))-{\textbf {x}}_{i})$ $\odot$
  - Aktualizujte polohu částice převodem na vektor rychlosti: . Tento krok se provádí bez ohledu na zlepšení hodnoty účelové funkce. ${\textbf {x}}_{i}$ ${\textbf {x}}_{i}\gets {\textbf {x}}_{i}+{\textbf {v}}_{i}$
  - Pokud , pak: $f({\textbf {x}}_{i})<f({\textbf {p}}_{i})$
    - Aktualizujte nejznámější polohu částice: . ${\textbf {p}}_{i}\gets {\textbf {x}}_{i}$
    - Pokud , pak aktualizujte nejznámější stav roje jako celku: . $f({\textbf {p}}_{i})<f({\textbf {g}})$ ${\textbf {g}}\gets {\textbf {p}}_{i}$
Nyní obsahuje nejlepší z nalezených řešení. ${\textbf {g))$

Parametry a jsou zvoleny kalkulátorem a určují chování a účinnost metody jako celku. Tyto parametry jsou předmětem mnoha studií . $\omega$ $\phi _{p}$ $\phi _{g}$

Výběr parametrů

Volba optimálních parametrů pro metodu roje částic je předmětem značného množství výzkumných prací, viz např. Shi a Eberhart [6] [7] , Carlyle a Dozer [8] , van den Berg [9] , Clerk a Kennedy [10] , Trelea [11] , Bratton a Blackwell [12] a Evers [13] .

Jednoduchý a efektivní způsob výběru parametrů metody navrhl Pedersen a další autoři [14] [15] . Prováděli také numerické experimenty s různými optimalizačními problémy a parametry. Technika výběru těchto parametrů se nazývá meta-optimalizace , protože k „vyladění“ parametrů MFR se používá jiný optimalizační algoritmus. Ukázalo se, že vstupní parametry MFM s nejlepším výkonem jsou v rozporu s hlavními principy popsanými v literatuře a často poskytují uspokojivé výsledky optimalizace pro jednoduché případy MFM. Jejich implementaci lze nalézt v open source knihovně SwarmOps .

Varianty algoritmu

Neustále jsou navrhovány nové varianty algoritmu roje částic, aby se zlepšila výkonnost metody. V těchto studiích existuje několik trendů, z nichž jeden navrhuje vytvořit hybridní optimalizační metodu využívající MFR v kombinaci s dalšími algoritmy, viz např . [16] [17] . Dalším trendem je metodu nějakým způsobem urychlit, například ustoupit zpět nebo změnit pořadí pohybu částic (k tomu viz [13] [18] [19] ). Existují také pokusy přizpůsobit parametry chování MFR během procesu optimalizace [20] .

Viz také

Poznámky

↑ Kennedy, J.; Eberhart, R. (1995). "Optimalizace roje částic". Sborník z mezinárodní konference IEEE o neuronových sítích . IV . str. 1942-1948.
↑ Shi, Y.; Eberhart, R. C. (1998). „Upravený optimalizátor roje částic“. Sborník IEEE International Conference on Evolutionary Computation . str. 69-73.
↑ Kennedy, J.; Eberhart, R. C. Swarm Intelligence (neurčité) . - Morgan Kaufmann , 2001. - ISBN 1-55860-595-9 .
↑ Poli, R. Analýza publikací o aplikacích optimalizace roje částic // Technical Report CSM-469 : journal. — Katedra informatiky, University of Essex, UK, 2007. Archivováno z originálu 16. července 2011.
↑ Poli, R. Analýza publikací o aplikacích optimalizace roje částic // Journal of Artificial Evolution and Applications : journal. - 2008. - S. 1-10 . - doi : 10.1155/2008/685175 .
↑ Shi, Y.; Eberhart, R. C. (1998). „Výběr parametrů v optimalizaci roje částic“. Proceedings of Evolutionary Programming VII (EP98) . str. 591-600.
↑ Eberhart, RC; Shi, Y. (2000). „Porovnání setrvačných hmotností a konstrikčních faktorů při optimalizaci roje částic“. Proceedings of Congress on Evolutionary Computation . 1 . str. 84-88.
↑ Carlisle, A.; Dozier, G. (2001). „Off-The-Shelf PSO“ . Sborník z workshopu k optimalizaci roje částic . str. 1-6.
↑ van den Bergh, F. An Analysis of Particle Swarm Optimizers . — Univerzita v Pretorii, Fakulta přírodních a zemědělských věd, 2001.
↑ Clerc, M.; Kennedy, J. Swarm částic - exploze, stabilita a konvergence v multidimenzionálním komplexním prostoru // IEEE Transactions on Evolutionary Computation : deník. - 2002. - Sv. 6 , č. 1 . - str. 58-73 .
↑ Trelea, IC The Particle Swarm Optimization Algorithm: analýza konvergence a výběr parametrů // Information Processing Letters : deník. - 2003. - Sv. 85 . - str. 317-325 .
↑ Bratton, D.; Blackwell, T. A Simplified Recombinant PSO (nespecifikováno) // Journal of Artificial Evolution and Applications. — 2008.
↑ 1 2 Evers, G. Mechanismus automatického přeskupování pro řešení stagnace při optimalizaci roje částic . — The University of Texas – Pan American, Department of Electrical Engineering, 2009.
↑ Pedersen , ladění MEH a zjednodušení heuristické optimalizace . - University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group, 2010. Archivovaná kopie (odkaz není k dispozici) . Získáno 3. června 2010. Archivováno z originálu dne 26. července 2011. (neurčitý)
↑ Pedersen, MEH; Chipperfield, AJ Zjednodušení optimalizace roje částic (neopr.) // Applied Soft Computing. - 2010. - T. 10 . - S. 618-628 . Archivováno z originálu 24. ledna 2014.
↑ Lovbjerg, M.; Krink, T. (2002). "Model životního cyklu: kombinace optimalizace roje částic, genetických algoritmů a horolezců." Proceedings of Parallel Problem Solving from Nature VII (PPSN) . str. 621-630.
↑ Niknam, T.; Amiri, B. Efektivní hybridní přístup založený na PSO, ACO a k-means pro shlukovou analýzu (anglicky) // Applied Soft Computing: journal. - 2010. - Sv. 10 , č. 1 . - str. 183-197 .
↑ Lovbjerg, M.; Krink, T. (2002). „Rozšiřování optimalizátorů roje částic se samoorganizovanou kritickostí“. Proceedings of the Fourth Congress on Evolutionary Computation (CEC) . 2 . str. 1588-1593.
↑ Xinchao, Z. Algoritmus rojení perturbed částic pro numerickou optimalizaci (neopr.) // Applied Soft Computing. - 2010. - T. 10 , č. 1 . - S. 119-124 .
↑ Zhan, Zh.; Zhang, J.; Li, Y; Chung, HS-H. Adaptive Particle Swarm Optimization (neopr.) // Transakce IEEE v systémech, člověku a kybernetice. - 2009. - T. 39 , č. 6 . - S. 1362-1381 .

Odkazy

Particle Swarm Central . Zprávy, lidé, místa, programy, články atd. Viz zejména aktuální standard MFR. (Angličtina)
Odkazy na zdrojové kódy implementací algoritmů MFR Archivovaná kopie z 15. dubna 2021 na Wayback Machine

Optimalizační metody
Jednorozměrný	metoda zlatého řezu Dichotomie Parabolová metoda Vyhledávání v mřížce Jednotná metoda vyhledávání bloků Fibonacciho metoda Ternární hledání Piyavského metoda Stronginovou metodou
Nulové pořadí	Gaussova metoda Metoda Nelder-Mead Hook-Jeevesova metoda Rosenbrockova metoda Powellova metoda
První objednávka	gradientní sestup Zeutendijkova metoda Souřadnicový sestup Metoda konjugovaného gradientu Kvazi-newtonské metody Levenberg-Marquardtův algoritmus
druhá objednávka	Newtonova metoda Newton-Raphsonova metoda Algoritmus Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastické	Metoda Monte Carlo Simulované žíhání Evoluční algoritmy diferenciální evoluce Algoritmus mravenců Metoda roje částic Algoritmus včelstva Metoda náhodné chůze
Metody lineárního programování	Simplexní metoda Gomoriho algoritmus Elipsoidní metoda Potenciální metoda
Metody nelineárního programování	Sekvenční kvadratické programování