A genetic algorithm (GA) is a search technique used in computing to find exact or approximate solutions to optimization and search problems.
In artificial intelligence, genetic programming (GP) is an evolutionary algorithm-based methodology inspired by biological evolution to find computer programs that perform a user-defined task.
Genetic programming (GP) is a specialization of genetic algorithms where each individual is a computer program.
Genetic algorithms are a kind of algorithm used to find approximations in search problems. Genetic algorithms are a class of evolutionary algorithms that use ideas inspired by evolution to find a solution.
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 categorised as global search heuristics, and have a wide variety of applications, particularly in generating useful Artificial Intelligence agents in computer games.
For decades, games and the field of game theory have provided competitive, dynamic, often unpredictable environments that make ideal test beds for computational intelligence theories, architectures, and algorithms. Natural evolution can be modelled as a game, in which the rewards for an organism that plays a good game of life are the propagation of its genetic material to its successors and its continued survival. In natural evolution, the performance of an individual is defined with respect to its competitors and collaborators, as well as to the environment. More simply described, genetic algorithms are a simulation in which a population of abstract representations (called chromosomes or the genotype of the genome, after their biological counterparts) of candidate solutions (called individuals, creatures, or phenotypes) to an optimisation problem.
Candidates are evaluated and crossbred in an attempt to generate high quality solutions which would be non obvious and extremely time consuming to a human programmer. An evolutionary phase is initialised with a population of randomly generated entities (or human specified instances of high quality). The process is subdivided into different generations. In each generation, the fitness of every individual in the population is evaluated, and multiple individuals are stochastically selected from the current population (based on their fitness), and modified (recombined and possibly randomly mutated) to form a new population. The new population is then used in the next iteration of the algorithm. The algorithm terminates when either a maximum number of generations has been produced, 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.
Genetic Algorithm Applications
Genetic algorithms have been successfully used in many fields of computer science, including but not limited to the optimisation of complex algorithms, the training of text classification systems, and the evolution of intelligent artificial agents in stochastic environments.
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, chess, and checkers. 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. 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 Template:Branching factor required for finding high quality solutions heavily restricts the look-ahead that can be used within a move sequence search.
The genetic algorithm can be utilised in computer games - for example, to allow an enemy opponent to adapt in order to cater against an effective but repetitive tactic exhibited by a human player. This allows for a more realistic game experience; if a human player can find a sequence of steps which, repeated in different games always lead to success, 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 increased playability.
Genetic algorithms require the following components:
- 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 customised to the problem domain. In many cases, particularly those involving code optimisation, 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 previously, and then improve through repetitive application of mutation, crossover, inversion and selection operators (as defined according to the problem domain).
The concept of having a full or partial view of the game changes the approach required significantly. An important point to note is that despite a computer obviously having a full view of the game state, making this fully available to the decision making process of an artificial player is going to make them behave unrealistically. Human-centered games are limited by what can easily be manipulated given human mental capacity and dexterity. Video games, on the other hand, operate under no such constraints and typically have a vastly more complex (internal) state space than even the most complex of human-centered games. This richer complexity encourages the development or evolution of more general purpose AI agents than are necessary for playing board or card games with sufficiently simulated skill levels. Currently, most computer controlled players in games implemented using manual scripting, which is quite tedious and time consuming to develop and test. The use of computational intelligence techniques offers an interesting alternative to scripted approaches, whereby the agent behavior can be controlled using an evolved neural network, for example, rather than being programmed. Since such a neural approach may result in unique, novel behaviour impossible to achieve with manual implementation, the resulting quality of the product could be far higher. Such approaches often result in significantly more original results for every different player, the replayability of the game is extended. Furthermore, evolved AI players tend to be excellent at exploiting loopholes in a game. Identifying and eliminating these elements (which are seen as problems by the players/developers) can be achieved by genetic algorithms. In addition to this, through the life of a game, human players will also discover these, giving them an unfair advantage. If an AI player can also take advantage of these, the playing field is levelled. To have game characters that effectively exhibit such “human” characteristics improves the game, extends its lifetime, and increases total revenue. These techniques must be developed very carefully, especially in cases where agent difficulty is curved to compete fairly with the player. It has been an established technique in such games for a human player to intentionally play badly earlier on in the game, thus easing the difficulty; which in the end will decrease the quality and longevity of the game. Unfortunately, players tend to blame the developer for allowing it to be possible.
Genetic programming (GP) is an evolutionary algorithm based methodology inspired by biological evolution to find computer programs that perform a user-defined task. Therefore it is a machine learning technique used to optimize a population of computer programs according to a fitness landscape determined by a program's ability to perform a given computational task. The roots of GP begin with the evolutionary algorithms first utilized by Nils Aall Barricelli in 1954 as applied to evolutionary simulations but evolutionary algorithms became widely recognized as optimization methods as a result of the work of Ingo Rechenberg in the 1960s and early 1970s - his group was able to solve complex engineering problems through evolution strategies (1971 PhD thesis and resulting 1973 book). Also highly influential was the work of John Holland in the early 1970s, and particularly his 1975 book. The first results on the GP methodology were reported by Stephen F. Smith (1980) and Nichael L. Cramer (1985),. In 1981 Forsyth reported the evolution of small programs in forensic science for the UK police. John R. Koza is a main proponent of GP and has pioneered the application of genetic programming in various complex optimization and search problems.
GP is very computationally intensive and so in the 1990s it was mainly used to solve relatively simple problems. But more recently, thanks to improvements in GP technology and to the exponential growth in CPU power, GP produced many novel and outstanding results in areas such as quantum computing, electronic design, game playing, sorting, searching and many more. These results include the replication or development of several post-year-2000 inventions. GP has also been applied to evolvable hardware as well as computer programs. There are several GP patents listed in the web site.
Developing a theory for GP has been very difficult and so in the 1990s GP was considered a sort of outcast among search techniques. But after a series of breakthroughs in the early 2000s, the theory of GP has had a formidable and rapid development. So much so that it has been possible to build exact probabilistic models of GP (schema theories and Markov chain models).
A function represented as a tree structure
GP evolves computer programs, traditionally represented in memory as tree structures. Trees can be easily evaluated in a recursive manner. Every tree node has an operator function and every terminal node has an operand, making mathematical expressions easy to evolve and evaluate. Thus traditionally GP favors the use of programming languages that naturally embody tree structures (for example, Lisp; other functional programming languages are also suitable).
Non-tree representations have been suggested and successfully implemented, such as the simpler linear genetic programming which suits the more traditional imperative languages. The commercial GP software Discipulus, uses AIM, automatic induction of binary machine code to achieve better performance. MicroGP uses a representation similar to linear GP to generate programs that fully exploit the syntax of a given assembly language.
The main operators used in evolutionary algorithms such as GP are crossover and mutation. Crossover is applied on an individual by simply switching one of its nodes with another node from another individual in the population. With a tree-based representation, replacing a node means replacing the whole branch. This adds greater effectiveness to the crossover operator. The expressions resulting from crossover are very much different from their initial parents.
The following code suggests a simple implementation of individual deformation using crossover:
individual. Children[randomChildIndex] = otherIndividual.Children[randomChildIndex];
Mutation affects an individual in the population. It can replace a whole node in the selected individual, or it can replace just the node's information. To maintain integrity, operations must be fail-safe or the type of information the node holds must be taken into account. For example, mutation must be aware of binary operation nodes, or the operator must be able to handle missing values.
A simple piece of code:
individual. Information = randomInformation;
individual = generateNewIndividual;
Meta-Genetic Programming is the proposed meta learning technique of evolving a genetic programming system using genetic programming itself. It suggests that chromosomes, crossover, and mutation were themselves evolved, therefore like their real life counterparts should be allowed to change on their own rather than being determined by a human programmer. Meta-GP was proposed by Jürgen Schmidhuber in 1987; it is a recursive but terminating algorithm, allowing it to avoid infinite recursion.
Critics of this idea often say this approach is overly broad in scope. However, it might be possible to constrain the fitness criterion onto a general class of results, and so obtain an evolved GP that would more efficiently produce results for sub-classes. This might take the form of a Meta evolved GP for producing human walking algorithms which is then used to evolve human running, jumping, etc. The fitness criterion applied to the Meta GP would simply be one of efficiency.
For general problem classes there may be no way to show that Meta GP will reliably produce results more efficiently than a created algorithm other than exhaustion. The same holds for standard GP and other search algorithms, of course.
Source: Wikipedia (All text is available under the terms of the GNU Free Documentation License and Creative Commons Attribution-ShareAlike License.)