Genetic Programming (GP) is a research area in artificial intelligence which attempts to solve computer problems using a model of evolution and natural selection. In this model, the computer creates a population of creatures, each of which are computer programs. In most implementations of GPs, these programs come in the form of rooted tree structures. Each node with children represents an operation, such as plus or minus. The children of that node are taken as the arguments to the operation. So, in order to execute a tree, the children of the node are first evaluated, and these results are inputted in to the operation of the node.
In all GP problems, there is a given task that each program, or creature, must try to accomplish. In this project, that task was to direct traffic signals in a network of streets so that the traffic flow was maximized. In other problems, the task might be to compute the average of a set of numbers. With this in mind, we can determine a creature's fitness level by how well it accomplishes its task. This evaluation function takes in a genetic programming creature, executes it, and assigns a ranking of it based on its performance. In a problem that attempts to compute the average of a set of numbers, this ranking might be how close the creature's result was to the actual average of the numbers. So, the closer the creature is to the true value, the better its fitness level, and the more likely it will survive in the population.
After the initial population of creatures have been evaluated and ranked, new populations of creatures are created and evaluated through an iterative process of removing the worst creatures (programs with the worst ranking) and being replaced by new creatures generated through computer analogies of mating and mutating. Crossover operators, the analogy of program mating, uses two creatures to generate a new creature by combining parts of the parents. Mutator operators take in a single creature and randomly change parts of it, to generate a new creature. In both of these operators, the parents that are used are chosen according to fitness level. In this way, the better performing creatures reproduce more often.
In this manner, the population is continually evolving. After many generations, the best programs that solve the problem should appear in the population and begin to denominate. In this way, the population converges to a creature that, hopefully, solves the problem a near optimal manner.