Jean-Baptiste Mouret

Stéphane Doncieux

Evolving modular neural-networks through exaptation

Despite their success as optimization methods, evolutionary algorithms face many difficulties to design artifacts with complex structures. According to paleontologists, living organisms evolved by opportunistically co-opting characters adapted to a function to solve new problems, a phenomenon called exaptation. In this paper, we draw the hypotheses (1) that exaptation requires the presence of multiple selection pressures, (2) that Pareto-based multi-objective evolutionary algorithms (MOEA) can create such pressures and (3) that the modularity of the genotype is a key to enable exaptation. To explore these hypotheses, we designed an evolutionary process to find the structure and the parameters of neural networks to compute a Boolean function with a modular structure. We then analyzed the role of each component using a Shapley value analysis.

Our results show that: (1) the proposed method is efficient to evolve neural networks to solve this task; (2) genotypic modules and multiple selections gradients needed to be aligned to converge faster than the control experiments. This prominent role of multiple selection pressures contradicts the basic assumption that underlies most published modular methods for the evolution of neural networks, in which only the modularity of the genotype is considered.

I. INTRODUCTION

Finding the parameters and the topology of neural networks is a complex task that has been successfully tackled with evolutionary algorithms many times (e.g. [START_REF] Gruau | Automatic definition of modular neural networks[END_REF]- [START_REF] Gauci | Generating large-scale neural networks through discovering geometric regularities[END_REF]). Although these methods easily lead to good parameters for many systems, they turn out to be inefficient to evolve artifacts with arbitrary complex structures. In other words, current evolutionary algorithms are widely successful optimization methods but are bad engineers. This result is surprising with regard to the complexity reached by living organisms using "natural" evolution.

These difficulties echo the main criticisms addressed by early -and current -opponents to Darwin. While it is easy to admit that natural selection can maintain and improve a given trait, how do complex characters emerge at first? Put differently, how natural selection could favor the intermediate structures required to solve complex tasks? Darwin wrote a lengthy answer to this challenge in the last edition of The Origin of Species [START_REF] Darwin | On the Origin of Species by Means of Natural Selection, or the Preservation of Favoured Races in the Struggle for Life[END_REF] in which he highlighted that a structure does not have to be employed for the same purpose during the whole evolution of a species. Consequently, structures might originate from an adaptation to a function and then be opportunistically co-opted to solve a new problem. Darwin termed this concept preadaptation, but modern evolutionary biologists use the less connoted word exaptation [START_REF] Gould | Exaptation; a missing term in the science of form[END_REF]. According to current paleontology, exaptation explains, in particular, crucial steps of the evolution of life such as the appearance of the digits of tetrapods, initially adapted to an aquatic environment [START_REF] Coates | Polydactyly in the earliest known tetrapod limbs[END_REF], or first bones, useful for the storage of inorganic ions.

Despite the prominent role of exaptation in the evolution of complex organisms, this phenomenon seems to be, if not absent, at least rare in artificial evolution. Complex life forms are subject to many selection pressures such as the performance of their vision system, the ability to move faster, the variety of food they can eat, etc. As a consequence, evolution can improve organisms with respect to many selection gradients and the obtained adaptations can later be employed to solve problems raised by another selection gradient, resulting in an exaptation. Classical artificial evolution defines only one selection gradient, the fitness function, thus preventing the evolutionary process to exploit exaptation to lead to complex artifacts.

Recognizing this problem, several researchers (e.g. [START_REF] Ray | An approach to the synthesis of life[END_REF]- [START_REF] Elfwing | Biologically inspired embodied evolution of survival[END_REF]) proposed to replace the fitness function by an implicit evaluation scheme in which individuals are situated in an artificial world. Inhabitants of these simulated environments compete for limited resources while trying to meet sexual partners to spread their genotype. These studies provide many insights about the dynamics of evolutionary systems and can lead to complex "artificial life forms"; however, they are not designed to solve concrete problems, such as creating a neuro-controller for a robot to clean a room or finding the optimal structure of a bridge. In this paper, we draw the hypothesis that Pareto-based multiobjective evolutionary algorithms (MOEA, see [START_REF] Deb | Multi-objectives optimization using evolutionnary algorithms[END_REF]) can explicitly provide multiple selection gradients, thus enabling exaptation to evolve complex and potentially useful artifacts.

The existence of a selection pressure may not be sufficient to improve a particular trait: if a gene has many pleiotropic effects 1 , it may be impossible to improve one character without altering some other ones; consequently, the more independent the genes coding for unrelated traits, the more efficiently a selection gradient can be followed. In other words, the genotype-phenotype map -how genotype variations are reflected in the phenotype -should be modular (see [START_REF] Callebaut | Modularity: Understanding The Development And Evolution Of Natural Complex Systems[END_REF]). This intuition is confirmed by a recent theoretical study [START_REF] Altenberg | Modularity in Evolution: Some Low-Level Questions[END_REF] that highlights that genotypic modules, phenotypic modules and selection gradients should be "aligned" to fully benefit from the advantages of modularity for the evolvability of complex systems. Moreover, modularity makes easier the repetition of a functional sub-part in an organism. Such a duplicated module can then be employed for a new function without damaging its use in the original context. The impor-tance of modularity to evolve complex systems and especially neural networks has been widely recognized ( [START_REF] Gruau | Automatic definition of modular neural networks[END_REF], [START_REF] Calabretta | A case study of the evolution of modularity: towards a bridge between evolutionary biology, artificial life, neuro-and cognitive science[END_REF]- [START_REF] Reisinger | Evolving reusable neural modules[END_REF]) but, to our knowledge, neural-network modules have never been explicitly linked to selection gradients.

In this article, we propose an evolutionary process designed to exploit exaptation and modularity to synthesize complex systems. Our aim is twofold: [START_REF] Gruau | Automatic definition of modular neural networks[END_REF] investigating the links between evolution, modularity and selection gradients and (2) introducing a scalable method to evolve complex systems. We illustrate our ideas by evolving neural-networks to compute a complex and modular Boolean function, a problem previously employed in another study about modularity [START_REF] Kashtan | Spontaneous evolution of modularity and network motifs[END_REF].

The remainder of this paper is organized into four parts. Section II is an overview of the related previous work. Section III describes our approach, from the definition of a modular genotype-phenotype map to the use of MOEAs to create multiple selection gradients. Section IV details our experiment and analyzes the results using the Shapley value. The last section is a brief discussion.

II. PREVIOUS WORK

Only a few papers explicitly deal with exaptation and preadaptation in the evolution of artificial systems [START_REF] De Oliveira | Simulation of Exaptive Behaviour[END_REF], [START_REF] Stork | Non-optimality via preadaptation in simple neural systems[END_REF]- [START_REF] Graham | A multiple-function toy model of exaptation in a genetic algorithm[END_REF]. De Oliveira [START_REF] De Oliveira | Simulation of Exaptive Behaviour[END_REF] studies an artificial ecosystem of two-dimensional cellular automata designed to make difficult adaptations by natural selection. Exaptation was possible by exploiting a sequence of non-adaptations caused by genetic drift. Studying the evolution of neural networks, Miglino et al. [START_REF] Miglino | Discontinuity in evolution: How different levels of organization imply pre-adaptation[END_REF] noticed that some changes of the neural networks were non-adaptive -and consequently only selected by chance -but were later required to increase the fitness. Miglino et al. conclude that this phenomenon was an evidence of artificial preadaptation. While these two papers report observations of preadaptation in an artificial context, Graham and Oppacher [START_REF] Graham | A multiple-function toy model of exaptation in a genetic algorithm[END_REF] proposed a process designed to exploit exaptation to improve existing evolutionary algorithms. Tackling a toy problem, the authors designed four fitness functions of increasing difficulty and associated them to four niches. Individuals of each niche were evaluated using the corresponding fitness but they were allowed to migrate between niches at the end of each generation. At the beginning of their experiments, individuals were viable only in the simplest niche but, after a few hundred generations, they managed to migrate from niches to niches to finally solve the most complex problem. These results demonstrate the power of exaptation to solve difficult tasks by providing different fitness gradients.

