Fadila Khadar
email: fadila.khadar@inria.fr

Tahiry Razafindralambo
email: tahiry.razafindralambo@univ-lille1.fr

Performance Evaluation of Gradient Routing Strategies for Wireless Sensor Networks

Keywords: Sensor Network, Routing protocol, Gradient

We consider Wireless Sensor Networks (WSN) applications in which sensors have to send data to a unique sink in a multi-hop fashion. Gradient routing protocol is a scalable way to route data in these applications. Many gradient routing protocols exist, they mainly differ in their performances (delay, delivery ratio, etc.). In this paper, we propose an extensive performance evaluation study of some gradient routing protocols in order to give guidelines for WSN developers.

Introduction

A Wireless Sensor Network (WSN) is a set of autonomous objects with limited processing and storage capabilities which cooperate in order to perform a common task. They are receiving more and more attentions due to their potential applications in various areas such as monitoring, security and data gathering. The communication paradigm in WSN is very characteristic since in most applications nodes send data only to a sink. Furthermore, they operate on limited capacity batteries. As a result, WSN protocols' design, especially routing protocol, is a challenging task. The routing problem in WSN has been the subject of intense studies. One important difference between wired and wireless networks is the use of location for routing purposes. Position awareness improves the efficiency and scalability of routing protocols as it helps reducing the number of messages used for route discovery. This information could be obtained by GPS or by an internal service. GPS is not a pratical solution in WSNs, as sensors would have to be equipped with additional hardware, which would increase both cost and energy consumption. Yet, other solutions exist, such as localization protocols based on trilateration and triangulation ( [START_REF] Niculescu | Ad hoc positioning system (aps)[END_REF], [2]). Other solutions include the use of virtual coordinates, i.e., a coordinate system set up for routing purposes only. This is how work gradient routing protocols. They create a one-dimensional virtual coordinate system where the position of a node corresponds to its hop distance to the sink. This information is then used to efficiently route packets to the sink in a multi-hop fashion. When receiving a packet, a node forwards it if it is closer to the sink than the previous sender. Since each sensor receiving the packet decides locally whether it should forward it, no state information about its neighborhood has to be kept, thus reducing routing complexity. Many variants of gradient routing protocols have been proposed in the literature. They mostly differ in the way a node decides whether it should forward a received packet. As a result, their performances concerning the message delivery ratio, the end-to-end delay, and the number of nodes involved in the transmission of a message also differ. We propose an extensive performance evaluation of different gradient routing algorithm strategies for wireless sensor networks. We identified three basic schemes: basic, probabilistic and unicast schemes. The evaluation of these strategies shows that there exists a trade-off between the four considered metrics (delay, delivery ratio, overhead and energy consumption). This paper is organized as follows. In Section 2 we give a brief review of gradientbased routing protocols. In Section 3 we describe the assumptions we make. We then describe the algorithm we consider in Section 4. The simulation results are discussed in Section 5. Finally we conclude in Section 6.

Related Work

A number of routing protocols have been proposed for wireless sensor networks [START_REF] Akkaya | A survey on routing protocols for wireless sensor networks[END_REF]. They aim at providing energy efficient, low delay and low overhead routing process. In this section we briefly describe data centric routing protocol in which the sink sends a request to certain regions (or all the network) and waits for data from the sensors which are located in these regions. For a more complete review of existing routing protocols for sensor networks please refer to [START_REF] Akkaya | A survey on routing protocols for wireless sensor networks[END_REF] or other surveys.

The most classical protocols are flooding and gossiping [START_REF] Haas | Gossip-based ad hoc routing[END_REF] [5] [6] [START_REF] Hedetniemi | A survey of gossiping and broadcasting in communication networks[END_REF]. In flooding, each sensor broadcasts the packet to all its neighbors. The basic gradient protocol described in this paper is equivalent to flooding except that only a subset of sensors are allowed to broadcast packets. Flooding is very easy to implement and delivery ratio can be very high. However, it has several drawbacks, the most important one being the overhead generated by the transmission of a single message. The probabilistic flooding described in this paper is very similar to gossip algorithm especially the one described in [START_REF] Barrett | Parametric probabilistic sensor network routing[END_REF]. Gossiping algorithms alleviate the problem of overhead compared to flooding algorithm. However delivery ratio can be very low.

Direct diffusion [START_REF] Intanagonwiwat | Directed diffusion: a scalable and robust communication paradigm for sensor networks[END_REF] is one of the first routing protocols that introduces gradient. In this protocol, an interest is flooded by the sink. The gradient is a reply link to a neighbor from which the interest was received. Rumor routing [START_REF] Braginsky | Rumor routing algorthim for sensor networks[END_REF] is a variant of direct diffusion where flooding is not used.

In Gradient-based routing protocol [START_REF] Schurgers | Energy efficient routing in wireless sensor networks[END_REF], the authors propose a variant of Directed diffusion. The authors keep the number of hops when the interest is flooded into the network. Therefore each sensor can evaluate the number of hops to the sink. The difference between a node's height and the one of its neighbor is considered as the gradient on that link. A packet is forwarded on a link with the largest gradient. In this paper, we use this version of gradient routing protocol as a basis. We do not use the version proposed in [START_REF] Schurgers | Energy efficient routing in wireless sensor networks[END_REF] in this paper since we do not consider data aggregation. Moreover, we mainly focus on forwarding scheme and consider that sensors do not have any information on possible next hops for the forwarding scheme.

3 Background and assumptions

s (0) 1 (1) 2 (2) 3 (3)
(c) Probabilistic process

s (0) 1 (1) 2 (2) 3 (3) 4 (1)

5

(2)

6 (3) 7 (2) 8 (3) 9 (2) 10 (3) 11 (3) 12 (4) 13 (4) 14 (4)
(d) Unicast process We assume a large number of quasi-static wireless sensor nodes and timedriven applications: the main task of each sensor node is to periodically collect data from the sensing devices. These data are then sent to the sink in a multihop fashion due to a limited radio range. The data are sent toward the sink using a geographic routing based on gradient. The sensor nodes are assumed to use CSMA/CA MAC protocol such as 802.15. 4 [11]. Acknowledgement scheme is used for unicast packet but broadcast packets are not acknowledge.

Each periodically collected data is stored into a packet P and broadcasted by the node. This packet also contains the depth of the node (P.depth = node.depth), the source of the packet (P.dsrc = node.id) and a sequence number (P.seq = node.seq) which is generated by the node.

Each node also keeps the list of sequence numbers of packets it has already forwarded. It is worth noting that our application does not need to store neighbors' list nor exchange discovery message (after the initialization phase) due to the stateless aspect of the presented protocols.

