Genetic Operators in Evolutionary Algorithms

Welcome to Control Automation's series on genetic programming. You can check out the rest of the series below. 

• An Introduction to Genetic Programming: A System That Programs Itself?
• Genetic Operators in Evolutionary Algorithms (you are here)
• Genetic Algorithm Examples: 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.

 

Genetic Operators in Genetic Algorithms

 

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. 

Roulette Wheel and Tournament Selection

Selection is performed in the usual way and is typically roulette wheel selection or tournament 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 numerous problems. Tournament selection has the additional advantage of being easy to implement.

 

Crossover

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 genetic algorithm (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 leads to increased fitness in their host programs and therefore will tend to propagate quickly.

 

Mutation

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 genetic programming (GP) is arguable and many successful results have been obtained in its absence. 

 

Closure

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 exclusive or (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 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. A high-level outline of the GP algorithm.

 

---

 

GP represents a future revolution in algorithm development. The above example algorithm helps 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.