The SMART recombination programs need the ability to examine their input programs in sufficient detail to make an informed decision. The SMART recombination programs need to be able to indicate their specific decisions. For SMART recombination operator programs this specification should take the form of ``Here are the subsets of the two input programs to be exchanged.'' Like the main population programs, the SMART recombination programs are given the standard PADO actions (see section 3.3.2). Table 3.2 shows the SMART operator special actions.
Table 3.2: The special actions given to the SMART recombination programs.
When a SMART recombination program is run, it continues until it executes special action 13 or the time-threshold is reached, whichever comes first. Whichever does occur, the program is halted and the two sets ( and ) the SMART recombination operator was responsible for building up are examined. If both sets have at least 1 and no more than -1 elements in them (i.e., if the exchange will be a meaningful recombination) then the recombination is performed (see beginning of section 3.4). Otherwise, as will be discussed in section 3.4.5, random recombination is performed on the two input programs and the SMART recombination operator receives 0 fitness for that trial.
One of the most important special actions is special action eight. This action sets to a random sized subset of randomly selected nodes from where i is specified (to be 0 or 1) by the single argument this action takes. In short, this is the random operator that the SMART operators are competing against. This is exactly why the SMART operator paradigm is safe to incorporate into the standard GP tool box: this primitive has to be written anyway (since it is the random operator the system uses). In addition, if we improve the random operator and install this improved version in our system, then the SMART operators, as well as the random operator, will reap the benefits.
Of course, if this were the only special action primitive there would be nothing to lose from the SMART operators, but also nothing to gain. If, however, the SMART operators are given the power either to build up sets from scratch, or to purposefully alter randomized node sets they had requested (from SA-8), then there is a potential for general operator improvement. While we believe that all of the special actions listed in table 3.2 give this potential power, SA-5 and SA-7 are of particular interest. Programming a depth-first traversal in a graph is non-trivial. SA-5 and SA-7 make such traversals possible (for the special cases of adding and deleting set nodes) through repeated applications of a single action. A few well thought out special actions can make a difficult computation easy.