In this paper, the term "broadcast" stands for message propagation in a node's neighborhood and the term "flooding" refers to network-wide message propagation. In the sequel, given a node n, we use the denotation n.x to refer to the variable x at the node n and given a message M and a name x that identifies a field, we use the denotation M.x to refer to the field x in message M.

Algorithm description

In this section, we describe the gradient establishment and the three algorithms that we evaluate. The gradient establishment or gradient construction is the scheme used to help routing process. The three algorithms are all based on the same gradient construction. The only difference between the algorithms is the way sensors forward each received packets to the sink.

Gradient construction

A BUILD message is flooded in the network starting from the sink s. The BUILD message contains the source of the message src which is the id of the node and the depth of the node. Initially, the sink sets BUILD.depth = s.depth = 0 and BUILD.src = s . Each node n that receives the BUILD message set its own n.depth to BUILD.depth + 1 and broadcasts the BUILD message with its own depth and also changes the BUILD.src field. A node can receive a BUILD message more than once. In this case, the node keeps the smallest depth received among all the BUILD messages but does not send the BUILD message if it has already sent one. See Figure 1(a) for the resulting process.

Basic Gradient routing protocol

Upon receiving a packet P which is not a BUILD message a node computes algorithm 1. It first checks if the depth in the packet field is greater than its own depth and if the sequence number of the packet is not in its packet sequence number list. If these conditions (Line 2 of Alg. 1) are met, the packet depth is changed to the actual node depth and the sequence number of the packet is added into the sequence list. If the node n is not the sink the packet is broadcasted.

Figure 1(b) gives an example of the paths obtained by the basic gradient routing protocol. Here, node 14 broadcasts a message, only nodes 8 and 11 forward it since their depths are smaller than the depth of node 14.

Algorithm 1 Basic Gradient routing protocol -Forwarding process

Message forwarding on node n:

Probabilistic Gradient routing protocol

The forwarding policy is the only difference between the basic gradient routing protocol and the probabilistic one. Indeed, in the probabilistic version, a packet P is forwarded based on a probability p. Line 3 of Alg. 1 is changed to:

[3-1] if (n = sink && rand(0, 1) ≤ p) then
The idea behind the probabilistic version of the gradient protocol is to reduce the overhead due to message forwarding while maintaining a good delivery ratio. Figure 1(c) gives an example of the paths obtained by the probabilistic gradient routing protocol. Here, node 14 broadcasts a message and only node 8 forwards it due to the proability and since its depth is smaller than the depth of node 14.

Unicast-based Gradient routing protocol

The unicast version of the gradient routing is built to reduce the overhead due to forwarding while maintaining a good delivery ratio. However this version is resource costly for nodes that are in the forwarding path. It is also worth noting that this version strongly relies on gradient construction.

In this version of gradient routing, each node needs to store the packet source of the BUILD message it considers for its depth. This information is stored at each node in a variable called hop (n.hop = BUILD.src). The forwarding process described in Alg. 1 is modified on Line 6 to implement the unicast version by the following line:

Performance Evaluation

We evaluate the performances of the gradient routing protocols through simulations using WSNet 1 . The performance metrics we use are delays, delivery ratio and overhead (number of duplicated messages received by the sink).

1 http://wsnet.gforge.inria.fr

Simulation settings

Network topology We consider scenario where static nodes are randomly deployed in a 1000 meters × 1000 meters flat square. The radio range is set to be 100 meters. The physical layer is modelled by the unit disk graph model. The total number of nodes varies from 100 to 400 and only connected networks are considered. We assume only one sink (at position (0,0)) initiates the gradient construction.

Node settings Sensors have to send data every 10 seconds with a random jitter to avoid synchronization. Each sensor has a buffer B of size 10 to keep packets it has to forward. FIFO policy is used for packet transmission. It has also a table S of size 20 in which it stores sequence numbers of packets it has already forwarded.

Metrics of interest We consider three metrics:

Delay Time between the sending of a packet and the first reception of it at the sink node.

Delivery ratio number of distinct received packets on number of distinct sent packets.

Overhead average number of times the same packet is received by the sink.

Gradient algorithms settings

For the probabilistic version of gradient routing, the probability of packet forwarding is set to 0.5. For the unicast version, data packets are acknowledged and retransmitted in case of failure following the scheme described in the 802.15.4 standard. Broadcast packets are also sent using the 802.15.4 standard. As our focus is to evaluate the routing process we do not try to optimize the gradient construction. It is worth noting that some optimizations avoiding unstable or long links increase the performance of the routing protocol. These optimizations on gradient construction are left to future work.

The simulation results are divided into three parts presented in Figure 2 for part I, Figures 3,4, and 5 for part II and Figure 6 and 7 for part III. The first part (Section 5.2) shows a performance comparison between the three routing strategies depending on the number of nodes in the network. None of the studied schemes outperforms the other ones in all the metrics. The second part (Section 5.3) studies the behavior of each protocol according to nodes' depth. As expected, it shows that the delay increases when the depth increases. In the third part we evaluate the energy consumption of each algorithm and plot the energy map at different simulation time. The results of this part show that the proabilistic version has the best performance among the three versions (Section 5.4). multiple path followed by each packet. This is confirmed by Figure 2(c) which shows the duplication ratio for each packet. Indeed, when the number of nodes increases, the number of possible forwarding nodes also increases. Therefore, packets can follow different paths using nodes that are not overloaded, decreasing the delay of each packet. The unicast version performs badly in term of delay. The mean delay remains constant when the number of nodes increases. This can be explained by the double effect increasing density has. On the one hand it increases the collision rate, leading to higher delays as packets must be retransmitted. On the other hand, delay decreases due to shorter paths in hop count. As a result, the end-to-end delay of the unicast version is stable. We can notice that the probabilistic version is a shift of the basic version. Indeed, the mean delay for 400 nodes in proba is close to the one for 200 nodes of basic and the mean delay for proba 300 nodes is close to the one for 150 nodes of basic. Delivery ratio The Figure 2(b) depicts the delivery ratio for the three strategies. The basic scheme is more efficient than the others. The delivery ratio for basic is always above 85%. This is explained by the multiple paths a packet can follow. The delivery ratio is decreasing when the number of nodes increases. This is due to the increasing number of collisions when the node density increases. proba gives a low but increasing delivery ratio. When the number of nodes is low there may exist only one single path from a sensor to the sink. In this case, the probability that a packet is successfully received by the sink is P r = (p) hops where p is the forwarding probability, a parameter of proba and hops is the number of hops from a given sensor to the sink. When the number of nodes increases, the probability that multiple paths exist increases and thus the delivery ratio increase for proba. The delivery ratio of unicast is around 80%. This high value is due to the retransmission used at the MAC layer for unicast packets. However, when the number of nodes increases, the number of collisions also increases, which then reduces the delivery ratio.

