Partikkelsvermoptimalisering - Particle swarm optimization

En partikkelsverm som søker etter det globale minimumet av en funksjon
Del av en serie om
Evolusjonær algoritme
Genetisk algoritme
Genetisk programmering

I beregningsvitenskap er optimalisering av partikkelsvermer ( PSO ) en beregningsmetode som optimaliserer et problem ved å iterativt prøve å forbedre en kandidatløsning med hensyn til et gitt kvalitetsmål. Det løser et problem ved å ha en populasjon av kandidatløsninger, her kalt partikler , og flytte disse partiklene rundt i søkeområdet i henhold til enkel matematisk formel over partikkelens posisjon og hastighet . Hver partikkels bevegelse påvirkes av den lokale mest kjente posisjonen, men ledes også mot de mest kjente posisjonene i søkeområdet, som oppdateres etter hvert som bedre posisjoner blir funnet av andre partikler. Dette forventes å bevege svermen mot de beste løsningene.

PSO er opprinnelig tilskrevet Kennedy , Eberhart og Shi og var først ment for å simulere sosial atferd , som en stilisert fremstilling av organismenes bevegelse i en fugleflokk eller fiskeskole . Algoritmen ble forenklet, og den ble observert for å utføre optimalisering. Boken av Kennedy og Eberhart beskriver mange filosofiske aspekter ved PSO og svermintelligens . En omfattende undersøkelse av PSO -applikasjoner er laget av Poli . Nylig har en omfattende gjennomgang av teoretiske og eksperimentelle verk på PSO blitt publisert av Bonyadi og Michalewicz.

PSO er en metaheurist, ettersom det gjør få eller ingen antagelser om at problemet blir optimalisert og kan søke i svært store mellomrom med kandidatløsninger. PSO bruker heller ikke gradienten til problemet som optimaliseres, noe som betyr at PSO ikke krever at optimaliseringsproblemet kan differensieres slik klassiske optimaliseringsmetoder som for eksempel nedstigning og kvasi-newton-metoder krever . Metheuristikk som PSO garanterer imidlertid ikke at en optimal løsning noensinne er funnet.

Algoritme

En grunnleggende variant av PSO -algoritmen fungerer ved å ha en populasjon (kalt en sverm) av kandidatløsninger (kalt partikler). Disse partiklene flyttes rundt i søkeområdet i henhold til noen få enkle formler. Bevegelsene til partiklene styres av deres egen mest kjente posisjon i søkeområdet samt hele svermens mest kjente posisjon. Når forbedrede posisjoner blir oppdaget, vil disse komme til å styre bevegelsene til svermen. Prosessen gjentas, og ved å gjøre det er det håpet, men ikke garantert, at en tilfredsstillende løsning til slutt vil bli oppdaget.

La formelt: f : ℝ n  → ℝ være kostnadsfunksjonen som må minimeres. Funksjonen tar en kandidatløsning som et argument i form av en vektor med reelle tall og produserer et reelt tall som utgang som indikerer den objektive funksjonsverdien til den gitte kandidatløsningen. Den gradienten av f er ikke kjent. Målet er å finne en løsning a som f ( a ) ≤  f ( b ) for alle b i søkeområdet, noe som betyr at a er det globale minimumet.

La S være antall partikler i svermen, som hver har en posisjon x i  ∈ ℝ n i søkeområdet og en hastighet v i  ∈ ℝ n . La p i være den mest kjente posisjonen til partikkel i og la g være den mest kjente posisjonen til hele svermen. En grunnleggende PSO -algoritme er da: 

for each particle i = 1, ..., S do
    Initialize the particle's position with a uniformly distributed random vector: xi ~ U(blo, bup)
    Initialize the particle's best known position to its initial position: pi ← xi
    if f(pi) < f(g) then
        update the swarm's best known position: g ← pi
    Initialize the particle's velocity: vi ~ U(-|bup-blo|, |bup-blo|)
while a termination criterion is not met do:
    for each particle i = 1, ..., S do
        for each dimension d = 1, ..., n do
            Pick random numbers: rp, rg ~ U(0,1)
            Update the particle's velocity: vi,d ← w vi,d + φp rp (pi,d-xi,d) + φg rg (gd-xi,d)
        Update the particle's position: xi ← xi + vi
        if f(xi) < f(pi) then
            Update the particle's best known position: pi ← xi
            if f(pi) < f(g) then
                Update the swarm's best known position: g ← pi

