Genetic Operators in Evolutionary AlgorithmsDecember 23, 2019 by Greg Schmidt
Learn about genetic operators and their role in future algorithms for automation.
Welcome to Control Automation's series on genetic programming. You can check out the rest of the series below before moving on to this article:
- An Introduction to Genetic Programming: The “Holy Grail” of Systems that Can Author Themselves
- Genetic Operators in Evolutionary Algorithms (you are here)
- Evolving a Sorting Program and Symbolic Regression
- Applications and Limitations of Genetic Programming
As we introduced in the last article, genetic programming is a method of utilizing genetic algorithms, themselves related to evolutionary algorithms.
In this article, we'll discuss genetic operators, the building blocks of writing a functional genetic programming algorithm.
Fitness Proportionate Reproduction
Fitness proportionate reproduction simulates a form of Darwinian selection analogous to "survival of the fittest." Without selection pressure, no force would drive the population toward finding better solutions. For each generation, a predetermined fraction of the population is selected and copied to the next generation.
Selection is performed in the usual way and is typically roulette wheel selection or tournament selection.
Roulette Wheel Selection
Roulette wheel selection is analogous to conducting a lottery involving the entire population where each individual holds some number of lottery tickets. The number of tickets held by an individual is in direct proportion to the fitness of that individual.
Tournament selection is roughly analogous to a competition held among a small group of individuals. K programs are randomly picked from the population. The fitness of each program is examined and the program that is most fit "wins" the tournament and is thereby selected. Tournament selection with a tournament size (k) of seven has been empirically shown to work well for a number of problems. Tournament selection has the additional advantage of being easy to implement.
Crossover is performed by using the selection operator to pick two parent programs and then "mating" them.
First, a random node (locus) in each program tree is selected. Since a tree is a
recursive structure, each node can be considered to be the root of some other tree, a subtree within its respective parent program tree.
Note that a tree may consist of a single node as is the case when a terminal node is selected. These subtrees are exchanged thus forming two, potentially new, offspring programs, as shown in Figure 1.
Figure 1. Crossover of two programs
Crossover introduces novelty into the population. As in a GA, it is believed that over time, it becomes likely that an "offspring" program will contribute useful subtrees or "building blocks" (often referred to as "schema" in GA terminology) of genetic code that lead to increased fitness in their host programs and therefore will tend to propagate quickly.
Mutation can be performed by first randomly selecting a single program and then randomly selecting a node within that program tree. The subtree rooted at this node is then replaced by a
new randomly generated subtree, as shown in Figure 2.
Figure 2. Mutating a program. Here, mutation occurs at node #5
The main benefit of mutation is to periodically inject new genetic material (functions and terminals) that may no longer be present in the current population. The value of mutation in GP is arguable and many successful results have been obtained in its absence.
At first glance it may seem highly improbable, if not impossible, to apply genetic operators to a computer program with the expectation that the result will be syntactically correct or otherwise yield any sort of meaningful result. This problem is addressed by enforcing a property called "closure", which ensures that the value produced by evaluating any function or terminal can be provided as an argument to any other function. The closure property holds for our XOR problem above since all nodes consistently accept and return Boolean values. Some experimental work has been done to relinquish the need for closure through the use of a modified set of genetic operators that preserves type compatibility.
Genetic Programming Example Algorithm
An initial generation is created consisting of a population of randomly generated individuals. The genetic operators are applied to individuals within each generation until enough individuals are available to populate the next generation. Whenever a new individual is created, it is evaluated and a fitness measure is assigned to it. Obviously, if an individual is merely selected for reproduction, reevaluation of its fitness is unnecessary.
The process of applying genetic operators to a current population to produce a new population is repeated for successive generations until a specified termination condition is satisfied. The termination criterion for the run can be based upon finding an individual that has reached a target fitness measure or we may simply quit after a fixed number of generations.
Putting it all together, we obtain the algorithm outlined in Listing 1.
Generate an initial random population within CURRENT_POPULATION NEXT_POPULATION := EMPTY WHILE termination criterion not met /* Perform Crossover */ WHILE less than f_XOV*PSIZE/2 individuals have been selected select a pair of parent individuals crossover the two parent individuals producing a pair of offspring calculate the fitness of each new offspring add the two offspring to NEXT_POPULATION END WHILE /* Perform Mutation */ WHILE less than f_MUT*PSIZE individuals have been selected select an individual apply the mutation operator to the individual calculate the fitness of the mutated individual add the mutated individual to NEXT_POPULATION END WHILE /* Perform Reproduction */ WHILE less than f_FPR*PSIZE individuals have been selected select an individual copy the individual to NEXT_POPULATION END WHILE /* NEXT_POPULATION now contains PSIZE individuals */ CURRENT_POPULATION := NEXT_POPULATION NEXT_POPULATION := EMPTY END WHILE Constants: f_FPR - Fitness proportionate reproduction fraction (0.19) f_XOV - Crossover fraction (0.80) f_MUT - Mutation fraction (0.01) PSIZE - Number of individuals in the population (500) Note that the parenthesized values above are merely suggested values
Listing 1. High-level outline of the GP algorithm
Genetic programming represents a future revolution in algorithm development. The above example algorithm will help introduce you to how this concept could change the way automation functions in the future.
In the next article, we'll discuss symbolic regression and take a look at an example of evolving a sorting program.