Genetic algorithm
 | The English used in this article or section may not be easy for everybody to understand. (December 2015) |
 | This article uses too much jargon, which needs explaining or simplifying. (December 2015) |
 | An editor is changing this article for a short while. This is called a major change. Please do not change this article. The person who added this notice will be shown in the change history of this article. If this article has not been changed recently, please remove this template to let others change it. This message is to help stop change conflicts. This article was last changed by Eptalon (20-07-2019 · see diff) |
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:
- Initialization: A number of candidate solutions is generated; very often these have random values
- Evaluation: A fitness function allows to score each candidate; the score will be a number that tells how good this solution solves the problem.
- The following steps are run until a stop criterion is met:
- Selection: Pick the solutions/individuals for the next iteration
- Recombination: Combine the solutions picked
- Mutation: Randomly change the newly generated solutions
- Evaluation: Apply the fitness function, see step 2.
- If the stop criterion is not met, re-start with the selection step.
Example
The above description is abstract. A concrete example helps.
Applications
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).
References
- ^ 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.
- ^ Lucas, S., and Kendell, G. 2006. Evolutionary computation and games. In IEEE Comput Intell Mag. February, 10–18. IEEE.
- ^ Yao, X. Recent new development in evolutionary programming.
- ^ Samuel, A. L. 1995. Some studies in machine learning using the game of checkers. 71–105.
- ^ Muller, M. 2002. Computer go. Artif. Intell. 134(1-2):145–179.
- ^ Bouzy, B., and Cazenave, T. 2001. Computer go: an AI oriented survey. Artificial Intelligence 132:39–103.