Repülési algoritmus - Fly algorithm

Történelem

A repülési algoritmus a párizsi megközelítésen alapuló kooperatív koevolúció egy típusa . A Fly algoritmust először dolgoztak 1999-ben az alkalmazási körét az evolúciós algoritmusok a számítógép sztereó látás . Ellentétben a sztereovízió klasszikus képalapú megközelítésével, amely kivonja a képprimitíveket, majd ezekhez illeszkedik a 3D-s információk megszerzése érdekében, a repülési algoritmus a jelenet háromdimenziós terének közvetlen feltárásán alapul. A légy egy 3D-s pont, amelyet a koordinátái ( x , y , z ) írnak le . Miután a legyek véletlenszerű populációját létrehozták a kamerák látómezőjének megfelelő keresési térben, az evolúciója (az evolúciós stratégia paradigmáján alapulva) egy olyan fitneszfunkciót használt, amely felméri, hogy a légy milyen valószínűséggel fekszik a objektum, a képvetítéseinek konzisztenciája alapján. Ebből a célból a fitnesz funkció a kiszámított légy vetületeinek szürke színét, színeit és/vagy textúráját használja.

A repülési algoritmus első alkalmazási területe a sztereovízió volt. Míg a klasszikus „képprioritásos” megközelítések a sztereó képek megfelelő tulajdonságait használják a 3-D modell létrehozásához, a repülési algoritmus közvetlenül feltárja a 3-D teret, és képadatok alapján értékeli a 3-D hipotézisek érvényességét. A "Dinamikus legyek" elnevezésű variáns a légyet 6 felfelé ( x , y , z , x ' , y' , z ' ) határozza meg, amely magában foglalja a légy sebességét. A sebességkomponenseket nem veszik kifejezetten figyelembe az alkalmasság számításakor, de a legyek helyzetének frissítésekor használják őket, és hasonló genetikai operátoroknak vannak kitéve (mutáció, kereszteződés).

A Legyek alkalmazása az akadályok elkerülésében a járművekben kihasználja azt a tényt, hogy a legyek populációja az időnek megfelelő, kvázi folyamatosan fejlődő ábrázolása a helyszínnek, hogy közvetlenül generálja a járművezérlő jeleket a legyekből. A repülési algoritmus használata nem korlátozódik szigorúan a sztereó képekre, mivel az optimalizálható fitneszfunkció további feltételei lehetnek más érzékelők (pl. Akusztikus közelségérzékelők stb.). Az odometriai információk felhasználhatók a legyek pozícióinak frissítésének felgyorsítására is, és fordítva, a legyek pozíciói felhasználhatók a lokalizációs és térképi információk szolgáltatására.

A repülési algoritmus másik alkalmazási területe az emissziós tomográfia rekonstrukciója a nukleáris medicinában . A repülési algoritmust sikeresen alkalmazták az egyfoton emissziós számítógépes tomográfiában és a pozitron emissziós tomográfiában . Itt minden légy fotonkibocsátónak számít, és alkalmassága azon alapul, hogy az érzékelők szimulált megvilágítása megfelel az érzékelőkön megfigyelt tényleges mintázatnak. Ebben az alkalmazásban a fitnesz funkciót újradefiniálták a „marginális értékelés” új koncepciójának használatára. Itt egy személy alkalmasságát úgy számítják ki, hogy az (pozitív vagy negatív) hozzájárul a globális népesség minőségéhez. Ennek alapja a kihagyható kereszt-érvényesítés elve. Egy globális fitneszfunkció értékeli a lakosság egészének minőségét; csak ezután számítjuk ki az egyén (légy) alkalmasságát a populáció globális alkalmassági értékei közötti különbségként azzal a légymel és anélkül, hogy az adott fitneszfunkciót ki kell értékelni. Az egyes légy alkalmasságában a „magabiztosság szintjének” tekintik. A voxelizációs folyamat során használják a légy egyéni lábnyomának módosítására implicit modellezéssel (például metaballal ). Sima, pontosabb eredményeket produkál.

A közelmúltban a digitális művészetben mozaikszerű képek vagy spray-festékek előállítására használták. Példák a képekre megtalálhatók a YouTube -on

Párizsi evolúció

Itt az egyének lakosságát olyan társadalomnak tekintik, ahol az egyének együttműködnek egy közös cél érdekében. Ez egy evolúciós algoritmus segítségével valósul meg, amely magában foglalja az összes gyakori genetikai operátort (pl. Mutáció, keresztezés, szelekció). A fő különbség a fitnesz funkcióban van. Itt a fitnesz funkció két szintjét használjuk:

• Helyi fitneszfunkció egy adott személy teljesítményének felmérésére (általában a kiválasztási folyamat során használják).
• Globális fitneszfunkció a teljes lakosság teljesítményének felmérésére. Ennek a globális alkalmasságnak a maximalizálása (vagy minimalizálása a figyelembe vett problémától függően) a lakosság célja.

Ezenkívül diverzitásmechanizmusra van szükség annak elkerülése érdekében, hogy az egyének a keresési tér csak néhány területén gyűljenek össze. Egy másik különbség abban rejlik, hogy az evolúciós ciklus befejeztével kivonjuk a problémamegoldást. A klasszikus evolúciós megközelítésekben a legjobb egyed felel meg a megoldásnak, és a populáció többi részét elvetik. Itt az összes egyént (vagy a lakosság egy alcsoportjának egyedeit) összegyűjtjük a probléma megoldásának felépítése érdekében. A fitneszfunkciók felépítésének módja és a megoldáskivonás módja természetesen problémafüggő.

Példák a párizsi Evolution alkalmazásokra:

• A Fly algoritmus .
• Szövegbányászat .
• Kézmozdulatok felismerése .
• Komplex kölcsönhatások modellezése az ipari mezőgazdasági élelmiszerek folyamatában .
• Pozitron emissziós tomográfia rekonstrukció .

Egyértelműség

Párizsi megközelítés vs kooperatív koevolúció

A kooperatív koevolúció az evolúciós algoritmusok széles osztálya, ahol egy összetett problémát úgy oldanak meg, hogy azt önállóan megoldott részkomponensekre bontják. A párizsi megközelítés sok hasonlóságot mutat a kooperatív koevolúciós algoritmussal . A párizsi megközelítés egyetlen populációt használ, míg több faj használható kooperatív koevolúciós algoritmusban . Hasonló belső evolúciós motorokat vesznek figyelembe a klasszikus evolúciós algoritmusban , a kooperatív koevolúciós algoritmusban és a párizsi evolúcióban. A kooperatív koevolúciós algoritmus és a párizsi evolúció közötti különbség a lakosság szemantikájában rejlik. A kooperatív koevolúciós algoritmus egy nagy problémát részproblémákra (egyének csoportjaira) oszt, és külön-külön oldja meg őket a nagy probléma felé. Nincs interakció/tenyésztés a különböző alpopulációk egyedei között, csak ugyanazon alpopuláció egyedeivel. A párizsi evolúciós algoritmusok azonban egy nagy problémaként megoldanak egy egész problémát. A lakosság minden egyede együttműködik annak érdekében, hogy az egész lakosságot a keresési tér vonzó területei felé terelje.

Repülési algoritmus vs részecskeraj optimalizálás

A kooperatív koevolúció és a részecskeraj optimalizálás (PSO) sok hasonlóságot mutat. A PSO -t a madárcsapás vagy a haltanítás társadalmi viselkedése ihlette. Kezdetben a számítógépes grafika valósághű animációjának eszközeként mutatták be. Összetett személyeket használ, amelyek kölcsönhatásba lépnek egymással annak érdekében, hogy vizuálisan reális kollektív viselkedést alakítsanak ki az egyének viselkedési szabályainak kiigazításával (amelyek véletlenszerű generátorokat is használhatnak). A matematikai optimalizálás során a raj minden részecske valahogy a saját véletlen útját követi, amely a raj legjobb részecskéje felé irányul. A repülési algoritmusban a legyek célja egy jelenet térbeli reprezentációinak felépítése a tényleges érzékelőadatokból; a legyek nem kommunikálnak vagy kifejezetten együttműködnek, és nem használnak semmilyen viselkedési modellt.

Mindkét algoritmus olyan keresési módszer, amely véletlenszerű megoldásokkal kezdődik, amelyeket iteratíven korrigálnak a globális optimum felé. A repülési algoritmus optimalizálási problémájának megoldása azonban a populáció (vagy a populáció egy részhalmaza): a legyek implicit módon együttműködnek a megoldás megalkotásában. A PSO -ban a megoldás egyetlen részecske, a legjobban alkalmas. Egy másik fő különbség a repülési algoritmus és a PSO között az, hogy a repülési algoritmus nem alapul semmilyen viselkedési modellre, hanem csak geometriai ábrázolást épít fel.

A Fly algoritmus alkalmazása

• Számítógépes sztereó látás
• Akadálykerülés
• Egyidejű lokalizáció és leképezés (SLAM)
• Egyfoton emissziós számítógépes tomográfia (SPECT) rekonstrukciója
• Pozitron emissziós tomográfia (PET) rekonstrukciója
• Digitális művészet

Példa: Tomográfiai rekonstrukció

Sinogram az , amely ismert.${\ displaystyle (Y)}$${\ displaystyle f}$

Példa egy hot rod fantom rekonstrukciójára a Fly algoritmus használatával.

A tomográfia rekonstrukciója fordított probléma , amely gyakran rosszul jelenik meg hiányzó adatok és/vagy zaj miatt. Az inverz probléma megoldása nem egyedi, és extrém zajszint esetén előfordulhat, hogy nem is létezik. A rekonstrukciós algoritmus bemeneti adatai megadhatók Radon -transzformációként vagy a rekonstruálandó adatok szinogramjaként . ismeretlen; ismert. A tomográfiai adatgyűjtés a következőképpen modellezhető: ${\ displaystyle \ left (Y \ right)}$${\ displaystyle \ left (f \ right)}$${\ displaystyle f}$${\ displaystyle Y}$

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

hol van a rendszer mátrixa vagy a vetítő operátor, és megfelel néhány Poisson -zajnak . Ebben az esetben a rekonstrukció a Radon transzformáció inverziójának felel meg : ${\ displaystyle P}$${\ displaystyle \ epsilon}$

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

Vegye figyelembe, hogy figyelembe veheti a zajt, a felvételi geometriát stb. A repülési algoritmus az iteratív rekonstrukció példája . A tomográfiai rekonstrukció iterációs módszerei viszonylag könnyen modellezhetők: ${\ displaystyle P^{-1}}$

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

ahol van egy becslés , amely minimálisra csökkenti a hibamutatókat (itt ℓ ² -norm , de más hibamutatók is használhatók) a és között . Ne feledje, hogy a túlszabályozás megelőzésére és a zaj kiegyenlítésére, az élek megőrzése mellett, szabályozási kifejezés is bevezethető. Az iterációs módszerek a következőképpen valósíthatók meg: ${\ displaystyle {\ hat {f}}}$${\ displaystyle f}$${\ displaystyle Y}$${\ displaystyle {\ hat {Y}}}$

Iteratív korrekció a tomográfia rekonstrukciójában.

  (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.

Az alábbi pszeudokód lépésről lépésre írja le a repülési algoritmust a tomográfiai rekonstrukcióhoz . Az algoritmus az egyensúlyi állapot paradigmáját követi. Szemléltetés céljából figyelmen kívül hagyják a fejlett genetikai operátorokat, például a mitózist, a kettős mutációt stb. A JavaScript implementáció megtalálható a Fly4PET -en .

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

Példa: Digitális művészet

Evolúciós keresés.

A kép az optimalizálás után rekonstruálva, minden csempe mintájaként csíkokat használva.

Ebben a példában a bemeneti képet közelíteni kell egy csempehalmazzal (például, mint egy ősi mozaikban ). Egy csempe tájolású (angle szög), három színkomponens (R, G, B), mérete (w, h) és helyzete (x, y, z). Ha N csempe van, akkor 9 N ismeretlen lebegőpontos számot kell kitalálni. Más szóval, 5000 csempe esetében 45 000 szám található. Egy klasszikus evolúciós algoritmus használatával, ahol az optimalizálási probléma a legjobb egyed, a válasz 45 000 génből állna. Ez a módszer rendkívül költséges lenne a komplexitás és a számítási idő szempontjából. Ugyanez vonatkozik minden klasszikus optimalizálási algoritmusra. A repülési algoritmus használatával minden személy utánoz egy lapkát, és egyénileg értékelhető a helyi alkalmassága alapján, hogy felmérje a lakosság teljesítményéhez való hozzájárulását (a globális alkalmasság). Itt egy egyednek 9 génje van, 9 N helyett , és N egyed van. Ez a következőképpen oldható meg rekonstrukciós problémaként:

${\ displaystyle rekonstrukció = \ operatornév {arg \, min} {\ overset {x <W} {\ underet {y = 0} {\ sum}}} {\ overset {j <H} {\ underet {j = 0 } {\ összeg}}} | input (x, y) -P [F] (x, y) |}$

ahol a bemeneti kép, illetve a vízszintes és függőleges tengely mentén lévő pixelkoordináták, illetve a kép szélessége, illetve magassága a képpontok számában, a légypopuláció , és egy vetítési operátor, amely legyekből készít képet. Ez a vetítési operátor sokféle lehet. Munkájában Z. Ali Aboodd az OpenGL -t használja különböző effektek (pl. Mozaikok vagy spray -festékek ) létrehozásához. A fitneszfunkciók értékelésének felgyorsítása érdekében az OpenCL -t is használják. Az algoritmus véletlenszerűen generált populációval kezdődik (lásd a fenti algoritmus 3. sorát). ezt követően a globális alkalmasság alapján értékelik a számítást (lásd a 10. sort). hibamutató, azt minimalizálni kell. ${\ displaystyle input}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle W}$${\ displaystyle H}$${\ displaystyle F}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle F}$${\ displaystyle F}$${\ displaystyle G_ {fitness} (F) = {\ overset {x <W} {\ underet {y = 0} {\ sum}}} {\ overset {j <H} {\ underet {j = 0} { \ összeg}}} | input (x, y) -P [F] (x, y) |}$${\ displaystyle G_ {fitness}}$

Lásd még

• Matematikai optimalizálás
• Metaheurisztikus
• Keresési algoritmus
• Sztochasztikus optimalizálás
• Evolúciós számítás
• Evolúciós algoritmus
• Genetikai algoritmus
• Mutáció (genetikai algoritmus)
• Crossover (genetikai algoritmus)
• Kiválasztás (genetikai algoritmus)

Hivatkozások