NEAT | Devpost

Poster

Original proposal:

Re-implementing NEAT

Who?

Theodore Akpinar (takpinar)

Chris Mascioli (cmasciol)

Joshua Tan (jtan31)

Introduction

The paper "Evolving Neural Networks through Augmenting Topologies" aims to propose a method, NeuroEvolution of Augmenting Topologies (NEAT), that is able to gain an advantage over other NeuroEvolution strategies by evolving its network topology along with the weights. This is in contrast to traditional NeuroEvolution approaches where the topology is chosen and fixed before the experiment begins. There has been much academic discussion around the effectiveness of evolving topologies. One such argument supporting the evolution of both topology and weights was put forward by Gruau et al. (1996), where a method that solved a pole-balancing benchmark problem was provided. However, it was later shown that the structure was not necessary and a fixed-topology method that convincingly outclassed this method was subsequently released. With the inconclusive nature of these results, the paper aims to demonstrate that evolving topologies and weights can significantly enhance the performance of a NeuralEvolution approach. According to the paper, such performance enhancements are achieved because of several key factors. The first of which is using crossover to combine different topologies. Next, structural innovation is protected using speciation, and lastly, the topologies are only grown incrementally and minimized throughout the entire evolution process. \

In addition, considering a method that uses evolving topologies also raises several concerns. For example, how do we crossover topologies that are significantly different from each other and how do we prevent the premature termination of potentially successful topologies? The paper also presents solutions to these concerns. \

We chose this paper as all of our group members found the concept of applying evolutionary strategies to deep learning interesting. We were intrigued by the idea of solving computer science problems using an interdisciplinary approach that draws inspiration from the natural world. Additionally, we were very impressed by past implementations of this method. \

Lastly, this approach is best suited to solve reinforcement learning problems.

Public Implementations

MarI/O - https://www.youtube.com/watch?v=qv6UVOQ0F44 NEAT-Python library - https://neat-python.readthedocs.io/en/latest/

Data

We will be generating our own data through the simulation of the games the NEAT agents will play

Methodology

The NEAT algorithm is a combination of evolutionary strategies and neural networks. The algorithm maintains a population $n=150$ of NNs that it is constantly evaluating and evolving to find more fit networks for the chosen task. In this section, we will go over each component of the NEAT algorithm

Genes

Each gene represents a connection inside the neural network. The components of each gene are: The node the connection starts at. The node the connection ends at. The weight of the connection. Whether the connection is active. The connection's innovation number.

Individuals

A set of genes form the genotype of each individual. In addition to the genes, each individual also has a fitness (their performance on the target task) and the generation in which they were created (for tracking purposes). Each individual's genotype can be mapped to a neural network (its phenotype) which is used in order to find its aforementioned fitness.

Mutation

After each generation is assessed, the individuals are mutated for the next generation in three ways Weight perturbation: Each connection has $\mathcal{U}$-distributed random noise added to its weight. New connection: The individual has a new connection formed between two nodes that were not previously connected New nodes: The individual has a new node added to it by deactivating one of its current connections and inserting a new node between where the old connection was.

Each of the latter two mutations has an innovation number, which is a number tracking when that particular connection was created (it's a global variable that starts at 0 and is incremented each time a new connection is formed).

Crossover

In addition to mutation, each individual can also be crossovered (or bred with) other individuals. In crossover, the genes of each individual are either shared (in both individuals), excess (present in one individual but not in the other and at the end of the genome), or disjoint (present in one individual but not in the other and in the middle of the genome). Any shared genes are preserved with a weight selected at random from either parent while all excess and disjoint genes from the parent with the higher fitness value are preserved as is.

Species

In order to preserve novel features, each individual is only compared against members of its own species. In NEAT, species are groups of "similar" individuals where the similarity is based on how close together two individual's genotypes are. In order to define species, we set a parameter $\delta_t$, and then say individuals are different species when $\delta . \delta_t$ according to: \begin{gather*} \delta = \frac{c_1E}{N} + \frac{c_2D}{N} + c_3 \bar{W}\ \intertext{where} \begin{aligned} &E - \text{The number of excess genes}\ &D - \text{The number of disjoint genes}\ &\bar{W} - \text{The average difference between weights}\ \end{aligned}\notag \end{gather*}

Fitness

In order to find the fitness of each individual, its genotype (list of genes/nodes) is converted to a phenotype (neural network) and then evaluated on the target task based on a fitness function that returns one number indicating overall fitness (for example, in flappy-bird this would be total points). The fitness for each individual in NEAT is found through explicit fitness sharing

\begin{gather*} f_i'=\cfrac{f_i}{\sum\limits_{j=1}^n\mathrm{sh}(\delta(i, j))} \intertext{where} \mathrm{sh}(x) = \begin{cases} 0 & x > \delta_t \ 1 & x \leq \delta_t \end{cases} \end{gather*}

Algorithm

NEAT begins by initializing each member of the population with the smallest network, where each input is connected directly to each output with a random weight, and then finds the fitness of each network created. We then, until we reach our desired fitness or some preset time limit, go through the following:

Select the best performing (champion) member of each species and carry it over to the next generation.
To create the rest of the population, select an individual at random and perform mutation/crossover on it to create a member of the next generation. Find its fitness.

Once this process is complete, we return the most fit individual.

Metrics

Our metric will be our fitness function. For flappy-bird, this will just be the number of points.

Ethics

How are you planning to quantify or measure error or success?

The performance of Genetic Algorithms like NEAT strongly hinges on the fitness function used in the evolution of species. The fitness function quantifies the performance of each topology, which is used to decide which species will 'evolve' and move on to the next generation. Since this is the core 'learning' mechanism, the behavior of the algorithm is largely influenced by whatever fitness function we choose to use.

In our case, the fitness function will simply be the score of each topology on the game we have it play. For example, in a game like flappy-bird, fitness can be quantified in the number of seconds the network can play for without losing. When learning a simple video game, the fitness function will often be obvious and innocuous. However, the ethical implications of fitness functions increase as the problems that genetic algorithms solve become more complex.

If Neuroevolution were applied to something like software engineering, it would be harder to articulate a good fitness function. A neural network that writes good software would probably need be judged on multiple criteria, such as code functionality, readability, elegance, etc. - which can be hard to precisely encapsulate in a single fitness function. So, when we have loftier goals for our artificial agents, it is very important that we precisely specify the fitness function. For example, if the software engineer networks were judged solely on code functionality, the fittest topologies might produce code that is very opaque, which would be a problem if a human needed to debug it or tweak it somehow. So, while choosing the fitness function for a simple game can be straightforward, it is important to recognize the vital importance that this function plays when applying Neuroevolution to more complex problems.

Division of Labor

There are 7 base functions, we are each implementing two individually and the largest part together.

Function that does breeding: Chris
Function that mutates: Theo
Function that finds species: Josh
Function that converts genome to network: Together
Initialization and fitness: TBD
Runs simulation: TBD
Visualizer: TBD