Verdiene b lo og b up representerer henholdsvis de nedre og øvre grensene for søkeområdet. W -parameteren er treghetsvekten. Parametrene φ p og φ g kalles ofte kognitiv koeffisient og sosial koeffisient.

Avslutningskriteriet kan være antall gjentatte iterasjoner, eller en løsning der tilstrekkelig objektiv funksjonsverdi er funnet. Parametrene w, φ p og are g velges av utøveren og kontrollerer oppførselen og effekten av PSO -metoden ( nedenfor ).

Valg av parameter

Ytelseslandskap som viser hvordan en enkel PSO -variant fungerer sammenlagt på flere referanseproblemer når to PSO -parametere varieres.

Valget av PSO -parametere kan ha stor innvirkning på optimaliseringsytelsen. Valg av PSO -parametere som gir god ytelse har derfor vært gjenstand for mye forskning.

For å forhindre divergens ("eksplosjon") må treghetsvekten være mindre enn 1. De to andre parameterne kan deretter avledes takket være innsnevringstilnærmingen, eller fritt valgt, men analysene antyder konvergensdomener for å begrense dem. Typiske verdier er i .

PSO-parametrene kan også justeres ved å bruke en annen overleggsoptimaliserer, et konsept som kalles metaoptimalisering , eller til og med finjusteres under optimaliseringen, f.eks. Ved hjelp av uklar logikk.

Parametere er også innstilt for ulike optimaliseringsscenarier.

Nabolag og topologier

Svermens topologi definerer delsettet av partikler som hver partikkel kan utveksle informasjon med. Den grunnleggende versjonen av algoritmen bruker den globale topologien som svermskommunikasjonsstruktur. Denne topologien gjør at alle partikler kan kommunisere med alle de andre partiklene, og dermed deler hele svermen den samme beste posisjonen g fra en enkelt partikkel. Imidlertid kan denne tilnærmingen føre til at svermen blir fanget inn i et lokalt minimum, og derfor har forskjellige topologier blitt brukt for å kontrollere informasjonsflyten mellom partikler. For eksempel, i lokale topologier, deler partikler bare informasjon med et delsett av partikler. Denne delmengden kan være en geometrisk - for eksempel "de m nærmeste partiklene" - eller oftere en sosial, det vil si et sett med partikler som ikke er avhengig av noen avstand. I slike tilfeller sies PSO -varianten å være lokal beste (vs global best for den grunnleggende PSO).

En vanlig svermetopologi er ringen, der hver partikkel bare har to naboer, men det er mange andre. Topologien er ikke nødvendigvis statisk. Siden topologien er relatert til mangfoldet av kommunikasjon av partiklene, har det faktisk blitt gjort noen forsøk på å lage adaptive topologier (SPSO, APSO, stokastisk stjerne, TRIBES, Cyber ​​Swarm og C-PSO).

Indre virkemåte

Det er flere tanker om hvorfor og hvordan PSO -algoritmen kan utføre optimalisering.

En vanlig oppfatning blant forskere er at svermadferden varierer mellom utforskende atferd, det vil si å søke i et bredere område av søkeområdet og utnyttende atferd, det vil si et lokalt orientert søk for å komme nærmere et (muligens lokalt) optimalt. Denne tankegangen har vært utbredt siden oppstarten av PSO. Denne tankegangen hevder at PSO -algoritmen og dens parametere må velges for å balansere riktig mellom leting og utnyttelse for å unngå for tidlig konvergens til et lokalt optimalt, men likevel sikre en god konvergenshastighet til det optimale. Denne troen er forløperen til mange PSO -varianter, se nedenfor .

En annen tankegang er at oppførselen til en PSO-sverm ikke er godt forstått når det gjelder hvordan den påvirker faktisk optimaliseringsytelse, spesielt for høyere dimensjonale søkeområder og optimaliseringsproblemer som kan være diskontinuerlige, støyende og tidsvarierende. Denne tankegangen prøver bare å finne PSO -algoritmer og parametere som forårsaker god ytelse uavhengig av hvordan svermadferden kan tolkes i forhold til f.eks. Leting og utnyttelse. Slike studier har ført til forenkling av PSO -algoritmen, se nedenfor .

Konvergens

I forhold til PSO refererer ordet konvergens vanligvis til to forskjellige definisjoner:

  • Konvergens av sekvensen av løsninger (aka, stabilitetsanalyse, konvergering ) der alle partikler har konvergert til et punkt i søkeområdet, som kanskje eller ikke er det optimale,
  • Konvergens til et lokalt optimalt der alle personlige rekorder p eller alternativt svermens mest kjente posisjon g , nærmer seg et lokalt optimalt for problemet, uavhengig av hvordan svermen oppfører seg.