Simulation results: density effect (part I) Delay

Overhead The overhead of each strategy is plotted in Figure 2(c). We can see that the overhead of unicast is 1, which means that each packet is received only once by the sink. This is the perfect behavior. The overhead of basic is increasing with the number of nodes. This is mainly due to the multipath effect produced by the forwarding scheme. The overhead proba is half of the overhead of basic when the number of nodes is 300 and 400. It is also interesting to notice that when the number of nodes is low (100), the overhead is close to 1 for the three strategies, reflecting the fact that there is no multiple disjoint path from a sensor to a sink. Basic The simulations for the basic gradient routing protocol are presented in Figure 3. The delay, delivery ratio and the overhead are plotted depending on the depth of the node initiating te message. Figure 3(a) shows that the delay increases when the depth increase, as expected. We can also notice that the maximum depth is lower when the number of nodes increases (21 for 200 nodes, and 15 for 400 nodes). This first result also indicates that for any depth the delay decreases when the number of nodes increases. Figure 3(b) plots the delivery ratio depending on the depth of the originating nodes. The depth does not seem to strongly affect the delivery ratio. The latter remains roughly constant. This behavior is explained by the multiple paths followed by each packet. The overhead for each packet depending on the depth is drawn in Figure 3(c). We can see that for 100 nodes, the overhead is decreasing along with the depth. This is probably due to the small number of paths available when the source node has an higher depth. For the other densities, the overhead is increasing when the number of nodes increases. Again, this is due to the multiple paths a packet can follow when the depth increases. For 200 nodes, we can see that the overhead remains stable. For this density, only a constant number of multiple paths can be found.

Unicast Figure 4 shows the simulation results for the unicast gradient routing protocol. The mean delay increases in the same way for each density when the depth increases ( Figure 4(a)). This is due to the fact that all packets follow only one path and that the delay for a one hop communication is constant. Figure 4(b) plots the delivery ratio depending on the depth. We can see that the delivery ratio decreases when the depth increases. This is mainly due to the buffer size of each node. In the unicast version, packets follow the same path which overloads the buffer. Packets may then be dropped. When the number of hops increases (depth), the probability for a packet to be dropped also increases, which explains this behavior. In Figure 4(c), we can see that the overhead is equal to 1 as unicast routing is used.

Probabilistic The simulation results for probabilistic gradient routing are shown in Figure 5. The results are similar to the basic gradient results (Figure 5(a)). However, the maximum depth changes depending on the number of nodes. When the number of node is 100, the maximum depth is only 5. This means that for the probabilistic version, messages coming from higher depth do not reach the sink. This also confirms the fact that for 100 nodes the probability of having multiple paths is very low. A simple way to avoid this problem is to modify the forwarding probability depending on the node depth. With the probabilistic approach, the delivery ratio (see Figure 5(b)) decreases when the depth increases. This is foreseeable since for a given path the delivery probability decreases when the number of hops increases.

Figure 5(c) shows the overhead for each packet depending on the depth of the originating nodes. For all number of nodes, the overhead increases and then remains stable. This is due to the number of paths reduction caused by the probability of retransmission. It is worth noting that the shape of the proba curve of 400 nodes is similar to the shape of basic the curve for 200 nodes. This indicates that the effect of the probability is the same as the effect of reducing the number of nodes.

Energy consumption (part III)

In the previous simulation battery lifetime was set to infinity to evaluate the performance of each protocol. In this part we introduce results about energy consumption for the different algorithms. The energy model we use is very simple and linear: the energy cost of a transmission is 2, the energy cost of a reception is 1. Each sensor has initially 200000 units of battery. The graph in Figure 6 shows the evolution of the percentage of dead nodes over time for the three algorithms. The unicast version seems to perform better than the other two versions after 160 secondes. Yet, one must be cautious with these results as they do not indicate the geographical repartition of dead nodes. Indeed, if all dead nodes are located near the sink, the network becomes useless.

For better understanding the repartition of dead nodes across the network we use energy maps. The energy maps of each algorithm at different step of the simulation (20s, 30s, 100s and 200s) for 200 sensors in a field of 1000m×1000m are drawn on Figure 7.

The sink is at the bottom-left corner of each figure and has the geographical coordinate (0,0). All other parameters are left unchanged. Black color means that sensors within the area have no battery left (0%). Blank color means that battery is full (100%). We can conclude from Figure 7 that the worst algorithm is the basic version. Indeed, after 20s most of the nodes within the sink's neighborhood have 0% battery left. This is due to the high number of sensors, especially sensors close to the sink, involved in the reception and (re)transmission of packets. For the unicast version, after 30s, most of the nodes around the sink have 0% battery left. After 100s and for the unicast version, nodes within the paths followed by the packets have almost 0% battery left. The probabilistic version exhibits better performances compared to both unicast and basic versions. We can see that for the probabilistic version, most of the nodes within the sink neighborhood are dead after 200s. These results demonstrate that there exists a trade-off between the network lifetime and the performances of the gradient routing algorithm. Note that the results may be different depending on the energy model used but the conclusion are still the same. It is also worth noting that the performance of the probabilistic algorithm can be enhanced by modifying the forwarding probability according to the remaining battery of each sensor such as in [START_REF] Jaffres-Runser | A probabilistic interference and energy aware gradient broadcasting algorithm for wireless sensor networks[END_REF]. However, modifying this probability may affect other performance metrics.

Conclusion and Future Work

In this paper we evaluated three routing algorithms for wireless sensor networks. The three algorithms are based on a gradient that helps sensors to forward the data they receive to the sink. We first evaluated an algorithm where packets are forwarded by each node using local broadcast. The second algorithm is based probabilistic forwarding of the packet and the third one is based on unicast forwarding of the packet. We evaluated these algorithms based on three metrics namely the delay, the delivery ratio and the overhead. Our simulations show that the performances of each scheme are very different and that none of the studied scheme is better than the other. We also evaluate the energy consumption of each algorithm and these results confirm that there exists a tradeoff between delivery ratio and energy comsumption. The choice of the algorithm must be based on what is expected from the network. If reliability is the main criteria, the basic scheme should be used at the expense of energy consumption. If the lost of some messages is not critical, the unicast version is a good compromise. The next step of this work is to evaluate the impact of having a better gradient construction and maintenance on the performance of each routing protocol. Indeed, in the gradient construction we use gradient may not be optimal due to message loss. We also want to evaluate the effect of different parameters especially for the probabilistic version of the gradient or evaluate the combination of different strategies depending on the depth of the originating sensor.

