Paul Tonelli
email: tonelli@isir.upmc.fr

Jean-Baptiste Mouret
email: mouret@isir.upmc.fr

Using a Map-Based Encoding to Evolve Plastic Neural Networks

Many controllers for complex agents have been successfully generated by automatically desiging artificial neural networks with evolutionary algorithms. However, typical evolved neural networks are not able to adapt themselves online, making them unable to perform tasks that require online adaptation. Nature solved this problem on animals with plastic nervous systems. Inpired by neuroscience models of plastic neuralnetwork, the present contribution proposes to use a combination of Hebbian learning, neuro-modulation and a a generative mapbased encoding. We applied the proposed approach on a problem from operant conditioning (a Skinner box), in which numerous different association rules can be learned. Results show that the map-based encoding scaled up better than a classic direct encoding on this task. Evolving neural networks using a mapbased generative encoding also lead to networks that works with most rule sets even when the evolution is done on a small subset of all the possible cases. Such a generative encoding therefore appears as a key to improve the generalization abilities of evolved adaptive neural networks.

I. INTRODUCTION

Artificial Neural Networks (ANNs) are now ubiquitous in neuroscience, but also in computational intelligence; this technological usefulness of ANNs and their links with their biological neurons, make them natural candidates to design bio-inspired controllers for intelligent agents. Nevertheless, neural networks -and especially recurrent ones-are also complex dynamic systems which are difficult to design with conventional engineering methods. A sensible way to tackle this challenge is to employ evolutionary algorithms, mainly because they only care about the result and do not constrain the inner workings of solutions. Additionally, these algorithms can act both on the structure and the parameters of neurocontrollers.

Evolved ANNs show impressive results as controllers for autonomous robots and artificial agents [START_REF] Meyer | Evolutionary approaches to neural control of rolling, walking, swimming and flying animats or robots[END_REF]- [START_REF] Floreano | Bio-inspired artificial intelligence: theories, methods, and technologies[END_REF]. But to be truly efficient in non-stationary problems, ANNs should be not only adapted to their task, but also plastic by adapting themselves during their lifetime. Following this line of thought, several papers proposed to add Hebbian learning rules to evolved ANNs [START_REF] Urzelai | Evolution of Adaptive Synapses : Robots with Fast Adaptive Behavior in New Environments[END_REF]; this work has then been extended to include neuromodulatory neurons that can trigger Hebbian learning in their adjacent neurons [START_REF] Soltoggio | Evolving neuromodulatory topologies for reinforcement learning-like problems[END_REF]. Despite promising results, these works required the agent to learn one choice with only two options (e.g. left or right in a maze) and each scenario was tested in the fitness function. This situation is not realistic for unknown environments, in which the agent will have to learn to react to situations for which it has not been selected. Moreover, current successful setups for evolved ANNs involves only a few outputs (less than 3) and a few inputs (less than 8).

The present paper aims at evolving plastic neural networks with better generalization abilities and able to use more input/outputs. Our approach relies on a neuroscience-inspired generative encoding [START_REF] Mouret | Importing the computational neuroscience toolbox into neuro-evolution-application to basal ganglia[END_REF], neuro-modulation of heterosynaptic Hebbian rules [START_REF] Soltoggio | Evolving neuromodulatory topologies for reinforcement learning-like problems[END_REF] and, to mitigate deception, an explicit selective pressures for new behaviors [START_REF] Soltoggio | Novelty of behaviour as a basis for the neuro-evolution of operant reward learning[END_REF]- [START_REF] Mouret | Using Behavioral Exploration Objectives to Solve Deceptive Problems in Neuro-evolution[END_REF]. To evaluate the proposed approach, we used a simulated Skinner box [START_REF] Skinner | The experimental analysis of operant behavior[END_REF], a typical setup in operant conditioning in which an agent must learn association rules between stimuli and actions.

II. BACKGROUND

A. Computational Neuroscience

Most animals critically rely on their ability to adapt their behavior thanks to modifications of the strength of synapses in their nervous systems, a phenomenon called synaptic plasticity [START_REF] Abbott | Synaptic computation[END_REF], [START_REF] Floreano | Neuroevolution: From Architectures to Learning[END_REF]. This process has been famously modeled by the Hebbian rule [START_REF] Hebb | The organization of behavior: A neuropsychological theory[END_REF], which states that the strength of a connection increases when both pre-and post-synaptic neurons have a strong activity. Further researches extended this learning rule to more general heterosynaptic rules that correlates the modifications to more complex combinations of pre and post synaptic activity [START_REF] Rauschecker | Changes in the circuitry of the kitten visual cortex are gated by postsynaptic activity[END_REF]. A generalized heterosynaptic Hebbian rule can be written as follows [START_REF] Niv | Evolution of Reinforcement Learning in Uncertain Environments : A Simple Explanation for Complex Foraging Behaviors[END_REF].

∆w ij = A • a i • a j + B • a i + C • a j + D (1)
where i and j are neurons, ∆w ij is the modification of synaptic weight w ij , a i is the activation of neuron i and A, B, C, D are four parameters of the rule. Synapses changes are also modulated by the concentration of some of the molecules emitted by other neurons [START_REF] Bailey | Is Heterosynaptic Modulation Essential for Stabilizing Hebbian Plasticity and Memory ?[END_REF]. Several of these molecules, like dopamin or serotonin, are emitted by specific neurons of the brain and are involved in the adaptation processes; for example, the activity of dopaminergic neuron has been shown to be a critical for reinforcement learning [START_REF] Barto | Adaptive Critics and the Basal Ganglia[END_REF]. To model this phenomena, the equation (1) can easily be extended to use a modulation factor m [START_REF] Soltoggio | Evolving neuromodulatory topologies for reinforcement learning-like problems[END_REF]:

∆w ij = m • (A • a i • a j + B • a i + C • a j + D) (2)
Researchers rely on these learning rules to build models that use neurons to describe basic functions of the brain, like action selection [START_REF] Girard | Contracting model of the basal ganglia[END_REF] or reinforcement learning [START_REF] Baldassarre | A Modular Neural-Network Model of the Basal Ganglia's Role in Learning and Selecting Motor Behaviours[END_REF], [START_REF] Morrison | A Spiking Neural Network Model of an Actor-Critic[END_REF], [START_REF] Morrison | A Spiking Neural Network Model of an Actor-Critic[END_REF], [START_REF] Potjans | A Spiking Neural Net-workModel of an Actor-Critic Learning Agent[END_REF]. Most of the time, these models do not arbitrarily connect individual neurons; instead, artificial neurons are arranged in organized structures, called neural maps, that projects to other maps using a few connection schemes such as "one-to-one" and "one-to-all" [START_REF] Mouret | Importing the computational neuroscience toolbox into neuro-evolution-application to basal ganglia[END_REF], [START_REF] Girard | Contracting model of the basal ganglia[END_REF]. In particular, neural maps and neuromodulation can be combined to model reinforcement learning in the basal ganglia [START_REF] Morrison | A Spiking Neural Network Model of an Actor-Critic[END_REF], [START_REF] Potjans | A Spiking Neural Net-workModel of an Actor-Critic Learning Agent[END_REF]. Considering these neuronbased models of basic brain functions, three main components appears to be useful to define brain-like neural networks: neural maps, heterosynaptic rules and neuro-modulation.

B. Evolution of Plastic Neural Networks