Konvergens av sekvensen av løsninger har blitt undersøkt for PSO. Disse analysene har resultert i retningslinjer for valg av PSO -parametere som antas å forårsake konvergens til et punkt og forhindre divergens av svermens partikler (partikler beveger seg ikke ubegrenset og vil konvergere til et sted). Imidlertid ble analysene kritisert av Pedersen for å være forenklet ettersom de antar at svermen bare har en partikkel, at den ikke bruker stokastiske variabler og at tiltrekningspunktene, det vil si partikkelens mest kjente posisjon p og svermens mest kjente posisjon g , forbli konstant gjennom optimaliseringsprosessen. Imidlertid ble det vist at disse forenklingene ikke påvirker grensene funnet av disse studiene for parameter der svermen er konvergent. Det har blitt gjort en betydelig innsats de siste årene for å svekke modelleringsforutsetningen som ble benyttet under stabilitetsanalysen av PSO, med det siste generaliserte resultatet som gjaldt for mange PSO -varianter og benyttet det som viste seg å være de minimale nødvendige modellforutsetningene.

Konvergens til et lokalt optimalt er blitt analysert for PSO i og. Det er bevist at PSO trenger noen endringer for å garantere å finne et lokalt optimalt.

Dette betyr at bestemmelse av konvergensmuligheter for forskjellige PSO -algoritmer og parametere fortsatt er avhengig av empiriske resultater. Ett forsøk på å løse dette problemet er utviklingen av en "ortogonal læring" -strategi for en forbedret bruk av informasjonen som allerede finnes i forholdet mellom p og g , for å danne et ledende konvergerende eksempel og for å være effektiv med enhver PSO -topologi. Målet er å forbedre ytelsen til PSO generelt, inkludert raskere global konvergens, høyere løsningskvalitet og sterkere robusthet. Imidlertid gir slike studier ikke teoretiske bevis for å faktisk bevise påstandene deres.

Adaptive mekanismer

Uten behovet for en avveining mellom konvergens ('utnyttelse') og divergens ('utforskning'), kan en adaptiv mekanisme innføres. Adaptive particle swarm optimization (APSO) gir bedre søkeeffektivitet enn standard PSO. APSO kan utføre globalt søk over hele søkeområdet med en høyere konvergenshastighet. Den muliggjør automatisk kontroll av treghetsvekten, akselerasjonskoeffisientene og andre algoritmiske parametere på kjøretiden, og forbedrer dermed søkeeffektiviteten og effektiviteten samtidig. APSO kan også virke på den globalt beste partikkelen for å hoppe ut av den sannsynlige lokale optimaen. Imidlertid vil APSO introdusere nye algoritmeparametere, det introduserer imidlertid ikke ytterligere design eller implementeringskompleksitet.

Varianter

Mange varianter av selv en grunnleggende PSO -algoritme er mulige. For eksempel er det forskjellige måter å initialisere partiklene og hastighetene (f.eks. Starte med nullhastigheter i stedet), hvordan man demper hastigheten, oppdaterer bare p i og g etter at hele svermen er oppdatert osv. Noen av disse valgene og deres mulig ytelsespåvirkning har blitt diskutert i litteraturen.

En serie standardimplementeringer er laget av ledende forskere, "beregnet på bruk både som grunnlag for ytelsestesting av forbedringer av teknikken, samt for å representere PSO for det bredere optimaliseringssamfunnet. Å ha et velkjent, strengt definert standardalgoritme gir et verdifullt sammenligningspunkt som kan brukes i hele forskningsfeltet for bedre å teste nye fremskritt. " Den siste er Standard PSO 2011 (SPSO-2011).

Hybridisering

Nye og mer sofistikerte PSO -varianter blir også stadig introdusert i et forsøk på å forbedre optimaliseringsytelsen. Det er visse trender i den forskningen; den ene er å lage en hybridoptimaliseringsmetode ved bruk av PSO kombinert med andre optimatorer, f.eks. kombinert PSO med biogeografibasert optimalisering, og inkorporering av en effektiv læringsmetode.

Gradientbaserte PSO -algoritmer

