Genetic Heuristic for Search Space Exploration

1 Introduction

1.1 Genetic algorithms

Genetic algorithms are adaptive systems inspired from Darwin's theories on natural evolution. Their fundamen­ tal bases were defined twenty five years ago by Holland ([Holland, 1975]) in his book on natural and artificial adaptation. Much works have been done since, in par­ ticular to improve their function optimization abilities ([Goldberg, 1989]).

The basic algorithm is simple: an initial population of N individuals is randomly drawn and evaluated given a fitness function; according to this fitness value, the in­ dividuals are allowed to reproduce in such a way that the number of expected children of each individual is proportional to the fitness; children are mated together, mutated, in order to obtain a new population of size N; and the algorithm loops until a stop condition is reached. Individuals may be problem solutions, function parame­ ters, and so on.

Improvements consist in modifying the evaluation step, the reproduction step, the mating and mutation step, or even the algorithm itself. But the main prob­ lem is always to choose an appropriate representation for the individuals. Dualism was introduced in order to by­ pass this problem by having an algorithm less sensitive to representation shortcomings.

a measure of difficulty for a genetic algorithm.

The definition of the fitness distance correlation (Foe) is quite simple. Given a set F = {h, /2, ... , fn} of fit­ ness values from n individuals and the corresponding set D = { d1, d2 , . . . , dn} of distances from them to the near­ est optimum, the correlation coefficient is calculated as:

is the covariance of F and D , and u F, u D, f and d are the standard deviations and means of F and D.

From the correlation coeffiCient r, problems may be divided in three classes:

1. deceptive problems (r 2: 0.15), for which the fit­ ness increases with the distance to optimum.
2. hard problems ( -0.15 < r < 0.15), for which there is no correlation between fitness and distance.
3. easy problems (r ~ -0.15) , for which the fitness increases when the distance decreases.

Hard problems are in fact hard to predict, since in this case, the FDC brings little information. So, Jones recom­ mends to examine the scatter plot distance vs. fitness, especially when r is near zero. This allows to distinguish between a problem such as a needle in a haystack (NIAH) from a problem with a symmetrical scatter plot, for ex­ ample. They both have a null coefficient, but NIAH is a hard problem, while there are symmetrical problems which are easy.

Jones recommends to use distances related to genetic operators. However, it is not sure that such distances exist, and if so, that they are easily computable. Jones claims that Hamming distance allows a first approxima­ tion of a FDC more related to the operators.

In order to validate the accuracy of the FDC, Jones uses it on problems with known difficulty. Results show undoubtedly the predictive ability of the FDC, even cal­ culated with Hamming distance.

These results are surprising, since the distances ac­ tually implied by operators are not taken into account. The only operator taken into account is the mutation, as the Hamming distance between two individuals is di­ rectly related to the number of bit flips to pass from one individual to the other.

Altenberg ([Altenberg, 1997]) goes further. He says the fact that the FDC is only a statistical and static mea­ sure, based on a distance which is apparently only bound to mutation, implies two assumptions: either Hamming distance is connected to the way genetic algorithms work; or this relation exists in a fortuitous way among the test set chosen by Jones. In which case, counter examples exist for which this relation does not hold, and which, therefore, deceive the FDC.

Since there seems that there is no relation between re­ combination operators and Hamming distance, and that mutation is supposed to play a marginal role in genetic algorithms, Altenberg claims that it is possible to con­ struct a counter example. The counter example he con­ structs is GA-easy, but the correlation between distance and fitness to optimum is null by construction. Further, the observation of the scatter plot gives no more infor­ mations.

This counter example deceives the Jones' conjecture which claims that if the FDC is close to 0 and if the scatter plot exhibits no particular structure, then the problem is GA-difficult. Moreover, Quick et al. ([Quick et al. , 1998a]) construct a class of problems, called ridge functions, which are GA-easy with a high positive corre­ lation.

While the Altenberg's counter example is prone to dis­ cussion, in particular on the definition of the GA-easiness, the counter example of Quick et al. is clear: there are functions that the FDC predicts misleading and which are in fact easy. Nevertheless, these two counter exam­ ples exploit known weaknesses of the FDC: its nullity for the symmetrical functions and the low contribution of a particular path in the global calculation. Besides, Quick et al. ([Quick et al., 1998b]) recognize that the FDC cal­ culated with the points actually sampled by the GA gives better results.

In a more general way, Naudts and Kallel ([Naudts and Kallel, 1998]) show that a FDC drawback is its great sensibility to non-linear scaling. Kallel and Schoenauer ([Kallel and Shoenauer, 1997]) show in a more formal frame the irrelevance of FDC as performance predictor for GA, in an article judiciously entitled: "no universal statistical measure but a set of hints".