Neural networks have been recognized as a good building block for creating arbitrarily complex functions, both in computational neuroscience and in machine learning [START_REF] Yao | Evolving Artificial Neural Networks[END_REF]. This make them classic candidates to design controllers for autonomous agents. Numerous methods have been proposed to find efficient neural networks for a given task, such as the one proposed by Kasabov [START_REF] Kasabov | ECOS: Evolving connectionist systems and the ECO learning paradigm[END_REF], which incrementally adds neural networks, used as modular solvers, in a complex, static architecture. Another solution, Evolutionary Algorithms (EA), are appealing because (1) they only require an evaluation of the overall achievement of the task, and not a time-step by timestep error signal (as in supervised learning), (2) they can define both the parameters and the topology of the neural network and (3) they can simultaneously optimize several conflicting objectives. Many methods have been proposed to evolve neural networks, from the direct application of real-valued evolutionary algorithms to the evolution of "construction programs" whose instructions are interpreted to build neural networks (see [START_REF] Floreano | Neuroevolution: From Architectures to Learning[END_REF], [START_REF] Yao | Evolving Artificial Neural Networks[END_REF] for reviews).

In most works, synaptic weights are fixed by the EA and can therefore not be changed during the lifetime of the agent, whereas agents that adapt during their lifetime would be even more useful than agents perfectly adapted to their task. In the simplest cases, classic machine learning algorithms (e.g. back-propagation or reinforcement learning) can be used but they cannot be applied to networks of arbitrary topology. An alternative way of thought is to take inspiration from computational neuroscience by importing models of synaptic plasticity into evolved neural networks. Some of the early works relied on simple homeostatic rules [START_REF] Di | Homeostatic adaptation to inversion of the visual field and other sensorimotor disruptions[END_REF], while more recent works employed more complex rules from a set of heterosynaptic primitives [START_REF] Urzelai | Evolution of Adaptive Synapses : Robots with Fast Adaptive Behavior in New Environments[END_REF], [START_REF] Niv | Evolution of Reinforcement Learning in Uncertain Environments : A Simple Explanation for Complex Foraging Behaviors[END_REF], [START_REF] Blynel | Levels of dynamics and adaptive behavior in evolutionary neural controllers[END_REF], [START_REF] Floreano | Evolution of plastic neurocontrollers for situated agents[END_REF] and introduced neuro-modulation [START_REF] Soltoggio | Evolving neuromodulatory topologies for reinforcement learning-like problems[END_REF], [START_REF] Risi | Evolving Plastic Neural Networks with Novelty Search[END_REF].

More precisely, [START_REF] Niv | Evolution of Reinforcement Learning in Uncertain Environments : A Simple Explanation for Complex Foraging Behaviors[END_REF] evolved the synaptic weights and the parameters A,B,C and D of heterosynaptic Hebbian rules (equation (1)) in a task which simulates bumblebees foraging for nectar. To add neuro-modulation, [START_REF] Soltoggio | Evolutionary Advantages of Neuromodulated Plasticity in Dynamic, Reward-based Scenarios[END_REF] and [START_REF] Risi | Evolving Plastic Neural Networks with Novelty Search[END_REF] evolved the parameters and the topology of neural networks to solve a T-maze and double T-maze problem in which the reward was alternatively placed in one of the branch. They proposed to distinguish two kinds of neurons: neuro-modulatory neurons and "standard" neurons. Using the Hebbian rule of equation ( 2), a neuro-modulatory neuron connected to a standard neuron will change the factor m, thus modulating or even de-activating the Hebbian learning rule. Hence, neuro-modulation allow to potentially stop synapse changes when an optimal behavior (according to the reward) is reached.

C. Behavioral diversity

Evolving plastic neural network raises a technical challenge for any evolutionary algorithm: in most situations, there exists a non-plastic (or non-adaptive) neural network that despite being non-optimal, solves a significant part of the task. Unfortunately, it is often impossible for the algorithm to add plastic synapses a posteriori without significantly degrading the fitness. From the optimization point of view, this makes most fitness functions that reward learning behaviors very deceptive [START_REF] Soltoggio | Novelty of behaviour as a basis for the neuro-evolution of operant reward learning[END_REF], [START_REF] Risi | Evolving Plastic Neural Networks with Novelty Search[END_REF]. A direct consequence is that most fitness employed to evolve plastic neural network have to be precisely crafted to make the adaptive behaviors very attractive, whereas an ideal fitness function should be straightforwardly deduced from the task.

One of the most efficient method to find solutions with this type of fitness is to reward the exploration of the fitness landscape by rewarding novel behaviors, either by using a separate objective, or by removing the fitness objective entirely in favor of a novelty or diversity score. To do so, we need to be able to compute a distance between behaviors. We then use this distance as an objective to maximize. This can be done through the use of diversity where an individual is compared to its nearest neighbors in the population, or using an archive of the previous generations [START_REF] Mouret | Using Behavioral Exploration Objectives to Solve Deceptive Problems in Neuro-evolution[END_REF], [START_REF] Lehman | Exploiting Open-Endedness to Solve Problems Through the Search for Novelty[END_REF], in which case we talk about novelty. These methods have successfully been applied to the problem of evolving adaptive neural networks by Stanley and Risi [START_REF] Risi | How Novelty Search Escapes the Deceptive Trap of Learning to Learn Categories and Subject Descriptors[END_REF] and Soltoggio [START_REF] Soltoggio | Novelty of behaviour as a basis for the neuro-evolution of operant reward learning[END_REF] using novelty of behavior.

D. Limits of previous papers

Many of the previously presented works use plasticity as a mean to solve tasks that change during the controller's lifetime [START_REF] Blynel | Levels of dynamics and adaptive behavior in evolutionary neural controllers[END_REF]. However, it has been shown that fixed [START_REF] Stanley | Evolving adaptive neural networks with and without adaptive synapses[END_REF] or recursive [START_REF] Tuci | Behavioral Plasticity in Autonomous Agents: a Comparison Between Two Types of Controller[END_REF] networks can often perform better than adaptive networks in these tasks, thanks to the internal dynamics created by recurrent connections. Additionally, the task investigated by these authors usually only requires a switch between two alternatives, both of them being available during evolution. By contrast, for many real tasks, we cannot test all the possible variations during the evolution because this would require too much time to evaluate each individual. Moreover, it can be argued that the long term goal of designing such plastic neural networks is to obtain neural networks which are able to cope with completely unknown situations, and not only with those which have been tried during the evolutionary process.

Other papers present adaptive networks as a solution for improving the robustness of the evolved controller. For example, in [START_REF] Niv | Evolution of Reinforcement Learning in Uncertain Environments : A Simple Explanation for Complex Foraging Behaviors[END_REF], a network is tested in a simulation, and the solution is then implemented on a real robot. Nevertheless, even if some papers present good results [START_REF] Niv | Evolution of Reinforcement Learning in Uncertain Environments : A Simple Explanation for Complex Foraging Behaviors[END_REF], recursive neural networks can also perform better than adaptive networks in some of these situations [START_REF] Tuci | Behavioral Plasticity in Autonomous Agents: a Comparison Between Two Types of Controller[END_REF], for example when reducing the sensory information available to the controller (reducing contrast).

Finally, many early works focused on evolving networks with a fixed topology [START_REF] Floreano | Evolution of plastic neurocontrollers for situated agents[END_REF] or relatively small neural networks, whereas most of the real-world problems require many effectors (e.g. legged robots) and complex sensory inputs (e.g. cameras). Hence, all the successful previous experiments involved from 1 [START_REF] Niv | Evolution of Reinforcement Learning in Uncertain Environments : A Simple Explanation for Complex Foraging Behaviors[END_REF], [START_REF] Soltoggio | Evolutionary Advantages of Neuromodulated Plasticity in Dynamic, Reward-based Scenarios[END_REF] to 3 [START_REF] Stanley | Evolving adaptive neural networks with and without adaptive synapses[END_REF] outputs and at most 8 inputs. Scaling up to more complex problems probably require to evolve modular and/or repetitive networks, which in turn need a complex encoding.

