Algorithme de vol - Fly algorithm

Histoire

Le Fly Algorithm est un type de coévolution coopérative basé sur l'approche parisienne. L'algorithme Fly a été développé pour la première fois en 1999 dans le cadre de l'application des algorithmes évolutionnaires à la vision stéréo par ordinateur . Contrairement à l'approche classique de la stéréovision basée sur l'image, qui extrait des primitives d'images puis les apparie afin d'obtenir des informations 3D, l'algorithme Fly est basé sur l'exploration directe de l'espace 3D de la scène. Une mouche est définie comme un point 3-D décrit par ses coordonnées ( x , y , z ). Une fois qu'une population aléatoire de mouches a été créée dans un espace de recherche correspondant au champ de vision des caméras, son évolution (basée sur le paradigme de la stratégie évolutive) a utilisé une fonction de fitness qui évalue la probabilité que la mouche repose sur la surface visible de un objet, en fonction de la cohérence de ses projections d'images. Pour cela, la fonction fitness utilise les niveaux de gris, les couleurs et/ou les textures des projections calculées de la mouche.

Le premier domaine d'application de l'algorithme Fly a été la stéréovision. Alors que les approches classiques de « priorité d'image » utilisent des caractéristiques d'appariement des images stéréo afin de construire un modèle 3-D, l'algorithme Fly explore directement l'espace 3-D et utilise des données d'image pour évaluer la validité des hypothèses 3-D. Une variante appelée "Dynamic Flies" définit la mouche comme un 6-uple ( x , y , z , x' , y' , z' ) impliquant la vitesse de la mouche. Les composantes de vitesse ne sont pas explicitement prises en compte dans le calcul de fitness mais sont utilisées dans la mise à jour des positions des mouches et sont soumises à des opérateurs génétiques similaires (mutation, croisement).

L'application des mouches à l'évitement d'obstacles dans les véhicules exploite le fait que la population de mouches est une représentation temporelle et évolutive quasi-continue de la scène pour générer directement des signaux de contrôle de véhicule à partir des mouches. L'utilisation de l'algorithme Fly n'est pas strictement limitée aux images stéréo, car d'autres capteurs peuvent être ajoutés (par exemple, des capteurs de proximité acoustiques, etc.) en tant que termes supplémentaires pour la fonction de fitness en cours d'optimisation. Les informations d'odométrie peuvent également être utilisées pour accélérer la mise à jour des positions des mouches, et inversement les positions des mouches peuvent être utilisées pour fournir des informations de localisation et de cartographie.

Un autre domaine d'application de l'algorithme Fly est la reconstruction pour la tomographie par émission en médecine nucléaire . L'algorithme Fly a été appliqué avec succès en tomographie par émission monophotonique et en tomographie par émission de positons . Ici, chaque mouche est considérée comme un émetteur de photons et sa fitness est basée sur la conformité de l'éclairage simulé des capteurs avec le motif réel observé sur les capteurs. Dans cette application, la fonction fitness a été redéfinie pour utiliser le nouveau concept d'« évaluation marginale ». Ici, la fitness d'un individu est calculée comme sa contribution (positive ou négative) à la qualité de la population mondiale. Il est basé sur le principe de validation croisée Leave-One-Out . Une fonction de fitness globale évalue la qualité de la population dans son ensemble ; alors seulement la fitness d'un individu (une mouche) est calculée comme la différence entre les valeurs de fitness globales de la population avec et sans la mouche particulière dont la fonction de fitness individuelle doit être évaluée. La condition physique de chaque mouche est considérée comme un « niveau de confiance ». Il est utilisé pendant le processus de voxelisation pour modifier l'empreinte individuelle de la mouche en utilisant une modélisation implicite (telle que les métaballes ). Il produit des résultats lisses qui sont plus précis.

Plus récemment, il a été utilisé dans l'art numérique pour générer des images de type mosaïque ou de la peinture en aérosol. Des exemples d'images peuvent être trouvés sur YouTube

L'évolution parisienne

Ici, la population d'individus est considérée comme une société où les individus collaborent vers un but commun. Ceci est mis en œuvre à l'aide d'un algorithme évolutif qui inclut tous les opérateurs génétiques courants (par exemple, mutation, croisement, sélection). La principale différence réside dans la fonction fitness. Ici, deux niveaux de fonction fitness sont utilisés :

