The basic function of a genetic recombination operator is to take K (usually two) programs as input and to produce some (usually K) new programs as output that replace the input programs in the population from which they were drawn. The context of the PADO representation lead to the need for recombination (crossover) of two arbitrary graphs. Partly because the ``right'' way to do graph recombination is not obvious, learning how to do graph recombination intelligently is a natural desire.
The SMART operators are programs that learn to do this graph crossover better than recombination operators acting at random. These SMART recombination operators co-evolve with the main population. Like the programs in the main population, the programs in the SMART operator population may begin as randomly generated programs. The programs in this SMART operator population are tested by allowing them to actually perform the recombinations on the main population. Their fitness values are a function of the relative fitness of the programs they take as input and the fitness of programs they produce as output. Our current research is studying ways to co-evolve the complete recombination paradigm. For this chapter, however, the recombination paradigm was fixed as shown below.
There is an important distinction between intelligent recombination in a particular recombination paradigm and an intelligent recombination paradigm. For example, in GP the standard recombination paradigm is crossover. A particular crossover between two parent programs requires choosing two subtree roots to exchange. The selection of these two roots can be done intelligently [Teller and Veloso 1995c] or randomly. There is an entirely different issue of whether the entire method of recombination (in this example crossover) is optimal. Part of our ongoing research effort is the more ambitious goal of learning the whole paradigm of recombination. Even if we constrain ourselves to a fixed recombination paradigm there is still room for smartness in this new representation. The paradigm for recombination on which this chapter will focus (as was used in the experiments) is as follows.
We could evolve both how to pick and how to reconnect the fragments. For this chapter, how they are reconnected is fixed as described above. In this constrained example, the only room for ``smartness'' in a recombination operator is, given two programs, to choose the fragments of those two programs that are likely to lead to highly fit new programs. Section 3.5 will show that we can co-evolve a subset selection strategy that is considerably better than random. The following subsections will provide necessary detail on the co-evolution of the SMART operators and the recombination strategy they will be compared against.