Fly algorithm: Difference between revisions

Revision as of 03:55, 4 June 2024

Latest revision as of 08:42, 23 June 2025

(One intermediate revision by one other user not shown)

Line 1:

{{COI|date=July 2018}}

{{intromissing|date=May 2024}}

{{Evolutionary algorithms}}

The '''Fly Algorithm''' is a computational method within the field of [[evolutionary algorithms]], designed for direct exploration of [[three-dimensional space|3D spaces]] in applications such as [[computer stereo vision]], [[robotics]], and [[medical imaging]]. Unlike traditional image-based [[stereopsis|stereovision]], which relies on matching features to construct 3D information, the Fly Algorithm operates by generating a 3D representation directly from random points, termed "flies." Each fly is a coordinate in 3D space, evaluated for its accuracy by comparing its projections in a scene. By iteratively refining the positions of flies based on fitness criteria, the algorithm can construct an optimized spatial representation. The Fly Algorithm has expanded into various fields, including applications in digital art, where it is used to generate complex visual patterns.

== History ==

The Fly Algorithm is a type of [[cooperative coevolution]] based on the Parisian approach.<ref name=Collet2009>{{cite book |title=Optimization in Signal and Image Processing|chapter=Artificial evolution and the Parisian approach: applications in the processing of signals and images|last2=Louchet|first2=Jean|last1=Collet|first1=Pierre|publisher=Wiley-ISTE|date=Oct 2009|isbn=9781848210448|editor1-last=Siarry|editor1-first=Patrick}}</ref> The Fly Algorithm has first been developed in 1999 in the scope of the application of [[Evolutionary algorithms]] to [[computer stereo vision]].<ref name=LouchetRFIA2000>{{cite conference |title=L'algorithme des mouches : une stratégie d'évolution individuelle appliquée en stéréovision|last1=Louchet|first1=Jean|conference=Reconnaissance des Formes et Intelligence Artificielle (RFIA2000)|date=Feb 2000}}</ref><ref name=Louchet2000ICPR>{{cite conference |title=Stereo analysis using individual evolution strategy|last1=Louchet|first1=Jean|publisher=IEEE|conference=Proceedings of 15th International Conference on Pattern Recognition, 2000 (ICPR’00)|pages=908–911|date=Sep 2000|doi=10.1109/ICPR.2000.905580|isbn=0-7695-0750-6|___location=Barcelona, Spain}}</ref> Unlike the classical image-based approach to stereovision, which extracts image primitives then matches them in order to obtain 3-D information, the Fly AgorithmAlgorithm 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.<ref name=LouchetRFIA2000 /><ref name=Louchet2000ICPR /><ref name=Louchet2001>{{cite journal |title=Using an Individual Evolution Strategy for Stereovision|last1=Louchet|first1=Jean|pages=101–109|date=Jun 2001|doi=10.1023/A:1011544128842|volume=2|issue=2|journal=Genetic Programming and Evolvable Machines|s2cid=8953837}}</ref><ref name=Boumaza2003>{{cite conference |title=Mobile robot sensor fusion using flies|last1=Boumaza|first1=Amine|last2=Louchet|first2=Jean|publisher=Springer|conference=European Conference on Genetic Programming (EuroGP 2003)|pages=357–367|date=Apr 2003|doi=10.1007/3-540-36605-9_33|isbn=978-3-540-00976-4|___location=Essex, UK|volume=2611|book-title=Lecture Notes on Computer Science}}</ref> While classical `image priority' approaches use matching features from the stereo images in order to build a 3-D model, the Fly Algorithm directly explores the 3-D space and uses image data to evaluate the validity of 3-D hypotheses. A variant called the "Dynamic Flies" defines the fly as a 6-uple (''x'', ''y'', ''z'', ''x’'', ''y’'', ''z’'') involving the fly's velocity.<ref name=Louchet2002>{{cite book |title=Apprentissage Automatique et Evolution Artificielle|chapter=L’algorithme des mouches dynamiques: guider un robot par évolution artificielle en temps réel|last1=Louchet|first1=Jean|last2=Guyon|first2=Maud|last3=Lesot|first3=Marie-Jeanne|last4=Boumaza|first4=Amine|publisher=Hermes Sciences Publications|date=Mar 2002|isbn=978-2746203600|language=fr|chapter-url=http://jean.louchet.free.fr/publis/2001ECA.pdf|editor1-last=Lattaud|editor1-first=Claude}}</ref><ref name=Louchet2002PatterRec>{{cite journal |title=Dynamic Flies: a new pattern recognition tool applied to stereo sequence processing|last1=Louchet|first1=Jean|last2=Guyon|first2=Maud|last3=Lesot|first3=Marie-Jeanne|last4=Boumaza|first4=Amine|pages=335–345|date=Jan 2002|doi=10.1016/S0167-8655(01)00129-5|volume=23|issue=1–3|journal=Pattern Recognition Letters|bibcode=2002PaReL..23..335L |url=http://jean.louchet.free.fr/publis/2001PRL.pdf}}</ref> 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).