III. MAP-BASED ENCODING

A. Inspiration and Goals

An examination of the published neuroscience models [START_REF] Girard | Contracting model of the basal ganglia[END_REF]- [START_REF] Potjans | A Spiking Neural Net-workModel of an Actor-Critic Learning Agent[END_REF], and especially of those that could be employed in artificial intelligence, allows to extract some regularities in the design of models. The most striking feature is the main building block: most models are based on N × M spatially organized grids of identical neurons, called neural maps, and not on individual neurons arbitrarily connected. Many models employ only maps of the same size, arbitrary fixed to the dimension of the input, and a few isolated neurons. Connection schemes between maps are of two main kinds, one to one connections with constant weights (neuron i of map M 1 is connected to neuron j of map M 2 , with a positive weight identical for each connection) and one to all connections with constant weights (neuron i of map M 1 is connected to each neuron of map M 2 , with identical weights for all connections).

Following the computational neuroscience practices, we opt here for maps as the basic building block to evolve neural networks. Our goal is threefold: (1) obtain neural network similar to those used in neuroscience models to use the latter as references or inspiration; (2) increase the scalability; and (3) improve the generalization properties of evolved plastic neural networks. Maps and regular connections schemes should indeed allow us to handle many similar inputs in the same way, thus making it easy to scale up to many inputs; encouraging preliminary results have already been obtained with a mapbased encoding and many similar inputs [START_REF] Mouret | Importing the computational neuroscience toolbox into neuro-evolution-application to basal ganglia[END_REF].

Such regular networks should be able to evolve general learning rules because they must use the same modulation scheme for each neuron in a map. This makes map based neural networks better suited for situations that have not yet been encountered during the evolution process.

We chose to use a transfer function which projects to [0 : 1] instead of the more classic [-1 : 1] commonly used in machine learning. In this situation, a neuron with a strong negative input will output 0, and therefore have no effect on the post-synaptic neurons. This enables the neuromodulatory mechanisms to selectively enable or disable parts of network. We further modified the links so that the sign of a connection cannot be changed by neuromodulation.

B. Hebbian Synaptic Changes

We opt here for the modulatory rule of equation 2 and used in [START_REF] Soltoggio | Evolutionary Advantages of Neuromodulated Plasticity in Dynamic, Reward-based Scenarios[END_REF] but we only set the parameter A at 1, while the four other parameters are set to 0; in effect we therefore use a modulated Hebbian rule. This choice was made because it led to the best convergence rate on preliminary experiments. Following [START_REF] Soltoggio | Evolutionary Advantages of Neuromodulated Plasticity in Dynamic, Reward-based Scenarios[END_REF] and [START_REF] Risi | Evolving Plastic Neural Networks with Novelty Search[END_REF], we distinguish two types of neurons: "standard neurons" and modulatory neurons; to use the modulation factor, inputs of each neuron are divided into modulatory inputs I m (connections from modulatory neurons with activity o j ) and standard I s inputs (inputs from standard neurons with activity p j ). The output a i of a neuron i then defined as follows:

a i = ϕ 1 j∈Is w ij o j + b i (3)
where i is the identifier of a neuron, a i its output, b i its bias, ϕ 1 (x) a sigmoid on [0, 1], w ij the synaptic weight between neurons i and j.

Additionally, each synaptic weight w ij is modified with regards to the sum of modulatory inputs and a constant coefficient η:

m i = ϕ 2 j∈Im w ij p j ( 4
)
∆w ij = η • m i • a i • o j (5)
w ij (t + δt) =        min(max(w ij (t) + ∆w ij , 0), 30) if w ij (t) ≥ 0 min(max(w ij (t) -∆w ij , -30), -1e -5) if w ij (t) < 0 (6)
At the beginning of each learning episode, non-modulatory synaptic weights are initialized with random values.

C. Evolving a Network of Maps

A network of neural maps can be efficiently represented with a labeled graph whose labels describe the properties of each map and of each connection (figure 1). Four parameters are associated to each vertex of the graph:

1) neural map / single neuron (Boolean);

2) modulatory neuron(s) / standard neuron(s) (Boolean); 3) bias of the activation function(s) (real value).

Similarly, each edge of the graph is labeled with two parameters:

1) synaptic weight.

2) connection type ("one to one" or "one to all");

The size of maps is not evolved; instead, it is a parameter of the experimental setup; as a result, the same graph can be interpreted for different map sizes. Such graphs are evolved with a classic direct encoding, broadly inspired by the NEAT encoding [START_REF] Stanley | Evolving neural networks through augmenting topologies[END_REF]. Mutations act directly on the graph and cross-over is not employed; three mutations are possible:

• add/remove a node;

• add/remove/change a connection;

• mutate one or several labels. No constraint is put to restrict the topology of the networks; in particular, recurrent connections are possible. More details about the map-based encoding can be obtained in [START_REF] Mouret | Importing the computational neuroscience toolbox into neuro-evolution-application to basal ganglia[END_REF]. At the first generation, the modulated weights in the network are initialized randomly

D. Control experiments: direct encoding

The same graph can be interpreted while ignoring the first label of nodes, resulting in a classic direct encoding for neural networks, without maps. The same mutations are employed.

IV. EXPERIMENTS

A. Task Origin

To evaluate our approach, we selected a task based on a setup used to study operant conditioning with animals, commonly called a "Skinner box". In this type of experiment a caged animal, usually a mouse or a rat, is presented with stimuli which can be either sound, light or a combination of the previous elements. When the stimuli are presented, the animal must perform a specific action to obtain a reward. The typical action is the activation (push) of a lever and the reward is usually food or water. If the action is performed without the right stimulus, a punishment is given (electric shock). An example is shown in figure 2. This task was selected for two main reasons. Firstly, it purposely does not involve delayed reward, a well known problem in reinforcement learning [START_REF] Sutton | Reinforcement learning: An introduction[END_REF] which require more complex mechanisms than basic neuro-modulation [START_REF] Baldassarre | A Modular Neural-Network Model of the Basal Ganglia's Role in Learning and Selecting Motor Behaviours[END_REF], [START_REF] Kimura | An Analysis of Actor-Critic Algorithms Using Eligibility Traces: Reinforcement Learning with Imperfect Value Functions[END_REF]. Secondly, this task presents a choice with many possible combinations for the answers. It is therefore different from a switch between only two alternatives, as done by most previous authors [START_REF] Risi | Evolving Plastic Neural Networks with Novelty Search[END_REF], [START_REF] Soltoggio | Evolutionary Advantages of Neuromodulated Plasticity in Dynamic, Reward-based Scenarios[END_REF]. Furthermore, as the number of stimuli and possible actions can be changed, the task combinatorial complexity can be arbitrarily increased or decreased. This feature will allow us to test the generalization abilities of the evolved networks.

B. Formalization

agent in a skinner box can be formalized as system which associates an input vector of size N s to a particular action among N a possible actions. To simplify the use of neural maps, we consider here that N s = N a . The goal of the agent is to learn a set of association rules that links each possible N s to an action that maximize its reward. To make the task easier, we restricted ourselves to vectors N s in which only one input is active at a given time. Such a constraint corresponds to classical reinforcement learning setups where an input is equivalent to a state and in which two inputs cannot be active at the same time. The final network topology is shown in figure 2 (b). Definitions

