Jump to content

Genetic algorithm

From Simple English Wikipedia, the free encyclopedia
The unusual form of this antenna, developed by NASA, was found using a genetic algorithm.

A genetic algorithm is an algorithm that imitates the process of natural selection. They help solve optimization and search problems. Genetic algorithms are part of the bigger class of evolutionary algorithms. Genetic algorithms imitate natural biological processes, such as inheritance, mutation, selection and crossover.

The concept of genetic algorithms is a search technique often used in computer science to find complex, non-obvious solutions to algorithmic optimisation and search problems. Genetic algorithms are global search heuristics.[1]

What is it

Natural evolution can be modeled as a game, in which the rewards for an organism that plays a good game of life are the passing on of its genetic material to its successors and its continued survival.[2] In natural evolution, how well an individual performs depends on its competitors and collaborators, as well as the environment. Genetic algorithms are a simulation of natural selection on a population of candidate solutions to an optimization problem (chromosomes, individuals, creatures, or phenotypes).

Candidates are evaluated and crossbred in an attempt to make good solutions. Such solutions may be very time consuming and unobvious to a human. An evolutionary phase is started with a population of randomly generated entities. In each generation, the fitness of every individual in the population is evaluated. Some are randomly selected from the current population (based on their fitness) and modified (recombined and possibly randomly mutated) to form a new population. The cycle repeats with this new population. The algorithm ends either after a set number of generations have passed, or a satisfactory fitness level has been reached for the population. If the algorithm has terminated due to a maximum number of generations, a satisfactory will not necessarily have been obtained.

Programming this on a computer

The pseudocode is:

  1. Initialization: A number of candidate solutions is generated; very often these have random values
  2. Evaluation: A fitness function allows to score each candidate; the score will be a number that tells how good this solution solves the problem.
  3. The following steps are run until a stop criterion is met:
    1. Selection: Pick the solutions/individuals for the next iteration
    2. Recombination: Combine the solutions picked
    3. Mutation: Randomly change the newly generated solutions
    4. Evaluation: Apply the fitness function, see step 2.
    5. If the stop criterion is not met, re-start with the selection step.

Example

The above description is abstract. A concrete example helps.

Applications

In general

Problems which appear to be particularly appropriate for solution by genetic algorithms include timetabling and scheduling problems. Genetic algorithms have also been applied to engineering.[1] They are often applied as an approach to solve global optimization problems.

As a general rule of thumb genetic algorithms might be useful in problem domains that have a complex fitness landscape as mixing, i.e., mutation in combination with crossover, is designed to move the population away from local optima that a traditional hill climbing algorithm might get stuck in. Observe that commonly used crossover operators cannot change any uniform population. Mutation alone can provide ergodicity of the overall genetic algorithm process (seen as a Markov chain).

Examples of problems solved by genetic algorithms include: mirrors designed to funnel sunlight to a solar collector,[2] antennae designed to pick up radio signals in space,[3] walking methods for computer figures,[4] optimal design of aerodynamic bodies in complex flowfields [5]

In his Algorithm Design Manual, Skiena advises against genetic algorithms for any task:

[I]t is quite unnatural to model applications in terms of genetic operators like mutation and crossover on bit strings. The pseudobiology adds another level of complexity between you and your problem. Second, genetic algorithms take a very long time on nontrivial problems. [...] [T]he analogy with evolution—where significant progress require [sic] millions of years—can be quite appropriate.

[...]

I have never encountered any problem where genetic algorithms seemed to me the right way to attack it. Further, I have never seen any computational results reported using genetic algorithms that have favorably impressed me. Stick to simulated annealing for your heuristic search voodoo needs.

— Steven Skiena[6]: 267 

Board games