Fig. 1 .

 1 Fig. 1. Illustration of the gradient routing. The sink is node s. In Figure 1(a) Lines represent BUILD message flooding used to set node depth. The number in brackets represents the node depth. Dashed lines represent communication links. Figure 1(b), 1(c) and 1(d) are examples of basic, probabilistic and unicast process based on the depth of each node.

[ 6 - 1 ]

 61 Figure 1(d) gives an example of the path obtained by the unicast-based gradient routing protocol. Here, the message follows a single path based on the depth of each node.

Fig. 2 .

 2 Fig. 2. Simulation results

5. 3 Fig. 3 .Fig. 4 .Fig. 5 .

 3345 Fig. 3. Simulation results basic gradient

Fig. 6 .

 6 Fig.6. Percentage of dead nodes over time for the 3 algorithms. After 160s the unicast version performs better, but the mean delay is higher (see Figure2(a))

Fig. 7 .

 7 Fig. 7. Energy map after of each algorithm at 20, 30, 100, and 200 seconds of simulation. Black (blank) color means that sensors within this area have 0% (100%) battery left.

1 :

 1 Reception of packet P 2: if (P.depth > n.depth) && (P.seq /

	3: 4: 5: 6: 7: 8: 9: 10: else if (n = sink ) then P.depth = n.depth ; n.seqlist ← P.seq broadcast packet P ; else Process packet P ; end if 11: Drop P; 12: end if	∈ n.seqlist) then


Jean-Baptiste Mouret
email: mouret@isir.fr

Stéphane Doncieux
email: doncieux@isir.fr

Using Behavioral Exploration Objectives to Solve Deceptive Problems in Neuro-evolution

Keywords: I.2.6 [Artificial intelligence]: Learning-Connectionism and neural nets Neural networks, multiobjective evolutionary algorithm, diversity, deceptive problems

Encouraging exploration, typically by preserving the diversity within the population, is one of the most common method to improve the behavior of evolutionary algorithms with deceptive fitness functions. Most of the published approaches to stimulate exploration rely on a distance between genotypes or phenotypes; however, such distances are difficult to compute when evolving neural networks due to (1) the algorithmic complexity of graph similarity measures, (2) the competing conventions problem and (3) the complexity of most neural-network encodings.

In this paper, we introduce and compare two conceptually simple, yet efficient methods to improve exploration and avoid premature convergence when evolving both the topology and the parameters of neural networks. The two proposed methods, respectively called behavioral novelty and behavioral diversity, are built on multiobjective evolutionary algorithms and on a user-defined distance between behaviors. They can be employed with any genotype. We benchmarked them on the evolution of a neural network to compute a Boolean function with a deceptive fitness. The results obtained with the two proposed methods are statistically similar to those of NEAT and substantially better than those of the control experiment and of a phenotypebased diversity mechanism.

INTRODUCTION

Finding good solutions for deceptive problems is one of the main challenge in evolutionary computation since the pioneers' work in this field [START_REF] Goldberg | Simple genetic algorithms and the minimal, deceptive problem[END_REF][START_REF] Goldberg | Massive multimodality, deception, and genetic algorithms[END_REF]. Starting with the assumption that a well spread population has a higher probability to find new fitness peaks than a population focused around only one peak, one of the most classic modification of the basic evolutionary algorithm to tackle deceptive problems is to explicitly maintain a high diversity of candidate solutions [START_REF] Holland | Adaptation in Natural and Artificial Systems[END_REF][START_REF] Goldberg | Genetic algorithms with sharing for multimodal function optimization[END_REF]. Improving the diversity within the population can also be viewed as a way to tune the exploration/exploitation trade-off underlying the evolutionary process in favor of more exploration: some inefficient candidate solutions can be kept in the population only because they are different from their counterparts.

Artificial neural networks have drawn considerable attention for the last twenty years mainly thanks to their versatility, as their range of application covers from the control of robots to data clustering. Evolutionary algorithms have often been successfully employed to design their topology and set their weights, leading to neuro-evolution processes (e.g. [START_REF] Gruau | Automatic definition of modular neural networks[END_REF][START_REF] Yao | Evolving artificial neural networks[END_REF][START_REF] Stanley | Evolving neural networks through augmenting topologies[END_REF][START_REF] Doncieux | Evolving PID-like neurocontrollers for non-linear control problems[END_REF][START_REF] Mouret | Mennag: a modular, regular and hierarchical encoding for neural-networks based on attribute grammars[END_REF]). However, despite the early interest in diversity for parameter optimization, current diversity preservation approaches are still difficult to exploit in neuro-evolution. One of the main reason is the algorithmic complexity to compute the similarity between candidate solutions, a NP-hard problem for unconstrained oriented graphs [START_REF] Bunke | Recent developments in graph matching[END_REF] and therefore for most neural networks. Another reason is the complexity of encodings used in neuroevolution, making each diversity maintenance method specific to a particular and often complex setup. The competing convention problem (see e.g. [START_REF] Yao | Evolving artificial neural networks[END_REF]) is a third difficulty to overcome when trying to compare neural networks. Furthermore, setting the parameters that controls the exploration/exploitation trade-off is often challenging and empiric, but critical for the efficiency of the evolutionary process.

In this paper, we introduce and compare two simple, generic, and efficient ways to improve exploration to bypass the problems posed by deceptive fitness functions when evolving both the topology and the parameters of neural networks. The two proposed methods, respectively called behavioral novelty and behavioral diversity, rely on Paretobased multiobjective evolutionary algorithms (see [START_REF] Deb | Multi-objectives optimization using evolutionnary algorithms[END_REF]) and on a user-defined distance between behaviors. To assess the efficiency of this behavioral approach, we employed the approximation of a Boolean function by a neural network with a deceptive fitness. The results obtained with both meth-ods are compared with those of NEAT [START_REF] Stanley | Evolving neural networks through augmenting topologies[END_REF], which includes a sophisticated diversity maintenance mechanism and with those obtained using a genotype diversity based on a graph distance (graph probing, [START_REF] Lopresti | A fast technique for comparing graph representations with applications to performance evaluation[END_REF]).

RELATED WORK

Many methods have been published to maintain diversity in evolutionary algorithms in order to improve their exploration capabilities and avoid premature convergence (e.g. [START_REF] Goldberg | Genetic algorithms with sharing for multimodal function optimization[END_REF][START_REF] Burke | A survey and analysis of diversity measures in genetic programming[END_REF][START_REF] Jong | Reducing bloat and promoting diversity using multi-objective methods[END_REF]). Among those, fitness sharing [START_REF] Goldberg | Genetic algorithms with sharing for multimodal function optimization[END_REF] is probably the most common one: the search landscape is modified by reducing the fitness of individuals in densely-populated regions, thus promoting search in less explored regions. To that aim, the fitness of each individual i is divided by a "niche coefficient", defined as the number of individuals whose distance to i is below a user-defined threshold. Typical distances are computed between genotypes, one of the simplest example being a Hamming distance between binary strings in a binary-based genetic algorithm.