• a rule is an association between a neuron i from the input map of size N s and a neuron j from the output map (which is of the same size N s ). To answer correctly to a rule, the neural controller must activate the output j when input i is presented. • a rule set is a group containing N s rules: one for each possible neuron in the input map. The same rule can be in two different rule sets, but two rule-set cannot be identical, they always have at least one rule different from one to the other. Depending on N s , there are N Ns s possible rule sets. If N s = 4, there are 256 rule-sets, which is different from the bumblebee foragging task with two choices.

To evaluate the performance of agent, the neural network is simulated with inputs which are not subject to random processes or noise other than the weight initialisation. This makes it difficult for the network to have an exploration behavior, whereas we know that this kind of exploration behavior is necessary to test the different solutions. The controller also cannot perform, multiple actions at once (if we take the analogy of the rat in a cage, it cannot push more than one lever at a time). The most elegant solution we found to solve both of these problems is to add a softmax mechanism on the outputs of the network. This softmax mechanism, described in [START_REF] Sutton | Reinforcement learning: An introduction[END_REF] and given in equation 7, has a probability of selecting an output that is linked to the output level of this output compared to the others:

P (i) = exp(βa i ) n i=1 exp(βa i ) (7)
where P (i) is the probability of selecting output i, a i is the activity of output i and β is a fixed coefficient. From previous experiments, we also observed that if we use only a max function on the outputs instead of the softmax, the EA finds solutions where the difference between outputs is around 1e-2 for a total range of 1. Using the softmax mechanism, we force the network to differentiate its outputs by a significant value.

The softmax mechanism selects an output based on both the output values and a random process, therefore, if we want the network to adapt, we must add inputs that provides to the network the decision of the softmax and the associated reward. The inputs of the networks can therefore be organised in three groups. The first group contains the input pattern from the rule. If we use the map encoding, it is a map of size N s , else, there are N s separate inputs. The second group consists in the feedback information from the last softmax choice, these inputs are also either a map of size N s or N s separate inputs. Finally, there are two additional inputs which represent the positive and negative rewards. Both are single neurons. This setup is shown in figure 2.

The modulation rule we use (section III-B) can only modify a weight efficiently if the postsynaptic neuron activity is different from 0; else, the total modification is 0. This can lead to situations in which an adaptation mechanism relies on both an adaptation rule with specific initial parameters as well as a precise initial weight value. We need to avoid these situations, because they create unstable behaviors. To do so, the connections of the controller which are modulated are randomly initialised before learning each rule set, as shown in 3. The objective is to obtain network which are more robust to various weight values.

In our algorithm, the evaluation procedure of each controller is described on figure 3. Each controller is evaluated against a number of rule sets. Each rule sets consists in a N s rules. For each rule sets, the modulated weights are randomly initialised. Then, each rule from the set is presented in a pseudo random order to the network. Each presentation is done in two parts. During the first part, the pattern is presented to the network while the other inputs are at O. After k 1 cycles, the output is read from the output and fed to the softmax mechanism, which selects the active output. The score of the network is then updated if it is a late trial. For the second phase, the same pattern is left on the first group of input, while the second group of input is fed the softmax output, which gives information to the network about which output was selected. At the same time, the reward input are set according to whether or not the selected output and the correct output match. After k 2 cycles, another rule is selected.

The neural network required to solve this may seem trivial at first sight. However, the simplest solutions using our simple building blocks require at least one hidden layer of neurons with non-trivial connectivity. The challenge raised by this problem is threefold: (1) identifying and correctly connecting the reward inputs, (2) gating the reward with the softmax choice to modify only the connections corresponding to the chosen action, and (3) applying the resulting reinforcement to a link between the inputs and the output. In classical rein-forcement learning implementations, the softmax mechanism integration as well as the delay tuning between an action and the associated reinforcement are not implemented using neurons. This makes the problem simpler to solve.

C. Objectives

The fitness of each individual depends on the process shown in figure 3. For each controller, we record, at the end of each rule set training session, the number of rules the controller was able to answer correctly out of the total number of rules. This gives us the performance of the controller for a set of rule. When we compute the fitness score, we use the same set of rules as the one used during the evolution process. When we test the generalisation abilities of a network, we use either a rule set different from the training set (a rule set cannot be in both sets) or the complete set of possible rule sets (in this last situation, the rule sets used during evolution represent a small fraction of the total).

For the training sessions, we present all the rules in a predefined pseudo-random order. Eeach rule from a set is presented multiple times so that the probability to select at least once all the correct associations is superior to 0.99 for a network with all outputs at a zero value. This random probability is possible thanks to the softmax mechanism previously described.

As explained in II-C, using the behavioral differences to force the EA to explore can improve results with deceptive fitnesses. In the present setup, we describe the behavior of a network with a vector containing the post-learning output values of the network for each rule set. This both partially reduce the softmax mechanism impact on the measure and reduces the importance of the random initialisation of the modulated weights. The distance between behaviors is computed with an Euclidean distance. The diversity score of each individual is its distance from its 15 nearest neighbors. We use the diversity score as a second objective in a multi-objective EA. Objectives are shown in equation 8 where the first objective is the performance with δ being the Kronecker distance between the given (A g ) and correct answer (A c ) while k is the total number of rules tested. The second objective is the diversity, which is the sum of the distance between behaviors with respect to the 15 nearest neighbors. Figure 5 also shows that a diversity objective speeds up the search for solutions. These results are similar to the ones obtained by Risi [START_REF] Risi | How Novelty Search Escapes the Deceptive Trap of Learning to Learn Categories and Subject Descriptors[END_REF] and Soltoggio [START_REF] Soltoggio | Novelty of behaviour as a basis for the neuro-evolution of operant reward learning[END_REF]. In our experiment, using diversity enabled us to half the number of generation necessary to converge in many variants of these experiments.

Maximize

F it(x) = 1 k k i=1 δ(A g , A c ) Div(x) = j=1 d(B x , B j ) (8)
Finally, these results show that a modulation rule is necessary to solve this task. We further show that maps without modulation have lower fitnesses (compared to a direct encoding without modulation) in this task where differentiation of the outputs is necessary.

B. Better generalisation when maps are used

Figures 6(a) show that the map-based encoding performs better than the direct encoding when tested on all the rule sets (most of which are not used during the evolutionary process). The better fitness of map encodings can be explained in two ways. The first way is that both encodings manage obtain similar maximum fitnesses during evolution. In this situation, it means that the direct encoding creates overlearning networks, which are performing well only on the training examples, while the maps create networks which are able to generalize and learn rule sets different from the ones used during training. This would confirm our hypothesis. The second solution is that the generative encoding always outperforms the direct encoding. The difference then comes only from the difference in the fitness between generative encoding and direct encoding.

To show that both encodings generate solutions, we considered only the networks which reach a fitness of 1 (all training rule sets perfectly learned). These results are shown on figure 6(b). In this situation, we show that the direct encoding only finds solutions when the evolution tests a few rule sets. In these situations, The map based encoding offer significantly better generalisation results. This confirms our hypothesis that using a map based encoding only generates networks which generalize better.

When we consider only the generative encoding, we see that we cannot differentiate results for two or more training rule sets. Though, when only one rule set is used evolution, generalisation score is low. After analysis, some networks were able to generate a fixed pattern different values for each output of the map. This was done by exploiting the constant pseudo random order in which the patterns are presented which is always the same.

CONCLUSION

This paper investigated the combination of Hebbian learning, neuro-modulation and a neuroscience-inspired map-based encoding to evolve adaptive neural networks. We applied the proposed approach on a toy problem inspired from a classic operant conditioning setup in which numerous different association rules can be learned.

