Partikelsvärmoptimering

En partikelsvärm som söker efter det globala minimumet av en funktion

Inom beräkningsvetenskap är partikelsvärmsoptimering ( PSO ) en beräkningsmetod som optimerar ett problem genom att iterativt försöka förbättra en kandidatlösning med hänsyn till ett givet mått på kvalitet. Det löser ett problem genom att ha en population av kandidatlösningar, här kallade partiklar , och flytta runt dessa partiklar i sökutrymmet enligt en enkel matematisk formel över partikelns position och hastighet . Varje partikels rörelse påverkas av dess lokala mest kända position, men styrs också mot de mest kända positionerna i sökutrymmet, som uppdateras när bättre positioner hittas av andra partiklar. Detta förväntas flytta svärmen mot de bästa lösningarna.

PSO tillskrivs ursprungligen Kennedy , Eberhart och Shi och var först avsedd för att simulera socialt beteende , som en stiliserad representation av organismers rörelse i en fågelflock eller fiskstim . Algoritmen förenklades och det observerades att den utförde optimering. Boken av Kennedy och Eberhart beskriver många filosofiska aspekter av PSO och svärmintelligens . En omfattande kartläggning av PSO-ansökningar görs av Poli . Nyligen har en omfattande recension om teoretiska och experimentella arbeten om PSO publicerats av Bonyadi och Michalewicz.

PSO är en metaheuristik eftersom den gör få eller inga antaganden om att problemet optimeras och kan söka i mycket stora utrymmen av kandidatlösningar. PSO använder inte heller gradienten för det problem som optimeras, vilket innebär att PSO inte kräver att optimeringsproblemet är differentierbart , vilket krävs av klassiska optimeringsmetoder som gradient descent och kvasi-newton-metoder . Men metaheuristik som PSO garanterar inte att en optimal lösning någonsin hittas.

Algoritm

En grundläggande variant av PSO-algoritmen fungerar genom att ha en population (kallad en svärm) av kandidatlösningar (kallade partiklar). Dessa partiklar flyttas runt i sökutrymmet enligt några enkla formler. Partiklarnas rörelser styrs av deras egen mest kända position i sökutrymmet samt hela svärmens mest kända position. När förbättrade positioner upptäcks kommer dessa sedan att styra svärmens rörelser. Processen upprepas och genom att göra det hoppas man, men inte garanterat, att en tillfredsställande lösning så småningom kommer att upptäckas.

Formellt, låt f : ℝ ⁿ → ℝ vara kostnadsfunktionen som måste minimeras. Funktionen tar en kandidatlösning som ett argument i form av en vektor av reella tal och producerar ett reellt tal som utdata som indikerar det objektiva funktionsvärdet för den givna kandidatlösningen. Gradienten för f är inte känd . Målet är att hitta en lösning a för vilken f ( a ) ≤ f ( b ) för alla b i sökutrymmet, vilket skulle betyda att a är det globala minimumet.

Låt S vara antalet partiklar i svärmen, som var och en har en position x _i ∈ ℝ ⁿ i sökutrymmet och en hastighet v _i ∈ ℝ ⁿ . Låt p _i vara den mest kända positionen för partikel i och låt g vara den mest kända positionen för hela svärmen. En grundläggande PSO-algoritm för att minimera kostnadsfunktionen är då:

 
      
           
         
              för  varje partikel  i  = 1, ...,  S  do  Initiera partikelns position med en  likformigt fördelad  slumpmässig vektor:  x  i  ~  U  (  b  lo  ,  b  up  ) Initiera partikelns mest kända position till dess initiala position:  p  i  ←  x  i  om  f  (  p  i  ) <  f  (  g  ) uppdatera   sedan  svärmens mest kända position:  g  ←  p  i  Initiera partikelns hastighet:  v  i  ~  U  (-|  b  up  -  b  lo  |, |  b  up  -  b  lo  | )  medan  ett avslutningskriterium inte är uppfyllt  gör  :  för  varje partikel  i  = 1, ...,  S  gör  för  varje dimension  d  = 1, ...,  n  gör  Välj slumpmässiga tal:  r  p  ,  r  g  ~  U  (0, 1) Uppdatera partikelns hastighet:  v  i,d  ← w  v  i,d  + φ  p  r  p  (  p  i,d  -  x  i,d  ) + φ  g  r  g  (  g  d  -  x  i,d  ) Uppdatera partikelns position:  x  i  ←  x  i  +  v  i  om  f  (  x  i  ) <  f  (  p  i  )  sedan  Uppdatera partikelns mest kända position:  p  i  ←  x  i  om  f  (  p  i  ) <  f  (  g  )  sedan  Uppdatera svärmens mest kända position:  g  ←  p  i 

