Partikelsværmmetode

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 14. december 2015; checks kræver 13 redigeringer .

Partikelsværmmetoden (PSM) er en numerisk optimeringsmetode , som ikke kræver at kende den nøjagtige gradient af den funktion, der optimeres.

MFR blev bevist af Kennedy , Eberhart og Shea [1] [2] og var oprindeligt beregnet til at efterligne social adfærd . Algoritmen er blevet forenklet og fundet egnet til at udføre optimeringer. Bogen af Kennedy og Eberhart [3] beskriver mange af de filosofiske aspekter af MFR og den såkaldte sværm-intelligens . Omfattende forskning i anvendelserne af MFR er blevet udført af Poly [4] [5] . MFR'en optimerer funktionen ved at opretholde en population af mulige opløsninger, kaldet partikler, og flytte disse partikler rundt i opløsningsrummet efter en simpel formel. Bevægelserne er underlagt princippet om den bedste position, der findes i dette rum, som konstant ændrer sig, når partiklerne finder mere gunstige positioner.

Algoritme

Lad være den objektive funktion, der skal minimeres, dvs. antallet af partikler i sværmen, som hver er forbundet med en koordinat i opløsningsrummet og en hastighed . Lad også være den bedst kendte position af partiklen med indeks , og være den bedst kendte tilstand af sværmen som helhed. Så er den generelle form for partikelsværmmetoden som følger. $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}$ $jeg$ ${\textbf {g))$