Using intermediate steps to evolve solutions for complex problems is often referred to as incremental evolution [START_REF] Mouret | Incremental evolution of target-following neuro-controllers for flapping-wing animats[END_REF], [START_REF] Harvey | Seeing the light: artificial evolution; real vision[END_REF]- [START_REF] Urzelai | Incremental Evolution with Minimal Resources[END_REF]. In these works, the task is split into stages of increasing complexity. Candidate solutions are first selected using a first fitness function and, once a convergence criterion is reached, the experimenter changes the fitness to a more complex one. Despite its practical successes, this manual approach has several drawbacks (see [START_REF] Mouret | Incremental Evolution of Animats Behaviors as a Multi-objective Optimization[END_REF]) such as the need to find a good switch criterion, the necessity to follow designer's ordering of sub-problems, the inability to explore multiple hypotheses and the absence of explicit selection pressures on the previous sub-tasks.

Mouret et al. [START_REF] Mouret | Incremental Evolution of Animats Behaviors as a Multi-objective Optimization[END_REF] show that these drawbacks can be efficiently overcome by defining a multiobjective optimization problem in which each objective corresponds to a sub-task and by then solving it using a Pareto-based MOEA (see [START_REF] Deb | Multi-objectives optimization using evolutionnary algorithms[END_REF]). At the beginning of the process, individuals obtain a non-minimal fitness only for the simplest objectives. As they improve with respect to these objectives, they will reach the minimal performance for the sub-tasks required to try the more complex ones. As a consequence of the Pareto sort, individuals that obtain a non-minimal fitness on a previously unreachable sub-task will be non-dominated -and consequently selected -but best individuals for the simpler sub-tasks will be non-dominated too. Thus, the evolutionary process will automatically switch to complex tasks as soon as possible, while maintaining a selection pressure on previous tasks and while not depending on any a priori ordering of sub-tasks. Moreover, a part of the population may dominate with respect to one of the intermediate sub-tasks while another part can improve along another selection gradient; the process can thus simultaneously explore different evolutionary paths. Each selection gradient in this case relies on complete solutions features and has no direct impact on sub-parts of it. This differs from natural evolution, in which particular evolutionary pressures can shape specific organs. This difficulty will be addressed in the present paper by introducing modules in candidate solutions.

The evolution of modular systems and especially modular neural networks has drawn considerable attention in the last few years because of the intuitive hypothesis that they are more evolvable than monolithic ones. Most papers about the evolution of modular neural networks deal with the design of modular encodings with different approaches. For instance, Gruau [START_REF] Gruau | Automatic definition of modular neural networks[END_REF], Hornby and Pollack [START_REF] Hornby | Creating high-level components with a generative representation for body-brain evolution[END_REF] and Mouret and Doncieux [START_REF] Mouret | Mennag: a modular, regular and hierarchical encoding for neural-networks based on attribute grammars[END_REF] derive techniques from evolutionary programming to exploit the intrinsic modularity of tree-based representations; Doncieux and Meyer [START_REF] Doncieux | Evolving modular neural networks to solve challenging control problems[END_REF] and Reisinger et al. [START_REF] Reisinger | Evolving reusable neural modules[END_REF] use simpler representations based on a list of modules, directly encoded, and a blueprint that specifies how modules are connected. In these papers, the authors implicitly assume that modular systems will be favored by the evolutionary process. Consequently, they do not propose any explicit link between the selection pressures and the modules.

Nevertheless, this hypothesis is questionable. As noticed in [START_REF] Bowers | Embryological modelling of the evolution of neural architecture[END_REF], monolithic neural networks are often more efficient and easier to obtain than their modular counterpart. The observation that living organisms are highly modular, and that it explains at least a part of their success, raises the question: how modularity did emerge in nature? Wagner et al. [START_REF] Wagner | Natural selection and the origin of modules[END_REF] review many proposed explanations and conclude that the direct selection for evolvability, i.e. the implicit hypothesis behind modular encodings, is one of the less likely ones. Recent papers in theoretical biology emphasize the role of the selection pressure to explain the modular organization of organisms. In particular, Lipson et al. [START_REF] Lipson | On the origin of modular variation[END_REF] and Kashtan and Alon [START_REF] Kashtan | Spontaneous evolution of modularity and network motifs[END_REF] employ numerical models to show that rapid changes of evolutionary pressures induce modular structures. In another theoretical study, Altenberg [START_REF] Altenberg | Modularity in Evolution: Some Low-Level Questions[END_REF] concludes: "My main proposal is that the evolutionary advantages that have been attributed to modularity do not derive from modularity per se. Rather, they require that there be an 'alignment' between the spaces of phenotypic variation, and the selection gradients that are available to the organism."

III. METHOD

A. Modular genotype-phenotype map

Definitions of what a module is are multiple and rather vague. In this work, we chose to call a module a subset of a system containing several entities functionally integrated and largely independent of the entities that constitute the other modules. In the context of neural-networks, the interactions between neurons are defined by the connections and the synaptic weights; so we can consider the network as a directed graph and try to find highly connected clusters. This problem has a long history in graph theory due to its usefulness in sociology -to analyze groups of people -and in biology -notably to analyze gene regulatory networks. Leicht and Newman [START_REF] Leicht | Community Structure in Directed Networks[END_REF] recently proposed a robust and efficient approach to detect modules by optimizing a measure (simply called "modularity") over the possible divisions of a network. Broadly, Leicht and Newman [START_REF] Leicht | Community Structure in Directed Networks[END_REF] state that, in a good division, the number of edges between groups is smaller than expected, i.e. in most cases, smaller than the mean number of edges in a random network of the same size. Good divisions regarding this measure can be computed using a spectral analysis method that demands O(n2 ) time, where n is the number of vertices in the network.

Such sub-graphs of a neural-network constitute phenotypic modules. Genotypic modules are more straightforward to define since one has only to check that genetic operators only affect sub-parts of the genotype. Using the approach introduced in [START_REF] Leicht | Community Structure in Directed Networks[END_REF], phenotypic modules can be extracted from any network and many modular genotypes can be designed. Consequently, the important point for the evolvability of complex systems is not only the existence of modules in the genotype and in the phenotype; it is how genotypic modules relate to phenotypic ones. This relation, called the genotype-phenotype map, is said to be modular if genotypic modules are developed into phenotypic modules 2 . The neural network modules emerge from the topology of the neural network. As a consequence, a small change in the neural network, for instance the addition of a connection induced by a mutation, can considerably modify the optimal division. This makes it difficult to define a modular genotype-phenotype map: depending on the neural network encoding, it can be difficult to guarantee that a genotypic module will lead to a meaningful phenotypic Fig. 1. An individual's genotype is made of a main network and one or several sub-networks. Each sub-network is associated with a list of links that connect the sub-networks to the main network. If several lists of links exist for a same sub-network, the latter is added several times to the main network. The neural network on the right is an example of a phenotype that could have been encoded with the genotype on the left. module. In a biological context, Wagner et al. [START_REF] Wagner | Natural selection and the origin of modules[END_REF] explain that only two processes can lead to a modular genotypephenotype map: parcellation, which consists in a differential suppression of pleiotropic effects between groups of characters, and integration, which corresponds to the selective acquisition of pleiotropy among characters from the same group. How could these two concepts be transposed to neural networks? Removing pleiotropic effects can be interpreted as making the contour of phenotypic modules more resistant to mutations. Parcellation can consequently be the isolation of the part of the genome coding for a module, extracted using the approach described in [START_REF] Leicht | Community Structure in Directed Networks[END_REF]. Thus a phenotypic module would remain stable during the evolution. Integration can be seen as the replacement of a module by a copy of another one, thus providing a repetition mechanism.

Trying to implement these operations as mutations in the simplest genotype possible, we start by considering a typical graph-based direct encoding in which two kinds of mutations are possible: synaptic weight or a neuronal bias; we use here a change in a set of 9 possible values (see appendix). To easily add integration and parcellation as mutation operators, we then defined our neural network encoding as a main network -encoded using the previously described direct encoding -and a list of sub-networks, each of them associated with links towards the main network (figure 1). Before applying any operator, the main network is divided into modules using [START_REF] Leicht | Community Structure in Directed Networks[END_REF] and their inputs and outputs are identified. Inputs of a module are either a connection between an extra-module neuron to an intra-module one, or an input of the main network. Outputs are defined similarly. The specification of each modular operator is now straightforward. The parcellation acts in three steps (figure 2(a)):

• removal of a module from the main network;