Dividing the fitness by the niche coefficient, as in fitness sharing, is an attempt to combine a performance objective, maximizing the fitness, and an exploration objective, minimizing the niche coefficient. Recent research in evolutionary computation proposed numerous algorithms to simultaneously optimize several objectives instead of aggregating them to a single one. Most of them rely on the concept of dominance: 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 Pareto-optimal set and its image in objective space is called the Pareto front. A typical multiobjective algorithm sorts individuals with respect to dominance and aims at finding a well spread sample of the Pareto front. The success of Pareto-based multi-objective evolutionary algorithms (MOEA, see e.g. [START_REF] Deb | Multi-objectives optimization using evolutionnary algorithms[END_REF][START_REF] Coello Coello | Applications Of Multi-Objective Evolutionary Algorithms[END_REF]) suggested to add the diversity of the population as an objective on its own in a multiobjective optimization. A MOEA can then be employed to obtain the set of all Pareto-optimal trade-offs between original solution candidates and efficient ones. Several recent papers deal with this idea in diverse contexts. In genetic programming, [START_REF] Jong | Reducing bloat and promoting diversity using multi-objective methods[END_REF] added the mean distance to the rest of the population as a second objective for the problems of 3, 4 and 5-parity. [START_REF] Toffolo | Genetic diversity as an objective in multi-objective evolutionary algorithms[END_REF] adopted a similar method by using the sum of Euclidean distance between each individual and the others; they also proposed to use only the distance to the closest individual. [START_REF] Abbass | Searching under multi-evolutionary pressures[END_REF] and [START_REF] Bui | Multiobjective optimization for dynamic environments[END_REF] analyzed numerous ways to add an objective to improve diversity and compared them to single objective mechanisms: the generation of appearance of an individual (to be minimized), a random value, the opposite of the main fitness, the distance of the nearest neighbor in the genotype space, the mean distance to individuals of the current population and the distance to the best individuals of the current population. They concluded that the best results were obtained using a multiobjective evolutionary algorithm combined with the distance to the closest neighbors or the mean distance to the whole population. A direct consequence of their results is that modern diversity preservation mechanisms seem to have much to gain by using multiobjective algorithms.

Such addition of new objectives to help the optimization process is sometimes termed a 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].

In each of the considered diversity maintenance approaches, single or multiobjective, N 2 distances must be computed at each generation for a population of N individuals. While this computational cost may appear negligible when solutions are represented by real-valued vectors or binary strings, it may easily rise when more complex genotypes are used. In particular, the edit distance between two graphs is NP-hard [START_REF] Bunke | Recent developments in graph matching[END_REF] and consequently not suitable to be used in a diversity maintenance mechanism. Nonetheless, the numerous applications in pattern matching lead to many heuristics to approximate a measure of the similarity between two graphs. Among recently published results (see [START_REF] Bunke | Recent developments in graph matching[END_REF] for an overview of classical methods), [START_REF] Lopresti | A fast technique for comparing graph representations with applications to performance evaluation[END_REF] proposed a fast algorithm based on the graph probing paradigm. According to this paradigm, "probes" are functions that examine the vertex and edge structure of a graph by counting in-and out-degrees. The results of such probes for each graph are then compared. A theoretical analysis [START_REF] Lopresti | A fast technique for comparing graph representations with applications to performance evaluation[END_REF] demonstrates that graph probing provides a lower bound on the true edit distance between two graphs. Empirical results showed a good correlation with the latter measure. The speed of this approach makes it suitable to be used in a evolutionary context, as did [START_REF] Reveaux | A Graph Classification Approach Using a Multi-objective Genetic Algorithm Application to Symbol Recognition[END_REF] for a pattern recognition task. In this paper, we will investigate its use to maintain the diversity in a population of neural networks.

The competing conventions are another problem when trying to compute the distance between two neural networks. Two given neural networks may only differ by the order of appearance of their hidden units and therefore be topologically equal while having a different genotype. This makes the design of a useful genotype-based distance very difficult and often computationally expensive.

NEAT [START_REF] Stanley | Evolving neural networks through augmenting topologies[END_REF], one of the most successful method to evolve neural networks, provides an interesting approach to bypass both the computational cost of graph distance and the competing convention problems. NEAT starts with only one topology for all the individuals and, during the evolutionary process, attributes a unique and global innovation number to new connections and new nodes. To compute the similarity between two genotypes, genes with the same innovation numbers are lined up and those that do not match are counted. A linear combination of the number of unmatched genes and weights differences results in a scalar measuring the similarity between two genotypes. Last, NEAT uses this measure to modify the raw fitness by fitness sharing. Despite the good results obtained by NEAT, one should note that this similarity measure requires to start the evolutionary process using only one topology and that it strongly depends on the used genotype.

APPROACH

Behavioral Diversity

An infinity of neural networks can return the same output for a given input data set. For instance, all the neural networks in which there exists no path between the inputs and the outputs have the same null output. Whatever their topology and their parameters are, these candidate solutions will obtain the same fitness. More generally, in most situations, rising the diversity of neural networks can be achieved by adding useless neurons and connections. This simple strategy slows down the simulation of neural networks but has no reason to enhance the process.

An alternative and more original view is to maintain the diversity of behaviors. All the neural networks with unconnected outputs have the same behavior -a null output; similarly, adding a neuron in a fully saturated network often has no effect on the overall behavior. While encouraging new topologies may not improve the process, we hypothesize here that allowing the selection of new behaviors, even if they are inefficient, can bring better results.

Let's suppose we have a distance d b (x, y) between the behavior of x and y. Following the conclusions published by [START_REF] Bui | Multiobjective optimization for dynamic environments[END_REF], we propose to define the originality B(x) of the behavior of individual x as the mean distance between x and the rest of the population. Maximizing B(x) lead naturally to the maximization of the diversity of behaviors. As suggested in [START_REF] 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] and [START_REF] Bui | Multiobjective optimization for dynamic environments[END_REF], this objective can then be added to the set of performance objectives to optimize all of them simultaneously with a Pareto-based MOEA. The expected results is, at each generation, an approximation of the Pareto-optimal trade-offs between performance and originality. Hence, instead of maximizing a set of performance objectives F1(x), F2(x), ..., F k (x), we maximize the following objectives:

