Genetic Programming
Genetic Programming: A Separate Entity?
Genetic programming is the chief application of genetic algorithms. The output of the genetic algorithm is a quantity, while the output of the genetic programming is a another computer program. In essence, this is the beginning of computer programs that program themselves.
Some GP scientists however believe that GP and GA are completely separate entities each with their own characteristics.
Genetic Programming is however inherently quite different from all other approaches to artificial intelligence, machine learning, neural networks, adaptive systems, reinforcement learning, or automated logic in that it is Biologically inspired; it conducts its search for a solution to problem within program space and it does not conduct its search by transforming a single point in the search space into another single point, but instead transforms a set of points into another set of points.
What is Genetic Programming?
Essentially, Genetic programming (GP) is an automated methodology inspired by biological evolution to find computer programs that best perform a user-defined task. It is therefore a particular machine learning technique that uses an evolutionary algorithm to optimize a population of computer programs according to a fitness landscape. The main goal of GP is to be able to tell the computer what task is to be performed and have it learn to perform that work, rather than programming the computer exactly how to do every possible task we want the computer to carry out.
Essentially Genetic Programming allows computers to solve problems without the users having to specify the methodology i.e. how it should be done. It achieves this goal of automatic programming (also sometimes called program synthesis or program induction) by genetically breeding a population of computer programs using the principles of Darwinian Natural Selection and biologically inspired operations. Specifically, genetic programming iteratively transforms a population of computer programs into a new generation of programs by applying analogs of naturally occurring genetic operations. The genetic operations include crossover (illustrated above), mutation, reproduction, gene duplication, and gene deletion.
As this process was very computationally intensive, it was mainly used to solve simple problems. The dawn of the 21st century brought with it rapid developments in the field of GP. This development was enhanced by growing CPU power and extensive research in parallel computing. GP has gone on to cease as a "theoretical pariah" and has delivered outstanding results in areas as diverse as quantum computing, electronic design, game playing, sorting, searching and many more.
Traditionally a generational evolutionary algorithm is used by Genetic programming. In GP a well-defined distinct generations is found to exist and this each such generations can be represented by a complete population of individuals. The newer population is created from the old population and then it replaces the former population.
The GP cycle can be simplified by the following steps:- A population is first initialized.
- Individual programs of the population are evaluated and numerical ratings or fitness is assigned to them.
- The following steps are carried out as long as the new population is fully populated:
- Individual(s) from the population are selected using the selection algorithm.
- Genetic operations are performed on the selected individuals.
- The results of the genetic operations are inserted in the new population.
- The termination condition if fulfilled in this step then continue to execute otherwise replace the existing population with the new population and the step 2-4 is repeated.
- The best individual outputs from each population are presented as result.
Genetic programming works best for several types of problems. The first type is where there is no ideal solution, (for example, a program that drives a car). There is no one solution to driving a car. Some solutions drive safely at the expense of time, while others drive fast at a high safety risk. Therefore, driving a car consists of making compromises of speed versus safety, as well as many other variables. In this case genetic programming will find a solution that attempts to compromise and be the most efficient solution from a large list of variables.
Furthermore, genetic programming is useful in finding solutions where the variables are constantly changing. In the previous car example, the program will find one solution for a smooth concrete highway, while it will find a totally different solution for a rough unpaved road.