• addition to the sub-network list;

• addition of the links to the sub-network's links list. The removed module can be, either randomly selected or deterministically chosen as the best module regarding one of the sub-tasks. In this work, this second approach is used. The integration requires also three steps (figure 2(b)):

• random selection of a module m 1 from the sub-network list; • random selection of a module m 2 of the main network with the same number of inputs and outputs as m 1 ; • removal of the module m 2 from the main network;

• addition of the links to the sub-network links list. To counterbalance the effects of these two operators, we added an operator named "differentiation" that puts back a sub-network into the main network and removes the corresponding links in the list (figure 2(c)). This operator undoes parcellation and integration and it can be used by the evolutionary process to create a variant of a repeated module. Each operator is assigned a mutation rate (between 0.05 and 0.2, see appendix).

A simple cross-over operator is implemented by exchanging two parcellated modules (figure 3).

Note that the proposed encoding aims at being simple and abstractly related to biology in order to investigate the links between selection gradients, genotypic modules and selection gradients. Our main goal is therefore not to introduce a novel encoding for a neural network but is to provide a tool to study modularity. Other modular encodings for neural networks (e.g [START_REF] Hornby | Measuring, enabling and comparing modularity, regularity and hierarchy in evolutionary design[END_REF], [START_REF] Reisinger | Evolving reusable neural modules[END_REF], [START_REF] Doncieux | Evolving modular neural networks to solve challenging control problems[END_REF]) might be used but their structure makes them harder to link to biological literature.

B. Selection gradients

Following the work of Altenberg [START_REF] Altenberg | Modularity in Evolution: Some Low-Level Questions[END_REF], we "align" phenotypic modules and selection gradients, which means that each phenotypic module should be linked to a fitness function.

To that aim, we propose to first define fitness functions able to evaluate sub-networks for potentially useful subfunctions. For each individual, the main network is divided into modules using the approach described in [START_REF] Leicht | Community Structure in Directed Networks[END_REF]. Each such module and each parcellated module are then evaluated according to each objective. We use the best value obtained by a module for each objective as the fitness of the individual with respect to this objective. Each of these fitness functions constitutes an objective of a multiobjective problem. The main fitness, which rewards the ability to solve the problem we are interested in, is added as another objective.

Using a Pareto-based MOEA to optimize this multiobjective problem has several consequences. An individual with an inefficient overall behavior will be considered as Paretooptimal if it contains at least a good module for a sub-task. If the main task requires such an efficient module to build more complex solutions, it will be gradually improved thanks to the selection pressure inducted by the corresponding objective. This module can be later co-opted at any time. Moreover, the same module can be repeated (it may be useful elsewhere) or propagated in the population by cross-over.

Another important consequence of the use of a MOEA is that, as shown in [START_REF] Mouret | Incremental Evolution of Animats Behaviors as a Multi-objective Optimization[END_REF], solving each sub-task is not mandatory. If the evolutionary process finds better solutions without using modules, these individuals will dominate with regard to the main objective and will consequently be selected. Different hypotheses about the usefulness of each sub-task can therefore be investigated at once: some individuals will be good at one sub-task while some other ones will contain useful modules for other sub-tasks; the evolutionary process will opportunistically modify them, without any a priori knowledge about the ordering of sub-tasks or about their utility.

C. Shapley value

When designing and evaluating an evolutionary process, it is important to understand what makes it efficient. A particular genetic operator may be mandatory to lead to working results; it may also only change the convergence speed or even have no influence on the results. Furthermore, the critical components may be combinations of some particular genetic operators, in which all of them are required to bring improvements but each one is useless alone. In the context of this paper, we would like to be able to estimate the usefulness of each modular operator (parcellation, integration, differentiation and cross-over) and to evaluate what brings the multiobjective approach.

Evaluating the contribution of each such component is equivalent to finding a fair allocation of gains, e.g. the fitness, between players in a coalitional game, a problem solved in game theory by the Shapley value [START_REF] Shapley | A value for n-person games[END_REF]. The Shapley value is defined from the marginal contribution of a player i to a coalition S, where i / ∈ S and v(S) is a value function (the fitness or any other relevant measure of efficiency):

∆ i (S) = v(S ∪ {i}) -v(S)
The Shapley value is then defined by the payoff γ i of each player i ∈ N :

γ i = 1 |N |! r∈R ∆ i (S i (r))
where R is the set of all |N |! orderings of N and S i (r) is the set of players preceding i in the ordering r.

Once the efficiency of the 2 n configurations has been evaluated, the Shapley value can be computed as a summation of v(s) for all the configurations, properly weighted by the number of possible orderings of the elements (see [START_REF] Keinan | Fair attribution of functional contribution in artificial and biological networks[END_REF]):

γ i = 1 |N |! S⊂N,i∈S v(s) • (|S| -1)! • (|N | -|S|)! configurations with i - 1 |N |! S⊂N,i / ∈S v(S) • (|S|)! • (|N | -|S| -1)! configurations without i IV. EXPERIMENT A. Experimental setup: (a ⊕ b) ∧ (c ⊕ d)
We evaluated the proposed approach on the evolution of neural networks to compute the Boolean function (a ⊕ b) ∧ (c⊕d) , where a, b, c and d are Boolean values and ⊕ denotes the exclusive "or" operator (xor). This previously used in [START_REF] Kashtan | Spontaneous evolution of modularity and network motifs[END_REF] to study the evolution of modular NAND networks, has a clear modular structure: it is made of two "xor" functions, each of them requiring at least one hidden neuron, linked by a simpler logical "and". The truth table of (a ⊕ b) ∧ (c ⊕ d) shows that a simple neural network that returns "false" for any input would have a 75% success rate, a good score at the beginning of the evolutionary process. As a consequence, these degenerated neural networks could easily invade the population whereas they do not constitute a good starting point. This makes the typical single-objective fitness for this function very deceptive. The (a⊕b)∧(c⊕d) function therefore constitutes a simple illustration of the situations in which exaptation could be useful: the typical fitness does not provide useful enough search gradients and we can suggest a helpful sub-function (xor).

We used the sum of errors for each possible set of inputs as the main fitness (expressed in a fitness maximization scheme):

F x = 1 - 1 16 16 i=1 |o i -d i |
where o i is the output of the neural network for the input set i and d i the desired output. Each neural network is simulated during 100 time-steps. Since we do not constrain the structure of the neural networks, nothing prevents them from oscillating. To avoid such behaviors, we attribute an arbitrary low fitness if the output is not constant during the last 10 time-steps.

We then defined a second objective F m that rewards the efficiency of a "xor" module in an individual:

F m = max m∈M F xor (m)
where M is the set of all modules. Considering that a module m is compatible if it has 2 inputs and 1 output, F xor is the sum of errors for the module m with respect to the function "xor":

F xor (m) = 1 -1 4 4 i=1 |o i -d i | if m is compatible -1 otherwise
The NSGA-II algorithm was employed with a population of 400 individuals and the parameters described in appendix. We launched five sets of experiments, each of them made of 32 runs:

• exaptation: parcellation (P), integration (I), differentation (D), cross-over (C) and multiple selection pressures (M); • M: multiple selection pressures only, i.e. no genotypic modules; • P+I+D+C: genotypic modules only;

• standard: direct encoding without genotypic modules and without selection pressures; • NEAT, a popular neuro-evolution approach [START_REF] Stanley | Evolving neural networks through augmenting topologies[END_REF]. We didn't compare our results with a modular encoding for neural network because (1) they are very complex to implement and to tune and (2) our main focus is on the benefits of linking selection gradients to modules.

B. Results

Figure 4(a) shows the proportion of converged runs (F x > 0.9) as a function of generation, for each of the three investigated approaches. Less than half of the control runs converged within 5000 generations. This result agrees with [START_REF] Kashtan | Spontaneous evolution of modularity and network motifs[END_REF], in which the authors report that only 72% of their control runs converged in less than 10 5 generations. NEAT leads to substantially better results since almost all the runs converged in 1500 generations and more than half of them in only 500 generations. This confirms the published results in which NEAT outperforms direct encodings (e.g. [START_REF] Stanley | Evolving neural networks through augmenting topologies[END_REF]). Nevertheless, the exaptation-based approach converged faster than NEAT. The 32 experiments converged in less than 1000 generations and half of them in about 300 generations. Figure 4(b) corroborates this observation: on average, 400 generations are required with the exaptation-based approach while NEAT need 700 generations 3 .

