SMART Operator Fitness

 

In any evolutionary computation, the fitness measure is largely responsible for directing the system's search. The fitness measure embodies any explicit goals of the system and largely determines the kind of behaviors that are produced. In a qualitative way we all know what we mean by a ``good'' operator and a ``bad'' one. What we need however is a quantitative measure for the fitness to drive our SMART operator populations.

The goal of the system with respect to the main population is to maximize the fitness of the maximally fit individual (or occasionally top few individuals) in the main population. At least while a perfect solution has not been reached most researchers assume that there is a strong correlation between the rise in average population fitness and maximum population fitness. Given this scant knowledge, what should a fitness measure of operators be?

The application of SMART operator programs to a main population of programs is not dependent on the particular choice of fitness measure, as long as that fitness measure is really an approximation to what we mean by a ``good'' operator. Let us propose one metric which is simple to understand and to measure. It is given here not to end the discussion on this subject but to ground the experiments and discussions in the rest of this chapter.

In any kind of recombination, the operator takes one or more programs out of the main population, changes them, and replaces them in the population. The fitness of the operator should be a function of the behavior of each input program and the output program that replaced it in the main population. In addition, the mechanism of evolutionary computation is such that when a program has low fitness, we do not care exactly how bad it is. We care when a program has high fitness relative to the population fitness distribution.

  
Table 3.3: Hypothetical Recombinations

The main justification for the fitness measure below is that we want to produce programs that are strictly more fit than their parents at least some of the time. In case 1 of table 3.3 the recombination leads to the same ratio of child to parent fitness as in case 2. However since our goal is really to maximize the child-parent fitness ratio only for fitness improvements, case 2 is probably the one that should return higher fitness to the operator that created it.

In examples 3 and 4, we see that both replacement pairs in the main population include one improvement. In this extreme comparison the fitness ratio is five for the Parent1 Child1 operator action in case 3 and is a fitness ratio of two for the Parent2 Child2 operator action in case 4. Even in this situation we would like the operator that caused these changes to be rewarded higher for case 4 than for case 3 because the total fitness increase is larger. The desire to weight these cases as described is why (M below) is added to the numerator and denominator when the fitness ratios are summed.

Let be the fitness of some program V to be recombined.

Let be the fitness of the program output to replace V in the main population.

Let be the set of all trials on a particular generation for some operator X such that . is the number of programs output by operator X whose fitness is strictly greater than the fitness of the input program it is replacing in the population.

Let be the number of main population programs given to operator X to recombine.

Let M be the maximum fitness a main population program can have.

And define

Given these definitions let us define the fitness of an operator ( ) as:

 

In English, the fitness of an operator translates to:

The percentage of the time that the main population program the SMART operator program places back in the main population is more fit than the main population program it is replacing (this is the part of equation 3.3) TIMES a fitness measure (relative to M) of how much more fit the improved programs are than the programs they replace (this is the part of equation 3.3).

As a final note about operator fitness, the question arises, ``What fitness does a SMART operator receive that does not split its input programs into two sets each?'' Such an operator reverts to the random operator, so that the main population is not punished for the failing of that SMART operator (more on that subject in section 3.6). The answer, at least for the experiments and discussions in this chapter, is that such a SMART operator receives no fitness boost, even if the random operator to which it has reverted to performs well. The rationale for this strategy is that there is a period of ``dumbness'' (the first few generations) that the SMART operators have to go through to reach more intelligent recombination strategies. There is less pressure on the SMART operators to learn during this period if the random operator, acting as back up for the inept SMART operators, provides these inept SMART operators with non-zero fitness.