2
$\begingroup$

I have been reading up on the NeuronEvolution of Augmented Topologies and there's this little thing that's been bothering me. While reading Kenneth Stanley's Paper on NEAT I came on this figure here:

NEAT mutation

The innovation numbers go from 1,2,3,4,5,6 to 1,2,3,4,5,6,7 on the first mutation.

On the second one it goes from 1,2,3,4,5,6 to 1,2,3,4,5,6,8,9.

My question is why does it skip number 7 and goes straight up to 8 instead? I didn't find anything related to deleting innovation numbers.

Same thing on this second figure, how did Parent 1 lose 6,7 and where did the 8th gene go to in Parent 2?

NEAT crossover

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Feb 1 '17 at 6:21
  • $\begingroup$ Considering Kenneth Stanley has a lot of his work online, why not just link to the paper you're talking about? $\endgroup$ – Apiwat Chantawibul Feb 1 '17 at 17:53
  • 1
    $\begingroup$ Not letting me, I need 10 or more rep tu post more than 2 links. Paper can be found here though: nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf Thanks for pointing this out. $\endgroup$ – Rikku121 Feb 1 '17 at 18:17
2
$\begingroup$

Here is what I gathered from skimming the paper for just the figure.

Your first figure, which is the figure 3 in the paper, already has the answer in its caption:

Figure 3: The two types of structural mutation in NEAT. Both types, adding a connection and adding a node, are illustrated with the connection genes of a network shown above their phenotypes. The top number in each genome is the innovation number of that gene. The innovation numbers are historical markers that identify the original historical ancestor of each gene. New genes are assigned new increasingly higher numbers. In adding a connection, a single new connection gene is added to the end of the genome and given the next available innovation number. In adding a new node, the connection gene being split is disabled, and two new connection genes are added to the end the genome. The new node is between the two new connections. A new node gene (not depicted) representing this new node is added to the genome as well.

In figure 3, it could be deduced that the add connection mutation (top half) occur preceding the add node mutation (buttom half).

  • When the add connection mutation occurred, the lowest free innovation number was 7. And so the gene created at that moment was assigned the marker of 7.
  • Later, when the add node mutation occurred, 2 new genes were created. And so they were assign the lowest free innovation number at the time which is 8 and 9.

The innovation number is not the indices of each gene inside the array representing a genome.

The innovation number is just a number permanently branded to each gene, telling us when the gene first occur. As if the year number when human first evolved a gene for hairless body were written down on the gene itself.

The uses of innovation is then explained around your latter figure, which is figure 4:

The historical markings give NEAT a powerful new capability. The system now knows exactly which genes match up with which (Figure 4). When crossing over, the genes in both genomes with the same innovation numbers are lined up. [...] This way, historical markings allow NEAT to perform crossover using linear genomes with out the need for expensive topological analysis.

From this I assumed that innovation number are always ordered increasingly within a genome, but gaps in innovation numbers are allowed to occur within genome. The order is probably ensured simply by the fact that all operations done on genome was designed to not violate this within-genome ordering.

This makes sense because each gene can be thought of as an instruction to construct a graph. By keeping the instruction ordered by when it was introduced, it makes sure that reading instruction on genome from left to right makes sense chronologically.

$\endgroup$
  • 1
    $\begingroup$ I now understand that I need to use some sort of database to keep track of each mutation taking into account both the innovation number and it's in neuron and out neuron. So if the same mutation where to happen on some other genome it will be assigned that same innovation number instead of getting the next one in line. $\endgroup$ – Rikku121 Feb 3 '17 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.