Board games are a very relevant part of the area of genetic algorithms as applied to game theory problems. Much of the early work on computational intelligence and games was directed toward classic board games, such as tic-tac-toe,[3] chess, and checkers.[4] Board games can now, in most cases, be played by a computer at a higher level than the best humans, even with blind exhaustive search techniques. Go is a noted exception to this tendency, and has so far resisted machine attack. The best Go computer players now play at the level of a good novice.[5][6] Go strategy is said to rely heavily on pattern recognition, and not just logical analysis as with chess and other more piece-independent games. The huge effective branching factor required for finding high quality solutions heavily restricts the look-ahead that can be used within a move sequence search.

Computer games

The genetic algorithm can be used in computer games to create artificial intelligence (the computer plays against you). This allows for a more realistic game experience; if a human player can find a sequence of steps which always lead to success even when repeated in different games, there can be no challenge left. Conversely if a learning technique such as a genetic algorithm for a strategist can avoid repeating past mistakes, the game will have more playability.

Genetic algorithms require the following parts:

  • A method for representing the challenge in terms of the solution (e.g. routing soldiers in an attack in a strategy game)
  • A fitness or evaluation function in order to determine the quality of an instance (e.g. a measurement of damage done to an opponent in such an attack).

The fitness function accepts a mutated instantiation of an entity and measures its quality. This function is customized to the problem domain. In many cases, particularly those involving code optimization, the fitness function may simply be a system timing function. Once a genetic representation and fitness function are defined, a genetic algorithm will instantiate initial candidates as described before, and then improve through repetitive application of mutation, crossover, inversion and selection operators (as defined according to the problem domain).

History

In 1950, Alan Turing proposed a "learning machine" which would parallel the principles of evolution.[7] Computer simulation of evolution started as early as in 1954 with the work of Nils Aall Barricelli, who was using the computer at the Institute for Advanced Study in Princeton, New Jersey.[8][9] His 1954 publication was not widely noticed. Starting in 1957,[10] the Australian quantitative geneticist Alex Fraser published a series of papers on simulation of artificial selection of organisms with multiple loci controlling a measurable trait. From these beginnings, computer simulation of evolution by biologists became more common in the early 1960s, and the methods were described in books by Fraser and Burnell (1970)[11] and Crosby (1973).[12] Fraser's simulations included all of the essential elements of modern genetic algorithms. In addition, Hans-Joachim Bremermann published a series of papers in the 1960s that also adopted a population of solution to optimization problems, undergoing recombination, mutation, and selection. Bremermann's research also included the elements of modern genetic algorithms.[13] Other noteworthy early pioneers include Richard Friedberg, George Friedman, and Michael Conrad. Many early papers are reprinted by Fogel (1998).[14]

Although Barricelli, in work he reported in 1963, had simulated the evolution of ability to play a simple game,[15] artificial evolution became a widely recognized optimization method as a result of the work of Ingo Rechenberg and Hans-Paul Schwefel in the 1960s and early 1970s – Rechenberg's group was able to solve complex engineering problems through evolution strategies.[16][17][18][19] Another approach was the evolutionary programming technique of Lawrence J. Fogel, which was proposed for generating artificial intelligence. Evolutionary programming originally used finite state machines for predicting environments, and used variation and selection to optimize the predictive logics. Genetic algorithms in particular became popular through the work of John Holland in the early 1970s, and particularly his book Adaptation in Natural and Artificial Systems (1975). His work originated with studies of cellular automata, conducted by Holland and his students at the University of Michigan. Holland introduced a formalized framework for predicting the quality of the next generation, known as Holland's schema theorem. Research in GAs remained largely theoretical until the mid-1980s, when The First International Conference on Genetic Algorithms was held in Pittsburgh, Pennsylvania.

