Fly algorithm

The Fly Algorithm has first been developed in 1999 in the scope of the application of Evolutionary algorithms to computer stereo vision. 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 [bib] and its application to obstacle avoidance in vehicles [bib]. A variant called the "Dynamic Flies" defines the fly as a 6-uple (x,y,z,x', y', z') involving the fly's velocity. 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 Emission Tomography [bib]. 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 woth the actual one ("marginal fitness" or "marginal evaluation") [ref].

Methodology

Fitness functions

Initialisation

Selection

Genetic operators

Stopping criteria

Extraction of the solution

Example: Tomography reconstruction

Pseudocode

algorithm fly-algorithm is
    input: Number of flies N, 
           input projection data preference
    
    output: 3-D volume VF such that the difference between pestimated estimated from fly population F and preference is minimal 
    
    START
    
    // Set the position of the N flies, i.e. create initial guess
    for each fly i in fly population F do
        F(i)x ← random(0, 1)
        F(i)y ← random(0, 1)
        F(i)z ← random(0, 1)
        Add F(i) projection in pestimated
    
    Gfitness(F) ← Compute the population's perfomance (i.e. the global fitness)
    
    fkill</sbu> ← Select a random fly of F
    
    Remove the fkill's contribution from pestimated
    
    Gfitness(F-{'fkill}) ← Compute the population's performance without fkill
    
    Compare the performances, i.e. compute the fly's local fitness
    
    If the local fitness is equal to or greater than the selection threshold,
        then go to Step 10,
        else go to Step 11
    
    Restore the fly's contribution, then go to Step 5
    
    Select a genetic operator
    
    If the genetic operator is mutation,
        then go to Step 13,
        else go to Step 19
    
    Select a random fly (fly_to_reproduce)
    
    Remove the fly's contribution
    
    Compute the population's performance without the selected fly
    
    Compare the performances, i.e. compute the fly's local fitness
    
    Restore the fly's contribution'
    
    If the local fitness is smaller than the selection threshold,
        then go to Step 13,
        else go to Step 20
    
    Replace fly_to_kill by a new fly with a random position, go to Step 22
    
    Replace fly_to_kill by a new fly based on fly_to_reproduce
    
    Add the fly's contribution to the population
    
    If stop the reconstruction,
        then go to Step 23,
        else go to Step 4
    
    VF ← Extract solution (voxelisation of F)
    
    return VF
   
   END

Flowchart

Reference test

Original work.^[1]

Reconstruction in SPECT in nuclear medicine^[2]

In Positron emission tomography^{[3] [4] [5] [6] [7]}

References

1. Louchet, Jean (Sep 2000). Stereo analysis using individual evolution strategy. Proceedings of 15th International Conference on Pattern Recognition, 2000 (ICPR’00). IEEE. pp. 908–911. doi:10.1109/ICPR.2000.905580. ISBN 0-7695-0750-6. {{cite conference}}: Cite has empty unknown parameter: |1= (help)
2. 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)
3. 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)
4. 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)
5. 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)
6. Vidal, Franck P.; Louchet, Jean; Rocchisani, Jean-Marie; Lutton, Évelyne (2010). "Flies for PET: An artificial evolution strategy for image reconstruction in nuclear medicine" (PDF). Medical Physics. 37 (6). American Association of Physicists in Medicine: 3139. doi:10.1118/1.3468200. {{cite journal}}: Cite has empty unknown parameter: |1= (help)
7. 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)