Flyalgoritme - Fly algorithm

Historie

Fluealgoritmen er en type kooperativ samevolusjon basert på den parisiske tilnærmingen. Flyalgoritmen har først blitt utviklet i 1999 innen omfanget av applikasjonen av evolusjonære algoritmer på datamaskinens stereosyn . I motsetning til den klassiske bildebaserte tilnærmingen til stereovisjon, som trekker ut bildeprimitiver og matcher dem for å få 3D-informasjon, er flyagoritmen basert på direkte utforskning av scenens 3D-rom. En flue er definert som et 3D-punkt beskrevet av koordinatene ( x , y , z ). Når en tilfeldig populasjon av fluer er opprettet i et søkeområde som tilsvarer synsfeltet til kameraene, brukte utviklingen (basert på evolusjonær strategiparadigme) en treningsfunksjon som evaluerer hvor sannsynlig flua ligger på den synlige overflaten av et objekt, basert på konsistensen i dets bildeprojeksjoner. Til dette formål bruker treningsfunksjonen de grå nivåene, fargene og/eller teksturene til den beregnede fluens anslag.

Det første applikasjonsfeltet i flyalgoritmen har vært stereovisjon. Mens klassiske tilnærminger for bildeprioritet bruker matchende funksjoner fra stereobildene for å bygge en 3D-modell, utforsker Flyalgoritmen 3D-rommet direkte og bruker bildedata for å evaluere gyldigheten av 3D-hypoteser. En variant som kalles "Dynamic Flies" definerer fluen som en 6-uple ( x , y , z , x ' , y' , z ' ) som involverer fluens hastighet. Hastighetskomponentene blir ikke eksplisitt tatt i betraktning i fitnessberegningen, men brukes i fluenes posisjoner og oppdateres og er gjenstand for lignende genetiske operatører (mutasjon, crossover).

Anvendelsen av Fluer for å unngå hindringer i kjøretøyer utnytter det faktum at bestanden av fluer er en tidskompatibel, kvasi-kontinuerlig utvikling av scenen for direkte å generere kjøretøykontrollsignaler fra fluene. Bruken av flyalgoritmen er ikke strengt begrenset til stereobilder, da andre sensorer kan legges til (f.eks. Akustiske nærhetssensorer, etc.) som tilleggsbetingelser for at treningsfunksjonen skal optimaliseres. Kilometertellerinformasjon kan også brukes til å øke hastigheten på oppdateringen av flueposisjoner, og omvendt kan flueposisjonene brukes til å gi lokaliserings- og kartinformasjon.

Et annet anvendelsesområde for flyalgoritmen er rekonstruksjon for utslippstomografi i nukleærmedisin . Fluealgoritmen er vellykket brukt i enkeltfotonemisjonstomografi og positronemisjonstomografi . Her regnes hver flue som en fotonemitter og dens egnethet er basert på samsvaret mellom den simulerte belysningen av sensorene med det faktiske mønsteret som observeres på sensorene. I denne applikasjonen har treningsfunksjonen blitt definert på nytt for å bruke det nye konseptet "marginal evaluering". Her beregnes egnetheten til ett individ som dets (positive eller negative) bidrag til kvaliteten på den globale befolkningen. Den er basert på kryssvalideringsprinsippet leave-one-out . En global treningsfunksjon evaluerer kvaliteten på befolkningen som helhet; bare da beregnes egnetheten til et individ (en flue) som forskjellen mellom de globale kondisjonsverdiene til befolkningen med og uten den spesielle fluen hvis individuelle kondisjonsfunksjon må evalueres. I form av hver flue betraktes som et `` nivå av tillit ''. Den brukes under vokseliseringsprosessen for å justere fluens individuelle fotavtrykk ved hjelp av implisitt modellering (for eksempel metaballer ). Det gir jevne resultater som er mer nøyaktige.

Mer nylig har det blitt brukt i digital kunst for å generere mosaikklignende bilder eller spraymaling. Eksempler på bilder finner du på YouTube

Parisisk evolusjon

Her blir befolkningen av individer betraktet som et samfunn der individene samarbeider mot et felles mål. Dette implementeres ved hjelp av en evolusjonær algoritme som inkluderer alle de vanlige genetiske operatorene (f.eks. Mutasjon, kryss, seleksjon). Hovedforskjellen er i treningsfunksjonen. Her brukes to nivåer av treningsfunksjon:

• En lokal treningsfunksjon for å vurdere ytelsen til et gitt individ (vanligvis brukt under utvelgelsesprosessen).
• En global treningsfunksjon for å vurdere ytelsen til hele befolkningen. Maksimering (eller minimering avhengig av problemet som vurderes) denne globale formen er befolkningens mål.

I tillegg kreves en mangfoldsmekanisme for å unngå at enkeltpersoner samles på bare noen få områder av søkeområdet. En annen forskjell er i ekstraksjonen av problemløsningen når evolusjonssløyfen avsluttes. I klassiske evolusjonære tilnærminger tilsvarer det beste individet løsningen, og resten av befolkningen kastes. Her samles alle individer (eller individer i en undergruppe av befolkningen) for å bygge problemløsningen. Måten treningsfunksjonene er konstruert og måten løsningsekstraksjonen er laget på er selvfølgelig problemavhengig.

Eksempler på programmer i Parisian Evolution inkluderer:

• Fly -algoritmen .
• Tekst-gruvedrift .
• Håndbevegelsesgjenkjenning .
• Modellering av komplekse interaksjoner i industriell matproduksjon .
• Rekonstruksjon av Positron Emission Tomography .

Disambiguation

Parisisk tilnærming vs kooperativ samevolusjon

Cooperative coevolution er en bred klasse av evolusjonære algoritmer der et komplekst problem løses ved å dekomponere det til delkomponenter som løses uavhengig. Den parisiske tilnærmingen deler mange likheter med den kooperative koevolusjonære algoritmen . Den parisiske tilnærmingen bruker en enkelt befolkning, mens flere arter kan brukes i kooperativ koevolusjonær algoritme . Lignende interne evolusjonære motorer vurderes i klassisk evolusjonsalgoritme , kooperativ koevolusjonær algoritme og parisisk evolusjon. Forskjellen mellom kooperativ koevolusjonær algoritme og parisisk evolusjon ligger i befolkningens semantikk. Kooperativ samevolusjonær algoritme deler et stort problem i delproblemer (grupper av individer) og løser dem separat mot det store problemet. Det er ingen interaksjon/avl mellom individer i de forskjellige underpopulasjonene, bare med individer av samme underpopulasjon. Imidlertid løser parisiske evolusjonære algoritmer et helt problem som en stor komponent. Alle befolkningens individer samarbeider for å drive hele befolkningen mot attraktive områder i søkeområdet.

Optimering av flyalgoritme vs partikkelsverm

Cooperative coevolution and particle swarm optimization (PSO) deler mange likheter. PSO er inspirert av den sosiale oppførselen til fugle flokk eller fiskeskole. Det ble opprinnelig introdusert som et verktøy for realistisk animasjon i datagrafikk. Den bruker komplekse individer som samhandler med hverandre for å bygge visuelt realistisk kollektiv atferd gjennom å justere individets atferdsregler (som kan bruke tilfeldige generatorer). I matematisk optimalisering følger hver partikkel av svermen på en eller annen måte sin egen tilfeldige bane forspent mot den beste partikkelen av svermen. I fluealgoritmen tar fluene sikte på å bygge romlige representasjoner av en scene fra faktiske sensordata; fluer kommuniserer ikke eller samarbeider eksplisitt, og bruker ikke noen atferdsmodell.

Begge algoritmene er søkemetoder som starter med et sett med tilfeldige løsninger, som iterativt blir korrigert mot et globalt optimalt. Imidlertid er løsningen på optimaliseringsproblemet i Fluealgoritmen populasjonen (eller en delmengde av befolkningen): Fluene samarbeider implisitt for å bygge løsningen. I PSO er løsningen en enkelt partikkel, den med den beste formen. En annen hovedforskjell mellom flyalgoritmen og med PSO er at flyalgoritmen ikke er basert på noen atferdsmodell, men bare bygger en geometrisk fremstilling.

Applikasjoner av Fly -algoritmen

• Datastereosyn
• Hindring av hindringer
• Samtidig lokalisering og kartlegging (SLAM)
• Rekonstruksjon av enkeltfotonemisjonstomografi (SPECT)
• Rekonstruksjon av positronemisjonstomografi (PET)
• Digital kunst

Eksempel: Tomografi rekonstruksjon

Sinogram av , som er kjent.${\ displaystyle (Y)}$${\ displaystyle f}$

Eksempel på rekonstruksjon av et hot rod -fantom ved bruk av flyalgoritmen.

Rekonstruksjon av tomografi er et omvendt problem som ofte er dårlig posert på grunn av manglende data og/eller støy. Svaret på det omvendte problemet er ikke unikt, og i tilfelle ekstremt støynivå kan det ikke engang eksistere. Inndataene til en rekonstruksjonsalgoritme kan gis som Radon -transformasjonen eller sinogrammet til dataene som skal rekonstrueres . er ukjent; er kjent. Datainnsamlingen i tomografi kan modelleres som: ${\ displaystyle \ left (Y \ right)}$${\ displaystyle \ left (f \ right)}$${\ displaystyle f}$${\ displaystyle Y}$

${\ displaystyle Y = P [f]+\ epsilon}$

hvor er systemmatrisen eller projiseringsoperatøren og tilsvarer noe Poisson -støy . I dette tilfellet tilsvarer rekonstruksjonen inversjonen av Radon -transformasjonen : ${\ displaystyle P}$${\ displaystyle \ epsilon}$

${\ displaystyle f = P^{-1} [Y]}$

Legg merke til at det kan ta hensyn til støy, anskaffelsesgeometri, etc. Flyalgoritmen er et eksempel på iterativ rekonstruksjon . Iterative metoder for tomografisk rekonstruksjon er relativt enkle å modellere: ${\ displaystyle P^{-1}}$

${\ displaystyle {\ hat {f}} = \ operatorname {arg \, min} || Y-{\ hat {Y}} || _ {2}^{2}}$

hvor er et estimat på , som minimerer en feilberegning (her ℓ ² -norm , men andre feilberegninger kan brukes) mellom og . Vær oppmerksom på at en reguleringsperiode kan innføres for å forhindre overmontering og for å jevne ut støy samtidig som kantene bevares. Iterative metoder kan implementeres som følger: ${\ displaystyle {\ hat {f}}}$${\ displaystyle f}$${\ displaystyle Y}$${\ displaystyle {\ hat {Y}}}$

Iterativ korreksjon ved tomografi -rekonstruksjon.

  (i) The reconstruction starts using an initial estimate of the image (generally a constant image),
  (ii) Projection data is computed from this image,
  (iii) The estimated projections are compared with the measured projections,
  (iv) Corrections are made to correct the estimated image, and
  (v) The algorithm iterates until convergence of the estimated and measured projection sets.

Den pseudo nedenfor er en trinn-for-trinn beskrivelse av Fly Algoritme for tomografisk rekonstruksjon . Algoritmen følger paradigmet for steady-state. For illustrasjonsformål ignoreres avanserte genetiske operatører, for eksempel mitose, dobbel mutasjon, etc. En JavaScript -implementering finnes på Fly4PET .

algorithm fly-algorithm is
    input: number of flies (N), 
           input projection data (preference)
    
    output: the fly population (F), 
            the projections estimated from F (pestimated)
            the 3-D volume corresponding to the voxelisation of F (VF)
    
    postcondition: the difference between pestimated and preference is minimal.
    
    START
    
 1.   // Initialisation
 2.   // Set the position of the N flies, i.e. create initial guess
 3.   for each fly i in fly population F do
 4.       F(i)x ← random(0, 1)
 5.       F(i)y ← random(0, 1)
 6.       F(i)z ← random(0, 1)
 7.       Add F(i)'s projection in pestimated
 8.   
 9.   // Compute the population's performance (i.e. the global fitness)
10.   Gfitness(F) ← Errormetrics(preference, pestimated)
11.    
12.   fkill ← Select a random fly of F
13.    
14.   Remove fkill's contribution from pestimated
15.    
16.   // Compute the population's performance without fkill
17.   Gfitness(F-{fkill}) ← Errormetrics(preference, pestimated)
18.    
19.   // Compare the performances, i.e. compute the fly's local fitness
20.   Lfitness(fkill) ← Gfitness(F-{fkill}) - Gfitness(F)
21.    
22.   If the local fitness is greater than 0, // Thresholded-selection of a bad fly that can be killed
23.       then go to Step 26.   // fkill is a good fly (the population's performance is better when fkill is included): we should not kill it
24.       else go to Step 28.   // fkill is a bad fly (the population's performance is worse when fkill is included): we can get rid of it
25.    
26.   Restore the fly's contribution, then go to Step 12.
27.    
28.   Select a genetic operator
29.    
30.   If the genetic operator is mutation,
31.       then go to Step 34.
32.       else go to Step 50.
33.    
34.   freproduce ← Select a random fly of F
35.    
14.   Remove freproduce's contribution from pestimated
37.    
38.   // Compute the population's performance without freproduce
39.   Gfitness(F-{freproduce}) ← Errormetrics(preference, pestimated)
40.    
41.   // Compare the performances, i.e. compute the fly's local fitness
42.   Lfitness(freproduce) ← Gfitness(F-{freproduce}) - Gfitness(F)
43.    
44.   Restore the fly's contribution
45.    
46.   If the local fitness is lower than or equal to 0, // Thresholded-selection of a good fly that can reproduce
47.       else go to Step 34.   // fkill is a bad fly: we should not allow it to reproduce
48.       then go to Step 53.   // fkill is a good fly: we can allow it to reproduce
49.    
50.   // New blood / Immigration
51.   Replace fkill by a new fly with a random position, go to Step 57.
52.    
53.   // Mutation
54.   Copy freproduce into fkill
55.   Slightly and randomly alter fkill's position
56.    
57.   Add the new fly's contribution to the population
58.    
59.   If stop the reconstruction,
60.       then go to Step 63.
61.       else go to Step 10.
62.    
63.   // Extract solution
64.   VF ← voxelisation of F
65.    
66.   return VF
   
   END

Eksempel: Digital kunst

Evolusjonært søk.

Bilde rekonstruert etter optimalisering ved hjelp av et sett med striper som mønster for hver flis.

I dette eksemplet skal et inndatabilde tilnærmes av et sett med fliser (for eksempel som i en gammel mosaikk ). En flis har en orientering (vinkel θ), en tre fargekomponenter (R, G, B), en størrelse (w, h) og en posisjon (x, y, z). Hvis det er N -fliser, er det 9 N ukjente flytende tall å gjette. Med andre ord for 5000 fliser, er det 45 000 tall å finne. Ved å bruke en klassisk evolusjonsalgoritme der svaret på optimaliseringsproblemet er det beste individet, vil genomet til et individ bestå av 45 000 gener. Denne tilnærmingen vil være ekstremt kostbar når det gjelder kompleksitet og datatid. Det samme gjelder for enhver klassisk optimaliseringsalgoritme. Ved bruk av Fly -algoritmen etterligner hvert individ en flis og kan evalueres individuelt ved hjelp av sin lokale egnethet for å vurdere sitt bidrag til befolkningens ytelse (den globale kondisjonen). Her har et individ 9 gener i stedet for 9 N , og det er N individer. Det kan løses som et gjenoppbyggingsproblem på følgende måte:

${\ displaystyle reconstruction = \ operatorname {arg \, min} {\ overset {x <W} {\ underset {y = 0} {\ sum}}} {\ overset {j <H} {\ underset {j = 0 } {\ sum}}} | input (x, y) -P [F] (x, y) |}$

hvor er inndatabildet, og er pikselkoordinatene langs henholdsvis den horisontale og vertikale aksen, og er henholdsvis bildebredden og høyden i antall piksler, er fluepopulasjonen, og er en projiseringsoperatør som lager et bilde fra fluer. Denne projiseringsoperatøren kan ha mange former. I sitt arbeid bruker Z. Ali Aboodd OpenGL for å generere forskjellige effekter (f.eks. Mosaikk eller spraymaling). For å fremskynde evalueringen av treningsfunksjonene, brukes OpenCL også. Algoritmen starter med en populasjon som genereres tilfeldig (se linje 3 i algoritmen ovenfor). blir deretter vurdert ved hjelp av den globale egnetheten til å beregne (se linje 10). er en feilberegning, må den minimeres. ${\ displaystyle input}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle W}$${\ displaystyle H}$${\ displaystyle F}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle F}$${\ displaystyle F}$${\ displaystyle G_ {fitness} (F) = {\ oversett {x <W} {\ undersett {y = 0} {\ sum}}} {\ oversett {j <H} {\ undersett {j = 0} { \ sum}}} | input (x, y) -P [F] (x, y) |}$${\ displaystyle G_ {fitness}}$

Se også

• Matematisk optimalisering
• Metauristisk
• Søkealgoritme
• Stokastisk optimalisering
• Evolusjonær beregning
• Evolusjonær algoritme
• Genetisk algoritme
• Mutasjon (genetisk algoritme)
• Crossover (genetisk algoritme)
• Seleksjon (genetisk algoritme)

Referanser