Värdena b _lo och b _up representerar sökutrymmets nedre respektive övre gränser. Parametern w är tröghetsvikten. Parametrarna φ _p och φ _g kallas ofta kognitiv koefficient och social koefficient.

Avslutningskriteriet kan vara antalet utförda iterationer eller en lösning där det adekvata objektiva funktionsvärdet finns. Parametrarna w, φ _p och φ _g väljs av läkaren och styr beteendet och effektiviteten av PSO-metoden ( nedan ).

Val av parameter

Prestandalandskap som visar hur en enkel PSO-variant presterar sammantaget på flera benchmarkproblem när två PSO-parametrar varieras.

Valet av PSO-parametrar kan ha stor inverkan på optimeringsprestandan. Att välja PSO-parametrar som ger bra prestanda har därför varit föremål för mycket forskning.

För att förhindra divergens ("explosion") måste tröghetsvikten vara mindre än 1. De två andra parametrarna kan sedan härledas tack vare förträngningsmetoden, eller fritt väljas, men analyserna föreslår konvergensdomäner för att begränsa dem. Typiska värden är i $[1,3]$ .

PSO-parametrarna kan också justeras genom att använda en annan överlagringsoptimerare, ett koncept som kallas metaoptimering , eller till och med finjusteras under optimeringen, t.ex. med hjälp av fuzzy logik.

Parametrar har också ställts in för olika optimeringsscenarier.

Grannskap och topologier

Svärmens topologi definierar den delmängd av partiklar som varje partikel kan utbyta information med. Den grundläggande versionen av algoritmen använder den globala topologin som svärmkommunikationsstruktur. Denna topologi tillåter alla partiklar att kommunicera med alla andra partiklar, så hela svärmen delar samma bästa position g från en enda partikel. Detta tillvägagångssätt kan dock leda till att svärmen fångas in i ett lokalt minimum, så olika topologier har använts för att kontrollera informationsflödet mellan partiklar. Till exempel, i lokala topologier delar partiklar endast information med en delmängd av partiklar. Denna delmängd kan vara en geometrisk sådan – till exempel "de m närmaste partiklarna" – eller, oftare, en social sådan, dvs en uppsättning partiklar som inte är beroende av något avstånd. I sådana fall sägs PSO-varianten vara lokalt bäst (mot globalt bäst för grundläggande PSO).

En vanlig svärmtopologi är ringen, där varje partikel bara har två grannar, men det finns många andra. Topologin är inte nödvändigtvis statisk. Eftersom topologin är relaterad till mångfalden av kommunikation mellan partiklarna, har vissa ansträngningar gjorts för att skapa adaptiva topologier (SPSO, APSO, stokastisk stjärna, TRIBES, Cyber ​​Swarm och C-PSO)

Inre arbeten

Det finns flera tankar om varför och hur PSO-algoritmen kan utföra optimering.

En vanlig uppfattning bland forskare är att svärmbeteendet varierar mellan utforskande beteende, det vill säga att söka i en bredare del av sökutrymmet, och exploaterande beteende, det vill säga ett lokalt orienterat sökande för att komma närmare ett (eventuellt lokalt) optimalt. Denna tankeskola har varit förhärskande sedan starten av PSO. Denna tankeskola hävdar att PSO-algoritmen och dess parametrar måste väljas för att korrekt balansera mellan utforskning och exploatering för att undvika för tidig konvergens till ett lokalt optimum men ändå säkerställa en god konvergenshastighet till optimum. Denna övertygelse är föregångaren till många PSO-varianter, se nedan .

En annan tankegång är att beteendet hos en PSO-svärm inte förstås väl i termer av hur det påverkar faktisk optimeringsprestanda, särskilt för högre dimensionella sökutrymmen och optimeringsproblem som kan vara diskontinuerliga, bullriga och tidsvarierande. Denna tankeskola försöker bara hitta PSO-algoritmer och parametrar som ger bra prestanda oavsett hur svärmbeteendet kan tolkas i relation till t.ex. utforskning och exploatering. Sådana studier har lett till en förenkling av PSO-algoritmen, se nedan .