Results show that the map-based encoding scaled up better than a classic direct encoding on this task. With few inputs, our generative encoding led to similar performance as a direct encoding. However, the best networks evolved with the direct encoding have lower fitnesses if we increase the number of inputs / outputs, while the map based encoding performance does not change depending on the number of inputs / outputs. Evolving neural networks using a map based generative encoding also led to networks that can learn most rule sets even when the evolution is done on a small subset of all the possible cases. Such a generative encoding therefore appears as a key to improve the generalization abilities of evolved adaptive neural networks.

While the present setup was a toy example, it can be assimilated to the actor in an actor-critic architecture. We hope to be able to evolve such an architecture in future work because it's both powerful in machine learning and has similarities to what can be observed in animals. Nevertheless, such an achievement will most probably require the addition of more advanced mechanisms, for instance based on eligibility traces [START_REF] Pan | Dopamine cells respond to predicted events during classical conditioning: evidence for eligibility traces in the reward-learning network[END_REF], [START_REF] Doya | Reinforcement learning in continuous time and space[END_REF].

ACKNOWLEDGMENT

This project was funded by the ANR EvoNeuro project (ANR-09-EMER-005-01) and a Monaco Ph.D. scholarship.

Fig. 1 .

 1 Fig.1. of a controller genotype and phenotype using map encoding for our setup. The view on the left shows the genotype with numerical parameters, the center view shows an intermediate development, where maps are instantiated but not the connections. The right view shows the developed phenotype with maps and connections.

Fig. 2 .

 2 Fig. 2. (a) Example of a typical skinner box used in operant conditioning. (b) formalization using an evolved neural network setup.

Fig. 3 .

 3 Fig. 3. Flowchart of the evaluation procedure.

Fig. 4 .

 4 Fig. 4. Fitnesses values for the best individuals for each generation on a 3 inputs / 3 outputs (a) or 4 inputs/ 4 outputs (b) problem with and without the map encoding. for a map size of Ns = 4, other parameters were tested. The values are medians over 30 runs.

Fig. 6 .

 6 Fig. 6. Scores on unknown datasets with (thick lines) and without (thin lines) maps with respect to the number of different examples used during evolution (4 inputs / 4 outputs). (a) Scores for all the runs. (b) Scores for the run that converged. The values are the median (red bar), the box extends from the lower to the upper quartile and the whiskers show the range of the data over 30 runs.

D. Parameters

The evolved networks have 2 • N s + 2 inputs, where N s is the size of the map:

• a map of size N s (N s inputs with a direct encoding) providing the rule input pattern; • a map of size N s (N s inputs with a direct encoding) providing the softmax choice previously done; • a single neuron providing the positive reward;

• a single neuron providing the negative rewards. The output is a map of size N s (N s outputs with a direct encoding). A sample network is shown in figure 1. Simple McCulloch and Pitts neurons are used. The modulation values are computed using a sigmoid projecting to [-1 : 1]. The sigmoid on the modulating inputs is used to normalize the modification inputs. If the input weights are sufficiently high. The sigmoid functions can be considered as a binary switch. Therefore, we allowed a maximum weight of 30 for our connections. In our problems, each map is a unidimensional list with a constant size. Therefore, the number of stimuli and possible actions is always the same. We used 3 or 4 elements in our experiments. For a map size of 3, we present 40 rules to each controller per rule-set and 90 for a size of 4. This number would allow a network with a constant output to select every correct rule at least once with a probability superior to 99 per cent (a constant output is a regular random when a softmax mechanism is used). The evolutionary algorithm we use is the state of the art NSGA-II [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF] with 2 objectives. We used a population size of 400 and 2000 generations. We then use the median, as well as the upper and lower quartiles over 30 runs to have statistically significant results (the distribution of the results is not normal).

E. Setups and Expected Results

The first experiment tests whether or not maps perform better than direct encodings in setups where the number of similar inputs / outputs increases. Our setup was tested both with and without maps with an input / output size of 3 (8 inputs, 3 outputs) and 4 (10 inputs, 4 outputs). With a map size of 4, we further tested the importance of other parameters such as the modulation mechanism and the diversity. If our hypothesis is right, maps should perform better than direct encodings, especially for the bigger size. The second experiment tests if maps create structures which generalize better than direct encodings when the fitness on difficult setups: the evolution fitness is computed on a few examples only. We evolve controllers with a fitness containing 1 to 5 rule tests, while the usual number is 10. The best controllers from each run are then tested against all the possible rule sets. If our hypothesis is correct, maps should have better performance than a direct encoding on the complete sets even when evolved on a few rule sets.

V. RESULTS

A. Increase of fitness when using maps

Left part (a) of figure 4 shows that, with a 3 inputs and 3 outputs, both the direct encoding and the map encoding provide equivalent results. The reason may be that while the map encoding simplifies the target network topology, it also adds multiple parameters to the genotype, which in turn increase the search space. This could explain why the results are similar.

By contrast, the results in part (b) of figure 4 show that, in a problem with a 4 inputs and 4 outputs, a map-based encoding is required to obtain the perfect fitness; with a direct encoding, the best individual can only learn 80 per cent of all rules.

As medians do not provide all the possible information, the additional information provided by figure 5 shows that a single run managed to reach the maximum fitness without maps. This proves that our generative encoding scales-up better than a basic direct encoding.


Jean-Baptiste Mouret
email: mouret@isir.upmc.fr

J.-B Mouret

Novelty-based Multiobjectivization

come

Introduction

Two recent papers [START_REF] Lehman | Exploiting open-endedness to solve problems through the search for novelty[END_REF][START_REF] Risi | How novelty search escapes the deceptive trap of learning to learn[END_REF] introduced a new but radical approach to evolve robot controllers: they propose to maximize the novelty of behaviors instead of the efficiency (the fitness) of these behaviors. This method, called "novelty search", relies on a user-defined distance between behaviors and the NEAT [START_REF] Stanley | Evolving neural networks through augmenting topologies[END_REF] evolutionary framework to synthesize neural networks. It could have a least two benefits over traditional fitness-based evolutionary methods:

(1) it could override the deceptiveness of some fitness functions and (2) the evolutionary process may be more open-ended.

Abandoning the efficiency objective(s) may be too radical in many contexts and especially in engineering processes -in which solutions to a problem are sought. If the search space is very large, novelty search can run for a very long time before finding any interesting solutions. In such situations, the objective is often the best guide to explore an interesting subset of the search space. Moreover, novelty search can not fine-tune results because the process is not aware that it should stop the exploration and begin a local search. Even if near-optimal solutions are found, the evolutionary pressure is kept towards finding individuals with a significantly different behavior; however, when the evolutionary process has almost found an optimal solution, we can reasonably expect it to cover the last small steps without any difficulty.

In this paper, a Pareto-based Multi-objective Evolutionary Algorithm (MOEA, see [START_REF] Deb | Multi-objectives optimization using evolutionnary algorithms[END_REF]) is employed to reconcile novelty search with objective-based optimization. Once defined a novelty objective and a fitness objective, the Pareto dominance relation can ensure that novel but inefficient candidate solutions will be selected, as in novelty search, but also that efficient but less novel ones will be considered equally interesting. As it will be demonstrated in this paper, this multiobjectivization -the transformation of a single-objective optimization problem to a multiobjective problem -has the potential to overcome the previously described limitations of novelty search.

To cope with the same limitations, an alternative to multiobjectivization is to switch from novelty search to fitness-based search once a criteria is met. We rejected this approach for three main reasons: (1) such a method would require to define an additional and hard to define switch criteria, (2) Paretobased MOEA are well-studied algorithms that are preferable to custom ones and, (3) a MOEA "automatically" switches back and forth between fitnessbased search and novelty search, according the context (in effect, it follows both approaches at the same time, but also all the trade-offs between them). From another point of view, novelty search is an exploration procedure and fitness-based algorithms are an exploitation procedure. Using a MOEA, we thus explicitly model the classic trade-off between exploration and exploitation (see e.g. [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]).