References

  1. ^ Herrera, F.; Lozano, M.; and Verdegay, J. L. 1998. Tackling real-coded genetic algorithms: Operators and tools for behavioural analysis. Artif. Intell. Rev. 12(4):265–319.
  2. ^ Lucas, S., and Kendell, G. 2006. Evolutionary computation and games. In IEEE Comput Intell Mag. February, 10–18. IEEE.
  3. ^ Yao, X. Recent new development in evolutionary programming.
  4. ^ Samuel, A. L. 1995. Some studies in machine learning using the game of checkers. 71–105.
  5. ^ Muller, M. 2002. Computer go. Artif. Intell. 134(1-2):145–179.
  6. ^ Bouzy, B., and Cazenave, T. 2001. Computer go: an AI oriented survey. Artificial Intelligence 132:39–103.
  1. ↑ Tomoiagă B, Chindriş M, Sumper A, Sudria-Andreu A, Villafafila-Robles R. Pareto Optimal Reconfiguration of Power Distribution Systems Using a Genetic Algorithm Based on NSGA-II. Energies. 2013; 6(3):1439-1455.
  2. ↑ Gross, Bill. "A solar energy system that tracks the sun". TED. Retrieved 20 November 2013.
  3. ↑ Hornby, G. S.; Linden, D. S.; Lohn, J. D., Automated Antenna Design with Evolutionary Algorithms (PDF)
  4. ↑ "Flexible Muscle-Based Locomotion for Bipedal Creatures".
  5. ↑ Evans, B.; Walton, S.P. (December 2017). "Aerodynamic optimisation of a hypersonic reentry vehicle based on solution of the Boltzmann–BGK equation and evolutionary optimisation". Applied Mathematical Modelling. 52: 215–240. doi:10.1016/j.apm.2017.07.024. ISSN 0307-904X.
  6. ↑ Skiena, Steven (2010). The Algorithm Design Manual (2nd ed.). Springer Science+Business Media. ISBN 978-1-849-96720-4.
  7. ↑ Turing, Alan M. (October 1950). "Computing machinery and intelligence". Mind. LIX (238): 433–460. doi:10.1093/mind/LIX.236.433.
  8. ↑ Barricelli, Nils Aall (1954). "Esempi numerici di processi di evoluzione". Methodos: 45–68.
  9. ↑ Barricelli, Nils Aall (1957). "Symbiogenetic evolution processes realized by artificial methods". Methodos: 143–182.
  10. ↑ Fraser, Alex (1957). "Simulation of genetic systems by automatic digital computers. I. Introduction". Aust. J. Biol. Sci. 10 (4): 484–491. doi:10.1071/BI9570484.
  11. ↑ Fraser, Alex; Burnell, Donald (1970). Computer Models in Genetics. New York: McGraw-Hill. ISBN 978-0-07-021904-5.
  12. ↑ Crosby, Jack L. (1973). Computer Simulation in Genetics. London: John Wiley & Sons. ISBN 978-0-471-18880-3.
  13. ↑ 02.27.96 - UC Berkeley's Hans Bremermann, professor emeritus and pioneer in mathematical biology, has died at 69
  14. ↑ Fogel, David B. (editor) (1998). Evolutionary Computation: The Fossil Record. New York: IEEE Press. ISBN 978-0-7803-3481-6. {{cite book}}: |first= has generic name (help)
  15. ↑ Barricelli, Nils Aall (1963). "Numerical testing of evolution theories. Part II. Preliminary tests of performance, symbiogenesis and terrestrial life". Acta Biotheoretica. 16 (16): 99–126. doi:10.1007/BF01556602.
  16. ↑ Rechenberg, Ingo (1973). Evolutionsstrategie. Stuttgart: Holzmann-Froboog. ISBN 978-3-7728-0373-4.
  17. ↑ Schwefel, Hans-Paul (1974). Numerische Optimierung von Computer-Modellen (PhD thesis).
  18. ↑ Schwefel, Hans-Paul (1977). Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie : mit einer vergleichenden Einführung in die Hill-Climbing- und Zufallsstrategie. Basel; Stuttgart: Birkhäuser. ISBN 978-3-7643-0876-6.
  19. ↑ Schwefel, Hans-Paul (1981). Numerical optimization of computer models (Translation of 1977 Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie. Chichester ; New York: Wiley. ISBN 978-0-471-09988-8.
Retrieved from "https://simple.wikipedia.org/w/index.php?title=Genetic_algorithm&oldid=6615845"