Mich Ele Sebag
email: fmichele.sebag@polytechnique.fr

Marc Schoenauer
email: marc.schoenauerg@polytechnique.fr

Controlling Crossover through Inductive Learning

Crossover may achieve the fast combination of performant building blocks ; but as a counterpart, crossover may as well break a newly discovered building block. We propose to use inductive learning to control such disruptive e ects of crossover. The idea is to periodically gather some examples of crossovers, labelled as "good" or "bad" crossovers according to their e ects on the current population.

From these examples, inductive learning builds rules characterizing the crossover quality. This ruleset then enables to control further evolution : crossovers classi ed "bad" according to the ruleset are refused. Some experimentations on the Royal Road problem are discussed.

Introduction

Various heuristics have been designed to face the central dilemma of genetic algorithms, i.e. the Exploitation of promising regions vs the Exploration of new regions 1]. Among these heuristics, see for instance tness scaling, niching, restricted mating 2]. However, these heuristics must be parameterized by errors and trials, given the lack of theoretical results ; furthermore, these heuristics should be adaptively parameterized : e.g. restricted mating is more adapted to the end than to the beginning of evolution.

This paper focuses on the adaptive control of the crossover operator. Crossover is commonly acknowledged the more powerful engine of evolution, as it enables to combine performant building blocks. But crossover may make a promising parent disappear [START_REF] Holland | Adaptation in natural and arti cial systems[END_REF] as well as give birth to a promising o spring. The danger of breaking a building block increases with its length, as shown by the Schemata Theorem 3] : the longer the schema, the more likely a crossover point belongs to its region. But whatever the length of a newly discovered schema, crossover is a danger to it.

This paper investigates the use of inductive learning 6] to prevent using disruptive crossovers ; the idea is to characterize crossovers that are "bad" with respect to the current population, to avoid using them in the next generations. Inductive learning must be periodically redone as the crossover quality heavily depends on the current population. Section 2 brie y introduces the problem taken as example all along this paper, the Royal Road problem 7] ; on this problem we discuss the kind of knowledge needed in order to control crossover. Section 3 deals with gathering examples of the crossover behavior and evaluating their potentialities for evolving further generations. The proposed frame integrating GA and inductive learning is described in section 4. Last, section 5 presents our rst experimental results.

Knowledge about Crossover

This section rst recalls the Royal Road problem, then discusses the parts respectively devoted to learning and evolving in an integrated scheme.

Description

The Royal Road problem (RRP) was conceived by M. Mitchell et coll. 7, 8] to study into detail the combined features most adapted to GAs (laying a royal road...). Let the problem space be = f0; 1g P and let H i;j denote the schema with i consecutive 1s, beginning at locus j. The order of a schema is its number of xed bits ; the tness of individual x is de ned as the sum of the orders of the schemas x belongs to. The authors expected this tness landscape to be GA-easy because of (a) its building block structure and (b) the reinforcement due to the fact that high-order schemas are composed of low-order schemas. However, the RRP is de nitely not GA-easy ; the analysis made by Mitchell and coll. 8] is that the relative failure of GA is due to a "hitchhiking" phenomenon. The idea is that the rst individual belonging to a high-level schema, say H 32;1 , will crowd the population ; in the meanwhile, its 32 last bits, "hitchhiked" by the performant rst 32 ones may cause any schema concerned with the last 32 bits, such as H 8;33 or H 16;33 , to disappear. Evolution then goes from scratch regarding the last 32 bits.

Broad Lines

Let us sketch the behavior required from a "smart" crossover on this problem :

1. No requirement should be put on crossover in the rst stages of evolution in order to achieve fast emergence of the low-order building blocks; 2. After a performant building block has emerged i.e. when it comes to have representatives in the population, it should be sequestered according to 8],

i.e. crossover should not break it ; e.g. after schema H 8;1 has emerged, no crossover should break apart the rst eight bits in the representatives of this schema. 3. The fact that a crossover is indesirable of course depends on the current population.

Do such requirements make sense in real-world problems ? They all rely on the assumption that the global tness function may be decomposed into parts de ned on subsets of the search space. These subsets, called schemas in a boolean space, can be thought of in a more general frame ; they are called formae by Radcli e 9].

But how are formae or schemas interrelated ? The answer to this key question should rule the crossover control. To take an example, breaking apart the 5 th and 6 th bits should be generally forbidden after schema 1 1 has emerged | if schemas do not overlap ; but what if schema 0 1 1 remains to be discovered ? If two schemas overlap and have di erent xed bit values, avoiding to disrupt the rstly discovered schema may prevent to ever discover the other one. Let us call con icting tness a tness landscape involving schemas that have di erent xed bit values for some bits, and are nevertheless of high average tness. Then, con icting and non-con icting tnesses must be handled through di erent kinds of <induction -GA> coupling.

Learning or Evolving ?

Let us precise the scope of the intended crossover control : A We may demand that at least one o spring of a representative of a given schema, still belongs to the schema. This requirement ensures this schema is not eetingly discovered. In this approach, learning precisely rules out how a given individual must be combined [START_REF] Levenick | Inserting introns improves genetic algorithm success rate : Taking a cue from biology[END_REF] . B We may demand that a given region is transmitted from any individual to at least one of its o springs. Patterns existing in this region will thus remain unchanged in the population (except through the selection and mutation e ects) ; patterns will evolve in other regions of the search space. What is learned here is something about how to combine individuals, whatever the individuals to be crossed.

Option A is clearly more powerful : it applies whatsoever the underlying tness landscape, be it con icting or not. In coupling A, induction is devoted to detect the good building blocks discovered so far, while GA provides a smart exploration and combination of these building blocks.

Option B is simpler and more rigid : it forbids some crossover points. Would this control be de ned once for all, this option would clearly be inadequate to a con icting tness landscape. But what if this control is re-de ned periodically ?

On the other hand, our goal in this paper is to study the potentialities of coupling inductive learning and GA. Studying the B coupling on the Royal Road problem5 may at least tell us if our approach is worth considering any further.

So, though we are well aware of the limitations of our choice, option B will be the only one considered in the sequel of this paper : we tackle the characterization of crossovers that are adapted to a whole population.

Since inductive learning needs labelled examples, we must de ne what representation of crossover we use, and what label, standing for the "desirability" of a crossover, meets our goal of crossover control.

Representation of a crossover

Let us consider a bit-string representation, and let = f0; 1g P be the search space. A crossover c may then be represented by a mask ; let c be given as (c 1 ; : : : c P ), c i 2 f0; 1g :

x 1 x 2 : : x P y 1 y 2 : : y P ! x 0 1 x 0 2 : : x 0 P y 0 1 y 0 2 : : y 0 P with x 0 i = x i if c i = 1 y i otherwise and y 0 i = y i if c i = 1

x i otherwise Crossover c may thus be represented by an element of . In a real-valued representation ( = R P ) a widely used cross-over operator involves barycentric recombination of the parents components 5, 9] :

x 0 i = i x i + (1 i )y i ; y 0 i = (1 i )x i + i y i
with i in 0,1] or -.5, 1.5]. A crossover can therefore be represented by vector ( 1 ; :: P ), that still belongs to (a subset of) .

Labelling a crossover

Intuitively, a crossover is good if it leads to o springs with better tness than that of parents ; it is bad if o springs tness is worse than that of parents ; otherwise, it is inactive.

Choosing good crossovers. The more natural idea is to perform only good crossovers. But a crossover considered good has led to discover a promising individual in the previous generations ; and, since the e ects of crossover are reversible, if it is applied on the same individual, it will destroy it. So, a crossover observed to be "good" on a given population is far from being good for ever.

Rejecting bad crossovers. The second natural idea is to reject bad crossovers.

Notice that good and bad crossovers evolve quite di erently along genetic evolution. A crossover, good at a given step of evolution, may be bad in the very next step. Conversely, if a crossover shows bad, it is because it breaks more useful schemas than it leads to discover ; this fact is likely to persist as long as the population does not change too much. It thus makes sense to characterize the disruptive crossovers by learning rules. These rules enable to reject further disruptive crossovers. This way, the crossover control biases the generation of crossover masks (otherwise random).

Rejecting inactive crossovers. A drawback of inductive learning is that, in order to characterize the class of good or bad crossovers, we need examples of these classes. And, as evolution goes on, the number of good or bad crossovers decreases, and most crossovers become inactive. But actually, inactive crossovers are still worse than disruptive ones (at least after a given stage of evolution) : with disruptive crossovers evolution goes backwards (hopefully to other promising regions) and the search goes on ; with inactive crossovers, evolution stops. So we ended in deciding to characterize inactive crossovers and to refuse them.

More precisely, we propose the following strategy :

{ when less than 70% of the observed crossovers are inactive, phase we denote by classical, we refuse disruptive crossovers ;

{ when more that 70% of the observed crossovers are inactive, phase we denote by modern, we refuse inactive crossovers.

The transition between both phases strongly depends on the niching phenomenon 2]. If only one species is to be found, then the population will (in case of success) converge toward a single optimum, i.e. to a uniform population. Long before that, most crossovers would be inactive. Retaining solely active crossovers is equivalent to speeding up the evolution. In opposition, if several species are to be found, it is usually irrelevant to cross individuals belonging to di erent species. Learning and rejecting disruptive crossovers then can play the same role than any niching heuristics (e.g. restricted mating).

An integrated frame

This section rst describes the GA we use, then give the broad lines of the coupling. Last, the interactions between GA and inductive learning are detailed.

Genetic Algorithm

The genetic algorithm we use is a lab-made software based on the standards 1] : bit-string encoding, roulette wheel selection with tness scaling, two-points crossover at a rate of 0.6 with both o springs replacing the parents, and mutation at a rate of 0.05. The evolution stops either after 1000 generations or when the tness is constant over the population. The tness scaling (number of o springs for the best individual) varies in the experiments (see 5.1).

Broad Lines of the Coupling

We combine GAs and inductive learning in the following scheme (Fig. 1) :

1. A rst darwinian period involves N generations of a classical GA ; 2. The next step corresponds to gaining experience about evolution. Examples of crossovers are generated and their behaviors are observed with respect to the current population (section 4.3). A set of rules is built from these examples by inductive learning (section 4.4). 3. Then a "civilized" period involves GA controlled according to the available experience. During M generations (M is called civilization length [START_REF] Michalski | A theory and methodology of inductive learning[END_REF] ), crossovers classi ed by the ruleset as disruptive or inactive are refused (section 4.5). 4. After these M generations, the population has evolved and acquiring new experience is necessary. So, the process goes back to step (2). We call civilization the phase of rules induction together with the consecutive M generations obeying these rules.

Gathering crossover examples

Let L be the size of the genetic population. L crossover examples are built as follows :

A 2-point crossover mask is randomly generated; Two individuals are randomly selected in the population; These individuals are crossed according to the crossover mask. The mask is labelled as good, bad or inactive, depending on whether the tness of the best o spring is better, worse or equal to the tness of the best parent; If this mask belongs to a class that includes less than 70% of the L examples, it is added to the example set.

The last condition may result in an never-ended loop if all crossovers belong to the same class. To settle this problem, if the example set is not completed in 5 L trials, an empty ruleset is considered all along this civilization (that period is therefore darwinian). The current phase is said classical if less than 70% of the examples are inactive, and modern otherwise.

Learning rules

We use a star-like algorithm 6], described into detail in 12, 11]. A rule consists of an hypothesis part and a conclusion part. The hypothesis can be thought of as [START_REF] Michalski | A theory and methodology of inductive learning[END_REF] In the following, we take M = N. a schema in the crossover space ; the conclusion here belongs to the set f good, bad, inactive g. A rule is said to cover a crossover mask i this mask belongs to the schema standing for the hypothesis of the rule.

The induction we use is a bottom-up process : from any example (crossover mask) Ex, we try to nd out rules covering Ex and not covering any example belonging to a class other than that of Ex. Among the many solutions, only rules covering the maximum number of examples are retained ; furthermore, we require that a rule covers at least 2 examples. This algorithm does not necessarily provide consistent rules. When an unlabelled crossover is covered by rules of di erent conclusion, the nal decision is determined via a majority vote among these rules.

Using the rules

A 2-point crossover mask is initialized at random. During the civilized periods, this mask is checked as follows : if the ruleset is empty, the mask is accepted. if the mask is classi ed as bad, and the current phase is classical, the mask is refused;

if the mask is classi ed as inactive, and the current phase is modern, the mask is refused; otherwise, the mask is accepted.

Again, this decision process may result in a never-ended loop if all crossovers are rejected. To prevent this, a gradual relaxation of the ruleset is used : rules are weighted ; the weight of a rule is set to the number of learning examples it covers ; only rules with weight greater than a threshold s are considered. Threshold s is initialized to 1 (i.e. all rules are considered in the beginning). if, on L consecutive trials, less than L 20 crossovers are retained, threshold s is incremented of 1. So, if no crossover is accepted, less and less rules are taken into account.

5 Results and Discussion

Protocol

Any presented result corresponds to the average result obtained on 30 independant runs. The population size is set to 100, 200 and 500 individuals. The tness scaling (number of o springs for the best individual) is set to 1.5 and 2. The civilization length varies from 0 (no learning at all) to 10.

Results on the Royal Road

