SUPPORT THE WORK

GetWiki

evolutionary algorithm

ARTICLE SUBJECTS
aesthetics  →
being  →
complexity  →
database  →
enterprise  →
ethics  →
fiction  →
history  →
internet  →
knowledge  →
language  →
licensing  →
linux  →
logic  →
method  →
news  →
perception  →
philosophy  →
policy  →
purpose  →
religion  →
science  →
sociology  →
software  →
truth  →
unix  →
wiki  →
ARTICLE TYPES
essay  →
feed  →
help  →
system  →
wiki  →
ARTICLE ORIGINS
critical  →
discussion  →
forked  →
imported  →
original  →
evolutionary algorithm
[ temporary import ]
please note:
- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
{{Artificial intelligence}}In artificial intelligence, an evolutionary algorithm (EA) is a subset of evolutionary computation,ARTICLE, Vikhar, P. A., Evolutionary algorithms: A critical review and its future prospects,weblink Proceedings of the 2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC), Jalgaon, 2016, pp. 261-265, 978-1-5090-0467-6, a generic population-based metaheuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as reproduction, mutation, recombination, and selection. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the quality of the solutions (see also loss function). Evolution of the population then takes place after the repeated application of the above operators.Evolutionary algorithms often perform well approximating solutions to all types of problems because they ideally do not make any assumption about the underlying fitness landscape. Techniques from evolutionary algorithms applied to the modeling of biological evolution are generally limited to explorations of microevolutionary processes and planning models based upon cellular processes. In most real applications of EAs, computational complexity is a prohibiting factor.BOOK, Cohoon, J, etal, Evolutionary algorithms for the physical design of VLSI circuits,weblink Advances in Evolutionary Computing: Theory and Applications, Springer, pp. 683-712, 2003, 978-3-540-43330-9, 2002-11-26, In fact, this computational complexity is due to fitness function evaluation. Fitness approximation is one of the solutions to overcome this difficulty. However, seemingly simple EA can solve often complex problems{{Citation needed|date=June 2018}}; therefore, there may be no direct link between algorithm complexity and problem complexity.

Implementation

Step One: Generate the initial population of individuals randomly. (First generation)Step Two: Evaluate the fitness of each individual in that population (time limit, sufficient fitness achieved, etc.)Step Three: Repeat the following regenerational steps until termination:
  1. Select the best-fit individuals for reproduction. (Parents)
  2. Breed new individuals through crossover and mutation operations to give birth to offspring.
  3. Evaluate the individual fitness of new individuals.
  4. Replace least-fit population with new individuals.

Types

Similar techniques differ in genetic representation and other implementation details, and the nature of the particular applied problem.
  • Genetic algorithm – This is the most popular type of EA. One seeks the solution of a problem in the form of strings of numbers (traditionally binary, although the best representations are usually those that reflect something about the problem being solved), by applying operators such as recombination and mutation (sometimes one, sometimes both). This type of EA is often used in optimization problems.
  • Genetic programming – Here the solutions are in the form of computer programs, and their fitness is determined by their ability to solve a computational problem.
  • Evolutionary programming – Similar to genetic programming, but the structure of the program is fixed and its numerical parameters are allowed to evolve.
  • Gene expression programming – Like genetic programming, GEP also evolves computer programs but it explores a genotype-phenotype system, where computer programs of different sizes are encoded in linear chromosomes of fixed length.
  • Evolution strategy – Works with vectors of real numbers as representations of solutions, and typically uses self-adaptive mutation rates.
  • Differential evolution – Based on vector differences and is therefore primarily suited for numerical optimization problems.
  • Neuroevolution – Similar to genetic programming but the genomes represent artificial neural networks by describing structure and connection weights. The genome encoding can be direct or indirect.
  • Learning classifier system – Here the solution is a set of classifiers (rules or conditions). A Michigan-LCS evolves at the level of individual classifiers whereas a Pittsburgh-LCS uses populations of classifier-sets. Initially, classifiers were only binary, but now include real, neural net, or S-expression types. Fitness is typically determined with either a strength or accuracy based reinforcement learning or supervised learning approach.

Comparison to biological processes