Konvergens

hänvisar ordet konvergens vanligtvis till två olika definitioner:

• Konvergens av sekvensen av lösningar (aka, stabilitetsanalys, konvergerande ) där alla partiklar har konvergerat till en punkt i sökutrymmet, som kanske eller kanske inte är den optimala,
• Konvergens till ett lokalt optimum där alla personbästa p eller alternativt svärmens mest kända position g , närmar sig ett lokalt optimum av problemet, oavsett hur svärmen beter sig.

Konvergens av sekvensen av lösningar har undersökts för PSO. Dessa analyser har resulterat i riktlinjer för att välja PSO-parametrar som tros orsaka konvergens till en punkt och förhindra divergens av svärmens partiklar (partiklar rör sig inte obegränsat och kommer att konvergera till någonstans). Analyserna kritiserades dock av Pedersen för att vara alltför förenklade då de antar att svärmen bara har en partikel, att den inte använder stokastiska variabler och att attraktionspunkterna, det vill säga partikelns mest kända position p och svärmens mest kända position . g , förbli konstant under hela optimeringsprocessen. Det visades dock att dessa förenklingar inte påverkar gränserna som hittas av dessa studier för parameter där svärmen är konvergent. Betydande ansträngningar har gjorts under de senaste åren för att försvaga det modelleringsantagande som användes under stabilitetsanalysen av PSO, där det senaste generaliserade resultatet gällde för många PSO-varianter och utnyttjade vad som visades vara de minsta nödvändiga modelleringsantagandena.

Konvergens till ett lokalt optimum har analyserats för PSO i och. Det har bevisats att PSO behöver modifieras för att garantera att man hittar ett lokalt optimum.

Detta innebär att bestämning av konvergensförmåga för olika PSO-algoritmer och parametrar fortfarande beror på empiriska resultat. Ett försök att ta itu med denna fråga är utvecklingen av en "ortogonal inlärning"-strategi för en förbättrad användning av den information som redan finns i relationen mellan p och g , för att bilda ett ledande konvergerande exemplar och vara effektiv med vilken PSO-topologi som helst. Syftet är att förbättra PSO:s prestanda totalt sett, inklusive snabbare global konvergens, högre lösningskvalitet och starkare robusthet. Sådana studier ger dock inga teoretiska bevis för att faktiskt bevisa deras påståenden.

Adaptiva mekanismer

Utan behov av en avvägning mellan konvergens (”exploatering”) och divergens (”utforskning”) kan en adaptiv mekanism införas. Adaptiv partikelsvärmoptimering (APSO) ger bättre sökeffektivitet än standard PSO. APSO kan utföra global sökning över hela sökutrymmet med högre konvergenshastighet. Det möjliggör automatisk kontroll av tröghetsvikten, accelerationskoefficienter och andra algoritmiska parametrar under körtiden, vilket förbättrar sökeffektiviteten och effektiviteten på samma gång. Dessutom kan APSO agera på den globalt bästa partikeln för att hoppa ur den troliga lokala optima. Men APSO kommer att introducera nya algoritmparametrar, det introducerar inte ytterligare design eller implementeringskomplexitet ändå.

Varianter

Många varianter av även en grundläggande PSO-algoritm är möjliga. Det finns till exempel olika sätt att initiera partiklarna och hastigheterna (t.ex. börja med nollhastigheter istället), hur man dämpar hastigheten, uppdaterar endast p _i och g efter att hela svärmen har uppdaterats etc. Några av dessa val och deras möjlig prestationspåverkan har diskuterats i litteraturen.

En serie standardimplementeringar har skapats av ledande forskare, "avsedda att användas både som en baslinje för prestandatestning av förbättringar av tekniken, såväl som att representera PSO för det bredare optimeringssamhället. Att ha en välkänd, strikt definierad standardalgoritm ger en värdefull jämförelsepunkt som kan användas inom hela forskningsområdet för att bättre testa nya framsteg." Den senaste är Standard PSO 2011 (SPSO-2011).

Hybridisering

Nya och mer sofistikerade PSO-varianter introduceras också kontinuerligt i ett försök att förbättra optimeringsprestandan. Det finns vissa trender i den forskningen; en är att göra en hybrid optimeringsmetod med PSO kombinerat med andra optimerare, t.ex. kombinerad PSO med biogeografibaserad optimering, och inkorporering av en effektiv inlärningsmetod.

