Evolutionary algorithm
Part of a series on |
Artificial intelligence |
---|
In
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.[2] 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;[3][4][5] therefore, there may be no direct link between algorithm complexity and problem complexity.
Evolutionary algorithms can be seen as a kind of
Implementation
The following is an example of a generic single-objective genetic algorithm.
Step One: Generate the initial population of individuals randomly. (First generation)
Step Two: Repeat the following regenerational steps until termination:
- Evaluate the fitness of each individual in the population (time limit, sufficient fitness achieved, etc.)
- Select the fittest individuals for reproduction. (Parents)
- Breed new individuals through crossover and mutation operations to give birth to offspring.
- Replace the least-fit individuals of the population with new individuals.
Types
Similar techniques differ in genetic representation and other implementation details, and the nature of the particular applied problem.
- optimizationproblems.
- 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. There are many variants of Genetic Programming, including Cartesian genetic programming, gene expression programming, grammatical evolution, linear genetic programming, multi expression programming etc.
- Evolutionary programming – Similar to genetic programming, but the structure of the program is fixed and its numerical parameters are allowed to evolve.
- Evolution strategy – Works with vectors of real numbers as representations of solutions, and typically uses self-adaptive mutation rates. The method is mainly used for numerical optimization, although there are also variants for combinatorial tasks.[7][8]
- numerical optimizationproblems.
- Coevolutionary algorithm – Similar to genetic algorithms and evolution strategies, but the created solutions are compared on the basis of their outcomes from interactions with other solutions. Solutions can either compete or cooperate during the search process. Coevolutionary algorithms are often used in scenarios where the fitness landscape is dynamic, complex, or involves competitive interactions.[9][10]
- 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.
- Quality–Diversity algorithms – QD algorithms simultaneously aim for high-quality and diverse solutions. Unlike traditional optimization algorithms that solely focus on finding the best solution to a problem, QD algorithms explore a wide variety of solutions across a problem space and keep those that are not just high performing, but also diverse and unique.[11][12][13]
Theoretical background
The following theoretical principles apply to all or almost all EAs.
No free lunch theorem
The no free lunch theorem of optimization states that all optimization strategies are equally effective when the set of all optimization problems is considered. Under the same condition, no evolutionary algorithm is fundamentally better than another. This can only be the case if the set of all problems is restricted. This is exactly what is inevitably done in practice. Therefore, to improve an EA, it must exploit problem knowledge in some form (e.g. by choosing a certain mutation strength or a problem-adapted coding). Thus, if two EAs are compared, this constraint is implied. In addition, an EA can use problem specific knowledge by, for example, not randomly generating the entire start population, but creating some individuals through heuristics or other procedures.[14][15] Another possibility to tailor an EA to a given problem domain is to involve suitable heuristics, local search procedures or other problem-related procedures in the process of generating the offspring. This form of extension of an EA is also known as a memetic algorithm. Both extensions play a major role in practical applications, as they can speed up the search process and make it more robust.[14][16]
Convergence
For EAs in which, in addition to the offspring, at least the best individual of the parent generation is used to form the subsequent generation (so-called elitist EAs), there is a general proof of
From the property of elitist offspring acceptance and the existence of the optimum it follows that per generation an improvement of the fitness of the respective best individual will occur with a probability . Thus:
I.e., the fitness values represent a monotonically non-decreasing sequence, which is bounded due to the existence of the optimum. From this follows the convergence of the sequence against the optimum.
Since the proof makes no statement about the speed of convergence, it is of little help in practical applications of EAs. But it does justify the recommendation to use elitist EAs. However, when using the usual panmictic population model, elitist EAs tend to converge prematurely more than non-elitist ones.[17] In a panmictic population model, mate selection (step 2 of the section about implementation) is such that every individual in the entire population is eligible as a mate. In non-panmictic populations, selection is suitably restricted, so that the dispersal speed of better individuals is reduced compared to panmictic ones. Thus, the general risk of premature convergence of elitist EAs can be significantly reduced by suitable population models that restrict mate selection.[18][19]
Virtual alphabets
With the theory of virtual alphabets, David E. Goldberg showed in 1990 that by using a representation with real numbers, an EA that uses classical recombination operators (e.g. uniform or n-point crossover) cannot reach certain areas of the search space, in contrast to a coding with binary numbers.[20] This results in the recommendation for EAs with real representation to use arithmetic operators for recombination (e.g. arithmetic mean or intermediate recombination). With suitable operators, real-valued representations are more effective than binary ones, contrary to earlier opinion.[21][22]
Comparison to biological processes
A possible limitation[
Applications
The areas in which evolutionary algorithms are practically used are almost unlimited[5] and range from industry,[27][28] engineering,[2][3][29] complex scheduling,[4][30][31] agriculture,[32] robot movement planning[33] and finance[34][35] to research[36][37] and art. The application of an evolutionary algorithm requires some rethinking from the inexperienced user, as the approach to a task using an EA is different from conventional exact methods and this is usually not part of the curriculum of engineers or other disciplines. For example, the fitness calculation must not only formulate the goal but also support the evolutionary search process towards it, e.g. by rewarding improvements that do not yet lead to a better evaluation of the original quality criteria. For example, if peak utilisation of resources such as personnel deployment or energy consumption is to be avoided in a scheduling task, it is not sufficient to assess the maximum utilisation. Rather, the number and duration of exceedances of a still acceptable level should also be recorded in order to reward reductions below the actual maximum peak value.[38] There are therefore some publications that are aimed at the beginner and want to help avoiding beginner's mistakes as well as leading an application project to success.[38][39][40] This includes clarifying the fundamental question of when an EA should be used to solve a problem and when it is better not to.
Related techniques
Swarm algorithms[clarification needed] include:
- Ant colony optimization is based on the ideas of ant foraging by pheromone communication to form paths.[41] Primarily suited for combinatorial optimization and graphproblems.
- The runner-root algorithm (RRA) is inspired by the function of runners and roots of plants in nature.[42]
- Artificial bee colony algorithm is based on the honeybee 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 honeybees. It has been applied in many applications such as routing and scheduling.
- optimizationproblems.
- numerical optimizationproblems.
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 method[43] adapted as a combinatorial optimization method.[44]
- 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.[45]
- 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.
- 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.
Examples
In 2020, Google stated that their AutoML-Zero can successfully rediscover classic algorithms such as the concept of neural networks.[46]
The computer simulations Tierra and Avida attempt to model macroevolutionary dynamics.
Gallery
-
A two-population EA search over a constrained Rosenbrock function with bounded global optimum
-
A two-population EA search over a constrained Rosenbrock function. Global optimum is not bounded.
-
A two-population EA search of a bounded optima of Simionescu's function
References
- )
- ^ ISBN 978-3-540-43330-9.
- ^ S2CID 212732659.
- ^ S2CID 31859338.
- ^ a b "International Conference on the Applications of Evolutionary Computation". The conference is part of the Evo* series. The conference proceedings are published by Springer. Retrieved 2022-12-23.
- ^ Ashlock, D. (2006). Evolutionary Computation for Modeling and Optimization. Deutschland: Springer New York. Page 491, https://books.google.de/books?id=kz0rofjQrwYC&pg=PA491
- ISBN 978-3-642-79386-8
- S2CID 13582781.
- S2CID 125149900, retrieved 2023-05-22
- ISBN 978-3-540-92910-9.
- ISSN 2296-9144.
- S2CID 17338175.
- S2CID 3467239.
- ^ OCLC 23081440.
- ISBN 978-3-540-58484-1, retrieved 2022-10-18
- ISBN 978-3-642-23246-6.
- PMID 18255718.
- ISBN 978-3-540-65078-2, retrieved 2022-10-21
- ISBN 978-0-387-77609-5.
- ISBN 978-3-540-54148-6, retrieved 2022-10-22
- OCLC 47216370.
- OCLC 851375253.
- ^ 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" Archived 2016-06-03 at the Wayback Machine. Proceedings of the IEEE Congress on Evolutionary Computing Special Section on Evolutionary Robotics, 2009. Trondheim, Norway.
- ^ 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.
- ^ Ferreira, C., 2001. "Gene Expression Programming: A New Adaptive Algorithm for Solving Problems". Complex Systems, Vol. 13, issue 2: 87–129.
- ISBN 978-3-642-27466-4.
- OCLC 45728460.
- ISBN 978-0-470-17226-1.
- OCLC 184984689.
- ISSN 1999-4893.
- ISBN 978-1-4613-5693-6.
- ISBN 978-3-540-67353-8, retrieved 2022-12-28
- ISBN 978-3-540-89377-6, retrieved 2022-12-23
- ISBN 978-3-7908-2512-1.
- ISBN 0-7803-8302-8.
- ISBN 978-1-55860-797-2.
- ^ S2CID 236318422, retrieved 2022-12-23
- S2CID 18637958.
- S2CID 20912932.
- ^ S2CID 3707290.
- ^ F. 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
- .
- ISBN 978-3-319-46567-8.
- ^ 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.
- ^ Gent, Edd (13 April 2020). "Artificial intelligence is evolving all by itself". Science | AAAS. Archived from the original on 16 April 2020. Retrieved 16 April 2020.
- S2CID 1717817.
- )
- ISBN 978-1-4822-5290-3.
External links
Bibliography
- Ashlock, D. (2006), Evolutionary Computation for Modeling and Optimization, Springer, New York, ISBN 0-387-22196-4.
- Bäck, T. (1996), Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford Univ. Press, New York, ISBN 978-0-19-509971-3.
- Bäck, T., Fogel, D., Michalewicz, Z. (1999), Evolutionary Computation 1: Basic Algorithms and Operators, CRC Press, Boca Raton, USA, ISBN 978-0-7503-0664-5.
- Bäck, T., Fogel, D., Michalewicz, Z. (2000), Evolutionary Computation 2: Advanced Algorithms and Operators, CRC Press, Boca Raton, USA, ISBN 978-0-3678-0637-8.
- Banzhaf, W., Nordin, P., Keller, R., Francone, F. (1998), Genetic Programming - An Introduction, Morgan Kaufmann, San Francisco, ISBN 978-1-55860-510-7.
- Eiben, A.E., Smith, J.E. (2003), Introduction to Evolutionary Computing, Springer, Heidelberg, New York, ISBN 978-3-662-44873-1.
- Holland, J. H. (1992), Adaptation in Natural and Artificial Systems, MIT Press, Cambridge, MA, ISBN 978-0-262-08213-6.
- Michalewicz, Z.; Fogel, D.B. (2004), How To Solve It: Modern Heuristics. Springer, Berlin, Heidelberg, .
- Benko, Attila; Dosa, Gyorgy; Tuza, Zsolt (2010). "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). pp. 298–302. S2CID 16875144.
- Poli, R.; Langdon, W. B.; McPhee, N. F. (2008). A Field Guide to Genetic Programming. Lulu.com, freely available from the internet. ISBN 978-1-4092-0073-4. Archived from the original on 2016-05-27. Retrieved 2011-03-05.[self-published source]
- Price, K., Storn, R.M., Lampinen, J.A., (2005). Differential Evolution: A Practical Approach to Global Optimization, Springer, Berlin, Heidelberg, .
- ISBN 3-7728-1642-8
- Hans-Paul Schwefel (1974), Numerische Optimierung von Computer-Modellen (PhD thesis). Reprinted by Birkhäuser (1977).
- ISBN 0-471-57148-2
- Simon, D. (2013), Evolutionary Optimization Algorithms Archived 2014-03-10 at the ISBN 978-0-470-93741-9
- Kruse, Rudolf; Borgelt, Christian; Klawonn, Frank; Moewes, Christian; Steinbrecher, Matthias; Held, Pascal (2013), Computational Intelligence: A Methodological Introduction. Springer, London. .
- Rahman, Rosshairy Abd.; Kendall, Graham; Ramli, Razamin; Jamari, Zainoddin; Ku-Mahamud, Ku Ruhana (2017). "Shrimp Feed Formulation via Evolutionary Algorithm with Power Heuristics for Handling Constraints". Complexity. 2017: 1–12. .