M aximize : 8 > > > < > > > : F1(x) . . . F k (x) B(x) = 1 |Pn| P j∈Pn d b (x, j)
where Pn denotes the population at the current generation n and j an individual of Pn.

We now have to design a distance between behaviors. Since interesting behaviors are trivially application-dependent, this distance should be user-defined. While this may appear as a considerable challenge, all the experiments we conducted, such as the results presented in this paper, showed that surprisingly simple and even naive distances substantially improved the evolutionary process.

For instance, when evolving neural networks to control a mobile robot interacting with some objects, a vector v (x) can contain the position of objects at the end of the experiment; if a robot has to explore a maze, its final position can also be stored in such a real-valued vector; if it has to reach some zones in an arena, such as feeding zones, v (x) k can take the value 1 if zone k has been reached and 0 otherwise. If neural networks have to perform a pattern classification task, a similar vector with a size equal to the number of training samples can track the output of the neural network for each case. The distance d b (x, y) can then be defined as the Euclidean distance between v (x) and v (y) :

d b (x, y) = ˛˛v (y) -v (x) ˛M
any other distances between behaviors can be designed, even if the evolved genotype does not represent a neural network. The only constraint is to be able to define a concept of behavior in the handled problem. Nonetheless, not every MOEA can be employed due to the dynamic nature of B(x).

For each individual i, B(x) depends on the behavior of the rest of the population. As a consequence, B(x) will change at each generation and a non-dominated individual thanks to a high B(x) value could be dominated at the next generation because of a lower B(x) value. This dynamic objective is compatible with MOEAs that compute the non-dominated set of solutions at each generation such as NSGA-II [START_REF] Deb | A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II[END_REF] or MOGA [START_REF] Fonseca | Genetic algorithms for multiobjective optimization : formulation, discussion and generalization[END_REF]. However, archive-based MOEAs, for instance ε-MOEA [START_REF] Deb | Evaluating the ε-Domination Based Multi-Objective Evolutionary Algorithm for a Quick Computation of Pareto-Optimal Solutions[END_REF], need to be slightly modified to recreate the archive at each generation (this does not require any reevalution of the fitness function).

Behavioral Novelty

In a recent work about open-endness in evolutionary computation, [START_REF] Lehman | Exploiting open-endedness to solve problems through the search for novelty[END_REF] proposed to maximize the "novelty" of behaviors instead of the fitness. They then argued that this process may be more efficient to find good solutions for a given objective -although unknown to the evolutionary process -by overcoming the deceptiveness of the fitness function. The authors computed the novelty of an individual using a distance between behaviors, similar to the one discussed in the present paper. However, contrary to the behavioral diversity defined in the previous section, novelty takes into account the set of all behaviors previously encountered (including the current population) and not only the current population. More precisely, [START_REF] Lehman | Exploiting open-endedness to solve problems through the search for novelty[END_REF] measured the novelty ρ(x) of an individual i by computing the mean behavioral distance between i and its k nearest neighbors:

ρ(x) = 1 k k X 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 in the archive of behaviors. 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 some minimal threshold.

Extending the work of [START_REF] Lehman | Exploiting open-endedness to solve problems through the search for novelty[END_REF] to a multiobjective context, this archive-based novelty measure can be used as a second objective in a multiobjective optimization. Hence, an individual will be non-dominated if and only if it represents a Pareto-optimal trade-off between novelty and efficiency. However, by relying on all the previously explored individuals and the current population, this approach mixes behavioral diversity -related to the current population -and behavioral novelty -related to the archive. To estimate the importance of novelty with regards to diversity, we propose to build an archive of behaviors and to use as an additional objective the mean distance to the nearest archived behaviors, the current population being ignored. More formally, using behavioral novelty consists in transforming the multiobjective maximization problem F1(x), F2(x), ..., F k (x) to:

M aximize : 8 > > > < > > > : F1(x) . . . F k (x) ρ(x)
Compared to mechanisms based only on the current population, this kind of archive-based objective has a substantial computational cost because the archive may easily be larger than current population. Finding the nearest neighbors in such a large set can therefore become costly.

Probe-based Graph Diversity

To further understand the advantages of the described behavioral objectives over genotypic or phenotypic diversity, we implemented a diversity objective based on the graphprobing distance measure [START_REF] Lopresti | A fast technique for comparing graph representations with applications to performance evaluation[END_REF]. Let G1 and G2 denotes two neural networks and VG the set of vertices of network G.

For each network, we can count vertices with in-degree i and collect the results in a vector IG such that

I G = (n0, n1, ..., n k ) where ni = ˛{v ∈ VG|indeg(v) = i}
where k denotes the maximum number of input connections of a neuron in our typical neural networks (e.g. 15). A similar vector can collect the out-degrees:

O G = (m0, m1, ..., m k ) where ni = ˛{v ∈ VG|outdeg(v) = i}
Ą network G can be described by the vector P G :

P G = (n0, n1, ..., n k , m0, m1, ..., m k )
Last, dp(G1, G2) is defined as the Euclidean distance between P G 1 and P G 2 and the graph diversity objective consists in maximizing the mean distance between the considered individual and the rest of the population:

Maximize 8 > > > < > > > : F1(x) . . . F k (x) D(x) = 1 |Pn| P
j∈Pn dp(x, j) where:

dp(x) = 1 N N X j=1 ˛˛P G i -P G j ˛4
. EXPERIMENTS

Genotype and Fitness

To benchmark these different approaches of exploration enhancement, we evolved 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). The truth table of ˆ(a ⊕ b) ∧ (c ⊕ d) ˜(table 1) shows that a simple neural network that returns "false" for any input would have a 75% success rate, a good score for this task, especially at the beginning of the evolutionary process. As a consequence, these degenerated neural networks can easily invade the population whereas they do not constitute a good starting point. This makes the typical single-objective fitness for this function -the sum of errors -very deceptive. This has been empirically illustrated in [START_REF] Kashtan | Spontaneous evolution of modularity and network motifs[END_REF]: using an elitist evolutionary algorithm, a population of 1000 individuals and a graph-based direct encoding for NAND gates, [START_REF] Kashtan | Spontaneous evolution of modularity and network motifs[END_REF] reports that only 72% of experiments found a solution in less than 10 5 generations; in other words, more than a quarter of their experiments were trapped in an inescapable local optima despite the large number of individuals and generations.

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 possible:

• 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. We used the classical sum of errors for each possible set of inputs as the main fitness for an individual x (expressed in a fitness maximization scheme):

Fxax(x) = 1 - 1 16 16 X i=1 |ox,i -di|
where ox,i is the output of the neural network x for the input set i and di 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.

Behavior Vectors

