Wikipedia

Fly algorithm

This is an old revision of this page, as edited by Fpvidal (talk | contribs) at 15:43, 4 November 2016 (→Pseudocode: Add pseudocode and image). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

History

The Fly Algorithm has first been developed in 1999 in the scope of the application of Evolutionary algorithms to computer stereo vision[1][2][3]. Unlike the classical image-based approach to stereovision, which extracts image primitives then matches them in order to obtain 3-D information, the Fly Agorithm is based on the direct exploration of the 3-D space of the scene. A fly is defined as a 3-D point described by its coordinates (x, y, z). Once a random population of flies has been created in a search space corresponding to the field of view of the cameras, its evolution (based on the Evolutionary Strategy paradigm) used a fitness function that evaluates how likely the fly is lying on the visible surface of an object, based on the consistency of its image projections. To this end, the fitness function uses the grey levels, colours and/or textures of the calculated fly's projections.

The first application field of the Fly Algorithm has been stereovision[4][5] and its application to obstacle avoidance in vehicles[6]. A variant called the "Dynamic Flies" defines the fly as a 6-uple (x, y, z, x’, y’, z’) involving the fly's velocity[7][8]. The velocity components are not explicitly taken into account in the fitness calculation but are used in the flies' positions updating and are subject to similar genetic operators (mutation, crossover).

Another application field of the Fly Algorithm is reconstruction for emission Tomography in nuclear medicine. The Fly algorithm has been successfully applied in single-photon emission computed tomography[9] and positron emission tomography[10] [11]. Here, each fly is considered a photon emitter and its fitness is based on the conformity of the simulated illumination of the sensors with the actual pattern observed on the sensors. Within this application, the fitness function has been re-defined as the (positive or negative_ contribution of the fly considered, to the global conformity of the simulated illumination with the actual one ("marginal fitness" or "marginal evaluation")[12][13].

.

Methodology

Fitness functions

Initialisation

Selection

Genetic operators

Stopping criteria

Extraction of the solution

Example: Tomography reconstruction

Pseudocode

The pseudocode below is a step-by-step description of the Fly algorithm for tomographic reconstruction. The Fly algorithm is an example of iterative reconstruction. Iterative methods in tomographic reconstruction are relatively easy to model

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

The algorithm presented here follows the steady-state paradigm. For illustrative purposes, we keep it simple and ignore more advanced genetic operators, such as mitosis, dual mutation, etc.[14]. A JavaScript implementation can be found on Fly4PET. 

algorithm fly-algorithm is
    input: Number of flies N, 
           input projection data preference
    
    output: VF the 3-D volume corresponding to the voxelisation of the fly population F so that the difference between pestimated (the projections estimated from F) 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) projection in pestimated
 8.   
 9.   // Compute the population's perfomance (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,
23.       then go to Step 26.   // fkill is a good fly
24.       else go to Step 28.   // fkill is a bad fly
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,
47.       else go to Step 34.   // fkill is a bad fly
48.       then go to Step 53.   // fkill is a good fly
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 6.
62.    
63.   // Extract solution
64.   VF ← voxelisation of F
65.    
66.   return VF
   
   END

Flowchart