Hence this paper explores one main question: can novelty search be combined with objective-based search using a MOEA? Additionally, we also want to improve the knowledge of novelty search and especially how it compares to diversity maintenance techniques and whether the NEAT encoding is required.

To that aim, we prolong the maze experiments described in the original novelty search paper [START_REF] Lehman | Exploiting open-endedness to solve problems through the search for novelty[END_REF] by comparing them to our multi-objective method. We also compare these results to behavioral diversity [START_REF] Mouret | Overcoming the bootstrap problem in evolutionary robotics using behavioral diversity[END_REF][START_REF] Mouret | Using behavioral exploration objectives to solve deceptive problems in neuro-evolution[END_REF], another multiobjectivization [START_REF] Knowles | Reducing Local Optima in Single-Objective Problems by Multi-objectivization[END_REF][START_REF] Handl | Multiobjectivization by decomposition of scalar cost functions[END_REF] that uses Pareto dominance to improve the exploration abilities of evolutionary algorithms.

Related Work

Novelty Search

Novelty search relies on three main concepts:

• a distance between behaviors of robots instead of a distance between genotypes as used in classical diversity preservation mechanism [START_REF] Goldberg | Genetic algorithms with sharing for multimodal function optimization[END_REF]; • a novelty measure, based on this distance and an archive of previously encountered behaviors; • the search for novel behavior instead of the optimization of a fitness function.

Lehman and Stanley [START_REF] Lehman | Exploiting open-endedness to solve problems through the search for novelty[END_REF] measured the novelty ρ(i) of an individual i by computing the mean behavioral distance between i and its k nearest neighbors:

ρ(x) = 1 k k j=0 d b (x, µ j )
where k is a user-defined parameter and µ j is the j-th nearest neighbor of x with respect to the distance d b . The neighbors are computed using the current population and an archive of all the previous novel individuals. An individual is added to the archive if its novelty is above a minimal threshold ρ min . This last parameter is adjusted dynamically during an experiment:

• if more than 2500 evaluations occurred and no new individual were added in the archive, ρ min is multiplied by 0.95; • if more than 4 individuals were added during the same generation, ρ min is multiplied by 1.05.

It is important to note that by using both the archive and the population, this nearest neighbors computation combine a diversity preservation mechanism (maximizing the novelty with respect to the current population) and a history-based search. It should also be noticed that, from a computational point of view, the time to find the k nearest neighbors grows continuously (at best logarithmically if a suitable data structure is employed).

Multi-Objective Evolutionary Algorithms

Recent research in evolutionary computation proposed numerous algorithms to simultaneously optimize several conflictual objectives without aggregating them (see [START_REF] Deb | Multi-objectives optimization using evolutionnary algorithms[END_REF]). Most of them rely on the concept of Pareto-dominance and generate the so-called Pareto Front: 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). MOEA are designed to find an approximation of the Pareto-front, i.e. the set of all the Pareto-optimal trade-offs. Most of the time, they implement two mechanisms:

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

A typical MOEA sorts individuals with respect to dominance. Nondominated individuals may, for instance, be ranked 1, making them the most suitable for reproduction. Individuals which are only dominated by nondominated 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], crowding [START_REF] Deb | A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II[END_REF] or clustering methods [START_REF] Zitzler | SPEA2: Improving the Strength Pareto Evolutionary Algorithm[END_REF].

Multiobjectivization

While MOEAs have been primarily designed to optimize several conflicting objectives, a growing trends in the MOEA community is to apply them to improve the optimization of single-objective problems. The term "multiobjectivization" [START_REF] Knowles | Reducing Local Optima in Single-Objective Problems by Multi-objectivization[END_REF][START_REF] Handl | Multiobjectivization by decomposition of scalar cost functions[END_REF][START_REF] Greiner | Improving Computational Mechanics Optimum Design Using Helper Objectives: An Application in Frame Bar Structures[END_REF] has recently been coined to describe this cast of a single objective problem to a multiobjective one. Two paths can be followed to achieve this reformulation: adding new objectives or decompose the original objective function.

The decomposition of the main fitness function was studied in evolutionary robotics in a few papers, with very encouraging results. In [START_REF] Mouret | Incremental Evolution of Animats Behaviors as a Multiobjective Optimization[END_REF] and [START_REF] Mouret | Evolving modular neural-networks through exaptation[END_REF], objectives were designed for each sub-task of a complex problem. This resulted in a fully automatic evolutionary process that can exploit sub-tasks without having to specify their order and when to switch between them. Moreover, several hypothesis about the usefulness of each sub-task were explored in parallel.

The addition of objectives were mostly investigated by adding a genotypebased diversity objective to the fitness [START_REF] De Jong | Reducing bloat and promoting diversity using multi-objective methods[END_REF][START_REF] Toffolo | Genetic diversity as an objective in multi-objective evolutionary algorithms[END_REF][START_REF] Abbass | Searching under multi-evolutionary pressures[END_REF][START_REF] Bui | Multiobjective optimization for dynamic environments[END_REF]. All the published papers about this topic concluded that adding this objective substantially improved the efficiency of evolutionary algorithms. Following this idea, [START_REF] Mouret | Using behavioral exploration objectives to solve deceptive problems in neuro-evolution[END_REF], [START_REF] Doncieux | Single step evolution of robot controllers for sequential tasks[END_REF] and [START_REF] Mouret | Overcoming the bootstrap problem in evolutionary robotics using behavioral diversity[END_REF] proposed to employ a behavior-based distance to compute a diversity objective. It had, in particular, been employed to evolve neural networks to compute a Boolean function [START_REF] Mouret | Using behavioral exploration objectives to solve deceptive problems in neuro-evolution[END_REF] and to evolve neuro-controllers for a mobile robot [START_REF] Doncieux | Single step evolution of robot controllers for sequential tasks[END_REF][START_REF] Mouret | Overcoming the bootstrap problem in evolutionary robotics using behavioral diversity[END_REF]. According to this approach, called behavioral diversity, instead of maximizing the fitness F (i), two objectives have to be maximized using a MOEA:

F (i) B(x) = 1 |Pn| j∈Pn d b (x, j) (1.1)
where P n denotes the population at generation n, d b (ij) the distance between the behaviors of individuals i and j, similar to the one used in novelty search.

1.3 Method To draw a fair comparaison with the original novelty search, we used the same maze navigation task as in [START_REF] Lehman | Exploiting open-endedness to solve problems through the search for novelty[END_REF]. In this task, a simulated mobile robot has to find a goal zone in a maze by relying only on its three laser range sensors and a goal sensor (see Fig. 1.1(a)).

1.3.1 Experiment (a) (b)
The robot is controlled by an evolved neural network (the topology and the synaptic weights are evolved) with 7 inputs (3 range sensors and 4 inputs for the goal sensor) and two outputs (the speed of the wheels). To keep our experiments simple and repeatable, we employed a typical graph-based direct encoding for neural-networks in which two kinds of mutations are possible1 :

• structural mutation: addition/removal of a random neuron or a random connection; • parametric mutation: change of a randomly chosen synaptic weight or a neuronal bias; we used here a change in a set of 9 possible values (see appendix).

