Content deleted Content added
→Parisian Evolution: Add final details |
m →History: Typo fixing, replaced: Agorithm → Algorithm |
||
| (52 intermediate revisions by 24 users not shown) | |||
Line 1:
{{COI|date=July 2018}}
{{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
The first application field of the Fly Algorithm has been stereovision
The application of Flies to obstacle avoidance in vehicles<ref name=Bomaza2001EvoIASP>{{cite conference |title=Dynamic Flies: Using Real-time evolution in Robotics|last1=Boumaza|first1=Amine|last2=Louchet|first2=Jean|publisher=Springer|conference=Artificial Evolution in Image Analysis and Signal Processing (EVOIASP2001)|pages=288–297|date=Apr 2001|doi=10.1007/3-540-45365-2_30|isbn=978-3-540-41920-4|___location=Como, Italy|volume=2037|book-title=Lecture Notes on Computer Science
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]]<ref name=Bousquet2007EA>{{cite conference |title=Fully Three-Dimensional Tomographic Evolutionary Reconstruction in Nuclear Medicine|last1=Bousquet|first1=Aurélie|last2=Louchet|first2=Jean-Marie|last3=Rocchisani|first3=Jean|publisher=Springer, Heidelberg|conference=Proceedings of the 8th international conference on Artificial Evolution (EA’07)|pages=231–242|date=Oct 2007|doi=10.1007/978-3-540-79305-2_20|isbn=978-3-540-79304-5|___location=Tours, France|volume=4926|book-title=Lecture Notes in Computer Science|url=http://jean.louchet.free.fr/publis/EA07Bousquet.pdf
.<ref name=Vidal2009MIC>{{cite conference |title=PET reconstruction using a cooperative coevolution strategy in LOR space|last1=Vidal|first1=Franck P.|last2=Louchet|first2=Jean|last3=Lutton|first3=Évelyne|last4=Rocchisani|first4=Jean-Marie|publisher=IEEE|conference=Medical Imaging Conference (MIC)|pages=3363–3366|date=
More recently it has been used in digital art to generate mosaic-like images or spray paint.<ref name=Abbood2017EvoIASP>{{cite conference |title=Evolutionary Art Using the Fly Algorithm|last1=Ali Abbood|first1=Zainab|last2=Amlal|first2=Othman|last3=Vidal|first3=Franck P.|publisher=Springer|conference=Applications of Evolutionary Computation (EvoApplications 2017)|pages=
<!--ref>{{cite conference }}</ref-->
<!--
<ref name=Vidal2010>{{cite journal |title=Flies for PET: An artificial evolution strategy for image reconstruction in nuclear medicine|last1=Vidal|first1=Franck P.|last4=Lutton|first4=Évelyne|last2=Louchet|first2=Jean|last3=Rocchisani|first3=Jean-Marie|publisher=American Association of Physicists in Medicine|page=3139|date=2010|doi=10.1118/1.3468200
-->
== Parisian
Here, the population of individuals is considered as a ''society'' where the individuals collaborate toward a common goal.
Line 27 ⟶ 32:
Another difference is in the extraction of the problem solution once the evolutionary loop terminates. In classical evolutionary approaches, the best individual corresponds to the solution and the rest of the population is discarded.
Here, all the individuals (or individuals of a sub-group of the population) are collated to build the problem solution.
The way the fitness functions are constructed and the way the solution extraction is made are of course problem-
Examples of Parisian Evolution applications include:
* [http://evelyne.lutton.free.fr/FlyAlgo.html The Fly algorithm].
* [http://evelyne.lutton.free.fr/TextRetrieval.html Text-mining].
* [http://evelyne.lutton.free.fr/HandGesture.html Hand gesture recognition].
Line 40 ⟶ 45:
=== Parisian approach ''vs'' [[cooperative coevolution]] ===
[[Cooperative coevolution]] is a broad class of [[evolutionary algorithm]]s where a complex problem is solved by decomposing it into subcomponents that are solved independently.
The Parisian approach shares many similarities with the [[cooperative coevolution|cooperative coevolutionary algorithm]]. The Parisian approach makes use of a single-population whereas multi-species may be used in [[cooperative coevolution|cooperative coevolutionary algorithm]].
Similar internal evolutionary engines are considered in classical [[evolutionary algorithm]], [[cooperative coevolution|cooperative coevolutionary algorithm]] and Parisian evolution.
The difference between [[cooperative coevolution|cooperative coevolutionary algorithm]] and Parisian evolution resides in the population's semantics.
[[cooperative coevolution|Cooperative coevolutionary algorithm]] divides a big problem into sub-problems (groups of individuals) and solves them separately toward the big problem
However, Parisian [[evolutionary algorithms]] solve a whole problem as a big component.
All population's individuals cooperate together to drive the whole population toward attractive areas of the search space.
=== Fly Algorithm ''vs'' [[particle swarm optimisation]] ===
[[Cooperative coevolution]] and [[particle swarm optimisation|particle swarm optimisation (PSO)]] share many similarities. [[particle swarm optimisation|PSO]] is inspired by the social behaviour of bird flocking or fish schooling
It It uses complex individuals that interact with each other in order to build visually realistic collective behaviours through adjusting the individuals' behavioural rules (which may use random generators).
However, the solution of the optimisation problem in the Fly Algorithm is the population (or a subset of the population): The flies collaborate to build the solution. In [[particle swarm optimisation|PSO]] the solution is a single particle, the one with the best fitness. Another main difference between the Fly Algorithm and with [[particle swarm optimisation|PSO]] is that the Fly Algorithm is not based on any behavioural model but only builds a geometrical representation.▼
In mathematical optimisation, every particle of the swarm somehow follows its own random path biased toward the best particle of the swarm.
In the Fly Algorithm, the flies aim at building spatial representations of a scene from actual sensor data; flies do not communicate or explicitly cooperate, and do not use any behavioural model.
Both algorithms are search methods that start with a set of random solutions, which are iteratively corrected toward a global optimum.
== Applications of the Fly Algorithnm ==▼
▲However, the solution of the optimisation problem in the Fly Algorithm is the population (or a subset of the population): The flies implicitly collaborate to build the solution. In [[particle swarm optimisation|PSO]] the solution is a single particle, the one with the best fitness. Another main difference between the Fly Algorithm and with [[particle swarm optimisation|PSO]] is that the Fly Algorithm is not based on any behavioural model but only builds a geometrical representation.
* [[Computer stereo vision]] <ref name=LouchetRFIA2000 /><ref name=Louchet2000ICPR /><ref name=Louchet2001 /><ref name=Boumaza2003 />▼
* [[Obstacle avoidance]] <ref name=Louchet2002 /><ref name=Bomaza2001EvoIASP /><ref name=Louchet2002PatterRec />▼
* [[Simultaneous localization and mapping|Simultaneous localization and mapping (SLAM)]] <ref name=Louchet2009EvoIASP />▼
▲* [[Computer stereo vision]]
▲* [[Obstacle avoidance]]
▲* [[Simultaneous localization and mapping|Simultaneous localization and mapping (SLAM)]]
* [[Single-photon emission computed tomography|Single-photon emission computed tomography (SPECT)]] reconstruction <ref name=Bousquet2007EA />
* [[Positron emission tomography|Positron emission tomography (PET)]] reconstruction <ref name=Vidal2009EA /><ref name=Vidal2009MIC /><ref name=Vidal2010EvoIASP /><ref name=Vidal2010PPSN /><ref name=Abbood2017SWEVO /><ref name=Abbood2017EA>{{cite conference |title=Basic, Dual, Adaptive, and Directed Mutation Operators in the Fly Algorithm|last1=Abbood|first1=Zainab Ali|last2=Vidal|first2=Franck P.|conference=13th Biennal International Conference on Artificial Evolution (EA-2017)|pages=106–119|date=2017|___location=Paris, France|book-title=Lecture Notes in Computer Science|isbn=978-2-9539267-7-4}}</ref>
* [[Digital art]]<ref name=Abbood2017EvoIASP /><ref name=Abbood2017ArtAndScience>{{cite journal |title=Fly4Arts: Evolutionary Digital Art with the Fly Algorithm|last1=Abbood|first1=Zainab Ali|last2=Vidal|first2=Franck P.|pages=1–6|date=Oct 2017|doi=10.21494/ISTE.OP.2017.0177|volume=17- 1|issue=1|journal=Art and Science|doi-access=free}}</ref>
<!--== Methodology ==
Line 69 ⟶ 81:
== Example: Tomography reconstruction ==
<!-- === Pseudocode === -->
{{multiple image
The Fly Algorithm is an example of [[iterative reconstruction]]. Iterative methods in [[tomographic reconstruction]] are relatively easy to model: [[File:Iterative-algorithm.svg|512x122px|thumb|right|Iterative correction in tomography reconstruction.]]▼
| width = 100
| right
| image1=
| caption1=Example of image to reconstruct <math>(f)</math>, which is unknown.
| image2=sinogram-hot_spheres.png
| caption2=Sinogram <math>(Y)</math> of <math>f</math>, which is known.
| image3=
| caption3=Image reconstructed using the Fly algorithm <math>(\hat{f})</math>.
| image4=
| caption4=Sinogram <math>(\hat{Y})</math> of <math>\hat{f}</math>.
| footer=Example of reconstruction of a hot rod phantom using the Fly Algorithm.
}}
Tomography reconstruction is an [[inverse problem]] that is often [[ill-posed]] due to missing data and/or noise. The answer to the inverse problem is not unique, and in case of extreme noise level it may not even exist. The input data of a reconstruction algorithm may be given as the [[Radon transform]] or sinogram <math>\left(Y\right)</math> of the data to reconstruct <math>\left(f\right)</math>. <math>f</math> is unknown; <math>Y</math> is known.
The data acquisition in tomography can be modelled as:
<math>
Y = P[f] + \epsilon
</math>
where <math>P</math> is the system matrix or projection operator and <math>\epsilon</math> corresponds to some [[Shot noise|Poisson noise]].
In this case the reconstruction corresponds to the inversion of the [[Radon transform]]:
<math>
f = P^{-1}[Y]
</math>
Note that <math>P^{-1}</math> can account for noise, acquisition geometry, etc.
▲The Fly Algorithm is an example of [[iterative reconstruction]]. Iterative methods in [[tomographic reconstruction]] are relatively easy to model:
<math>
\hat{f} = \operatorname{arg\,min} || Y - \hat{Y}||^2_2
</math>
where <math>\hat{f}</math> is an estimate of <math>f</math>, that minimises an error metrics (here [[Norm (mathematics)|{{math|''ℓ<sup>2</sup>''}}-norm]], but other error metrics could be used) between <math>Y</math> and <math>\hat{Y}</math>. Note that a [[Regularization (mathematics)|regularisation term]] can be introduced to prevent overfitting and to smooth noise whilst preserving edges.
Iterative methods can be implemented as follows:
[[File:Iterative-algorithm.svg|512x122px|thumb|right|Iterative correction in tomography reconstruction.]]
(i) The reconstruction starts using an initial estimate of the image (generally a constant image),
(ii) Projection data is computed from this image,
Line 78 ⟶ 127:
(v) The algorithm iterates until convergence of the estimated and measured projection sets.
The [[pseudocode]] below is a step-by-step description of the Fly Algorithm for [[tomographic reconstruction]]. The algorithm follows the steady-state paradigm. For illustrative purposes,
<!-- [[File:Fly4pet.svg|512x616px|thumb|right|Flowchart of the Fly Algorithm for Positron Emission Tomography.]] -->▼
▲The [[pseudocode]] below is a step-by-step description of the Fly Algorithm for [[tomographic reconstruction]]. The algorithm follows the steady-state paradigm. For illustrative purposes, we keep it simple and ignore more advanced genetic operators, such as mitosis, dual mutation, etc.<ref>{{cite conference |title=Threshold selection, mitosis and dual mutation in cooperative co-evolution: Application to medical 3D tomography|last1=Vidal|first1=Franck P.|last2=Lutton|first2=Évelyne|last3=Louchet|first3=Jean|last4=Rocchisani|first4=Jean-Marie|publisher=Springer Berlin / Heidelberg|conference=Parallel Problem Solving from Nature - PPSN XI|pages=414–423|date=Sep 2010|doi=10.1007/978-3-642-15844-5_42|isbn=978-3-642-15843-8|___location=Kraków, Poland|volume=6238|book-title=Lecture Notes in Computer Science|url=http://www.fpvidal.net/fly4pet/pdf/Vidal2010PPSN.pdf|}}</ref><ref>{{cite conference |title=Basic, Dual, Adaptive, and Directed Mutation Operators in the Fly Algorithm|last1=Ali Abbood|first1=Zainab|last2=Vidal|first2=Franck P.|publisher=Springer-Verlag|conference=13th Biennal International Conference on Artificial Evolution|date=Oct 2017|___location=Paris, France|book-title=Lecture Notes in Computer Science|}}</ref>. A [[JavaScript]] implementation can be found on [http://www.fpvidal.net/fly4pet/demo.php Fly4PET].
<!-- [[File:evolutionary_PET_reconstructions.png|299x501px|thumb|right|Example of evolutionary reconstructions at successive resolutions (with ''N'' the number of flies and ''TS'' the time-stamp in minutes).]]-->▼
▲[[File:Fly4pet.svg|512x616px|thumb|right|Flowchart of the Fly Algorithm for Positron Emission Tomography.]]
▲[[File:evolutionary_PET_reconstructions.png|299x501px|thumb|right|Example of evolutionary reconstructions at successive resolutions (with ''N'' the number of flies and ''TS'' the time-stamp in minutes).]]
'''algorithm''' fly-algorithm '''is'''
Line 111 ⟶ 159:
14. Remove ''f''<sub>''kill''</sub>'s contribution from ''p''<sub>''estimated''</sub>
15.
16. ''// Compute the population's performance without
17. ''G''<sub>''fitness''</sub>(''F''-<nowiki/>{''f''<sub>''kill''</sub>}) ← ''Error''<sub>metrics</sub>(''p''<sub>''reference''</sub>, ''p''<sub>''estimated''</sub>)
18.
Line 118 ⟶ 166:
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. ''//
24. '''else''' go to Step 28. ''//
25.
26. Restore the fly's contribution, then go to Step 12.
Line 133 ⟶ 181:
14. Remove ''f''<sub>''reproduce''</sub>'s contribution from ''p''<sub>''estimated''</sub>
37.
38. ''// Compute the population's performance without
39. ''G''<sub>''fitness''</sub>(''F''-<nowiki/>{''f''<sub>''reproduce''</sub>}) ← ''Error''<sub>metrics</sub>(''p''<sub>''reference''</sub>, ''p''<sub>''estimated''</sub>)
40.
41. // Compare the performances, i.e. compute the fly's local fitness
42. ''L''<sub>''fitness''</sub>(''f''<sub>''reproduce''</sub>) ← ''G''<sub>''fitness''</sub>(''F''-<nowiki/>{''f''<sub>''reproduce''</sub>}) - ''G''<sub>''fitness''</sub>(''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. ''//
48. '''then''' go to Step 53. ''//
49.
50. ''// New blood / Immigration''
Line 166 ⟶ 214:
== Example: Digital arts ==
<!-- [[File:Initial_random_fly_population.png|200x200px|thumb|left|Image of the initial population (random fly positions).]] -->
In this example, an input image is to be approximated by a set of tiles (for example as in an ancient [[mosaic]]). A tile has an orientation (angle θ), a three colour components (R, G, B), a size (w, h) and a position (x, y, z). If there are ''N'' tiles, there are 9''N'' unknown floating point numbers to guess. In other words for 5,000 tiles, there are 45,000 numbers to find. Using a classical evolutionary algorithm where the answer of the optimisation problem is the best individual, the genome of an individual would made of 45,000 genes. This approach would be extremely costly in term of complexity and computing time. The same applies for any classical optimisation algorithm. Using the Fly Algorithm, every individual mimics a title and can be individually evaluated using its local fitness to assess its contribution to the population's performance (the global fitness). Here an individual has 9 genes instead of 9''N'', and there are ''N'' individuals. It can be solved as a reconstruction problem as follows:▼
{{multiple image
<math>reconstruction = \operatorname{arg\,min} \overset{x<W}{\underset{y=0}{\sum}}\overset{j<H}{\underset{j=0}{\sum}}|input(x,y) - P[F](x,y)|</math>▼
| width = 200
| right
| image1=evolutionary_search_Y_Lliwedd_flies.gif
| caption1=Evolutionary search.
| image2=Y_Lliwedd_flies.png
| caption2=Image reconstructed after optimisation using a set of stripes as the pattern for each tile.
}}
▲In this example, an input image is to be approximated by a set of tiles (for example as in an ancient [[mosaic]]). A tile has an orientation (angle θ), a three colour components (R, G, B), a size (w, h) and a position (x, y, z). If there are ''N'' tiles, there are 9''N'' unknown floating point numbers to guess. In other words for 5,000 tiles, there are 45,000 numbers to find. Using a classical evolutionary algorithm where the answer of the optimisation problem is the best individual, the genome of an individual would be made up of 45,000 genes. This approach would be extremely costly in term of complexity and computing time. The same applies for any classical optimisation algorithm. Using the Fly Algorithm, every individual mimics a
▲<math>reconstruction = \operatorname{arg\,min} \overset{x<W}{\underset{
where <math>input</math> is the input image, <math>x</math> and <math>y</math> are the pixel coordinates along the horizontal and vertical axis respectively, <math>W</math> and <math>H</math> are the image width and height in number of pixels respectively, <math>F</math> is the fly population, and <math>P</math> is a projection operator that creates an image from flies. This projection operator <math>P</math> can take many forms. In her work, Z. Ali Aboodd <ref name=Abbood2017EvoIASP /> uses [[OpenGL]] to generate different effects (e.g. mosaics, or spray paint). For speeding up the evaluation of the fitness functions, [[OpenCL]] is used too.
The algorithm starts with a population <math>F</math> that is randomly generated (see Line 3 in the algorithm above). <math>F</math> is then assessed using the global fitness to compute <math>G_{fitness}(F) = \overset{x<W}{\underset{
== See also ==
Line 191 ⟶ 248:
<!-- Inline citations added to your article will automatically display here. See https://en.wikipedia.org/wiki/WP:REFB for instructions on how to add citations. -->
{{reflist}}
{{Evolutionary computation}}
[[:Category:Genetic algorithms]]▼
[[
[[
[[
[[Category:Nature-inspired metaheuristics]]
[[Category:Evolutionary computation]]
| |||