Surprisingly, not only did the approach based only on the genotypic modularity (P+I+D+C) not improve the convergence rate over the control experiments, but also it deteriorated it slightly. The runs that employed only the multiple (a) Proportion of converged runs (Fx > 0.9) as a function of generation. "M+P+I+D+C" denotes the full exaptation experiments, "standard" denotes the control experiments, which use a simple direct encoding (with the same parameters as the one used by the exaptation experiment) and one objective; the experiments "M" correspond to the multiobjective approach with the modular genetic operators disabled; in "P+I+D+C", the modular operators are used with the main fitness only. (b) Mean generation of convergence and standard deviation (the other experiments are omitted because only a few runs converged in less than 5000 generations). The differences between these two sets of experiments are statistically significant (p < 0.003). pressures scheme (M) obtained even worse results: only one run converged in less than 1500 generations. Given that our exaptation experiment used the combination of P, I, D, C and M, these results demonstrate that, at least in this experiment, both a modular encoding and multiple selection gradients are required to improve the efficiency of the evolutionary process. A simple "waste of resources" may explain the results obtained with the "M" experiment: a part of the population is used to maintain many Pareto-optimal candidate solutions with a low main fitness; if this scheme does not improve the evolutionary process, it is broadly equivalent to reducing the population size, hence possibly deteriorating the convergence rate over the control experiment. Further investigations are needed to fully understand this phenomenon.

A typical neural network obtained with the exaptation approach is drawn on figure 5. It Is clearly made of two repeated modules, each of them computing a "xor" function. These modules are two instances of a parcellated module, which obtained an optimal fitness according to F xor .

C. Shapley value analysis

To draw a better picture of what makes the proposed approach efficient, we employed the Shapley value analysis described in section III-C. We investigated the role of the use of two selection gradients (M), of the parcellation (P), of the cross-over (C), of the integration (I) and of the differentiation (D). The efficiency of 2 5 = 32 variants must therefore be evaluated.

Several choices are available for the value function, which should reflect the efficiency of a variant. We chose to focus our work on the convergence rate because we are primarily interested in getting as much successful experiments as possible. In some configurations, some components of our system can substantially decrease the convergence rate. For instance, we found that using the two selection gradients without parcellation lead to a 3% success rate whereas the control experiment has a 44% rate (section IV-B). If this component is required to obtain good scores in other configurations, it should have a high Shapley value but this value can be substantially lowered by these bad configurations, hiding the interesting analysis. We are interested in understanding which components improve over the control experiments and not about the fact that they can lower the scores in some cases. We consequently designed the following value function:

v(S) = max(v c (∅), v c (S))
where v c (S) is the convergence rate for the configuration S and v c (∅) denotes the convergence rate of the control experiment.

We launched 32 runs of each variant for 1500 generations with the same parameters as in section IV-B. The resulting Shapley values are displayed on figure 6.

The two highest values are obtained by the multiple selection gradients (M) and the parcellation operator (P). This means that these two components are critical to get the highest convergence rates. The fact that their values are very close 4 confirms that using only one of them is not sufficient to improve the efficiency of a variant; both of them are required. The parcellation operator links genotypic modules to phenotypic modules and selections gradients are linked to phenotypic modules by the multiobjective approach (M). As a consequence, the obtained Shapley values highlights the need for the alignment suggested by the theoretical work of [START_REF] Altenberg | Modularity in Evolution: Some Low-Level Questions[END_REF]: genotypic modularity (P) is useless if it is not linked to selection gradients. This conclusion contradicts the underlying hypothesis of current modular encodings for neural networks, which assumes that providing a modular genetic encoding is enough to improve the efficiency of the evolutionary process.

The next highest value is obtained by the integration operator, which is trivially useful for the (a ⊕ b) ∧ (c ⊕ d) function. This Shapley value is substantially lower than the two previous ones, showing that the key-point in the evolution of our modular neural networks is not the repetition mechanism. The cross-over only slightly improves the results and the differentiation has almost no effect.

V. DISCUSSION

In the artificial evolution paradigm, researchers often try to design a universal encoding which would allow to easily solve any problem by only specifying a simple and high-level fitness function. Hence, they put complex mechanisms in the encoding and try to use as little knowledge as possible in the fitness function. This approach is surprisingly disconnected from evolutionary biology, in which most descriptions of the evolution of living organisms primarily rely on selection pressures. When Darwin introduced his theory, nothing was known about the genome; but this didn't prevent him and his successors from successfully explaining the essence of the origin of most species.

The results presented in this paper indicate that the use of a single fitness function might be an over-simplification of the natural evolutionary process, which could prevent the evolution of complex artifacts. In particular, the Shapley value analysis shows that multiple selection pressures are required to efficiently evolve neural networks for the investigated problem. This result was expected as the presence of multiple selection gradients is the key to enable exaptation, hence the evolution of complex designs. However, a more interesting result of this analysis is that multiple selection gradients are useless by themselves. Both modularity and selections pressures are required: if one of them is omitted, the evolutionary process is less efficient than the control experiment. This leads to a new evolutionary scheme centered on evolutionary pressures and genome modularity.

Since we add more knowledge in the fitness function, this approach might move our research away from a mythical "universal problem solver". However, all the published methods to evolve complex systems rely on biases that could constrain them to specific problems, since we do not know any universally good bias. NEAT, for instance, begins the evolutionary process using only one topology, typically a feed-forward neural network without hidden nodes. This requires from the experimenter the implicit knowledge that such a network is a good starting point. Putting biases in the selections gradients possesses at least the advantage of being explicit, and therefore could allow a better analysis. Compared to incremental evolution methods, the approach presented in this paper puts fewer constraints on the search because intermediate steps are not mandatory. We only suggest potentially useful steps; the process is then free to use or to ignore them.

Having highlighted the need for multiple selection gradients and modular genomes, we can wonder if the selected genome and MOEAs are the best tools for these tasks. The main difference between the proposed encoding and other modular encodings lies in the idea that genotypic modules should develop to phenotypic modules. However, applying a selection pressure directly on the sub-network associated with a genotypic module might be enough to facilitate the emergence of phenotypic modules. Hence, more elaborated modular encodings (e. g. [START_REF] Mouret | Mennag: a modular, regular and hierarchical encoding for neural-networks based on attribute grammars[END_REF]) could be used as long as the inputs and outputs of each module can be determined.

The use of a classical Pareto-based MOEA to introduce multiple selection gradients allows us to rely on a well established set of efficient algorithms. However, recent theoretical [START_REF] Teytaud | On the hardness of offline multi-objective optimization[END_REF] and empirical [START_REF] Praditwong | How well do multi-objective evolutionary algorithms scale to large problems[END_REF] studies demonstrate that such evolutionary processes were not well suited to optimize more than three antagonistic objectives. By employing an objective for each sub-function, the proposed process will easily require more than three objectives and consequently could put Pareto-based MOEA out of their limits. Nevertheless, if our starting hypothesis is valid, the objectives will not be antagonistic: the exaptation process should exploit individuals with a good fitness on one objective to build individuals for the more difficult objectives. Therefore, some individuals could dominate on most objectives. However, the dominance relation puts all objectives at the same level whereas we are mainly interested in the main task. Some experiments with modified domination criteria may therefore reveal themselves more efficient.

VI. CONCLUSION

We explored the hypothesis that multiple selection gradients and a modular genotype-phenotype map were two key-points to evolve complex artifacts. To that aim, we defined a bio-inspired modular encoding and employed it with a Pareto-based MOEA in which one objective rewarded the efficiency of a module to complete a sub-function. We further hypothesized that exaptations should occur in this evolutionary framework by co-opting modules evolved for simple sub-functions to solve more complex ones.

We tested these ideas on the evolution of neural networks to compute a modular Boolean function. Our results show that: (1) the proposed method is efficient to solve this task;

(2) both modularity and multiple selections gradients were required to converge faster than the control experiments. This prominent role of multiple selection pressures contradicts the basic assumption that underlies previously published modular methods for the evolution of neural networks.