References

  1. ^ Louchet, Jean (Feb 2000). L’algorithme des mouches : une stratégie d’évolution individuelle appliquée en stéréovision. Reconnaissance des Formes et Intelligence Artificielle (RFIA2000). {{cite conference}}: Cite has empty unknown parameter: |1= (help)
  2. ^ Boumaza, Amine; Louchet, Jean (Apr 2003). "Mobile robot sensor fusion using flies". Lecture Notes on Computer Science. European Conference on Genetic Programming (EuroGP 2003). Vol. 2611. Essex, UK: Springer. pp. 357–367. doi:10.1007/3-540-36605-9_33. ISBN 978-3-540-00976-4. {{cite conference}}: Cite has empty unknown parameter: |1= (help)
  3. ^ Collet, Pierre; Louchet,, Jean (Oct 2009). "Artificial evolution and the Parisian approach: applications in the processing of signals and images". In Siarry, Patrick (ed.). Optimization in Signal and Image Processing. 9781848210448. ISBN 9781848210448.{{cite book}}: CS1 maint: extra punctuation (link)
  4. ^ Louchet, Jean (Sep 2000). Stereo analysis using individual evolution strategy. Proceedings of 15th International Conference on Pattern Recognition, 2000 (ICPR’00). Barcelona, Spain: IEEE. pp. 908–911. doi:10.1109/ICPR.2000.905580. ISBN 0-7695-0750-6. {{cite conference}}: Cite has empty unknown parameter: |1= (help)
  5. ^ Louchet, Jean (Jun 2001). "Using an Individual Evolution Strategy for Stereovision". Genetic Programming and Evolvable Machines. 2 (2). Kluwer Academic Publishers: 101–109. doi:10.1023/A:1011544128842.
  6. ^ Louchet,, Jean; Guyon, Maud; Lesot, Marie-Jeanne; Boumaza, Amine (Mar 2002). "L'algorithme des mouches dynamiques: guider un robot par évolution artificielle en temps réel". In Lattaud, Claude (ed.). Apprentissage Automatique et Evolution Artificielle (PDF) (in French). Hermes Sciences Publications. ISBN 274620360X.{{cite book}}: CS1 maint: extra punctuation (link)
  7. ^ Boumaza, Amine; Louchet, Jean (Apr 2001). "Dynamic Flies: Using Real-time evolution in Robotics". Lecture Notes on Computer Science. Artificial Evolution in Image Analysis and Signal Processing (EVOIASP2001). Vol. 2037. Como, Italy: Springer. pp. 288–297. doi:10.1007/3-540-45365-2_30. ISBN 978-3-540-41920-4. {{cite conference}}: Cite has empty unknown parameter: |1= (help)
  8. ^ Louchet,, Jean; Guyon, Maud; Lesot, Marie-Jeanne; Boumaza, Amine (Jan 2002). "Dynamic Flies: a new pattern recognition tool applied to stereo sequence processing" (PDF). Pattern Recognition Letters. 23 (1–3). Elsevier Science B.V.: 335–345. doi:10.1016/S0167-8655(01)00129-5.{{cite journal}}: CS1 maint: extra punctuation (link)
  9. ^ Bousquet, Aurélie; Louchet, Jean-Marie; Rocchisani, Jean (Oct 2007). "Fully Three-Dimensional Tomographic Evolutionary Reconstruction in Nuclear Medicine" (PDF). Lecture Notes in Computer Science. Proceedings of the 8th international conference on Artificial Evolution (EA’07). Vol. 4926. Tours, France: Springer, Heidelberg. pp. 231–242. doi:10.1007/978-3-540-79305-2_20. ISBN 978-3-540-79304-5. {{cite conference}}: Cite has empty unknown parameter: |1= (help)
  10. ^ Vidal, Franck P.; Lazaro-Ponthus, Delphine; Legoupil, Samuel; Louchet, Jean; Lutton, Évelyne; Rocchisani, Jean-Marie (Oct 2009). "Artificial evolution for 3D PET reconstruction" (PDF). Lecture Notes in Computer Science. Proceedings of the 9th international conference on Artificial Evolution (EA’09). Vol. 5975. Strasbourg, France: Springer, Heidelberg. pp. 37–48. doi:10.1007/978-3-642-14156-0_4. ISBN 978-3-642-14155-3. {{cite conference}}: Cite has empty unknown parameter: |1= (help)
  11. ^ Vidal, Franck P.; Louchet, Jean; Lutton, Évelyne; Rocchisani, Jean-Marie (Oct–Nov 2009). "PET reconstruction using a cooperative coevolution strategy in LOR space". IEEE Nuclear Science Symposium Conference Record (NSS/MIC), 2009. Medical Imaging Conference (MIC). Orlando, Florida: IEEE. pp. 3363–3366. doi:10.1109/NSSMIC.2009.5401758. {{cite conference}}: Cite has empty unknown parameter: |1= (help)CS1 maint: date format (link)
  12. ^ Vidal, Franck P.; Louchet, Jean; Rocchisani, Jean-Marie; Lutton, Évelyne (Apr 2010). "New genetic operators in the Fly algorithm: application to medical PET image reconstruction" (PDF). Lecture Notes in Computer Science. European Workshop on Evolutionary Computation in Image Analysis and Signal Processing (EvoIASP’10). Vol. 6024. Istanbul, Turkey: Springer, Heidelberg. pp. 292–301. doi:10.1007/978-3-642-12239-2_30. ISBN 978-3-642-12238-5. {{cite conference}}: Cite has empty unknown parameter: |1= (help)
  13. ^ Vidal, Franck P.; Lutton, Évelyne; Louchet, Jean; Rocchisani, Jean-Marie (Sep 2010). "Threshold selection, mitosis and dual mutation in cooperative co-evolution: Application to medical 3D tomography" (PDF). Lecture Notes in Computer Science. Parallel Problem Solving from Nature - PPSN XI. Vol. 6238. Kraków, Poland: Springer Berlin / Heidelberg. pp. 414–423. doi:10.1007/978-3-642-15844-5_42. ISBN 978-3-642-15843-8. {{cite conference}}: Cite has empty unknown parameter: |1= (help)
  14. ^ Vidal, Franck P.; Lutton, Évelyne; Louchet, Jean; Rocchisani, Jean-Marie (Sep 2010). "Threshold selection, mitosis and dual mutation in cooperative co-evolution: Application to medical 3D tomography" (PDF). Lecture Notes in Computer Science. Parallel Problem Solving from Nature - PPSN XI. Vol. 6238. Kraków, Poland: Springer Berlin / Heidelberg. pp. 414–423. doi:10.1007/978-3-642-15844-5_42. ISBN 978-3-642-15843-8. {{cite conference}}: Cite has empty unknown parameter: |1= (help)
Retrieved from "https://en.wikipedia.org/w/index.php?title=Fly_algorithm&oldid=747820989"