To describe behaviors, each individual x is associated to a Boolean behavior vector v (x) that contains the output of the neural network for each of the 16 different input sets:

v (x) i = nnx(bi), i = 1, 2, ..., 16; bi ∈ {0000, 0001, ..., 1111}
The distance between behaviors is then straightforward:

d b (x, y) = ˛˛v (y) -v (x) ˛T
o implement behavioral novelty, an archive An stores all the behavior vectors v (x) present in the populations P0, ..., Pn, where n denotes the generation number:

An(v) =  v if v ∈ P0, P1, ..., Pn ∅ otherwise
The novelty score is equal to the mean distance to the k = 10 nearest behaviors in An, where k was experimentally chosen using our experiments and those of [START_REF] Lehman | Exploiting open-endedness to solve problems through the search for novelty[END_REF].

Experiments

We launched 5 sets of 16 experiments; using the previously defined notations, for an individual x:

1. Control experiment. Maximize Fxax(x) 2. Behavioral diversity. Maximize  Fxax(x) B(x) = 1 |Pn| P j∈Pn d b (x, j) 3. Behavioral novelty. Maximize  Fxax(x) B(x) = 1 k P k j=0 d b (x, µj)
Figure 1: Mean maximum fitness (over 16 runs of each experiment), with respect to generation number. Behavioral diversity, behavioral novelty and NEAT reached a value close to the maximum (1) in less than 1500 generations whereas the control experiment and the graph probing approach did not exceed 0.75 (the attractive local maximum).

where µj is the j-th nearest neighbors in the archive An,

Probe-based diversity.

Maximize

 Fxax(x) D(x) = 1 |Pn| P j∈Pn dp(x, j)
5. NEAT. Maximize Fxax(x) using NEAT [START_REF] Stanley | Evolving neural networks through augmenting topologies[END_REF].

With the exception of the NEAT experiment, in which we employed the NEAT algorithm, each set of objectives has been maximized using NSGA-II [START_REF] Deb | A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II[END_REF], one of the most efficient MOEAs [START_REF] Deb | Multi-objectives optimization using evolutionnary algorithms[END_REF]. It should be emphasized that all these experiments (except NEAT) use a standard algorithm and a classic genotype; repeating them should be easy.

The detailed parameters and the url to download the source are available in appendix.

RESULTS

Maximum Fitness and Convergence Rates

Figure 2 shows the mean maximum fitness with respect to generation for each set of experiments. The best fitnesses are obtained by behavioral diversity, behavioral novelty and NEAT, with a mean maximum fitness of more than 0.95 after 1500 generations. The control experiment and probebased diversity led to significantly worse results, with a mean fitness around 0.75, i.e. the best networks are not better than a network that returns "false" for any input.

These results are confirmed by analyzing the convergence rates (figure 2): while 90% of the experiments made with behavioral diversity, behavioral diversity and NEAT converged (the fitness of the best individual was more than 0.95) in less than 1500 generations, only a few (12%) of the control experiments did so. Probe-based diversity led to worse results than the control experiment, no run having converged after 1500 generations.

We then analyzed the mean convergence generation for behavioral diversity, behavioral novelty and NEAT (table 2). Behavioral novelty and NEAT required slightly fewer generations to converge (about 750 versus about 900) than behavioral diversity but a Student T-test reveals that this difference is not statistically significant.

Behavioral Analysis

To draw a picture of the behavioral diversity process in an experiment, we introduce here an original type of diagram, called behavioral diversity diagram (figures 3, 4, 5 and 6). For each generation, we counted the proportion of individuals that returned the correct output for each of the 16 input sets. On the diagrams, this proportion is reported as the gray level of a small vertical stripe for each input set, aligned with the generation number. In a population with diverse behaviors, we expect a diagram almost uniformly gray because all behaviors should be present in the population, at any generation. Contrarily, in a population with uniform behaviors, which probably lacks diversity, we expect to see large horizontal white stripes (behaviors shared by 100% of the population during a significant amount of generations) and black horizontal stripes (behaviors absent of the population during many generations). Last, the fitness of the best individual is plotted with respect to the generation number in order to see how best fitnesses are related to behaviors.

Unsurprisingly, the diagrams corresponding to the control experiments (figure 3) shows such black and white stripes. In the run analyzed on figure 3, more than 90% of the pop- ulation returned "false" for all the possible inputs for about 300 generations; this is translated as long white stripes for the 12 input sets that should lead to "false" and four black stripes for the 4 ones that should lead to "true". In this run, a novel behavior appeared at generation 300 and quickly invaded the population. All the runs of the control experiments we analyzed led to similar diagrams, confirming the diagnosis of a lack of diversity.

These black and white stripes contrast with the uniformity and the grayness of figure 4, which shows the diagram corresponding to a typical experiment using behavioral diversity. All the behaviors are present in the population, and only short cycles -displayed as changes between dark and clear gray levels -can be distinguished.

The behavioral novelty approach led to different and more complex patterns (figure 5) in which diversity episodes succeed to uniform behaviors. These diversity episodes were correlated with rapid increases of the archive size. The diversity-uniformity cycles reveal that once in a while a new "invention" gives birth to many new behaviors; they are then selected and only the ones with the best fitnesses are kept. After the best individual reached the maximum fitness, the only selective pressure is towards novelty. This results in a high diversity episode, which fills the archive. Once the archive is almost full, all the population converged to the same behavior, the optimal one; this is illustrated by a large white zone on the diagram.

While behavioral novelty adds a selective advantage to new behaviors when they appear, this advantage is not maintained for many generations because the behaviors are not new anymore. This results in a situation in which a novel individual has an influence on the evolutionary dynamics only when it has almost no neighbors. Once one individual with each of the close behavior has been generated, nothing prevents the evolutionary algorithm from premature convergence to a small subset of behaviors. Taking into account the current population when computing the nearest neighbors, No behavior seems to be shared by more than half of the population as no white zone can be observed. Similarly, no behavior seems absent from the population as there are no black zones. The alternation of light and dark grays denotes small (one to a few generations) cycles in which a behavior is first original, therefore kept in the next generation, then less original because of the offspring of the kept individual. (bottom) Fitness of the best individual with respect to generation number. The optimum (1.0) is reached after about 500 generations.

as did [START_REF] Lehman | Exploiting open-endedness to solve problems through the search for novelty[END_REF], could have added a selective pressure towards diversity. However, since the size of the archive is large compared to the population size, this pressure will decrease during the evolutionary process.

Last1 , the diagram corresponding to probe-based diversity (figure 6) shows that this mechanism maintains more diversity than the control experiment. It is therefore surprising that it did not improve the convergence rate and even decreased it. This issue should be investigated in future work.

DISCUSSION AND CONCLUSION

