Using GP is NEAT: Evolving Compositional Pattern Production Functions

One of the goals of NeuroEvolution (NE) is the automatisation of learning in Artificial Neural Networks (ANNs). To that end, NE applies Evolutionary Computation (EC) to search and tune the best solutions for the values of the weights of ANNs. On this work we focus on approaches that aim at evolving learning rules, based on the premise that the network’s weights follow some pattern that can be learned.

HyperNEAT is based on the use of NEAT to evolve Compositional Pattern Production Network (CPPNs), which are structurally similar to ANNs, and are used as a means to encode the weights of a network. At a high level, CPPNs are a function that, given the position of two neurons, outputs the synaptic weight of the connection between them. As such, and since a CPPN can be seen as a function mapping the coordinates of a pair of nodes into a weight, instead of evolving CPPNs one can use conventional EC techniques, such as GP, to evolve functions to the same task. Such functions are known as Compositional Pattern Production Functions.

In the current work we apply different methods to the optimisation of CPPFs: NEAT, GP, GE, and DSGE. We test these approaches in two different problems: a visual discrimination, and a line following task. The results show that GP consistently obtains the best results.

Generation of CPPFs

CPPFs are functions with 4 inputs: x1, y1, x2, y2, which similarly to HyperNEAT, are the positions of the neurons in the substrate. The substrate is the ANN that is used to solve the problem at hand. It is a grid of neurons, with a fixed number of inputs and outputs that varies according to the problem to be solved. To know the weights of the connections between the neurons in the substrate we need to query the evolved CPPF; if it returns a value above a defined threshold then the connection between the input neurons ((x1, y1) and (x2, y2)) exists and the synaptic weight is the one returned by the CPPF; conversely, if the value is bellow the threshold, the connection does not exist.

Figure 1 depicts the interaction between evolution, the generated CPPFs and the substrate. Four different approaches are tested: NEAT, GP, GE, and DSGE.

Experiments

The experiments are conducted in two different tasks: (i) visual discrimination; and (ii) line following. The objectiv of the visual discrimination task is to distinguish between two different objects – a target and a distractor – independently of their positions in a field. In the line following task the goal is to evolve the controllers of an agent so that it can effectively navigate a road, i.e., follow a line at maximum speed.

We perform 30 independent evolutionary runs with each evolutionary engine (NEAT, GP, GE, and SGE).

Visual Discrimination

Figure 2 depicts the evolution of fitness across generations on two configurations of the visual discrimination problem. The results are averages of the 30 best solutions across generations. These charts show that with any of the evolutionary engines evolution is promoted and there is convergence. The difference in the setups complexity is noticeable by the analysis of the difference in the fitness scales: in both setups the average fitness of the best solutions starts approximately from the same point, but in the big-little setup it is capable of reaching much lower values than in the triup-down setup. Having the target and distractor shapes with the same size but mirrored makes the problem too challenging for an appropriate function capable of encoding the weights of the substrate to be found in the given number of generations.

Nonetheless, for both setups, in terms of fitness, the results reported by NEAT and GP are superior to those of the grammar-based methods. To better analyse the quality of the generated solutions we use box plots, focusing on the distribution of the quality of the best individuals from each evolutionary run (see Figure 3). It is possible to conclude that GE has the worse performance. Focusing on each of the setups individually, in the case of the big-little setup NEAT and GP have a close median, with GP having a slightly superior dispersion. For the triup-down setup NEAT and GP also have roughly the same median, but the dispersion is lower in GP. GP has more outliers, but these outliers correspond to runs that achieve better solutions. Looking at the DSGE performance, in the big-little setup it performs worse than NEAT or GP, and in the triup-down setup it has a similar performance, but larger dispersion.

Line Following

Contrary to the visual discrimination task, the goal of the line following task is the maximisation of the average speed of a robot in a road navigation task, i.e., maximise the distance travelled in a fixed amount of time. We start by analysing the evolution of fitness across generations (see Figure 4). GE is the approach that takes the largest number of generations to converge, reaching the lowest results. Conversely, NEAT, GP, and DSGE are the methods that generate the best solutions, with GP outperforming the other two in the easy and hard setups.

The box plots allow stronger conclusions than before (see Figure 5); while in the visual discrimination task NEAT or GP were not superior in the two setups, in the line following task it is perceptible that GP performs better than the remaining approaches in the easy and hard setups, i.e., despite having a few outliers GP has a median that is higher than those of the remaining approaches, and the interquartile range is smaller, meaning that the results are more consistent.

In Proceedings

• F. Assunçao, N. Lourenço, P. Machado, and B. Ribeiro, “Using GP is NEAT: Evolving Compositional Pattern Production Functions,” in European Conference on Genetic Programming (EuroGP), 2018.

  • Bibtex
  @inproceedings{assuncao2018using,
  author = {Assun{\c{c}}ao, Filipe and Louren{\c{c}}o, Nuno and Machado, Penousal and Ribeiro, Bernardete},
  booktitle = {European Conference on Genetic Programming (EuroGP)},
  organization = {Springer},
  title = {Using GP is NEAT: Evolving Compositional Pattern Production Functions},
  year = {2018}}
  • |
  • PDF