The Royal Road problem is modi ed as in 8] : if N(i) denotes the number of schemas of order i (with i equals 8, 16, 32 or 64) individual x belongs to, the tness of x is the sum, for all orders i of 0 if N(i) = 0 and i+N(i) :2 otherwise (instead of N(i) i).

Table 1 shows the number of hits of the global optimum over 30 runs. The mean number of function evaluations needed to hit the optimum is given between parentheses for population size 200 and 500 (meaningless for population size 100).

Pop 1 : Number of hits (mean nb of evaluations needed) Note that the results obtained without learning are not identical to those of Mitchell et al. 8], since they never found the optimum in 10 6 evaluations, for a population size of 2000. This di erence is due to the tness scaling mechanism : in 8], the number of o springs of the best individual is set to the ratio between its tness and the average tness over the population.

Discussion

A rst remark is that, as expected, civilized evolution (i.e. evolution + learning) discovers the global optimum more often than darwinian evolution (Table 1). Furthermore, when both evolutions do reach the optimum, civilized evolution requires less computational e ort (Fig. 2.b). On the other hand, when neither evolution does not reach the optimum, civilized evolution goes higher (Fig. 2.a).

Second, it seems that civilized evolution needs a scaling factor smaller than darwinian evolution, of which we propose the following explanation. Selection ensures the survival of performant schemas through duplication of performant individuals. But in civilized evolution, no disruptive crossover is to fear : performant schemas are ensured to survive. Learning thus replaces to some extent, the individual selection by the crossover selection.

Last, we claim that our approach is more general than the heuristic proposed in 8] to overcome the di culties of the Royal Road problem. Introns are zones of bits not contributing to the tness 4] ; Mitchell et coll. modify the representation of the Royal Road by separating order-8 schemas by introns of length 24. The use of introns therefore signi cantly decreases the chances for a crossover to be disruptive : a crossover point may freely arise in an intron zone without disturbing any low-order schema in the current individuals.

However, this heuristic is not easy to use in real-world problems since it requires strong presumptions as to the localization of schemas. In the meanwhile, a learning approach does not require any such a priori information.

Conclusion

This paper investigates the coupling of GA and inductive learning according to the following scheme : a rst period, called "darwinian evolution" only involves some generations of classical GA ; next periods, called "civilizations", are twostep processes :

A learning step gathers examples of crossovers and observes their behavior on the current population. These examples enable inductive learning to build a set of rules characterizing relevant crossovers.

Then, a civilized evolution step consists of M generations, where M is called "civilization length", that di ers of classical GA in that that the crossovers selection is biased according to the current ruleset ; only crossovers relevant according to this ruleset, are retained. In the end of a civilization, the population is signi cantly di erent from what it was in its beginning. Another learning phase thus open to a new civilization. This approach asks a key question : inductive learning provides the evolution with an explicit memory | compared to the implicit memory consisting of the population itself. The implicit memory is safely (if not fast) optimized by GA and modi cations of the tness landscape can lead to powerful optimization strategies 10]. We may then fear explicit memory to disturb the evolution mechanism. Of course, our experiments only considered the arti cial problem of the Royal Road, and many more experiments are needed to validate the scope, if any, of our approach.

However, at a very theoretical level, an argument on behalf of explicit memory could be the following. Implicit memory makes few di erences between discovery and re-discovery. But this di erence is of great importance for the acceleration of evolution : an anthropomorphic analogy of the explicit memory we propose to equip the evolution with, is the invention of writing ... Further research will consider other problems, especially deceptive ones. We also plan to investigate the in uence of the civilization length and of the scaling factor on the hybrid evolution we called "civilized" evolution.

Figure 1 :

 1 Figure 1 : Combining GAs and Induction ( stands for a generation)

Figure 2 :

 2 Average best tness function of the number of evaluations Another criterion of performance is the evolution speed. Fig.2(a) plots the mean best tness obtained for N nb of evaluations, for a population size 100, and a civilization length of 0, 3, 5 and 10. Fig.2 (b)gives the results corresponding to a population size of 500. Of course, the number of function evaluations includes the number of experiments needed for learning.

  The rst version of the RRP de ned on = f0; 1g 64 involves schemas H 8;1 ; H 8;9 ; H 8;1+8 k , H 16;1 ; H 16;17 ; H 16;1+16 l , H 32;1 ; H 32;33 and H 64;1

Mutation can also destroy it, but with a usually much smaller rate than that of crossover.

A still more precise control would concern who to combine with a given individual.

The limitations of option B should not be too severe regarding the Royal Road landscape, since it is not con icting.