Cross-over was not employed. This encoding has been used in several previous works [START_REF] Mouret | Overcoming the bootstrap problem in evolutionary robotics using behavioral diversity[END_REF][START_REF] Mouret | Using behavioral exploration objectives to solve deceptive problems in neuro-evolution[END_REF][START_REF] Doncieux | Single step evolution of robot controllers for sequential tasks[END_REF] in which a basic encoding for neural-networks was needed. This maze navigation task is interesting because maps with dead ends near the goal can be easily designed. This makes the typical fitness function (the opposite of the distance to the goal) very deceptive. Moreover, we can visualize the part of the maze explored by the robots and thus understand how the search space has been explored.

The map used in this paper (Fig. 1.1(b)) is similar to the "hard map" used by [START_REF] Lehman | Exploiting open-endedness to solve problems through the search for novelty[END_REF], with a very deceitful cul-de-sac in the direction of the goal.

Fitness Function and Distance Between Behaviors

The fitness F (x) of an individual i (to be maximized) is the opposite of the minimum Euclidean distance to the goal obtained during the whole trajectory:

F (x) = - t=T min t=0 p r (t) -p g
where p r (t) is the position of the robot at time t, p g the position of the goal and T the total time of one evaluation.

To describe the behavior of an individual x, we use the position of the robot at the end of the experiment:

b(x) = p r (T )
The distance between individual i and j is then the Euclidean distance between their position at time T :

d b (i, i) = b(i) -b(j)
Many other distances between behaviors can be designed, such as measuring the difference between trajectories or exploiting the Kolmogorov complexnetworks that are complexified during the evolution. This way of exploring topologies well suits the concept on novelty search in which simple behaviors are first explored. However, in this paper we would like to deal with the selective pressure with the simplest encoding as possible. Positive results with a basic graph-based direct encoding would ensure that novelty search does not critically depends on NEAT (which adds noticeably speciation and cross-over) ity [START_REF] Gomez | Sustaining diversity using behavioral information distance[END_REF]. We will not explore these ideas in this paper in order to match the original novelty search algorithm.

Variants

To evaluate the contribution of a novelty-based multiobjectivization and improve the knowledge about novelty search, we investigate 6 variants of the experiment. Each of them aims at answering a particular question about novelty search.

Control experiment.

Question: is this fitness really too deceptive for a classic evolutionary approach? Maximize F (x)

Novelty search (basic).

Question: can we confirm/infirm the published results about novelty search [START_REF] Lehman | Exploiting open-endedness to solve problems through the search for novelty[END_REF] without using NEAT?

Maximize ρ(x) = 1 k k j=0 d b (x, µ j )
where µ j is computed using the archive and the population.

Novelty search (no diversity).

Question: is it necessary to compute novelty using both the archive and the current population?

Maximize ρ(x) = 1 k k j=0 d b (x, µ j )
where µ j is computed using the archive. 4. Fitness + Novelty (MOEA).

Question: can novelty and fitness be reconciled with a MOEA?

Maximize F (x) ρ(x) = 1 k k j=0 d b (x, µ j )
where µ j is computed using the archive and the population.

Fitness + Diversity (MOEA).

Question: how does novelty search compare to multiobjective behavioral diversity [START_REF] Mouret | Overcoming the bootstrap problem in evolutionary robotics using behavioral diversity[END_REF]?

Maximize F (x) B(x) = 1 |Pn| j∈Pn d b (x, j)
6. Fitness + Diversity + Novelty (no diversity) (MOEA).

Question: can diversity and novelty be combined with a multi-objective approach instead of aggregating them?

Maximize    F (x) B(x) = 1 |Pn| j∈Pn d b (x, j) ρ(x) = 1 k k j=0 d b (x, µ j )
where µ j is computed using only the archive.

Expected Results

We expect the control experiments not to converge at all because of the deceitful local extrema. Following Lehman and Stanley [START_REF] Lehman | Exploiting open-endedness to solve problems through the search for novelty[END_REF], we can expect novelty search to work well to go close to the goal. However, it should encounter some difficulties to exactly reach the goal. "Novelty search + fitness" should overcome this problem. This last setup should not be substantially faster than novelty search because the fitness function does not provide a good guide to reach the goal. Nevertheless, adding the fitness objective to novelty search should not decrease the convergence speed. The three-objectives approach should be mostly equivalent to the two objectives "fitness + novelty" variant. However, MOEA give better results with two objectives than three [START_REF] Purshouse | On the Evolutionary Optimization of Many Conflicting Objectives[END_REF][START_REF] Praditwong | How well do multi-objective evolutionary algorithms scale to large problems[END_REF], consequently this variant may encounter some difficulties.

Given the good results observed with the addition of a diversity objective in previous experiments [START_REF] Mouret | Using behavioral exploration objectives to solve deceptive problems in neuro-evolution[END_REF][START_REF] Doncieux | Single step evolution of robot controllers for sequential tasks[END_REF][START_REF] Mouret | Overcoming the bootstrap problem in evolutionary robotics using behavioral diversity[END_REF], we can reasonably expect a good convergence rate. The convergence speed may be slower because less data are employed to guide the search.

Experimental parameters

To get statistically significant data, 30 runs of each variant were launched. NSGA-2 [START_REF] Deb | A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II[END_REF], a popular and efficient MOEA, was used to optimize the objectives. In the single objective case, it is equivalent to a tournament-based evolutionary algorithm. The detailed parameters of the direct encoding are available in appendix.

To compute the novelty, we used k = 15 (the same value as [START_REF] Lehman | Exploiting open-endedness to solve problems through the search for novelty[END_REF]) and ρ min = 10. Population size was 200 and each run lasted 1000 generation; put differently, our budget was of 200000 evaluations. The single objective control experiments converged to a fitness of 60 that corresponds to the distance between the main dead-end and the goal. This means that most runs were trapped in the local maximum (20% of them found a controller that managed to drive the robot near the goal, see section 1.4.2).

Results

Average Fitness

Novelty search and multiobjective novelty search ("fitness + novelty") required about 200 generations to get all the runs close to the goal. Novelty search was slightly faster but only the multiobjective variant is able to reach the optimal value. This difference can be easily spotted on Fig. 1.3(b), which displays a zoom on the high fitness values.

If novelty is computed using only the archive, novelty search still converges a lot faster than the control experiment but it requires significantly more generations to converge. Surprisingly, it is also more noisy, suggesting that individuals close to the goal are often lost from the current population in favor of more novel ones. Last, the three objectives approach lead to results very similar to those obtained with the multiobjectivization "Novelty + Diversity".

Convergence Rate

Considering that a run "converged" when one robot get at less than 10 units to the goal (the optimum is 3 units in these experiments; the choice of 10 is here related to ρ min in novelty search), the convergence rate of each variant can be analyzed (Fig. 1.5(a)). 29% of the control experiments (fitness only) converged in spite of the attractive local maximum. Nevertheless, 100% of the other experiments converged in less than 1000 generations (200000 evaluations). Novelty search and multiobjective novelty search are the fastest to converge while substantially more generations are needed for the novelty search variant that uses only the archive.

If we count as converged only the experiments that reach the optimum fitness (-3, Fig. 1.5(b)), only the novelty-based multiobjectivization runs get a 100% convergence rate whereas 90% of the novelty search runs converged.

