How to evolve weights of a neural network in Neuroevolution?

Question

I'm new to Artificial Neural Networks and NeuroEvolution algorithms in general. I'm trying to implement the algorithm called NEAT (NeuroEvolution of Augmented Topologies), but the description in original public paper missed the method of how to evolve the weights of a network, it says

Connection weights mutate as in any NE system, with each connection either perturbed or not at each generation

I've done some searching about how to mutate weights in NE systems, but can't find any detailed description, unfortunately.

I know that while training a neural network, usually the backpropagation algorithm is used to correct the weights, but it only works if you have a fixed topology (structure) through generations and you know the answer to the problem. In NeuroEvolution, you don't know the answer, you have only the fitness function, so it's not possible to use backpropagation here.

Geisel

Your tag, genetic-algorithm is one answer. Back-propagation isn't really GA. To have real GA you need to mimic some aspects of genetic evolution, namely inheriting from previous generations, with random mutations, and some kind of splicing/merging of genetics from multiple parents. – Clova

@Clova When doing connection-mutation or node-mutation, you actually assigning a random weight to a connection, so the only way to improve the weights is during crossovers? – Alford

When you mutate, you don't have to assign a completely random weight to a connection; you can just add a little noise to the existing weight. – Velleman

Answer 1

I have some experience with training a fixed-topology NN using a genetic algorithm (What the paper refers to as the "traditional NE approach"). There are several different mutation and reproduction operators we used for this and we selected those randomly.

Given two parents, our reproduction operators (could also call these crossover operators) included:

• Swap either single weights or all weights for a given neuron in the network. So for example, given two parents selected for reproduction either choose a particular weight in the network and swap the value (for our swaps we produced two offspring and then chose the one with the best fitness to survive in the next generation of the population), or choose a particular neuron in the network and swap all the weights for that neuron to produce two offspring.

• swap an entire layer's weights. So given parents A and B, choose a particular layer (the same layer in both) and swap all the weights between them to produce two offsping. This is a large move so we set it up so that this operation would be selected less often than the others. Also, this may not make sense if your network only has a few layers.

Our mutation operators operated on a single network and would select a random weight and either:

• completely replace it with a new random value
• change the weight by some percentage. (multiply the weight by some random number between 0 and 2 - practically speaking we would tend to constrain that a bit and multiply it by a random number between 0.5 and 1.5. This has the effect of scaling the weight so that it doesn't change as radically. You could also do this kind of operation by scaling all the weights of a particular neuron.
• add or subtract a random number between 0 and 1 to/from the weight.
• Change the sign of a weight.
• swap weights on a single neuron.

You can certainly get creative with mutation operators, you may discover something that works better for your particular problem.

IIRC, we would choose two parents from the population based on random proportional selection, then ran mutation operations on each of them and then ran these mutated parents through the reproduction operation and ran the two offspring through the fitness function to select the fittest one to go into the next generation population.

Of course, in your case since you're also evolving the topology some of these reproduction operations above won't make much sense because two selected parents could have completely different topologies. In NEAT (as I understand it) you can have connections between non-contiguous layers of the network, so for example you can have a layer 1 neuron feed another in layer 4, instead of feeding directly to layer 2. That makes swapping operations involving all the weights of a neuron more difficult - you could try to choose two neurons in the network that have the same number of weights, or just stick to swapping single weights in the network.

I know that while training a NE, usually the backpropagation algorithm is used to correct the weights

Actually, in NE backprop isn't used. It's the mutations performed by the GA that are training the network as an alternative to backprop. In our case backprop was problematic due to some "unorthodox" additions to the network which I won't go into. However, if backprop had been possible, I would have gone with that. The genetic approach to training NNs definitely seems to proceed much more slowly than backprop probably would have. Also, when using an evolutionary method for adjusting weights of the network, you start needing to tweak various parameters of the GA like crossover and mutation rates.

Hammons

In NEAT the synapses are a part of the genotype (in fact, it is the most important part) and they are swapped as a whole, i.e. including the source and target neuron as well as its weight. So there is no need for explicit weight-swapping operator. The original implementation of NEAT in C++ (by the author) has an option to use hebbian larning to optimize the weights a bit. – Boles

I did exactly this kind of GA with my Q-networks. Though I had quite large networks to train, so I decided to have Reinforced Learning (experience replay with backpropagation) with the GA. It works too. – Clishmaclaver

Answer 2

In NEAT, everything is done through the genetic operators. As you already know, the topology is evolved through crossover and mutation events.

The weights are evolved through mutation events. Like in any evolutionary algorithm, there is some probability that a weight is changed randomly (you can either generate a brand new number or you can e.g. add a normally distributed random number to the original weight).

Implementing NEAT might seem an easy task but there is a lot of small details that make it fairly complicated in the end. You might want to look at existing implementations and use one of them or at least be inspired by them. Everything important can be found at the NEAT Users Page.

Boles