{
  "id": "enwiki-001377564246",
  "slug": "fly-algorithm",
  "title": "Fly algorithm",
  "qid": "",
  "lead": "The Fly Algorithm is an approach in 3D reconstruction that utilizes clusters of points (\"flies\") corresponding to different nearby objects via genetic algorithms and stereovision principles. The resulting reconstruction is partial, but can be used to recognize obstacles in robot navigation and other applications. This technique has a high computational load due to numerous inputs and parameters, making performance optimization difficult.",
  "body": "The Fly Algorithm is an approach in 3D reconstruction that utilizes clusters of points (\"flies\") corresponding to different nearby objects via genetic algorithms and stereovision principles. The resulting reconstruction is partial, but can be used to recognize obstacles in robot navigation and other applications. This technique has a high computational load due to numerous inputs and parameters, making performance optimization difficult. More recently it has been used in digital art to generate mosaic-like images or spray paint. Examples of images can be found on YouTube Y = P[f] + \\epsilon where P is the system matrix or projection operator and \\epsilon corresponds to some Poisson noise. In this case the reconstruction corresponds to the inversion of the Radon transform: f = P^{-1}[Y] Note that P^{-1} 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: \\hat{f} = \\operatorname{arg\\,min} || Y - \\hat{Y}||^2_2 where \\hat{f} is an estimate of f , that minimises an error metrics (here -norm, but other error metrics could be used) between Y and \\hat{Y} . Note that a regularisation term can be introduced to prevent overfitting and to smooth noise whilst preserving edges. Iterative methods can be implemented as follows: (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 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, advanced genetic operators, such as mitosis, dual mutation, etc. are ignored. A JavaScript implementation can be found on 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 &larr; random(0, 1) 5. F(i) y &larr; random(0, 1) 6. F(i) z &larr; 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) &larr; Error metrics (p reference , p estimated ) 11. 12. f kill &larr; 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 }) &larr; Error metrics (p reference , p estimated ) 18. 19. // Compare the performances, i.e. compute the fly's local fitness 20. L fitness (f kill ) &larr; 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 &larr; 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 }) &larr; Error metrics (p reference , p estimated ) 40. 41. // Compare the performances, i.e. compute the fly's local fitness 42. L fitness (f reproduce ) &larr; 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 reproduce is a bad fly: we should not allow it to reproduce 48. then go to Step 53. // f reproduce 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 &larr; voxelisation of F 65. 66. return V F END reconstruction = \\operatorname{arg\\,min} \\overset{x where input is the input image, x and y are the pixel coordinates along the horizontal and vertical axis respectively, W and H are the image width and height in number of pixels respectively, F is the fly population, and P is a projection operator that creates an image from flies. This projection operator P can take many forms. In her work, Z. Ali Aboodd 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 F that is randomly generated (see Line 3 in the algorithm above). F is then assessed using the global fitness to compute G_{fitness}(F) = \\overset{x (see Line 10). G_{fitness} is the objective function that has to be minimized.",
  "categories": [
    "115986874",
    "129211757",
    "20181550",
    "20277800",
    "23127192",
    "23617828",
    "24890786",
    "27179440",
    "29176353",
    "30525120",
    "48128016",
    "72784985"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1377564246",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1790722722.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001377564246",
    "type": "webpage",
    "title": "Fly algorithm",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/fly-algorithm",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001377564246",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1377564246",
    "note": "Immutable snapshot enwiki-001377564246"
  }
}