To understand if the observed difference are statistically significant, the average generation to converge (F (i) > -10) has been computed (table 1 significant except between the "diversity + fitness" and the "novelty (archive only)" variants and between "fitness + diversity + novelty" and most of the other variants. Despite a small difference in average generation of convergence (25 generations/500 evaluations), novelty search appears statistically faster than the multiobjective variant. This small difference is easily understood by taking into account that, in the multiobjective variant, a part of the population is kept only because of its good fitness; the deceptiveness of the fitness makes these individuals almost useless to the algorithm. This drawback may be compensated by the better fitness obtained with the multiobjective variant (Fig. 1.3(b)). Results obtained with novelty search and multiobjective novelty search are of the same order of magnitude when they are compared to the "fitness only" runs: in both cases, only a few generations are required to converge. A more complex problem, with a larger search space, could allow to draw a real efficiency distinction between these two approaches.

The diversity multiobjectivization was significantly slower to converge than the novelty variants. However, its computational cost is substantially lower than novelty search. To compute the diversity, only N 2 distances (N being the size of the population) need to be computed. With novelty search, the archive is an order of magnitude larger than the population (in our experiments, the typical archive size at the end of the experiments was about 1500 whereas the population size was 200).

Exploration

Figure 1.7 depicts the position at the end of the experiment of each evaluated until the first one reaches the goal. The first surprising observation is that, in all runs (successful or not), only the bottom left part of the maze has been explored. This can be explained by understanding where lies the difficulty of this task; two behaviors are the key to reach the goal: turning towards the right at the beginning of the experiment and efficiently avoiding obstacles. The turn of the bottom right is difficult to negotiate so if an individual manages to overcome this part of the maze, it is likely able to also come close to the goal. Since the fitness rewards the minimum distance to the goal during the whole experiment, robots don't have to adjust precisely their trajectory to get above the convergence threshold (10 units), they only have to wander near the goal.

The second surprising observation is that the explored points are not as different as suggested by the convergence rates. The points may be more evenly distributed when a novelty objective is used but the difference is not obvious. The multiobjectivization "fitness + novelty" (Fig. 1.7(b)) put a clear emphasis on the top left part of the maze, near the goal but in the deadend, especially if it is compared to the original novelty search (Fig. 1.7(e)). However, it seems hard to predict which run will succeed using only the explored points. This similarity may be interpreted in term of selective pressure: the key to converge is not to explore the good points but to recognize which point could lead to the solution. In the control experiment (Fig. 1.7(a), the robots that end at the bottom right part of the maze will be ranked last, because they are far away from the goal. However, with a novelty objective, the same behavior will be ranked first because there is almost no previous behaviors in this area. One may wonder why there is not many points in this part of the maze in the novelty experiments compared to the left part. A possible explanation is that such behaviors are hard to obtain, because a small variation of an individual with this behavior may more likely drive the robot in a wall near the starting point than in the same area. Consequently, it is only by persistently trying to modify the bottom right individuals that a successful individual can emerge. To test this hypothesis, one should evaluate how many children of such individuals reach the same area as their parents.

Conclusion and Discussion

This paper investigated several ways to combine novelty search and objectivebased search using a multiobjectivization. These methods were compared to behavioral diversity, a multiobjectivization that is also based on a distance between behaviors of candidate solutions.

The experimental results show at least that:

• novelty search is well adapted to the investigated deceptive task (this confirms the previously published results [START_REF] Lehman | Exploiting open-endedness to solve problems through the search for novelty[END_REF]); • adding a fitness objective to novelty search does not harm the efficiency of the search; • adding a fitness objective to the novelty objective allows to fine-tune the result more efficiently than with the original novelty search algorithm; • diversity-based multiobjectivization requires more generations to converge but also lead to successful results in a few hundred of generations, whereas its computational cost is lower than novelty search; • a straight-forward graph-based encoding leads to similar results than NEAT in this setup (at least qualitatively).

Overall, the successful experiments suggest that the difficulties encountered to evolve neural networks to solve complex tasks, especially observed in robotics, may currently be more a problem of good selective pressures than of bad encodings.

A more complex task, with a larger search space and/or with a less obvious dead-end, is needed to further compare novelty search to the multiobjectivizations introduced in this paper. The guide provided by the fitness in the maze experiment described here is deceptive by design but the success of evolutionary algorithms proves that fitness can be a good guide towards efficient solutions. We believe that the proposed multiobjectivization can combine the best of both worlds by using fitness when it is a good guide and novelty search when it is not.

The computational cost of novelty search compared to the one of behavioral diversity is a significant drawback of novelty search. One of the first idea to reduce the algorithmic complexity of novelty search is to efficiently structure the archive to compute the nearest neighbors as fast as possible. The typical structure used in computer graphics to this task is the kd-tree [START_REF] Bentley | Multidimensional binary search trees used for associative searching[END_REF]; future work should investigate this idea. Another approach is to keep the size of the archive bounded by periodically removing the least significant elements.

Fig. 1 . 1

 11 Fig. 1.1 (a) Overview of the simulated mobile robot. Each arrow outside of the robot's body is a range sensor (e.g. a laser range finder) that returns the normalized distance to the closest obstacle in that direction. The robot is also equipped with four pie-slice sensors that act as a compass towards the goal. This compass can "see" through walls. The robot is moved by two motors, the neural network setting the speed of each of them. (b) Map employed in this set of experiments (size: 512 × 512 units). The circle denotes the starting position and the cross denotes the goal.

Fig. 1 . 2

 12 Fig. 1.2 Average maximum fitness in the population for each generation and for each variant (30 runs).

Figure 1 .

 1 Figure1.3 shows the average (over the 30 runs) best fitness for each variant. The single objective control experiments converged to a fitness of 60 that corresponds to the distance between the main dead-end and the goal. This means that most runs were trapped in the local maximum (20% of them found a controller that managed to drive the robot near the goal, see section 1.4.2).Novelty search and multiobjective novelty search ("fitness + novelty") required about 200 generations to get all the runs close to the goal. Novelty search was slightly faster but only the multiobjective variant is able to reach the optimal value. This difference can be easily spotted on Fig.1.3(b), which displays a zoom on the high fitness values.If novelty is computed using only the archive, novelty search still converges a lot faster than the control experiment but it requires significantly more generations to converge. Surprisingly, it is also more noisy, suggesting that individuals close to the goal are often lost from the current population in favor of more novel ones. Last, the three objectives approach lead to results

Fig. 1 . 3

 13 Fig. 1.3 Zoom of figure 1.3 on the best fitness values: the novelty-based multiobjectivization (fit + nov.) get the optimum fitness while the basic novelty search get close to it but never reach it.

Fig. 1 . 4 Fig. 1 . 5 Fig. 1 . 6 Table 1 . 1

 14151611 Fig. 1.4 Proportion of converged runs with regards to the generation number when considering that a run has converged when the best individual get at less than 10 units to the goal.

Fig. 1 . 7

 17 Fig. 1.7 (top) Position of each individual present at each generation until the first one reaches the goal (i.e. the robot is at less than 10 units from the goal), for a typical run of each variant. The control experiment (fitness only) did not converge so the first 200 generations are displayed. The color of a point denotes the last generation the corresponding individual has been part of the population. (bottom) Maximum fitness with regards to the generation number. The gray zone corresponds to the number of generations displayed in the top diagram.

Novelty-based Multiobjectivization

The NEAT[START_REF] Stanley | Evolving neural networks through augmenting topologies[END_REF] encoding could have been used, as in the original novelty papers. One argument to use NEAT is its incremental nature: the search begins with simple neural

Parameters and Source Code

-available weights / bias:

-2.0, -1.5, -1.0, -0.5, 0.0, 0.5, 1.0, 1.5, 2.0 -proba. of weight/bias change (for each value): 0.1 -number of inputs/outputs: 7/2 -min./max. number of neurons (random generation): 10/20 -min./max. number connections (random generation): 20/45 -probability of adding/deleting a connection: 0.15/0.25 -probability of changing a connnection: 0.1 -probability of adding/deleting a neuron: 0.025/0.025 -activation function for neurons:

• source code: http://www.isir.fr/evorob_db