PSO -algoritmenes evne til effektivt å utforske flere lokale minimum kan kombineres med muligheten til gradientbaserte lokale søkealgoritmer for effektivt å beregne et nøyaktig lokalt minimum for å produsere gradientbaserte PSO -algoritmer. I gradientbaserte PSO -algoritmer brukes PSO -algoritmen til å utforske mange lokale minima og finne et punkt i tiltrekningsbassenget til et dypt lokalt minimum. Deretter brukes effektive gradientbaserte lokale søkealgoritmer for å nøyaktig lokalisere det dype lokale minimumet. Beregningen av gradienter og hessere av komplekse høydimensjonale kostnadsfunksjoner er ofte beregningsmessig kostbar og manuelt umulig i mange tilfeller som forhindrer utbredt bruk av gradientbaserte PSO-algoritmer. Imidlertid har tilgjengeligheten av høy kvalitet symbolsk automatisk differensiering (AD) programvare de siste årene ført til en økning i interessen for gradientbaserte PSO -algoritmer.

Lindre for tidlig konvergens

En annen forskningstrend er å prøve å lindre for tidlig konvergens (det vil si optimaliseringstagnasjon), f.eks. Ved å reversere eller forstyrre bevegelsen til PSO-partiklene, er en annen tilnærming for å håndtere for tidlig konvergens bruk av flere svermer ( optimalisering av flere svermer ). Multisverm-tilnærmingen kan også brukes til å implementere flerobjektoptimalisering. Til slutt er det utvikling i å tilpasse atferdsparametrene til PSO under optimalisering.

Forenklinger

En annen tankegang er at PSO bør forenkles så mye som mulig uten å svekke ytelsen; et generelt begrep som ofte omtales som Occams barberhøvel . Forenkling av PSO ble opprinnelig foreslått av Kennedy og har blitt studert mer omfattende, hvor det så ut til at optimaliseringsytelsen ble forbedret, og parametrene var lettere å justere og de utførte mer konsekvent på tvers av forskjellige optimaliseringsproblemer.

Et annet argument for å forenkle PSO er at metaheuristikk bare kan få demonstrert sin effekt empirisk ved å gjøre beregningseksperimenter på et begrenset antall optimaliseringsproblemer. Dette betyr at en metaheuristikk som PSO ikke kan bevises riktig, og dette øker risikoen for å gjøre feil i beskrivelsen og implementeringen. Et godt eksempel på dette presenterte en lovende variant av en genetisk algoritme (en annen populær metaheuristisk), men den ble senere funnet å være defekt da den var sterkt partisk i optimeringssøket mot lignende verdier for forskjellige dimensjoner i søkeområdet, som tilfeldigvis var det optimale av referanseproblemene som vurderes. Denne skjevheten skyldtes en programmeringsfeil, og er nå rettet.

Initialisering av hastigheter kan kreve ekstra innganger. Bare Bones PSO -varianten ble foreslått i 2003 av James Kennedy, og trenger ikke bruke hastighet i det hele tatt.

En annen enklere variant er den akselererte partikkelsvermeroptimaliseringen (APSO), som heller ikke trenger å bruke hastighet og kan fremskynde konvergensen i mange applikasjoner. En enkel demokode for APSO er tilgjengelig.

Flerobjektiv optimalisering

PSO har også blitt brukt på flerobjektive problemer , der objektivfunksjonssammenligningen tar hensyn til pareto-dominans når PSO-partiklene flyttes og ikke-dominerte løsninger lagres for å tilnærme pareto-fronten.

Binær, diskret og kombinatorisk

Siden PSO -ligningene som er gitt ovenfor, fungerer på reelle tall, er en vanlig metode for å løse diskrete problemer å kartlegge det diskrete søkeområdet til et kontinuerlig domene, bruke en klassisk PSO og deretter dempe resultatet. En slik kartlegging kan være veldig enkel (for eksempel ved bare å bruke avrundede verdier) eller mer sofistikert.

Imidlertid kan det bemerkes at bevegelsesligningene bruker operatører som utfører fire handlinger:

  • beregne forskjellen mellom to posisjoner. Resultatet er en hastighet (mer presist en forskyvning)
  • multiplisere en hastighet med en numerisk koeffisient
  • legge til to hastigheter
  • bruke en hastighet til en posisjon

Vanligvis er en posisjon og en hastighet representert med n reelle tall, og disse operatorene er ganske enkelt -, *, +og igjen +. Men alle disse matematiske objektene kan defineres på en helt annen måte for å takle binære problemer (eller mer generelt diskrete) eller til og med kombinatoriske. En tilnærming er å omdefinere operatørene basert på sett.

Se også

Referanser

Eksterne linker