For hver partikel skal du gøre: $i=1,\ldots ,S$
- Generer partiklens begyndelsesposition ved hjælp af en tilfældig vektor med en flerdimensionel ensartet fordeling , hvor og er henholdsvis de nedre og øvre grænser for opløsningsrummet. ${\textbf {x}}_{i}\sim U({\textbf {b}}_{lo},{\textbf {b}}_{up})$ ${\textbf {b}}_{lo}$ ${\textbf {b}}_{up}$
- Tildel den bedst kendte partikelposition til dens begyndelsesværdi: . ${\textbf {p}}_{i}\får {\textbf {x}}_{i}$
- Hvis , så opdater den bedst kendte tilstand for sværmen: . $f({\textbf {p}}_{i})<f({\textbf {g}})$ ${\textbf {g}}\får {\textbf {p}}_{i}$
- Tildel en partikelhastighedsværdi: . ${\textbf {v}}_{i}\sim U(-({\textbf {b}}_{up}-{\textbf {b}}_{lo}),({\textbf { b))_{up}-{\textbf {b}}_{lo}))$
Indtil stopkriteriet er opfyldt (for eksempel at nå et givet antal iterationer eller den påkrævede værdi af den objektive funktion), gentag:
- For hver partikel skal du gøre: $i=1,\ldots ,S$
  - Generer tilfældige vektorer . ${\textbf {r}}_{p},{\textbf {r}}_{g}\sim U(0,1)$
  - Opdater partikelhastighed: , hvor operationen betyder komponentvis multiplikation . ${\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$
  - Opdater partiklens position ved at oversætte til hastighedsvektoren :. Dette trin udføres uanset forbedringen i værdien af den objektive funktion. ${\textbf {x}}_{i}$ ${\textbf {x}}_{i}\får {\textbf {x}}_{i}+{\textbf {v}}_{i}$
  - Hvis , så: $f({\textbf {x}}_{i})<f({\textbf {p}}_{i})$
    - Opdater bedst kendte partikelposition: . ${\textbf {p}}_{i}\får {\textbf {x}}_{i}$
    - Hvis , så opdater den bedst kendte tilstand for sværmen som helhed: . $f({\textbf {p}}_{i})<f({\textbf {g}})$ ${\textbf {g}}\får {\textbf {p}}_{i}$
Nu indeholder de bedste af de fundne løsninger. ${\textbf {g))$

Parametrene , og er valgt af lommeregneren og bestemmer adfærden og effektiviteten af metoden som helhed. Disse parametre er genstand for mange undersøgelser . $\omega$ $\phi _{p}$ $\phi _{g}$

Valg af parametre

Valget af optimale parametre for partikelsværmmetoden er genstand for et betydeligt antal forskningsartikler, se f.eks. Shi og Eberhart [6] [7] , Carlyle og Dozer [8] , van den Berg [9] , Clerk og Kennedy [10] , Trelea [11] , Bratton og Blackwell [12] og Evers [13] .

En enkel og effektiv måde at vælge metodens parametre på blev foreslået af Pedersen og andre forfattere [14] [15] . De udførte også numeriske eksperimenter med forskellige optimeringsproblemer og parametre. Teknikken til at vælge disse parametre kaldes meta-optimering , da en anden optimeringsalgoritme bruges til at "tune" MFR-parametrene. MFM-inputparametrene med den bedste ydeevne har vist sig at være i modstrid med hovedprincipperne beskrevet i litteraturen og giver ofte tilfredsstillende optimeringsresultater for simple tilfælde af MFM. Deres implementering kan findes i SwarmOps open source-bibliotek .

Varianter af algoritmen

Nye varianter af partikelsværmalgoritmen bliver konstant foreslået for at forbedre metodens ydeevne. Der er flere tendenser i disse undersøgelser, hvoraf den ene foreslår at skabe en hybrid optimeringsmetode ved hjælp af MFR i kombination med andre algoritmer, se for eksempel [16] [17] . En anden tendens er at fremskynde metoden på en eller anden måde, for eksempel ved at træde tilbage eller ændre rækkefølgen af partikelbevægelse (se [13] [18] [19] for dette ). Der er også forsøg på at tilpasse adfærdsparametrene for MFR under optimeringsprocessen [20] .

Se også

Noter

↑ Kennedy, J.; Eberhart, R. (1995). "Partikelsværmoptimering". Proceedings of IEEE International Conference on Neurale Networks . IV . pp. 1942-1948.
↑ Shi, Y.; Eberhart, R.C. (1998). "En modificeret partikelsværmoptimering". Proceedings of IEEE International Conference on Evolutionary Computation . pp. 69-73.
↑ Kennedy, J.; Eberhart, R. C. Swarm Intelligence (ubestemt) . - Morgan Kaufmann , 2001. - ISBN 1-55860-595-9 .
↑ Poli, R. En analyse af publikationer om partikelsværmoptimeringsapplikationer // Technical Report CSM-469 : journal. — Department of Computer Science, University of Essex, UK, 2007. Arkiveret fra originalen den 16. juli 2011.
↑ Poli, R. Analyse af publikationerne om anvendelserne af partikelsværmoptimering // Journal of Artificial Evolution and Applications: tidsskrift. - 2008. - S. 1-10 . - doi : 10.1155/2008/685175 .
↑ Shi, Y.; Eberhart, R.C. (1998). "Parametervalg i partikelsværmoptimering". Proceedings of Evolutionary Programming VII (EP98) . pp. 591-600.
↑ Eberhart, RC; Shi, Y. (2000). "Sammenligning af inertivægte og indsnævringsfaktorer i partikelsværmoptimering". Proceedings of the Congress on Evolutionary Computation . 1 . pp. 84-88.
↑ Carlisle, A.; Dozier, G. (2001). "En off-the-shelf PSO". Proceedings af partikelsværmoptimeringsværkstedet . pp. 1-6.
↑ van den Bergh, F. An Analysis of Particle Swarm Optimizers . — University of Pretoria, Fakultet for Natur- og Landbrugsvidenskab, 2001.
↑ Clerc, M.; Kennedy, J. Partikelsværmen - eksplosion, stabilitet og konvergens i et multidimensionelt komplekst rum // IEEE Transactions on Evolutionary Computation : journal. - 2002. - Bd. 6 , nr. 1 . - S. 58-73 .
↑ Trelea, IC The Particle Swarm Optimization Algorithm: konvergensanalyse og parametervalg // Information Processing Letters : journal. - 2003. - Bd. 85 . - s. 317-325 .
↑ Bratton, D.; Blackwell, T. A Simplified Recombinant PSO (uspecificeret) // Journal of Artificial Evolution and Applications. – 2008.
↑ 1 2 Evers, G. En automatisk omgrupperingsmekanisme til at håndtere stagnation i partikelsværmoptimering . — The University of Texas - Pan American, Department of Electrical Engineering, 2009.
↑ Pedersen , MEH Tuning & Simplifying Heuristical Optimization . - University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group, 2010. Arkiveret kopi (link ikke tilgængeligt) . Hentet 3. juni 2010. Arkiveret fra originalen 26. juli 2011. (ubestemt)
↑ Pedersen, MEH; Chipperfield, AJ Simplifying partikelsværmoptimering (neopr.) // Applied Soft Computing. - 2010. - T. 10 . - S. 618-628 . Arkiveret fra originalen den 24. januar 2014.
↑ Lovbjerg, M.; Krink, T. (2002). "Livscyklusmodellen: kombinerer partikelsværmoptimering, genetiske algoritmer og bakkeklatrere." Proceedings of Parallel Problem Solving from Nature VII (PPSN) . pp. 621-630.
↑ Niknam, T.; Amiri, B. En effektiv hybrid tilgang baseret på PSO, ACO og k-midler til klyngeanalyse (engelsk) // Applied Soft Computing : journal. - 2010. - Bd. 10 , nej. 1 . - S. 183-197 .
↑ Lovbjerg, M.; Krink, T. (2002). "Udvidelse af partikelsværmoptimering med selvorganiseret kritik". Proceedings of the Fourth Congress on Evolutionary Computation (CEC) . 2 . pp. 1588-1593.
↑ Xinchao, Z. En forstyrret partikelsværmalgoritme til numerisk optimering (neopr.) // Applied Soft Computing. - 2010. - T. 10 , nr. 1 . - S. 119-124 .
↑ Zhan, Zh.; Zhang, J.; Li, Y; Chung, HS-H. Adaptiv partikelsværmoptimering (neopr.) // IEEE-transaktioner på systemer, mennesker og kybernetik. - 2009. - T. 39 , nr. 6 . - S. 1362-1381 .

Links

Partikelsværm Central . Nyheder, personer, steder, programmer, artikler osv. Se især den gældende MFR-standard. (Engelsk)
Links til kildekoderne for implementeringer af MFR-algoritmerne Arkiveret kopi af 15. april 2021 på Wayback Machine

Optimeringsmetoder _
Endimensionel	gyldne snit metode Modsætning Parabel metode Netsøgning Ensartet bloksøgningsmetode Fibonacci metode Ternær søgning Piyavsky metode Strongin metode
Nul orden	Gauss metode Nelder-Mead metode Hook-Jeeves metode Rosenbrock metode Powell metode
Første ordre	gradient nedstigning Zeutendijk metode Koordinat nedstigning Konjugeret gradientmetode Kvasi-newtonske metoder Levenberg-Marquardt algoritme
anden orden	Newtons metode Newton-Raphson metode Broyden-Fletcher-Goldfarb-Shanno-algoritme (BFGS)
Stokastisk	Monte Carlo metode Simuleret udglødning Evolutionære algoritmer differentiel evolution Myre-algoritme Partikelsværmmetode Algorithme for bikoloni Tilfældig gå-metode
Lineære programmeringsmetoder _	Enkel metode Gomoris algoritme Ellipsoid metode Potentielle metode
Ikke-lineære programmeringsmetoder	Sekventiel kvadratisk programmering