The experiments reported in this paper show at least that:

• without any diversity preservation mechanism, the diversity of behaviors is very low (figure 3);

• behavioral diversity, behavioral novelty and NEAT are three efficient solutions to override the deceptiveness of a fitness when evolving neural-networks (figure 2); the difference between them was not statistically significant in these experiments (table 2) but the observed tendency suggests that NEAT and behavioral novelty might converge faster than behavioral diversity;

• the phenotype-based approach to diversity investigated did not improve the convergence rate and even deteriorated it.

These results add weights to the previous experiments that report performance enhancements with multiobjective diversity mechanisms [START_REF] Jong | Reducing bloat and promoting diversity using multi-objective methods[END_REF][START_REF] Abbass | Searching under multi-evolutionary pressures[END_REF][START_REF] Toffolo | Genetic diversity as an objective in multi-objective evolutionary algorithms[END_REF][START_REF] Bui | Multiobjective optimization for dynamic environments[END_REF]. They also demonstrate that maintaining the diversity of the behaviors of candidate solutions instead of preserving the diversity of their genotype or phenotype is a simple and efficient approach. Algorithmically and conceptually simple distances can be designed while being independent of the encoding. Moreover, no special evolutionary process is required; classic and efficient MOEA can be employed.

The computational cost of behavioral novelty over behavioral diversity does not seem justified in these experiments but some other benchmarks problems might lead to more differences between these two methods. Moreover, their combination may be investigated in future work: while keeping diverse behaviors can be done using a diversity objective, a selective pressure to encourage new behaviors could be added as a third objective. However, adding many objectives in addition to the main ones can decrease the efficiency of the evolutionary process, as reported in many papers [START_REF] Praditwong | How well do multi-objective evolutionary algorithms scale to large problems[END_REF][START_REF] Purshouse | On the Evolutionary Optimization of Many Conflicting Objectives[END_REF].

The efficiency of NEAT could suggest the conclusion that the presented method is not an improvement over the literature. However, at least two points should be taken into account. First, by starting with a fully-connected feed-forward neural network and disabling recurrent connections, NEAT constrains the search process to feed-forward networks. This is an intuitively useful bias in the considered experiment that was not included in the other methods. Second, implementing NEAT is more complex than using a direct encoding, notably because the encoding scheme is tightly linked to the evolutionary algorithm. Fitness sharing in NEAT, i.e. the modified evolutionary process, requires innovation numbers, which are deeply integrated in the encoding. At the opposite, behavioral methods can be used with any encoding and do not require any specific evolutionary algorithm. They can even be used with other phenotypes than neural networks such as Bayesian networks or fuzzy rules based systems. Last, NEAT is based on the assumption that the experimenter is able to provide a starting topology, an assumption that may not be valid in every context.

As a general conclusion, behavioral diversity and novelty appear to be simple and efficient methods to improve neuroevolution when facing a deceptive problem, at least when simple behavioral distance can be designed. These results highlight that although considerable efforts have been put in designing neural networks encodings, working on the selective pressures can also be fruitful while being simpler. Future work should extend the behavioral diversity concept to more general contexts than neuro-evolution. For instance, the diversity of robots' behaviors can be maintained using a similar approach to the one presented here [START_REF] Mouret | Overcoming the bootstrap problem in evolutionary robotics using behavioral diversity[END_REF].

Figure

  Figure 2: Convergence rate (over 16 runs of each experiment), with respect to generation number. 90% of the runs corresponding to behavioral diversity, behavioral novelty and NEAT converged in less than 1500 generations whereas only a few control runs converged. No run converged in the graph probing experiments.

Figure 3 :

 3 Figure 3: Behavioral diversity diagram for a typical run of the control experiment. (top) Ratio of the population that returns the desired output for each of the 16 data sets, with respect to generation number. During the first 300 generations, almost all the population had the same behavior: returning "false" for each data set and consequently having the right answer 12 times over 16. This is illustrated by the black stripes. (bottom) Fitness of the best individual with respect to generation number. It does not exceed 0.75.

Figure 4 :

 4 Figure 4: Behavioral diversity diagram for a typical run of behavioral diversity.No behavior seems to be shared by more than half of the population as no white zone can be observed. Similarly, no behavior seems absent from the population as there are no black zones. The alternation of light and dark grays denotes small (one to a few generations) cycles in which a behavior is first original, therefore kept in the next generation, then less original because of the offspring of the kept individual. (bottom) Fitness of the best individual with respect to generation number. The optimum (1.0) is reached after about 500 generations.

Figure 5 :

 5 Figure 5: Behavioral diversity diagram for a typirun of behavioral novelty. (top) Episodes of high diversity succeed to low diversity ones. (middle) Fitness of the best individual with respect to generation number. A fitness increase often precedes diversity increase. (bottom) Size of the archive. Each high diversity episode results in an increase of the archive size.

Figure 6 :

 6 Figure 6: Behavioral diversity diagram for a typical run of the graph probing experiment. While the gray levels are not as uniform as in figure 4, this figure shows that many different behaviors are present in the population. (bottom) Fitness of the best individual with respect to generation number. Despite the diversity of behaviors, the best fitness never exceeds 0.75.

Table 1 :

 1 Truth table of the function ˆ(a ⊕ b) ∧ (c ⊕ d) ˜, where a, b, c et d are Boolean values and ⊕ the exclusive or (xor). 75% of outputs are "false".

Table 2 :

 2 2: Convergence rate (over 16 runs of each experiment), with respect to generation number. 90% of the runs corresponding to behavioral diversity, behavioral novelty and NEAT converged in less than 1500 generations whereas only a few control runs converged. No run converged in the graph probing experiments. Mean convergence generation (maximum Fxax > 0.95) and Student T-test. Behavioral diversity seems to require more generations to converge but the difference is not statistically significant.

		B. div	B. nov.	NEAT
	Mean gen.	921.7	734.6	757.3
	Std. dev.	463.1	494.7	499.4
	T-test div.	p=1.0	p=0.2401 p=0.3025
	T-test nov.	p=0.2401 p=1.0	p=0.9083
	T-test NEAT p=0.3025 p=0.9083 p=1.0

The diagram corresponding to NEAT was not generated for technical reasons.

APPENDIX A. PARAMETERS: DIRECT ENCODING

• MOEA: NSGA-II (pop. size : 400)

• Neural network (direct encoding):

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: 4/1 -min./max. neurons (random gen.): 10/20 -min./max. connections (random gen.): 20 -proba. of adding/deleting a conn.: 0.15/0.25 -proba. of changing a conn.: 0.1 -proba. of adding/deleting a neuron: 0.025/0.025 -activation function for neurons: