Algorytm lotu - Fly algorithm

Historia

Algorytm Fly to rodzaj koewolucji opartej na paryskim podejściu. Algorytm Fly został opracowany po raz pierwszy w 1999 roku w zakresie zastosowania algorytmów ewolucyjnych do komputerowego widzenia stereo . W przeciwieństwie do klasycznego podejścia do stereowizji opartego na obrazie, które wyodrębnia prymitywne obrazy, a następnie dopasowuje je w celu uzyskania informacji 3D, Agorithm Fly opiera się na bezpośredniej eksploracji przestrzeni 3D sceny. Mucha jest zdefiniowana jako trójwymiarowy punkt opisany przez jego współrzędne ( x , y , z ). Po utworzeniu losowej populacji much w przestrzeni wyszukiwania odpowiadającej polu widzenia kamer, jej ewolucja (w oparciu o paradygmat Strategii Ewolucyjnej) wykorzystywała funkcję dopasowania, która ocenia prawdopodobieństwo, że mucha leży na widocznej powierzchni obiekt, w oparciu o spójność jego projekcji obrazu. W tym celu funkcja fitness wykorzystuje poziomy szarości, kolory i/lub tekstury obliczonych rzutów muchy.

Pierwszym obszarem zastosowania algorytmu Fly była stereowizja. Podczas gdy klasyczne podejścia oparte na „priorytecie obrazu” wykorzystują cechy dopasowania ze stereoobrazów w celu zbudowania modelu trójwymiarowego, algorytm Fly bezpośrednio bada przestrzeń trójwymiarową i wykorzystuje dane obrazu do oceny słuszności hipotez trójwymiarowych. Wariant zwany „Dynamic Muchy” definiuje muchę jako 6-krotność ( x , y , z , x' , y' , z' ) obejmującą prędkość muchy. Komponenty prędkości nie są wyraźnie brane pod uwagę w obliczeniach sprawności, ale są wykorzystywane do aktualizacji pozycji much i podlegają podobnym operatorom genetycznym (mutacja, krzyżowanie).

Zastosowanie much do omijania przeszkód w pojazdach wykorzystuje fakt, że populacja much jest zmienną w czasie, quasi-ciągle ewoluującą reprezentacją sceny, aby bezpośrednio generować sygnały sterujące pojazdem z much. Użycie algorytmu Fly nie jest ściśle ograniczone do obrazów stereo, ponieważ można dodać inne czujniki (np. akustyczne czujniki zbliżeniowe itp.) jako dodatkowe terminy do optymalizowanej funkcji fitness. Informacje z odometrii mogą być również wykorzystywane do przyspieszenia aktualizacji pozycji much i odwrotnie, pozycje much mogą być wykorzystywane do dostarczania informacji o lokalizacji i mapowaniu.

Innym obszarem zastosowania algorytmu muchy jest rekonstrukcja tomografii emisyjnej w medycynie nuklearnej . Algorytm Fly został z powodzeniem zastosowany w emisyjnej tomografii komputerowej pojedynczych fotonów i pozytonowej tomografii emisyjnej . Tutaj każda mucha jest uważana za emiter fotonów, a jej sprawność opiera się na zgodności symulowanego oświetlenia czujników z rzeczywistym wzorcem obserwowanym na czujnikach. W tej aplikacji funkcja fitness została przedefiniowana w celu wykorzystania nowej koncepcji „oceny marginalnej”. Tutaj przydatność jednej osoby jest obliczana jako jej (pozytywny lub negatywny) wkład w jakość globalnej populacji. Opiera się na zasadzie walidacji krzyżowej typu „leave-one-out ”. Globalna funkcja fitness ocenia jakość populacji jako całości; dopiero wtedy przydatność osobnika (muchy) jest obliczana jako różnica między ogólnymi wartościami przystosowania populacji zi bez danej muchy, której indywidualna funkcja sprawności musi być oceniona. Przydatność każdej muchy jest uważana za „poziom pewności”. Jest używany podczas procesu wokselizacji w celu dostosowania indywidualnego śladu muchy za pomocą niejawnego modelowania (takiego jak metaball ). Daje gładkie wyniki, które są dokładniejsze.

Ostatnio był używany w sztuce cyfrowej do generowania obrazów przypominających mozaikę lub farby w sprayu. Przykłady obrazów można znaleźć na YouTube

Ewolucja paryska

Tutaj populacja jednostek jest uważana za społeczeństwo, w którym jednostki współpracują w celu osiągnięcia wspólnego celu. Jest to realizowane za pomocą algorytmu ewolucyjnego, który obejmuje wszystkie typowe operatory genetyczne (np. mutacje, krzyżowanie, selekcja). Główna różnica polega na funkcji fitness. Tutaj używane są dwa poziomy funkcji fitness:

Lokalna funkcja sprawności służąca do oceny wyników danej osoby (zwykle stosowana podczas procesu selekcji).
Globalna funkcja sprawności służąca do oceny wyników całej populacji. Maksymalizowanie (lub minimalizowanie w zależności od rozważanego problemu) tej globalnej sprawności jest celem populacji.

Ponadto wymagany jest mechanizm różnorodności, aby uniknąć gromadzenia się osobników tylko w kilku obszarach przestrzeni poszukiwań. Kolejna różnica polega na wyodrębnianiu rozwiązania problemu po zakończeniu pętli ewolucyjnej. W klasycznych podejściach ewolucyjnych najlepszy osobnik odpowiada rozwiązaniu, a reszta populacji jest odrzucana. Tutaj wszystkie osoby (lub osoby z podgrupy populacji) są porównywane w celu zbudowania rozwiązania problemu. Sposób, w jaki konstruowane są funkcje sprawności oraz sposób, w jaki przeprowadza się ekstrakcję rozwiązania, są oczywiście zależne od problemu.

Przykłady aplikacji Parisian Evolution obejmują:

Ujednoznacznienie

Podejście paryskie a koewolucja spółdzielcza

Koewolucja kooperacyjna to szeroka klasa algorytmów ewolucyjnych, w których złożony problem jest rozwiązywany przez rozłożenie go na podkomponenty, które są rozwiązywane niezależnie. Podejście paryskie dzieli wiele podobieństw z algorytmem koewolucyjnej koewolucji . Podejście paryskie wykorzystuje pojedynczą populację, podczas gdy wielogatunkowe może być stosowane w kooperatywnym algorytmie koewolucyjnym . Podobne wewnętrzne silniki ewolucyjne są rozważane w klasycznym algorytmie ewolucyjnym , kooperacyjnym algorytmie koewolucyjnym i ewolucji paryskiej. Różnica między koewolucyjnym algorytmem koewolucji a ewolucją paryską tkwi w semantyce populacji. Algorytm koewolucji współpracy dzieli duży problem na podproblemy (grupy jednostek) i rozwiązuje je oddzielnie w kierunku dużego problemu. Nie ma interakcji/hodowlanych między osobnikami z różnych subpopulacji, tylko z osobnikami z tej samej subpopulacji. Jednak paryskie algorytmy ewolucyjne rozwiązują cały problem jako duży komponent. Wszystkie jednostki populacji współpracują ze sobą, aby skierować całą populację w kierunku atrakcyjnych obszarów przestrzeni poszukiwań.

Mucha algorytm vs cząstek optymalizacji roju

Koewolucja koewolucji i optymalizacja roju cząstek (PSO) mają wiele podobieństw. PSO jest inspirowane zachowaniami społecznymi związanymi ze stadami ptaków lub hodowlą ryb. Został on początkowo wprowadzony jako narzędzie do realistycznej animacji w grafice komputerowej. Wykorzystuje złożone jednostki, które oddziałują ze sobą w celu budowania wizualnie realistycznych zachowań zbiorowych poprzez dostosowywanie reguł behawioralnych jednostek (które mogą wykorzystywać generatory losowe). W optymalizacji matematycznej każda cząstka roju w jakiś sposób podąża własną losową ścieżką nastawioną na najlepszą cząstkę roju. W algorytmie muchy muchy mają na celu budowanie przestrzennych reprezentacji sceny na podstawie rzeczywistych danych z czujników; muchy nie komunikują się, nie współpracują wprost i nie stosują żadnego modelu behawioralnego.

Oba algorytmy są metodami wyszukiwania, które zaczynają się od zestawu losowych rozwiązań, które są iteracyjnie korygowane w kierunku globalnego optimum. Jednak rozwiązaniem problemu optymalizacji w algorytmie muchy jest populacja (lub podzbiór populacji): muchy domyślnie współpracują, aby zbudować rozwiązanie. W PSO rozwiązaniem jest pojedyncza cząstka, ta o najlepszej sprawności. Inną główną różnicą między algorytmem Fly a PSO jest to, że algorytm Fly nie opiera się na żadnym modelu behawioralnym, a jedynie buduje reprezentację geometryczną.

Zastosowania algorytmu Fly

Komputerowe widzenie stereo
Unikanie przeszkód
Jednoczesna lokalizacja i mapowanie (SLAM)
Rekonstrukcja tomografii komputerowej emisyjnej pojedynczego fotonu (SPECT)
Rekonstrukcja pozytonowej tomografii emisyjnej (PET)
Sztuka cyfrowa

Przykład: rekonstrukcja tomografii

Sinogram z , co jest znane.

{\ Displaystyle (Y)}

f

Przykład rekonstrukcji fantomu hot rod za pomocą algorytmu muchy.

Rekonstrukcja tomografii jest problemem odwrotnym , często źle stawianym z powodu brakujących danych i/lub szumu. Odpowiedź na odwrotny problem nie jest unikalna, aw przypadku ekstremalnego poziomu hałasu może nawet nie istnieć. Dane wejściowe algorytmu rekonstrukcji mogą być podane jako transformata Radona lub sinogram danych do rekonstrukcji . jest nieznany; jest znany. Pozyskiwanie danych w tomografii można modelować jako: ${\ Displaystyle \ lewo (Y \ prawo)}$ ${\ Displaystyle \ lewo (f \ prawo)}$ $f$ ${\ Displaystyle Y}$

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

gdzie jest macierzą systemu lub operatorem projekcji i odpowiada pewnemu szumowi Poissona . W tym przypadku rekonstrukcja odpowiada odwróceniu transformaty Radona : $P$ $\epsilon$

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

Zauważ, że może to uwzględniać szum, geometrię akwizycji itp. Algorytm muchy jest przykładem rekonstrukcji iteracyjnej . Metody iteracyjne w rekonstrukcji tomograficznej są stosunkowo łatwe do modelowania: ${\ Displaystyle P ^ {-1}}$

${\ Displaystyle {\ kapelusz {f}} = \ operatorname {arg \ min} | | Y- {\ kapelusz {Y}} | | _ {2} ^ {2}}$

gdzie jest oszacowaniem , które minimalizuje metryki błędu (tutaj $ℓ$ $2$ -norm , ale można użyć innych metryk błędu) pomiędzy i . Należy zauważyć, że można wprowadzić termin regularyzacyjny, aby zapobiec nadmiernemu dopasowaniu i wygładzić hałas przy jednoczesnym zachowaniu krawędzi. Metody iteracyjne można zaimplementować w następujący sposób: ${\kapelusz {f}}$ $f$ ${\ Displaystyle Y}$ ${\ Displaystyle {\ kapelusz {Y}}}$

Korekcja iteracyjna w rekonstrukcji tomograficznej.

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

Poniższy pseudokod to opis krok po kroku algorytmu muchy do rekonstrukcji tomograficznej . Algorytm jest zgodny z paradygmatem stanu ustalonego. W celach ilustracyjnych ignorowane są zaawansowane operatory genetyczne, takie jak mitoza, podwójna mutacja itp. JavaScript realizacja można znaleźć na Fly4PET .

algorithm fly-algorithm is
    input: number of flies (N), 
           input projection data (p_reference)
    
    output: the fly population (F), 
            the projections estimated from F (p_estimated)
            the 3-D volume corresponding to the voxelisation of F (V_F)
    
    postcondition: the difference between p_estimated and p_reference 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 p_estimated
 8.   
 9.   // Compute the population's performance (i.e. the global fitness)
10.   G_fitness(F) ← Error_metrics(p_reference, p_estimated)
11.    
12.   f_kill ← Select a random fly of F
13.    
14.   Remove f_kill's contribution from p_estimated
15.    
16.   // Compute the population's performance without f_kill
17.   G_fitness(F-{f_kill}) ← Error_metrics(p_reference, p_estimated)
18.    
19.   // Compare the performances, i.e. compute the fly's local fitness
20.   L_fitness(f_kill) ← G_fitness(F-{f_kill}) - G_fitness(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.   // f_kill is a good fly (the population's performance is better when f_kill is included): we should not kill it
24.       else go to Step 28.   // f_kill is a bad fly (the population's performance is worse when f_kill 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.   f_reproduce ← Select a random fly of F
35.    
14.   Remove f_reproduce's contribution from p_estimated
37.    
38.   // Compute the population's performance without f_reproduce
39.   G_fitness(F-{f_reproduce}) ← Error_metrics(p_reference, p_estimated)
40.    
41.   // Compare the performances, i.e. compute the fly's local fitness
42.   L_fitness(f_reproduce) ← G_fitness(F-{f_reproduce}) - G_fitness(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.   // f_kill is a bad fly: we should not allow it to reproduce
48.       then go to Step 53.   // f_kill is a good fly: we can allow it to reproduce
49.    
50.   // New blood / Immigration
51.   Replace f_kill by a new fly with a random position, go to Step 57.
52.    
53.   // Mutation
54.   Copy f_reproduce into f_kill
55.   Slightly and randomly alter f_kill'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.   V_F ← voxelisation of F
65.    
66.   return V_F
   
   END

Przykład: sztuka cyfrowa

Poszukiwanie ewolucyjne.

Obraz zrekonstruowany po optymalizacji przy użyciu zestawu pasków jako wzoru dla każdej płytki.

W tym przykładzie obraz wejściowy ma być aproksymowany zestawem kafelków (np. jak w antycznej mozaice ). Płytka ma orientację (kąt θ), trzy składowe koloru (R, G, B), rozmiar (w, h) i położenie (x, y, z). Jeśli jest N płytek, do odgadnięcia jest 9 N nieznanych liczb zmiennoprzecinkowych. Innymi słowy, na 5000 płytek do znalezienia jest 45 000 liczb. Stosując klasyczny algorytm ewolucyjny, w którym odpowiedzią na problem optymalizacji jest najlepszy osobnik, genom osobnika składałby się z 45 000 genów. Takie podejście byłoby niezwykle kosztowne pod względem złożoności i czasu obliczeniowego. To samo dotyczy każdego klasycznego algorytmu optymalizacji. Korzystając z algorytmu Fly, każda osoba naśladuje kafelek i może być indywidualnie oceniana przy użyciu lokalnej sprawności, aby ocenić jej wkład w wydajność populacji (sprawność globalna). Tutaj osobnik ma 9 genów zamiast 9 N , i jest N osobników. Można go rozwiązać jako problem rekonstrukcji w następujący sposób:

${\ Displaystyle rekonstrukcja = \ nazwa operatora {arg \, min} {\ przesunięte {x<W} {\ przesunięte {y = 0} {\ suma}}}}} {\ przesunięte {j<H} {\ przesunięte {j = 0 }{\suma }}}|wejście(x,y)-P[F](x,y)|}$

gdzie jest obrazem wejściowym i są współrzędnymi pikseli odpowiednio wzdłuż osi poziomej i pionowej oraz są odpowiednio szerokością i wysokością obrazu w liczbie pikseli, jest populacją much i jest operatorem projekcji, który tworzy obraz z much. Ten operator projekcji może przybierać różne formy. W swojej pracy Z. Ali Aboodd wykorzystuje OpenGL do generowania różnych efektów (np. mozaiki czy farby w sprayu). Aby przyspieszyć ocenę funkcji fitness, używany jest również OpenCL . Algorytm rozpoczyna się od populacji, która jest generowana losowo (patrz wiersz 3 w powyższym algorytmie). jest następnie oceniany przy użyciu globalnej zdolności do obliczeń (patrz wiersz 10). jest wskaźnikiem błędu, należy go zminimalizować. $dane wejściowe$ $x$ $y$ ${\ Displaystyle W}$ ${\ Displaystyle H}$ ${\ Displaystyle F}$ $P$ $P$ ${\ Displaystyle F}$ ${\ Displaystyle F}$ ${\ Displaystyle G_ {fitness} (F) = {\ przesunięte {x < W} {\ przesunięte {y = 0} {\ suma}}} {\ przesunięte {j < H} {\ przesunięte {j = 0} \sum }}}|wejście(x,y)-P[F](x,y)|}$ $G_{fitness}$

Languages

In other projects