In further work, we will try to link modules used in other modular encodings to selection gradients in order to understand the set of features required for modular encoding. Then, other methods to create multiple selection gradients should be investigated because Pareto-based MOEA are not well suited to optimize more than three antagonistic objectives. Last, the proposed method should be benchmarked on other tasks to assess its generality.

Fig. 2 .

 2 Fig. 2. The three main mutation operators. (a) Parcellation: isolation of a sub-network. (b) Integration: replacing a sub-network by a link to a parcellated one (this allows the repetition of a module) (c) Differentiation: putting a sub-network back in the main network.

Fig. 3 .

 3 Fig. 3.Principle of the cross-over operator. If both parents have a parcellated module, it is exchanged to create their offspring. Otherwise, the each children is a copy of one of the parent (mutation operators are then applied).

Fig. 4 .

 4 Fig. 4.

Fig. 5 .

 5 Fig. 5. (a) Typical neural network obtained with the proposed approach. (b) The parcellated module used in (a).

Fig. 6 .

 6 Fig. 6. Shapley values for each component. M: Multiple selection gradients; P: Parcellation; C: Cross-over; I: Integration; D: differentiation.

Jean-Baptiste Mouret and Stéphane Doncieux are with the Université Pierre et Marie Curie (UPMC) -Paris 6, Institut des Systèmes Intelligents et de Robotique (ISIR), CNRS UMR 7222, F-75005, Paris, France; e-mail: {mouret,doncieux}@isir.fr

Pleiotropy occurs when a single gene influences multiple phenotypic traits.

In real organisms, many levels of modules are nested and so the modularity of genotype-phenotype map can be difficult to express clearly.

• structural mutation: addition/removal of a neuron or a connection; • parametric mutation: change of a randomly chosen

This difference is statistically significant (p < 0.003).

Actually, they are equals but proving this equality is out of the scope of this work.

APPENDIX

• population size: 400 • weights/biases: ˘-2.0, -1.5, -1.0, -0.5, 0.0, 0.5, 1.0, 1.


Overcoming the bootstrap problem in evolutionary robotics using behavioral diversity

Jean-Baptiste Mouret Stéphane Doncieux

Abstract-The bootstrap problem is often recognized as one of the main challenges of evolutionary robotics: if all individuals from the first randomly generated population perform equally poorly, the evolutionary process won't generate any interesting solution. To overcome this lack of fitness gradient, we propose to efficiently explore behaviors until the evolutionary process finds an individual with a non-minimal fitness. To that aim, we introduce an original diversity-preservation mechanism, called behavioral diversity, that relies on a distance between behaviors (instead of genotypes or phenotypes) and multiobjective evolutionary optimization.

This approach has been successfully tested and compared to a recently published incremental evolution method (multisubgoal evolution) on the evolution of a neuro-controller for a light-seeking mobile robot. Results obtained with these two approaches are qualitatively similar although the introduced one is less directed than multi-subgoal evolution.

I. INTRODUCTION

Evolutionary algorithms have been widely used to design controllers, and especially neuro-controllers, for robots (see [START_REF] Meyer | Evolutionary robotics: a survey of applications and problems[END_REF], [START_REF] Nolfi | Evolutionary Robotics: The Biology, Intelligence, and Technology of Self-Organizing Machines[END_REF] and [START_REF] Floreano | Neuroevolution: from architectures to learning[END_REF] for an overview). Compared to other learning methods, one of their main strength is their ability to evolve both the structure and the parameters of complex architectures using a high-level reward function. However, this huge amount of work hides many unsuccessful attempts to evolve complex behaviors by only rewarding the performance of the global behavior. The bootstrap problem is often viewed as the main cause of this difficulty, and consequently as one of the main challenges of evolutionary robotics: if the objective is so hard that all the individuals in the first generation perform equally poorly, evolution cannot start and no functioning controllers will be found. For instance, it has been found hard to evolve a light-seeking behavior for a robot in a complex arena without having first evolved an obstacle-avoidance reflex [START_REF] Urzelai | Incremental robot shaping[END_REF].

In consequence, many researchers added some kind of rewards for intermediate steps, leading to successful incremental evolution processes [START_REF] Urzelai | Incremental robot shaping[END_REF]- [START_REF] Mouret | Incremental evolution of animats' behaviors as a multi-objective optimization[END_REF]. Nonetheless, these evolutionary approaches rely on some assumptions that require an accurate knowledge of the problem to solve and can lead the evolutionary algorithm to a local extremum. Most of them, for instance, require to precisely order the different sub-tasks or to determine when to switch from a sub-task to another one. These biases prevent them from scaling up well to more complex or more open tasks; remarkably, most of them have been tried with only two or three sub-tasks.

Jean-Baptiste Mouret and Stéphane Doncieux are with the Université Pierre et Marie Curie (UPMC) -Paris 6, Institut des Systèmes Intelligents et de Robotique (ISIR), CNRS UMR 7222, F-75005, Paris, France; e-mail: {mouret,doncieux}@isir.fr Fig. 1. Dominated and non-dominated solutions for a problem in which the two objectives f 1 and f 2 must be maximized.

Another idea to bootstrap an evolutionary process is to efficiently explore the neighborhood of current candidate solutions to find one with a non-minimal fitness. This concept is close to diversity-preserving mechanisms, widely investigated in evolutionary computation (e.g [START_REF] Goldberg | Genetic algorithms with sharing for multimodal function optimization[END_REF]- [START_REF] Mahfoud | Niching methods[END_REF]), which typically rely on a distance between the genotypes or the phenotypes. However, such distances are conceptually and computationally difficult to employ with complex structures as neural networks.

Drawing inspiration from these diversity-preserving mechanisms and adapting them to evolutionary robotics, we introduce in this paper the behavioral diversity, an original method to maintain the diversity in a population that relies on a distance between behaviors and a multiobjective evolutionary algorithm (MOEA, see [START_REF] Deb | Multi-objectives optimization using evolutionnary algorithms[END_REF]). We then show how such a diversity preservation mechanism can efficiently overcome the bootstrap problem in an evolutionary robotics experiment in which a simulated robot that has to successively reach some lights in an arena. As a reference point, we compare the results obtained using this new approach with the ones obtained with multi-subgoal evolution [START_REF] Mouret | Incremental evolution of animats' behaviors as a multi-objective optimization[END_REF], a recently published incremental method based on multiobjective evolution.

The remainder of this paper is organized into four parts. In section II, we briefly review the related literature about multiobjective evolutionary algorithms, incremental evolution and diversity preservation. The proposed method is detailed in section III. Section IV describes an evolutionary robotics experiment and reports the results of both methods. A short discussion concludes this paper.

II. PREVIOUS WORK

A. Multi-objective evolutionary algorithms

Most problems tackled in evolutionary robotics involve trade-offs between numerous objectives, such as energy versus efficiency (see e.g. [START_REF] Mouret | Incremental evolution of target-following neuro-controllers for flapping-wing animats[END_REF]). The classical approach is to aggregate objectives using a weighted sum or a product to define a composite fitness. Hence, a particular set of weights defines a particular trade-off. Despite its experimental success, this method has several substantial drawbacks. First, it can be theoretically shown that some trade-offs cannot be found (see [START_REF] Deb | Multi-objectives optimization using evolutionnary algorithms[END_REF]), thus silently constraining the study to a subset of possible trade-offs. Second, weights have usually to be inferred from a time-consuming trial-and-error approach because no theoretical methods to define them are available. Last, the exploration of each trade-off requires launching a new evolutionary process. These different implications generally limit analysis and discussions of results to one or two particular trade-offs, associated to a particular set of weight parameters that may be difficult to explain.

Recent research in evolutionary computation proposed numerous algorithms to simultaneously optimize several objectives without aggregating them [START_REF] Deb | Multi-objectives optimization using evolutionnary algorithms[END_REF]; most of them rely on the concept of domination and generate the so-called Pareto Front (figure 1):

Definition 1: A solution x (1) is said to dominate another solution x (2) , if both conditions 1 and 2 are true: 1) the solution x (1) is not worse than x (2) with respect to all objectives; 2) the solution x (1) is strictly better than x (2) with respect to at least one objective. The non-dominated set of the entire feasible search space is the globally Pareto-optimal set (Pareto front).

Multi-objective evolutionary algorithms are designed to find the Pareto-front, i.e. the set of all the Pareto-optimal trade-offs. Most of them rely on two mechanisms:

• a selection procedure that ensures that non-dominated individuals have a selective advantage; • a diversity-preservation method designed to spread nondominated individuals along the whole Pareto front, i.e. that as many different trade-offs as possible are explored.

A typical MOEA sorts individuals with respect to domination. Non-dominated individuals may, for instance, be ranked 1, making them the most suitable for reproduction. Individuals which are only dominated by non-dominated ones may be ranked 2, and so on. The diversity on the Pareto front can be maintained using several ways such as fitness sharing [START_REF] Fonseca | Genetic algorithms for multiobjective optimization : formulation, discussion and generalization[END_REF] or clustering methods [START_REF] Zitzler | SPEA2: Improving the Strength Pareto Evolutionary Algorithm[END_REF].

Despite their considerable success in the optimization field (see [START_REF] Coello | Applications Of Multi-Objective Evolutionary Algorithms[END_REF]), MOEAs deserved little attention in the evolutionary robotic literature (notable exceptions being [START_REF] Mouret | Incremental evolution of target-following neuro-controllers for flapping-wing animats[END_REF], [START_REF] Shan | Design of central pattern generator for humanoid robot walking based on multi-objective ga[END_REF]- [START_REF] Moshaiov | Multi-objective Evolution of Robot Neuro-Controllers[END_REF]). One of the ambitions of this paper is to highlight how they can be useful in evolutionary robotics, in particular to solve the bootstrap problem.

B. Incremental evolution

Four main approaches emerge from the different attempts to tackle the bootstrap problem in evolutionary robotics: staged evolution, environmental complexification, fitness shaping and behavioral decomposition.

Staged evolution is probably the most intuitive -and most used -incremental process. The main task is split into ordered sub-tasks, each with a corresponding fitness function. During each stage, individuals are selected only using the associated fitness. The process is switched from each stage to the next one once a convergence criterion is reached, for instance when a "good enough" fitness is obtained by the best individual or when the best fitness doesn't change for some generations. This technique has first been successfully employed by Harvey et al. [START_REF] Harvey | Seeing the light: artificial evolution; real vision[END_REF] to evolve a vision-based target location task. Three stages were used, from locating a large immobile target to tracking a moving smaller one.

Many other examples of staged evolution can be found in the literature (e.g. [START_REF] Kodjabachian | Evolution and development of neural networks controlling locomotion, gradient-following, and obstacleavoidance in artificial insects[END_REF], [START_REF] Urzelai | Incremental Evolution with Minimal Resources[END_REF], [START_REF] Mouret | Incremental evolution of target-following neuro-controllers for flapping-wing animats[END_REF], [START_REF] Winkeler | Incremental evolution in genetic programming[END_REF]- [START_REF] Parker | The Incremental Evolution of Gaits for Hexapod Robots[END_REF]).

Following the same idea, environmental complexification aims at more continuously changing the complexity of the task through the tuning of dedicated parameters. Gomez and Miikkulainen [START_REF] Gomez | Incremental evolution of complex general behavior[END_REF] thus worked on a prey-capture task parameterized with the prey speed and the delay before starting the pursuit. Ten ordered sub-tasks were thus defined by specific values of these parameters and their use proved to lead to more efficient solutions.

In behavioral decomposition, each sub-task is solved by a sub-controller evolved using a dedicated fitness, different from the main goal. Another evolutionary process is then used to combine all the sub-controllers together. This approach has been recently used to evolve a position controller for an autonomous helicopter [START_REF] De Nardi | Evolution of Neural Networks for Helicopter Control: Why Modularity Matters[END_REF].

Fitness shaping is sometimes used to help to bootstrap an evolutionary process, though it is not often seen as an incremental evolution scheme. The fitness is defined as an aggregation (a weighted sum or a product) of different evaluation criteria in order to create a fitness gradient. For example, Nolfi and Parisi [START_REF] Nolfi | Evolving non-Trivial Behaviors on Real Robots: An Autonomous Robot that Picks up Objects[END_REF] successfully evolved a feedforward neuro-controller for a robot to locate, recognize, and grasp a target object. The fitness was increased if the individual was close to the target object, if the target was in front of the robot, if the robot tried to pick-up the object, if the robot had the object in the gripper and if the robot released the object outside the area.

C. Multi-subgoal evolution

The previously mentioned approaches allowed to generate non trivial behaviors, but they require an important help from the human designer: intermediate steps have to be defined, ordered and their combination also requires the intervention of the human designer, may it be to trigger the switch between these steps or to gather all the elementary solutions in a wider controller. The method introduced in [START_REF] Mouret | Incremental evolution of animats' behaviors as a multi-objective optimization[END_REF], called multi-subgoal evolution, intends to relax some of the constraints of these incremental approaches.

In multi-subgoal optimization, intermediate steps still have to be defined, but once this is done, the evolutionary process will do the rest, without the need to order them or to choose when to switch between the goals. Another interesting aspect with this approach is that all those intermediate steps are optional. We can therefore provide more information than what is actually necessary without endangering the convergence of the evolutionary run. This feature also differentiates it from fitness shaping in which the fitness pushes towards individuals that fulfill all the intermediate behaviors even if some of them are not mandatory.

The principle of multi-subgoal optimization consists in defining an objective for each of the intermediate steps and another one for the final goal and then to use multiobjective evolutionary algorithms to perform the search. In such a context, difficult objectives that require to solve simpler tasks won't be explored at all by the algorithm at the beginning of the search process, as all individuals will perform equally poorly, while simpler objectives will draw much of the search effort. As soon as performances will be high enough on simpler tasks so that more complex tasks resolution will be reachable, individuals able to solve them will and the algorithm will then automatically start to concentrate on this part of the search space. The other advantage is that this "switch" is not irremediable because the search with respect to the simpler tasks will never stop, thus leaving the possibility to obtain individuals relying on more efficient solutions of the simpler problems. On the other side, the search on the complex task will start as soon as possible, thus avoiding to consider only individuals that may be overspecialized on the simple task which could be difficult to adapt to the complex one, as it can happen with manual switches. Formally, this approach can be considered as a multiobjective formulation of fitness shaping.

More details about multi-subgoal evolution can be found in [START_REF] Mouret | Incremental evolution of animats' behaviors as a multi-objective optimization[END_REF].

D. Diversity

The previously described approach requires to optimize many objectives whereas current multiobjective evolutionary algorithms have poor performance when more than three objectives are used [START_REF] Purshouse | On the Evolutionary Optimization of Many Conflicting Objectives[END_REF], [START_REF] Teytaud | On the hardness of offline multi-objective optimization[END_REF]. We consequently explored a different idea relying on the exploration of new behaviors.

The bootstrap problem, and similarly the local minima problem, takes its roots in a lack of a useful selective gradient to select potentially good individuals: all of them share the same poor fitness (sometimes, all of them get a null fitness). In the best case, the evolution is then equivalent to a random search; in the worst case, we observe a premature convergence of the evolutionary process to one, often degenerate, solution. Among genotypes with the same fitness, we can heuristically choose the ones which are the most original. This idea, which can be seen as a push in favor of diversity, has a long history in evolutionary algorithm literature, one of the most popular method being fitness sharing [START_REF] Goldberg | Genetic algorithms with sharing for multimodal function optimization[END_REF]. In this approach, the search landscape is modified by decreasing the fitness of similar individuals, thus encouraging search in unexplored regions. More precisely, if d i j is the distance between the genotype of i and j, the sharing function sh(d i j ) is defined as follows:

Sh(d i j ) = 1 -( d i j σ share ) α , if d ≤ σ share 0 otherwise (1)
where σ share is a user-defined parameter. The fitness of individual i is then divided by the niche count c i :

F i = F(x i ) c i where c i = N ∑ j=1 Sh(d i j ) (2)
Dividing the fitness by the niche count can be seen as an aggregation of two objectives, the fitness and the diversity. Given the recent progress of Pareto-based multiobjective evolutionary algorithms, some researchers suggested to use a multiobjective approach instead of the aggregation. This explicitly models the classic trade-off between exploration and exploitation [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] and let the evolutionary algorithm automatically tune it. Different ways to improve the diversity by adding an objective have been investigated and compared, from the distance to the nearest neighbor to a simple random value [START_REF] Bui | Multiobjective optimization for dynamic environments[END_REF], [START_REF] Abbass | Searching under multi-evolutionary pressures[END_REF], [START_REF] Jong | Reducing bloat and promoting diversity using multi-objective methods[END_REF]. All the available studies conclude that (1) multiobjective methods to preserve the diversity are more efficient than their single-objective counterparts and (2) the mean distance between the individual and the remaining of the population leads to the best results.

III. BEHAVIORAL DIVERSITY

Computing a distance between individuals is, however, difficult in evolutionary robotics, especially when evolving the topology of neuro-controllers. The distance between genotypes is often hard to compute because typical distances between two graphs, thereby two neural networks, are NPcomplete [START_REF] Bunke | A graph distance metric based on the maximal common subgraph[END_REF]. The permutation problem [START_REF] Yao | Evolving artificial neural networks[END_REF] prevents the definition of simple metrics on neural-networks with a fixed topology. Although some methods have been published to allow the fitness sharing of neural networks [START_REF] Stanley | Evolving neural networks through augmenting topologies[END_REF], an infinity of very different neural-networks can lead to a similar behavior. This is especially striking with degenerate individuals as those observed when the evolutionary process is unable to start: any neural network not linked to the motors will lead to an immobile robot, thus fitness sharing won't help here. Moreover, fitness sharing has not originally been formulated for multiobjective evolution while the interest of using these methods in evolutionary robotics is growing (see [START_REF] Mouret | Incremental evolution of target-following neuro-controllers for flapping-wing animats[END_REF], [START_REF] Teo | Automatic Generation of Controllers for Embodied Legged Organisms: A Pareto Evolutionary Multi-Objective Approach[END_REF], [START_REF] De Margerie | Artificial evolution of the morphology and kinematics in a flapping-wing mini-UAV[END_REF], for instance). Hence, maintaining the diversity of genotypes with fitness sharing when evolving neuro-controllers for robots is hard to implement and often inefficient.

The goal of fitness sharing was to differentiate individuals on other aspects than fitness values. Considering the genotype to provide some more information to push towards diversity was natural in classical evolutionary algorithms, but evolutionary robotics experiments offers some other possibilities: the behavior can be used to distinguish individuals. Fitness values are based on an observation of the behavior, but they are focused on a small set of behavior consequences, not on behaviors on their own. As an alternative approach to fitness sharing, we propose to compute a distance between behaviors instead of genotypes, thus explicitly promoting new behaviors. This distance could be used to modulate the fitness, as in fitness sharing. However, using a multiobjective evolutionary algorithm allows to rely on the good results obtained with multiobjective approaches to preserve the diversity and to explicitly model the exploration/exploitation trade-off.

Let us denote by D i j the distance between the behaviors of individuals i and j. In its simplest form, the behavior sharing function B(i) can be formulated as the mean distance between the behavior of i and the one of each individual of the population. Instead of maximizing the fitness F(i) only, we have to maximize two objectives:

F(i) B(i) = 1 N ∑ N j=1 D i j (3)
Designing a distance between behaviors of robots may seem to be a challenging task. However, we have found that in many cases a distance built on basic features tied to robot behavior was sufficient to bootstrap the evolutionary process and avoid many local minima. A simple and efficient approach for mobile robotics is to associate to each individual i a vector v (i) describing the state of the environment at the end of the experiment. D i j can then be defined as the Euclidean distance between v (i) and v ( j) . For instance, if the robot has to move objects in an arena, a v (i) may contain the positions of the objects. If the robot has to explore a maze, the final positions can also be used. As a last example, when evolving a n inputs logic function, e.g. XOR, the output for each of the 2 n set of inputs can be stored in a 2 n -dimensional vector.

The behavioral diversity approach shares some similarities with the recently published novelty search [START_REF] Lehman | Exploiting Open-Endedness to Solve Problems Through the Search for Novelty[END_REF]. In this paper, Lehman and Stanley proposed to maximize the novelty of behaviors instead of fitness to define an open-ended evolutionary process. Using a distance between behaviors D(i, j), similar to the one discussed here, they defined the sparseness ρ at a point x:

ρ(x) = 1 k ∑ k i=0 D(x, µ i
) where µ i is the i-th nearest neighbor of x with respect to the distance D. The neighbors are computed using the current population and an archive of all the previously explored behaviors. Three main points differentiate the two approaches:

• they optimize only novelty whereas we propose to use a multiobjective algorithm that does not ignore the main goal; • they use an archive of all the previously explored behaviors;

• since the distance is computed using the archive and the current population, they mixed a diversity measure with a novelty one. Despite the substantially high computational cost induced by the growing archive, novelty search could avoid evolutionary cycles that could occur with behavioral diversity. Nonetheless, we will see in the next section that some intuitive Fig. 2. Overview of the benchmark task. Seven colored lights are placed in an arena, each of them being mounted on a button switch which turns on some other lights; the light circuit (unknown to the algorithm) is represented by arrows. The goal-task is to turn on light 6.

behavior distance can not be employed with novelty search while they can be used with behavioral diversity.

IV. LIGHT-SEEKING ROBOT

A. Main task

To benchmark the proposed approach on a typical incremental task, we designed a variant of the light-seeking task which involves seven sub-tasks with complex dependencies. A similar but simple version of this task has, for example, been studied in [START_REF] Floreano | Evolution of plastic control networks[END_REF]. A simulated wheeled robot is placed in an arena with seven different colored lights (figure 2). Each light is mounted on a button switch which, when pressed, turns on one or more lights in the arena. Once a light is on, it remains in the same state during the whole experiment. The main goal is to turn on a particular light. The connection between lights and switches, a simple explicit dependency between tasks, is to be discovered by the evolutionary algorithm. To benchmark future incremental algorithms, the task can be easily complexified by adding lights or changing the dependencies between lights. This task has been chosen because it does not require nor complex genotypes nor complex fitness functions to be solved: its main challenge is its incremental nature.

The underlying structure of this incremental task is depicted on figure 2. Each lights turn on only if the previous related light is on, following the relations depicted on figure 2. The first light turns on two other lights, creating two paths to solve the goal-task. A part of the population may choose to learn to turn on lights {0, 1, 2, 3, 4, 5, 6} and another one may learn sequence {0, 4, 5, 6}. This task can therefore be learned in different ways. Despite the simplicity of this problem and of the different sub-tasks, it involves at least four sub-tasks (turn on each of the lights belonging to the shortest path to the goal light), making it one of the most complex composite tasks explored with incremental evolution at this time.

The simulated robot (figure 3) is equipped with seven pairs of light-sensors, each one sensing a different light color. Light sensors have a 90 degrees field of view and a binary output (1 if the light is in the field of view, 0 otherwise). A robot is controlled by an evolved neural network with 14 inputs and 2 outputs whose topology and synaptic weights are encoded by a simple direct encoding [START_REF] Meyer | Evolutionary robotics: a survey of applications and problems[END_REF]: the network is represented by a weighted directed graph in which neurons and connections can be randomly added or removed. Two kinds of mutations are possible:

• structural mutation: addition/removal of a neuron or a connection; • parametric mutation: change of a randomly chosen synaptic weight or a neuronal bias; we used here a change in a set of 15 possible values (similar results were obtained using real-valued weights and Gaussian mutation). The mutation rates of each operator are detailed in appendix.

Cross-over is not used. Neurons use the following activation function, based on tanh(x), to easily allow the inhibition of a neuron in the case of negative inputs:

f (x) = tanh(x) if x > 0 0 otherwise

B. Experimental setup

Behavioral diversity and multi-subgoal evolution have been tested on this problem to compare them.

To use the multi-subgoal approach, one objective for each light (F msb i , i ∈ 0, 1, • • • , 6) was defined. To avoid overlearning and check the robustness of the evolved behaviors, each objective is the minimal score for three experiments in which the robot starts from different positions:

F msb i (x) = min n=1,2,3 -ϕ(n, i) T ( 4
)
where i = 0, 1, ..., 6 is the identifier of the light, T is the length (in time-steps) of each experiments and ϕ(n, i) denotes the number of time-steps spent before reaching light i, for experiment n.

The behavioral diversity approach first requires to define a classic fitness F bd corresponding to the goal to be reached. Here we used the number of time-steps to reach the last light:

F bd (x) = F msb 6 (x) = min n=1,2,3 -ϕ(n, i) T (5)
We then have to define a distance D i j between the behavior of i and j. We chose to describe the behavior of i by a Boolean vector v (i) such that:

v (i) k = 1 if the k-th switch has been pressed 0 otherwise (6)
D i j can be computed using an Euclidean distance between v (i) and v ( j) :

D i j = v (i) -v ( j) (7)
This distance lead to surprising results if we use it with novelty search. To distinguish novelty and diversity, we only consider here the archive when computing ρ. Thus, we will not mix the diversity with the novelty. At the end of the random generation, the archive typically contains the following behaviors, due to the incremental structure of the task: 0000000, 10000000, 1000100 and 1100000. We are clearly more interested in 1000100 and 1100000 because the corresponding robot reaches more lights. Since the archive contains only 4 entries, only 4 kinds of behaviors are present in the population. Let's compute their novelty score to know which ones will be selected for the reproduction: 0000000 : ρ = 0.957 1000000 : ρ = 0.75 1000100 : ρ = 0.957 1100000 : ρ = 0.957

The most interesting individuals have the same fitness than individuals with the 0000000 behavior. Since the latter is the least interesting and easiest to obtain, we can predict that the evolutionary process will never start. This prediction has been confirmed by some preliminary experiments.

We used NSGA-2 [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF], a state-of-the-art MOEA, to maximize the objectives in the multi-subgoal case and in the behavioral diversity case, with a population of 200 individuals. 30 runs of 1000 generations for each of the proposed methods have been launched.

V. RESULTS

Runs of a direct evolution algorithm designed to minimize the number of time-steps to turn-on the last light, did not find any working controller, all individuals obtaining the minimum fitness. This contrasts with the results obtained with the two presented methods, summarized in table I. In both cases, all the runs converged to very similar values of the goal fitness. The bootstrap generation (the generation where at least one individual reach a main fitness greater than -0.8) was significantly lower with multi-subgoal evolution than with the behavioral diversity (138 versus 218) but both values are of the same order of magnitude: the bootstrap problem was overcome in a few hundred of generations and similar fitness values were obtained at comparable generations.

All observed dominant individuals for the last light objective followed the shortest path (i.e. 0, 4, 5, 6) whereas a slightly longer path, using more lights, was possible (figure 4). An aggregation of all the subgoals into one single objective would have lead to individuals trying to push all the switch buttons. All the obtained neuro-controllers were robust to the robot starting point: from any reasonable starting position, the robot efficiently performed the good sequence. As a consequence, not overlearned behavior was observed.

Figure 5 displays the neural network of a typical nondominated individual, after 500 generations. This neural network is surprisingly simple as it uses only 4 hidden neurons and some sensors are not connected to any neuron. This low complexity emphasizes that the investigated problem is mostly a selection pressure problem and not a genotype problem. Moreover, it can be noticed that such simple neural network is unlikely to learn the complex sequence "by heart" and more likely to rely on its sensors.

To analyze the bootstrap process, we plotted the proportion of the population which reaches each light in a typical run of each method (figures 6 and 7).

The diagram corresponding to multi-subgoals evolution shows a clear staircase structure. Almost 50 generations are required to obtain the first individuals to reach the light 0 but after 100 generations, the whole population reaches it. Individuals can then switch the next lights, 1 and 4. These new skills are shared by the whole population in a few generations, allowing some individuals to reach light 6 in less than 150 generations. This incremental structure gives support to our assumptions about the effect of the multiobjective evolutionary pressure: the first attainable objectives are first optimized and the process automatically switches to new ones as soon as possible; the two hypothesis -the two available paths to solve the task -are explored simultaneously; and solved objectives apply almost no pressure once they are solved.

The diagram corresponding to behavioral diversity shows a very similar structure in which gradients show that each subtasks is successively solved. However, the picture is noisier because the diversity approach also maintains individuals that don't solve each task, since at a given generation, they may be different from the remaining of the population. Significantly fewer generations are required to converge with the multi-subgoal method than with the behavioral diversity.

VI. CONCLUSION AND DISCUSSION

We proposed a new method to solve the bootstrap problem observed in evolutionary robotics and compared it with a recently published approach. Compared to previous methods, both approaches don't require to order sub-tasks or to specify when to switch between them since the evolutionary process automatically explores all the available orders. Moreover, the performance on the subgoals can be continuously improved and some may be ignored. We showed that both methods efficiently solved the bootstrap problem on a typical incremental robotics task although the newly introduced method is less directive than the previously published one. Hence, our contribution is twofold: [START_REF] Meyer | Evolutionary robotics: a survey of applications and problems[END_REF] we propose a new way to maintain the diversity of a population, especially adapted to evolutionary robotics and (2) we show that such a diversity preservation mechanism can efficiently overcome the bootstrap problem in an evolutionary robotics experiment.

Although they seem at first glance very different, the two approaches actually share the same basic principle: their common goal is to provide a selective pressure towards exploration and they only differ by the method used to supply it. Both behavioral diversity and multi-subgoal will select individuals which are able to switch on lights that no other can1 . However, the behavioral diversity ranks individuals according to an averaged Euclidean distance whereas multisubgoal uses a Pareto sort. Consequently, behavioral diversity will also select individuals that can't switch a single light, as long as they are the only one to do so, whereas an individual that switches any light will always dominate an individual that doesn't switch any light at all in multi-subgoal. This doesn't make a huge difference here, as individuals that don't switch any light are easy to find and then won't capture the search effort for long. More formally, the main difference lies in the fact that multi-subgoal is an oriented search. It means that the designer has to know how to sort good and bad behaviors and how to evaluate the robot's performance for each of the subgoals. To use behavioral diversity, only a frame in which behaviors can be described needs to be provided. On the toy problem we considered here, this doesn't make a huge difference, neither on the results, nor on the knowledge we have provided to the algorithm, but it might be more significant in other tasks.

The simplicity of behavioral diversity makes this approach appealing and easy to integrate in an existent framework. However, in particular problems, it may be hard to design a relevant distance between behaviors. A generic way to describe behaviors of mobile robots would be useful to design such distances, hence making easier the application of behavioral diversity to new tasks.

Behavioral diversity makes explicit the exploration and exploitation part of the algorithm through the behavioral diversity objective and the goal fitness. Compared to other learning algorithms like reinforcement learning, there is no need to explicit here the balance between the two objectives, it is autonomously managed by the multiobjective algorithm. The true ability of the algorithm to handle this important aspect of the search should be more carefully studied.

The cross-over operator, not used in this work for the sake of simplicity, could have an effect on the two investigated methods. Since multi-subgoal evolution and behavioral diversity maintain individuals able to solve different subtasks, each part of them could be combined to create more efficient individuals. Using this operator to evolve neurocontrollers would probably require a modular encoding of neural networks, such as MENNAG [START_REF] Mouret | Mennag: a modular, regular and hierarchical encoding for neural-networks based on attribute grammars[END_REF].

Fig. 3 .

 3 Fig.3. The simulated robot is equipped with seven pairs of binary light sensors, each one sensing a different light. The controller is an evolved neural-network with 14 inputs and 2 outputs (the speed of the motors).

Fig. 4 .

 4 Fig. 4. Trajectory of a typical non-dominated individual after 500 generation. The robot follows the shortest path (0,4,5,6).

Fig. 5 .

 5 Fig. 5. Neural network of a typical non-dominated individual, after 500 generations. Input and output neurons are double-circled (some inputs are unused); i0 and i1 are connected to the sensors able to see the first light, i2 and i3 the second one, etc.

Fig. 6 .

 6 Fig. 6. Multi-subgoal evolution. (top) Proportion of individuals which reach each light as a function the generation, in a typical run. (bottom) Best fitness for the main objective.

Fig. 7 .

 7 Fig. 7. Behavioral diversity. (top) Proportion of individuals which reach each light as a function of generation, in a typical run. (bottom) Best fitness for the main objective.

They would be even more similar with a binary value for the subgoals in the multi-subgoal approach: 0 light not switched on, 1 light switched on during evaluation.

APPENDIX

• population size: 200 • number of runs : 30 for each method • weights:

-5.0, -4.0, -3.0, -2.0, -1.5, -1.0, -0.5, 0.0, 0.5, 1.0, 1.5, 2.0, 3.0, 4.0, 5.0 • weight mutation rate: 0.