NeuroEvolution: NEAT algorithm innovation numbers

Question

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:

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?

Answer 1

An innovation number (I'll use IN for short) is kind of a label of a specific piece of structure. So a connection from a neuron number 1 to neuron number 2 would have an IN e.g. 1 and all networks with that connection would have this connection labeled as IN 1. When a new connection is created (either by add connection mutation or by add node mutation), it is first checked whether there is such connection in a "database" of INs. If there already is such connection, its IN is used. If it is not, an IN counter is increased, the new connection gets this new IN and is stored in the database.

In the first figure in the upper part, a new connection is added from neuron 3 to neuron 5. If this is the first ever such connection that appeared in the whole population, you increase the IN counter and use this new IN for that connection. If it has already happened elsewhere, you use its IN instead of creating a new one. It could be either of those cases, we don't know how the rest of the population looks like. It just happens that connection 3->5 has IN 7.

Now, in the bottom part of the first figure, you add a neuron 6 between neurons 3 and 4, which means that you add connections 3->6 and 6->4. Again, you first ask "Is there an IN for connection 3->6 in the database?" If it is you use that IN, if not you increase the counter. The same goes for the other connection. In that figure, you can imagine that all these new connections were new ones, so in the upper part the IN counter was at 6 and with the new connection, that was not encountered yet, you increased the IN counter and assigned 7 to the connection. Then the bottom part happened, with two brand new connections, so you increase the IN counter to 8 and 9. In the bottom part, there is no connection 3->5 which has IN 7, so that's the reason the IN 7 is not there.

Regarding the second figure, it's just an example to show how the crossover works when there are disjoint INs. The parents just are this way, for the sake of the example. However, they could have gotten to this state quite easily. Imagine that parent 1, in some earlier point of time of the evolution, had just the INs 1 to 5 and 5 was the newest IN so far. Then, somewhere else in the population, a new neuron (No. 6) between neurons 5 and 4 was added, i.e. new connections 5->6 and 6->4 were created. Since such connections were not encountered yet, the IN counter was increased to 6 and 7. Then, after this, parent 1 was mutated by adding new connection 1->8. Since this was also new, new IN 8 was assigned.