Original English version: http://www.projectcomputing.com/resources/psovis/
Sist oppdatert: 14. april 2004
Bunnen av denne siden inneholder en enkel Java-mini-program som visuelt demonstrerer en partikkelsvarm som søker etter en maksimumsverdi i et 3-D-landskap. Java-mini-program leveres som en 45KB jar-fil som har blitt testet med Microsoft JVM installert under IE6, men skal fungere med noen JVM 1.1 eller høyere.
En kort introduksjon til Partikkel sverm optimalisering
Partikkel sverm optimalisering er en tilnærming til problemer hvis løsninger kan representeres som et punkt i et n-dimensjonalt løsningsrom. Et antall partikler blir tilfeldig satt i bevegelse gjennom dette rommet. Ved hver iterasjon observerer de “fitness” av seg selv og deres naboer og “etterligner” vellykkede naboer (de som har nåværende posisjon som en bedre løsning på problemet enn deres) ved å bevege seg mot dem. Forskjellige ordninger for gruppering av partikler i konkurrerende, semi-uavhengige flokker kan brukes, eller alle partiklene kan tilhøre en enkelt global flokk. Denne ekstremt enkle tilnærmingen har vært overraskende effektiv over en rekke problemdomener.
PSO ble utviklet av James Kennedy og Russell Eberhart i 1995 etter å ha blitt inspirert av studien av fugleflockende oppførsel av biolog Frank Heppner. Det er relatert til evolusjon-inspirerte problemløsende teknikker som genetiske algoritmer.
Ressurser
- Partikkel sverm optimalisering, papir av James Kennedy og Russell Eberhart
- Bok: Sverm Intelligens av James Kennedy, Russell C Eberhart, med Yuhui Shi (Innh)
- Partikkel sverm sentral – en katalog av ressurser knyttet til PSO
Ta gjerne kontakt med Project Computing for å diskutere anvendelser av PSO.
Om denne mini-programen
PSO brukes vanligvis til å løse problemer med mange ukjente (av mange “dimensjoner”). Denne visualiseringen er relativt ekstremt enkel og triviell: sværmen søker over 2 ukjente (eller “dimensjoner”), og verdien av hvert punkt i disse 2 dimensjonene er plottet i tredje dimensjon.
Denne mini-programen ble skrevet av Kent Fitch, Project Computing ved å bygge videre på og kombinere modifiserte versjoner av disse to programmene:
- Koden inkludert i 3D datagrafikk: Flytte fra sideoppsett tegninger til solide, skyggefulle modeller av Todd Sundsted, som dukket opp i JavaWorld 1997. Selv om Java 3D-API gir den nødvendige funksjonaliteten, er enkel Todd kode juli og kjører under Java 1.1
- Den PSO implementering fra adaptiveview.com, som er enkel og var lett å få kjøre under Java 1.1.
- Dette mini-program genererer et semi-tilfeldig 3-D landskapet. En tilfeldig partikkel sverm av 12 partikler forsøker å finne den “globale maksimum” på landskapet. Svermen ikke “vet” hva den maksimale verdien er: det er bare beskjed om å stoppe når den støter på det.
- En ny sverm (med nye startposisjoner) kan genereres, som kan nye landskap.
- Svermen av 12 partiklene kan “arbeide sammen” som en flokk, eller kan deles i 2, 3 eller 4 randsone flokker.
- Svermen kan kjøres til fullførelse (eller 100 iterasjoner), “enkelt trappet” og midlertidig stoppet.
- Ulike farger brukes til å gjengi posisjonen til de nåværende og tidligere generasjoner, og bevegelsesspor gjengis til å visualisere utviklingen av svermen.
- Vent til mini-program laster. Som koden er bare 45KB, dette burde ikke ta lang tid. Du skal da se en 3-D landskapet under. Enten begynne å klikke knapper, eller lese forklaringen som følger!
- Den globale maksimum (som er poenget svermen søker) er markert med en rød pil.
- Du kan rotere landskapet med Opp/Ned/Venstre/Høyre-knappene, eller ved å klikke på landskapet og ved hjelp av piltastene. Du kan ikke rotere landskapet ved hjelp av musen.
- Klikk på “trinn” knappen. Dette vil initial svermen på landskapet. Utgangsstillingen for hver partikkel vil bli vist ved hjelp av en liten grønn markør. Rotere landskapet for å se partiklene i forhold til hverandre, og det maksimale.
- Klikk på “trinn” knappen igjen. De grønne rutene vil bevege seg, generelt i retning av “fittest” partikkel. Den foregående plassering av partiklene er markert med en gul markør, og en grønn linje trekkes fra det foregående til den aktuelle posisjonen, “visualisere” bevegelsen.
- “Trinn” igjen: den opprinnelige generasjon er nå farget magenta, blir den andre generasjon nå farget gule og plasseringen av dagens generasjon blir igjen gjengitt i grønt. Gule linjer viser de vektorer som er tatt av den opprinnelige generasjon bevegelig til den andre generasjon, og grønne linjer viser de vektorer som tas ved denne generasjonen bevegelige til dagens generasjon.
- “skritt” igjen: den opprinnelige generasjon er nå farget blå. Trinn igjen, og denne generasjonen er nå svart. Det vil si, generasjoner er representert ved hjelp av følgende farger: grønn, gul, magenta, blå, svart. Posisjonene til alle generasjoner eldre de siste 4 er gjengitt i svart. Bevegelse vektorer er vist for bare de 2 siste generasjoner.
- Bevegelses vektorer er alltid gjengitt “på toppen” av landskapet og kan sees selv om landskapet ville skjule vektor i den “virkelige verden”.
- Statusinformasjonen nederst mini-program-vinduet viser antall gjentakelser fullført, maksimumsverdien svermen søker, maksimumsverdien funnet i det siste (nyeste) køyring og maksimumsverdien funnet i noen gjentakelse i denne kjøringen.
- Første enkelt-trinns svermen for å få en følelse for hva som skjer. Dette er enklest med bare en flokk, så er det ingen visuell indikasjon av hvilken partiklene er i gruppert sammen i en flokk.
- Deretter kjøre noen tester til ferdigstillelse, observere flokken beveger seg over landskapet.
- Legg merke til hvordan omproduksjon tester på det samme landskapet gir ofte utrolig forskjellige resultater; det vil si hvor enkelte startposisjonene til partiklene føre til rask plassering av det globale maksimum, og hvor andre stillinger føre til svikt etter 100 iterasjoner.
- Test resultatene av å bruke ulike antall flokker på det samme landskapet.
- Prøv nye landskap. Observere hvordan noen landskap er bare vanskeligere, for eksempel de med “attraktiv” lokale maksima viss avstand fra det globale maksimum.
- Legg merke til at svermen har ingen andre enn den nåværende generasjons minne. Det gjenopptar tidligere steder som, hvis den hadde et slikt minne, ville det “vet” ikke kan være den globale maksimum. Legg også merke til at noen ganger gjentatte mønstre vil bli satt opp, ofte med flere partikler samtidig forskyves over de samme vektorer.
PSO visualisering mini-program:
Zip inneholder all kilde: backup11apr04psovis.zip
Project Computing Pty Ltd ACN: 008 590 967