Lindra för tidig konvergens

En annan forskningstrend är att försöka lindra för tidig konvergens (det vill säga optimeringsstagnation), t.ex. genom att vända eller störa rörelsen av PSO-partiklarna, ett annat tillvägagångssätt för att hantera för tidig konvergens är användningen av flera svärmar (multi-svärmoptimering ) . Multi-svärm-metoden kan också användas för att implementera multi-objektiv optimering. Slutligen finns det utvecklingar för att anpassa beteendeparametrarna för PSO under optimering.

Förenklingar

En annan tankegång är att PSO bör förenklas så mycket som möjligt utan att försämra dess prestanda; ett allmänt begrepp som ofta ses till som Occams rakkniv . Att förenkla PSO föreslogs ursprungligen av Kennedy och har studerats mer omfattande, där det visade sig att optimeringsprestandan förbättrades, och parametrarna var lättare att justera och de presterade mer konsekvent över olika optimeringsproblem.

Ett annat argument för att förenkla PSO är att metaheuristik endast kan få sin effektivitet demonstrerad empiriskt genom att göra beräkningsexperiment på ett begränsat antal optimeringsproblem. Detta innebär att en metaheuristik som PSO inte kan bevisas korrekt och detta ökar risken för att göra fel i dess beskrivning och implementering. Ett bra exempel på detta presenterade en lovande variant av en genetisk algoritm (en annan populär metaheuristik) men den visade sig senare vara defekt eftersom den var starkt partisk i sin optimeringssökning mot liknande värden för olika dimensioner i sökutrymmet, vilket råkade vara det optimala av de övervägda benchmarkproblemen. Denna bias berodde på ett programmeringsfel och har nu åtgärdats.

Initiering av hastigheter kan kräva extra ingångar. Bare Bones PSO-varianten har föreslagits 2003 av James Kennedy, och behöver inte använda hastighet alls.

En annan enklare variant är den accelererade partikelsvärmoptimeringen (APSO), som inte heller behöver använda hastighet och kan påskynda konvergensen i många applikationer. En enkel demokod för APSO är tillgänglig.

Multi-objektiv optimering

PSO har också tillämpats på multiobjektiva problem , där den objektiva funktionsjämförelsen tar hänsyn till Pareto-dominans när PSO-partiklarna flyttas och icke-dominerade lösningar lagras för att approximera paretofronten.

Binär, diskret och kombinatorisk

Eftersom PSO-ekvationerna ovan fungerar på reella tal, är en vanlig metod för att lösa diskreta problem att mappa det diskreta sökutrymmet till en kontinuerlig domän, att tillämpa en klassisk PSO och sedan avmappa resultatet. En sådan mappning kan vara mycket enkel (till exempel genom att bara använda avrundade värden) eller mer sofistikerad.

Det kan dock noteras att rörelseekvationerna använder sig av operatorer som utför fyra åtgärder:

• beräkna skillnaden mellan två positioner. Resultatet är en hastighet (mer exakt en förskjutning)
• multiplicera en hastighet med en numerisk koefficient
• lägga till två hastigheter
• applicera en hastighet på en position

Vanligtvis representeras en position och en hastighet av n reella tal, och dessa operatorer är helt enkelt -, *, + och igen +. Men alla dessa matematiska objekt kan definieras på ett helt annat sätt, för att klara av binära problem (eller mer allmänt diskreta sådana), eller till och med kombinatoriska. Ett tillvägagångssätt är att omdefiniera operatörerna utifrån set.

Se även

• Konstgjord bikolonialgoritm
• Bins algoritm
• Derivatfri optimering
• Multi-svärm optimering
• Partikelfilter
• Svärm intelligens
• Fiskskolasökning
• Dispersiv flugoptimering

externa länkar

• Particle Swarm Central är ett förvar för information om PSO. Flera källkoder är fritt tillgängliga.
• En kort video av partikelsvärmar som optimerar tre benchmarkfunktioner.
• Simulering av PSO-konvergens i ett tvådimensionellt rum (Matlab).
• Tillämpningar av PSO.
• Liu, Yang (2009). "Automatisk kalibrering av en modell för nederbörd och avrinning med hjälp av en snabb och elitistisk multi-objektiv partikelsvärmalgoritm". Expertsystem med applikationer . 36 (5): 9533–9538. doi : 10.1016/j.eswa.2008.10.086 .
• Länkar till PSO källkod