Genetic programming operators

The four general genetic operators are: crossover, reproduction, mutation, and inversion. The following overview describes each in brief.

  
Figure 2: The effect of a crossover operation. Figures 6.5 and 6.7, Koza

• crossover Koza considers crossover, along with reproduction, to be the two foremost genetic operations. It is mainly responsible for the genetic diversity in the population of programs. Similar to its performance under genetic algorithms, crossover operates on two programs (a binary operator), and produces two child programs. Two random nodes are selected from within each program and then the resultant ``sub-trees'' are swapped, generating two new programs. These new programs become part of the next generation of programs to be evaluated. See Figure 2.
• reproduction Reproduction, the second main operation, is performed by simply copying a selected member from the current generation to the next generation. An interesting note about convergence of the population using the two main operators is made by Koza:

  ... in genetic programming, when an individual incestuously mates with itself (or copies of itself), the two resulting offspring will, in general, be different.... As before, the Darwinian reproduction operation creates a tendency toward convergence; however, in genetic programming, the crossover operation exerts a counterbalancing pressure away from convergence. Thus, convergence of the population is unlikely in genetic programming.

• mutation With genetic algorithms, mutation becomes an important operator which provides diversity to the population. As Koza points out, however, mutation is relatively unimportant in the new environment, because the dynamic sizes and shapes of the individuals in the population already provide diversity, and as stated above, the population should not converge. Thus, mutation can be considered as a variation on the crossover operation.
• inversion (permutation) Koza states that the effectiveness of this operation has never been conclusively demonstrated, so he basically dismisses its use in his book.