Nevertheless, the success of the FDC on a large number of functions remains an unsolved question. Collard et al. ([Collard et al., 98]) bring some elements of response, exhibiting a correlation between Hamming distance and instability implied by crossover.

3 FDC and Dualism

This section deals with the relations that can be estab­ lished between FDC theory and dualism. In the first part, we define the dual distance that should be used to cal­ culate the FDC in the dual case. In the second part, a conjecture on dynamical behavior of DGA is proposed.

3.1 Dual FDC

The dualism implies two ways to transform an individual X E n to another individual y E n. The first one, called direct, is equivalent to mute the dH(x,y) different bits between x and y. This corresponds to a walk on the boolean hypercube and the associated distance is simply the Hamming distance. The second one is equivalent to get x and y each in a different mirror subspace and to mute the >.- dH(x, y) identical bits, where >. is the chromosome length. This corresponds to a step through the boolean hypercube followed by a walk on it. We called the associated distance the codistance, de. It can be established that :

The 1 is for the step through, and >. - dH(x, y) is the length of the walk on the hypercube.

The dual distance between two individuals from the basic space x andy, is naturally defined as follows :

where dl-1 is the Hamming distance, Ox E (!1) and 1x E (!1) , are the two dual individuals corresponding to x. Since:

where A, is the length of x andy, we get:

A 1 being the length of strings over (!1) (A' = A+ 1). This result expresses that the dual distance between x and y is the minimum of the Hamming distance and the codistance.

The dual distance remains a distance over the basic space !1. But, it can be easily extended to the mirror space (!1). We note (d) the distance over the mirror space (!1) to the nearest optimum. It is easily shown that :

where :i; is the individual of !1 corresponding to x, and x* is the optimum over !1. Thus, there is a correspondence between a distance over (!1) appropriate to calculate a FDC and the dual distance defined over !1.

Now, we are going to study the predictive capacity of the dual FDC on a well known function family, the Trap functions ([Deb and Goldberg, 1993]) . They are defined over the unitation of chromosomes, that is the number of genes set to '1'. They admit two optima, a global one and a local one, one being the logical complement of the other. They are parametrized by two values Xb and r. The first one, Xb allows to set the width of the attractive basin for each optima, and r sets their relative importance. The function fr is so defined by :

where Un(x) is the unitation divided by A, the length of chromosomes (in the experiments, A= 20).

We calculated the exact value of FDC (that is with all the points of !1) , in function of Xb and r. Results are shown on figure 1. They are roughly identical to the Deb & Goldberg [Deb and Goldberg, 1993] ones, who used another theoretical framework to obtain the condi­ tions on Xb and r for which the Trap function is decep­ tive. These results are corroborated by the performance obtained with a "real" GA.

We define performance as the number of runs for which the global optimum is found in less than a given num­ ber of generations (200), divided by the total number of runs (40). The figure 2 presents such performance mea­ sures obtained with a GA on the Trap functions. It is shown that the experimental deceptive area (where per­ formance is less than 0.05) corresponds approximately to the theoretical deceptive area found with the FDC.

For DGA, the predicted deceptive area is less important (figure 3). It can be shown, from figure 4, that there is no couple (xb, r) for which the global optimum is never found. This reinforces the hypothesis made elsewhere ([Collard and Aurand, 1994]) for which there is no totally deceptive problem for DGA.

3.2 Fitness Driven Distance

Now, we are concerned in studying the dynamical be­ haviors of DGA and the relation that can be made with FDC. During evolution, the DGA has to make choices be­ tween direct path and indirect path, that is, for each dual pair, it has to choose between the chromosome and the anti-chromosome. Indeed, keeping both of them implies too much instability. Such a choice cannot be influenced directly by fitness, since dual individuals have, by defini­ tion, the same fitness. So, there is no direct explanation on the way these choices are made.

In the context of FDC, this choice may be expressed by the definition of a distance over n to the optimum. If the optimum is considered in one of the two mirror subspaces, say on, choosing an individual in the same subspace is equivalent to consider the Hamming distance between it and the considered optimum; and choosing an individual in the other subspace is equivalent to consider the codistance. Thus, there is a strong relation between a strategy of choice for the DGA and the effective distance over n used to calculate the FDC.

In the next, we are going to show that the best strat­ egy, with regard to the FDC, is that which consists in choosing the individual in the same mirror subspace than the optimum if its fitness is above average, and in the other subspace else. This strategy is instantiated by the so-called fitness driven distance (fd) , defined as follows

It may be obviously established that:

Property 1 The fitness-distance correlation coefficient calculated with the fitness driven distance is always neg­ ative.

Moreover, the following property is verified:

Property 2 The fitness driven distance is the best strat­ egy of choice between dual individuals with regard to the fitness- distance correlation.

Demonstration: Let d be a distance over n representing a choice strategy for each individual between Ham­ ming distance and codistance to the optimum. It is ob­ vious that:

Then, each term c(i) = (f(i) - ])(d(i) -d) involved in the covariance calculation is