A possible limitation{{According to whom|date=May 2013}} of many evolutionary algorithms is their lack of a clear genotype-phenotype distinction. In nature, the fertilized egg cell undergoes a complex process known as embryogenesis to become a mature phenotype. This indirect encoding is believed to make the genetic search more robust (i.e. reduce the probability of fatal mutations), and also may improve the evolvability of the organism.G.S. Hornby and J.B. Pollack. "Creating high-level components with a generative representation for body-brain evolution". Artificial Life, 8(3):223–246, 2002.Jeff Clune, Benjamin Beckmann, Charles Ofria, and Robert Pennock. "Evolving Coordinated Quadruped Gaits with the HyperNEAT Generative Encoding" {{Webarchive|url=https://web.archive.org/web/20160603205252weblink |date=2016-06-03 }}. Proceedings of the IEEE Congress on Evolutionary Computing Special Section on Evolutionary Robotics, 2009. Trondheim, Norway. Such indirect (a.k.a. generative or developmental) encodings also enable evolution to exploit the regularity in the environment.J. Clune, C. Ofria, and R. T. Pennock, "How a generative encoding fares as problem-regularity decreases", in PPSN (G. Rudolph, T. Jansen, S. M. Lucas, C. Poloni, and N. Beume, eds.), vol. 5199 of Lecture Notes in Computer Science, pp. 358–367, Springer, 2008. Recent work in the field of artificial embryogeny, or artificial developmental systems, seeks to address these concerns. And gene expression programming successfully explores a genotype-phenotype system, where the genotype consists of linear multigenic chromosomes of fixed length and the phenotype consists of multiple expression trees or computer programs of different sizes and shapes.Ferreira, C., 2001. "Gene Expression Programming: A New Adaptive Algorithm for Solving Problems". Complex Systems, Vol. 13, issue 2: 87–129. {{Synthesis inline|date=May 2013}}

Related techniques

Swarm algorithms{{clarify|reason=Why are swarm algorithms associated with evolutionary ones?|date=January 2018}} include
  • Ant colony optimization – Based on the ideas of ant foraging by pheromone communication to form paths. Primarily suited for combinatorial optimization and graph problems.
  • The runner-root algorithm (RRA) is inspired by the function of runners and roots of plants in natureF. Merrikh-Bayat, "The runner-root algorithm: A metaheuristic for solving unimodal and multimodal optimization problems inspired by runners and roots of plants in nature", Applied Soft Computing, Vol. 33, pp. 292–303, 2015
  • Artificial bee colony algorithm – Based on the honey bee foraging behaviour. Primarily proposed for numerical optimization and extended to solve combinatorial, constrained and multi-objective optimization problems.
  • Bees algorithm is based on the foraging behaviour of honey bees. It has been applied in many applications such as routing and scheduling.
  • Cuckoo search is inspired by the brooding parasitism of the cuckoo species. It also uses Lévy flights, and thus it suits for global optimization problems.
  • Electimize optimization - Based on the behavior of electron flow through electric circuit branches with the least electric resistance.JOURNAL, Khalafallah Ahmed, Abdel-Raheem Mohamed, 2011-05-01, Electimize: New Evolutionary Algorithm for Optimization with Application in Construction Engineering, Journal of Computing in Civil Engineering, 25, 3, 192–201, 10.1061/(ASCE)CP.1943-5487.0000080,
  • Particle swarm optimization – Based on the ideas of animal flocking behaviour. Also primarily suited for numerical optimization problems.

Other population-based metaheuristic methods

  • Hunting Search – A method inspired by the group hunting of some animals such as wolves that organize their position to surround the prey, each of them relative to the position of the others and especially that of their leader. It is a continuous optimization methodJOURNAL, Oftadeh, R., Mahjoob, M.J., Shariatpanahi, M., A novel meta-heuristic optimization algorithm inspired by group hunting of animals: Hunting search, Computers & Mathematics with Applications, October 2010, 60, 7, 2087–2098, 10.1016/j.camwa.2010.07.049, adapted as a combinatorial optimization method.JOURNAL, Amine Agharghor, Mohammed Essaid Riffi, 2017, First Adaptation of Hunting Search Algorithm for the Quadratic Assignment Problem, Europe and MENA Cooperation Advances in Information and Communication Technologies, 520, 263–267, 10.1007/978-3-319-46568-5_27, 978-3-319-46567-8, Advances in Intelligent Systems and Computing,
  • Adaptive dimensional search – Unlike nature-inspired metaheuristic techniques, an adaptive dimensional search algorithm does not implement any metaphor as an underlying principle. Rather it uses a simple performance-oriented method, based on the update of the search dimensionality ratio (SDR) parameter at each iteration.Hasançebi, O., Kazemzadeh Azad, S. (2015), "Adaptive Dimensional Search: A New Metaheuristic Algorithm for Discrete Truss Sizing Optimization", Computers and Structures, 154, 1–16.
  • Firefly algorithm is inspired by the behavior of fireflies, attracting each other by flashing light. This is especially useful for multimodal optimization.
  • Harmony search – Based on the ideas of musicians' behavior in searching for better harmonies. This algorithm is suitable for combinatorial optimization as well as parameter optimization.
  • Gaussian adaptation – Based on information theory. Used for maximization of manufacturing yield, mean fitness or average information. See for instance Entropy in thermodynamics and information theory.
  • Memetic algorithm – A hybrid method, inspired by Richard Dawkins's notion of a meme, it commonly takes the form of a population-based algorithm coupled with individual learning procedures capable of performing local refinements. Emphasizes the exploitation of problem-specific knowledge, and tries to orchestrate local and global search in a synergistic way.
  • Emperor Penguins Colony – A method inspired by the behavior of emperor penguins in their colony. The emperor penguins in the colony seek to create the appropriate heat and regulate their body temperature, and this heat is completely coordinated and controlled by the movement of the penguins.JOURNAL, Harifi, Sasan, Khalilian, Madjid, Mohammadzadeh, Javad, Ebrahimnejad, Sadoullah, Emperor Penguins Colony: a new metaheuristic algorithm for optimization, Evolutionary Intelligence, 25 February 2019, 12, 2, 211–226, 10.1007/s12065-019-00212-x,

Examples

The computer simulations Tierra and Avida attempt to model macroevolutionary dynamics.

Gallery

JOURNAL, Simionescu, P.A., Beale, D.G., Dozier, G.V., Constrained optimization problem solving using estimation of distribution algorithms, Proc. of the 2004 Congress on Evolutionary Computation - CEC2004, Portland, OR, 1647–1653, 2004, 10.1109/CEC.2006.1688506,weblink 7 January 2017, BOOK, Simionescu, P.A., 2006 IEEE International Conference on Evolutionary Computation, Dozier, G.V., Wainwright, R.L., A Two-Population Evolutionary Algorithm for Constrained Optimization Problems, Proc 2006 IEEE International Conference on Evolutionary Computation, Vancouver, Canada, 1647–1653, 2006, 10.1109/CEC.2006.1688506,weblink 7 January 2017, 0-7803-9487-9, BOOK, Simionescu, P.A., Computer Aided Graphing and Simulation Tools for AutoCAD Users, 2014, CRC Press, Boca Raton, FL, 978-1-4822-5290-3, 1st, File:Two-population EA search (2).gif|A two-population EA search over a constrained Rosenbrock function with bounded global optimum.File:Two-population EA search (3).gif|A two-population EA search over a constrained Rosenbrock function. Global optimum is not bounded.File:Estimation of Distribution Algorithm animation.gif|Estimation of distribution algorithm over Keane's functionFile:Two population EA animation.gif|A two-population EA search of a bounded optima of Simionescu's function.

References

{{Reflist}}

Bibliography

  • Ashlock, D. (2006), Evolutionary Computation for Modeling and Optimization, Springer, {{ISBN|0-387-22196-4}}.
  • Bäck, T. (1996), Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford Univ. Press.
  • Bäck, T., Fogel, D., Michalewicz, Z. (1997), Handbook of Evolutionary Computation, Oxford Univ. Press.
  • Banzhaf, W., Nordin, P., Keller, R., Francone, F. (1998), Genetic Programming - An Introduction, Morgan Kaufmann, San Francisco
  • Eiben, A.E., Smith, J.E. (2003), Introduction to Evolutionary Computing, Springer.
  • Holland, J. H. (1992), Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor
  • Michalewicz Z., Fogel D.B. (2004). How To Solve It: Modern Heuristics, Springer.
  • BOOK, 10.1109/BICTA.2010.5645312, Bin Packing/Covering with Delivery, solved with the evolution of algorithms, 2010 IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA), 298–302, 2010, Benko, Attila, Dosa, Gyorgy, Tuza, Zsolt, 978-1-4244-6437-1,
  • BOOK, Poli, R., Langdon, W. B., McPhee, N. F., 2008, A Field Guide to Genetic Programming, Lulu.com, freely available from the internet,weblink 978-1-4092-0073-4,
  • Price, K., Storn, R.M., Lampinen, J.A., (2005). "Differential Evolution: A Practical Approach to Global Optimization", Springer.
  • Ingo Rechenberg (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis). Reprinted by Fromman-Holzboog (1973).
  • Hans-Paul Schwefel (1974): Numerische Optimierung von Computer-Modellen (PhD thesis). Reprinted by Birkhäuser (1977).
  • Simon, D. (2013): Evolutionary Optimization Algorithms, Wiley.
  • Computational Intelligence: A Methodological Introduction by Kruse, Borgelt, Klawonn, Moewes, Steinbrecher, Held, 2013, Springer, {{ISBN|978-1-4471-5012-1}}
  • JOURNAL, Rahman, Rosshairy Abd., Kendall, Graham, Ramli, Razamin, Jamari, Zainoddin, Ku-Mahamud, Ku Ruhana, Shrimp Feed Formulation via Evolutionary Algorithm with Power Heuristics for Handling Constraints, Complexity, 2017, 2017, 1–12, 10.1155/2017/7053710,


- content above as imported from Wikipedia
- "evolutionary algorithm" does not exist on GetWiki (yet)
- time: 3:28pm EDT - Tue, Aug 20 2019
[ this remote article is provided by Wikipedia ]
LATEST EDITS [ see all ]
GETWIKI 09 JUL 2019
Eastern Philosophy
History of Philosophy
GETWIKI 09 MAY 2016
GETWIKI 18 OCT 2015
M.R.M. Parrott
Biographies
GETWIKI 20 AUG 2014
GETWIKI 19 AUG 2014
CONNECT