Une fonction d'aptitude locale pour évaluer les performances d'un individu donné (généralement utilisée pendant le processus de sélection).
Une fonction fitness globale pour évaluer les performances de l'ensemble de la population. Maximiser (ou minimiser selon le problème considéré) cette fitness globale est l'objectif de la population.

De plus, un mécanisme de diversité est nécessaire pour éviter que les individus ne se rassemblent dans quelques zones seulement de l'espace de recherche. Une autre différence réside dans l'extraction de la solution du problème une fois la boucle évolutive terminée. Dans les approches évolutives classiques, le meilleur individu correspond à la solution et le reste de la population est écarté. Ici, tous les individus (ou individus d'un sous-groupe de la population) sont rassemblés pour construire la solution du problème. La façon dont les fonctions de fitness sont construites et la façon dont l'extraction de la solution est effectuée dépendent bien sûr du problème.

Voici des exemples d'applications Parisian Evolution :

Désambiguïsation

Approche parisienne vs coévolution coopérative

La coévolution coopérative est une large classe d' algorithmes évolutionnaires où un problème complexe est résolu en le décomposant en sous-composants qui sont résolus indépendamment. L'approche parisienne partage de nombreuses similitudes avec l' algorithme co-évolutif coopératif . L'approche parisienne utilise une seule population alors que plusieurs espèces peuvent être utilisées dans un algorithme coévolutif coopératif . Des moteurs évolutionnaires internes similaires sont considérés dans l' algorithme évolutionnaire classique , l' algorithme coévolutif coopératif et l'évolution parisienne. La différence entre l' algorithme coévolutif coopératif et l'évolution parisienne réside dans la sémantique de la population. L'algorithme co-évolutif coopératif divise un gros problème en sous-problèmes (groupes d'individus) et les résout séparément vers le gros problème. Il n'y a pas d'interaction/reproduction entre les individus des différentes sous-populations, uniquement avec des individus de la même sous-population. Cependant, les algorithmes évolutionnaires parisiens résolvent tout un problème en tant que gros composant. Tous les individus de la population coopèrent pour conduire l'ensemble de la population vers des zones attractives de l'espace de recherche.

Optimisation de l' algorithme de vol par rapport à l' essaim de particules

La coévolution coopérative et l'optimisation des essaims de particules (PSO) partagent de nombreuses similitudes. PSO s'inspire du comportement social des vols d'oiseaux ou des bancs de poissons. Il a été initialement présenté comme un outil d'animation réaliste en infographie. Il utilise des individus complexes qui interagissent les uns avec les autres afin de construire des comportements collectifs visuellement réalistes en ajustant les règles comportementales des individus (qui peuvent utiliser des générateurs aléatoires). Dans l'optimisation mathématique, chaque particule de l'essaim suit en quelque sorte son propre chemin aléatoire biaisé vers la meilleure particule de l'essaim. Dans l'algorithme Fly, les mouches visent à construire des représentations spatiales d'une scène à partir de données de capteurs réelles ; les mouches ne communiquent pas, ne coopèrent pas explicitement et n'utilisent aucun modèle comportemental.

Les deux algorithmes sont des méthodes de recherche qui commencent par un ensemble de solutions aléatoires, qui sont corrigées itérativement vers un optimum global. Cependant, la solution du problème d'optimisation dans l'algorithme Fly est la population (ou un sous-ensemble de la population) : les mouches collaborent implicitement pour construire la solution. Dans PSO, la solution est une seule particule, celle avec la meilleure forme physique. Une autre différence principale entre l'algorithme Fly et avec PSO est que l'algorithme Fly n'est basé sur aucun modèle comportemental mais construit uniquement une représentation géométrique.

Applications de l'algorithme Fly

Vision stéréo par ordinateur
Évitement d'obstacle
Localisation et cartographie simultanées (SLAM)
Reconstruction par tomographie par émission monophotonique (SPECT)
La tomographie par émission de positrons (PET) reconstruction
Art numérique

Exemple : Reconstruction tomographique

Sinogramme de , qui est connu.

{\style d'affichage (O)}

{\style d'affichage f}

Exemple de reconstruction d'un fantôme de hot rod à l'aide de l'algorithme Fly.

La reconstruction tomographique est un problème inverse qui est souvent mal posé en raison de données manquantes et/ou de bruit. La réponse au problème inverse n'est pas unique, et en cas de niveau de bruit extrême, elle peut même ne pas exister. Les données d'entrée d'un algorithme de reconstruction peuvent être données sous forme de transformée de Radon ou de sinogramme des données à reconstruire . est inconnu; est connu. L'acquisition de données en tomographie peut être modélisée comme : ${\style d'affichage \gauche(Y\droite)}$ ${\style d'affichage \gauche(f\droit)}$ ${\style d'affichage f}$ ${\style d'affichage Y}$

$Y=P[f]+\epsilon$

où est la matrice du système ou l'opérateur de projection et correspond à du bruit de Poisson . Dans ce cas la reconstruction correspond à l'inversion de la transformée de Radon : ${\style d'affichage P}$ ${\style d'affichage \epsilon }$

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

Notez que peut prendre en compte le bruit, la géométrie d'acquisition, etc. L'algorithme Fly est un exemple de reconstruction itérative . Les méthodes itératives de reconstruction tomographique sont relativement faciles à modéliser : ${\style d'affichage P^{-1}}$

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

où est une estimation de , qui minimise une métrique d'erreur (ici $ℓ$ $2$ -norm , mais d'autres métriques d'erreur pourraient être utilisées) entre et . A noter qu'un terme de régularisation peut être introduit pour éviter le surajustement et lisser le bruit tout en préservant les contours. Les méthodes itératives peuvent être implémentées comme suit : ${\hat {f}}$ ${\style d'affichage f}$ ${\style d'affichage Y}$ ${\hat {Y}}$

Correction itérative dans la reconstruction tomographique.

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

Le pseudocode ci-dessous est une description étape par étape de l'algorithme Fly pour la reconstruction tomographique . L'algorithme suit le paradigme de l'état stationnaire. A des fins d'illustration, les opérateurs génétiques avancés, tels que la mitose, la double mutation, etc. sont ignorés. Une implémentation JavaScript peut être trouvée sur 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

Exemple : Arts numériques

Recherche évolutive.

Image reconstruite après optimisation en utilisant un ensemble de rayures comme motif pour chaque tuile.

Dans cet exemple, une image d'entrée doit être approximée par un ensemble de tuiles (par exemple comme dans une mosaïque ancienne ). Une tuile a une orientation (angle θ), trois composantes de couleur (R, V, B), une taille (l, h) et une position (x, y, z). S'il y a N tuiles, il y a 9 N nombres à virgule flottante inconnus à deviner. En d'autres termes, pour 5 000 tuiles, il y a 45 000 numéros à trouver. En utilisant un algorithme évolutionnaire classique où la réponse au problème d'optimisation est le meilleur individu, le génome d'un individu serait composé de 45 000 gènes. Cette approche serait extrêmement coûteuse en termes de complexité et de temps de calcul. Il en va de même pour tout algorithme d'optimisation classique. À l'aide de l'algorithme Fly, chaque individu imite une tuile et peut être évalué individuellement en utilisant sa fitness locale pour évaluer sa contribution à la performance de la population (la fitness globale). Ici, un individu a 9 gènes au lieu de 9 N , et il y a N individus. Il peut être résolu comme un problème de reconstruction comme suit :

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

où est l'image d'entrée, et sont respectivement les coordonnées des pixels le long des axes horizontal et vertical, et sont respectivement la largeur et la hauteur de l'image en nombre de pixels, est la population de mouches et est un opérateur de projection qui crée une image à partir de mouches. Cet opérateur de projection peut prendre plusieurs formes. Dans son travail, Z. Ali Aboodd utilise OpenGL pour générer différents effets (par exemple des mosaïques ou de la peinture en aérosol). Pour accélérer l'évaluation des fonctions de fitness, OpenCL est également utilisé. L'algorithme commence par une population générée aléatoirement (voir la ligne 3 de l'algorithme ci-dessus). est ensuite évalué à l'aide de l'aptitude globale à calculer (voir ligne 10). est une métrique d'erreur, elle doit être minimisée. ${\saisie du style d'affichage}$ ${\style d'affichage x}$ ${\style d'affichage y}$ ${\style d'affichage W}$ ${\style d'affichage H}$ ${\style d'affichage F}$ ${\style d'affichage P}$ ${\style d'affichage P}$ ${\style d'affichage F}$ ${\style d'affichage F}$ $G_{fitness}(F)={\overset {x<W}{\underset {y=0}{\sum }}}{\overset {j<H}{\underset {j=0}{ \somme }}}|entrée(x,y)-P[F](x,y)|$ $G_{fitness}$

Languages

In other projects