Since c1 = min(cH(i), cc(i)), it is easily established that the covariance calculated using the fitness driven dis­ tance is inferior or equal to the covariance using any other distance d.

So, the correlation coefficient calculated with the fitness driven distance is inferior or equal to the one calculated with any other distance d. ·

We conjecture that the DGA tends to follow the strat­ egy expressed by the fitness driven distance.

4 FDC and Population Dynamics

In this section, we give more insight in the DGA dynam­ ical behavior, by plotting the trajectories of the popula­ tion centroid on the fitness-distance plane. In particular, we point out the "leg-up" behavior, which allows the al­ gorithms to lean on a deceptive attractor to reach the global optimum.

4.1 Fitness distance trajectories

Representing the population dynamics is a difficult task. Indeed, there is a trade-off to do between the informa­ tion being presented and the clarity of the representa­ tion. The first step is to choose a relevant plane. The fitness distance space seems to be an interesting one. The second step consists in choosing how the population is to be represented in this plane. To do so, it is natural to plot the position at each generation of the centroid of the population, that is, the point corresponding to the mean distance to the optimum and the mean fitness of the population.

4.2 "Leg-up" : a way to converge

In order to exhibit the choices made by a DGA during evolution, we are going to consider two functions, the previously introduced Trap function (>. = 50, Xb = 10, r = 0.8), and a modified Trap function called bi- Trap.

The Trap function

The trajectory of the population centroid for the SGA (see figure 5) is not surprising. The population follows the deceptive branch of the landscape toward the local optimum.

The figure 6 represents the trajectory for a DGA con­ sidering distances in the basic space. First, as for the SGA, the population converges toward the deceptive op­ timum. But after a while, the population crosses the space to converge on the global optimum. This is the "leg-up" phenomenon: the algorithm leans on the local optimum to reach the global one.

The representation in the mirror space (n) (see figure 7) gives another point of view of this behavior. In par­ ticular, it shows that the population begins to move on the mirror subspace on (solid line). Then it jumps on 1n to reach the global optimum (dashed line).

The bi- Trap function

The Trap function involves an unique "leg-up". Indeed, although the space n is crossed from part to part , this corresponds to the change of only 1 bit in (n). But this strategy may be used by DGA, even when the local optimum is not in the vicinity of the global optimum complement . Moreover, there may be several successive "leg-up" during evolution.

Now, we are going to introduce a function involving two "leg-up" . The Trap function is modified in order to get many local optima (see figure 8) : The binary com­ plement of the global one and the individuals situated at unitation 10.

According to the initial population, the SGA behaves half of the time as for the Trap function, that is it con­ verges toward the complement of the global optimum. Any time else, it converges toward the other local op­ tima, from where it occasionally reaches the global opti­ mum.

With DGA, the trajectory of the population exhibits clearly two "leg-up" (see figure 8). Initially, the popu­ lation follows the left branch. It jumps a first time to follow the right one and converge toward the deceptive optimum. Then it makes another jumps to reach the global optimum as with the standard Trap. These jumps in n correspond in fact to mirror subspace changes, as shown figure 9.

5 Conclusion

Dual genetic algorithms seem to be a promising improve­ ment of genetic algorithms. However, it lacked explana­ tion on why they are so efficient and on the way they be­ have. In this paper, we bring some element of response, using the fitness distance correlation, and plotting their dynamical behaviors in the fitness distance plane.

The trajectories plots in the distance fitness space ex­ hibit the "leg-up" phenomenon. The choice of the Trap functions was influenced by our needs to get a function with a simple representation irr this space. This way, the position of the centroid gives more informations about the distribution of chromosomes and anti chromosomes, than with functions with fuzzier representation. How­ ever, in the general case, it may be supposed that this jumping behavior is also present, while less observable.

This reinforces our conjecture, firstly made with the fitness driven distance, for which, during evolution, the DGA is confronted to choices between dual individuals, and that it tends to make such choices in a way which optimizes the correlation between fitness and distance to the global optimum.