NeuroEvolution of Augmenting Topologies (NEAT) and global innovation number

Question

I was not able to find why we should have a global innovation number for every new connection gene in NEAT.

From my little knowledge of NEAT, every innovation number corresponds directly with an node_in, node_out pair, so, why not only use this pair of ids instead of the innovation number? Which new information there is in this innovation number? chronology?

Update

Is it an algorithm optimization?

Answer 1

When I created my first implementation of NEAT I thought the same... why would you keep a innovation number tracker...? and why would you use it only for one generation? Wouldn't be better to not keep it at all and use a key value par with the nodes connected?

Now that I am implementing my third revision I can see what Kenneth Stanley tried to do with them and why he wanted to keep them only for one generation.

When a connection is created, it will start its optimization in that moment. It marks its origin. If the same connection pops out in another generation, that will start its optimization then. Generation numbers try to separate the ones which come from a common ancestor, so the ones that have been optimized for many generations are not put side to side that one that was just generated. If a same connection is found in two genomes, that means that that gene comes from the same origin and thus, can be aligned.

Imagine then that you have your generation champion. Some of their genes will have 50 percent chance to be lost due that the aligned genes are treated equally.

What is better...? I haven't seen any experiments comparing the two approaches.

Kenneth Stanley also addressed this issue in the NEAT users page: https://www.cs.ucf.edu/~kstanley/neat.html

Should a record of innovations be kept around forever, or only for the current generation?

In my implementation of NEAT, the record is only kept for a generation, but there is nothing wrong with keeping them around forever. In fact, it may work better. Here is the long explanation:

The reason I didn't keep the record around for the entire run in my implementation of NEAT was because I felt that calling something the same mutation that happened under completely different circumstances was not intuitive. That is, it is likely that several generations down the line, the "meaning" or contribution of the same connection relative to all the other connections in a network is different than it would have been if it had appeared generations ago. I used a single generation as a yardstick for this kind of situation, although that is admittedly ad hoc.

That said, functionally speaking, I don't think there is anything wrong with keeping innovations around forever. The main effect is to generate fewer species. Conversely, not keeping them around leads to more species..some of them representing the same thing but separated nonetheless. It is not currently clear which method produces better results under what circumstances.

Note that as species diverge, calling a connection that appeared in one species a different name than one that appeared earlier in another just increases the incompatibility of the species. This doesn't change things much since they were incompatible to begin with. On the other hand, if the same species adds a connection that it added in an earlier generation, that must mean some members of the species had not adopted that connection yet...so now it is likely that the first "version" of that connection that starts being helpful will win out, and the other will die away. The third case is where a connection has already been generally adopted by a species. In that case, there can be no mutation creating the same connection in that species since it is already taken. The main point is, you don't really expect too many truly similar structures with different markings to emerge, even with only keeping the record around for 1 generation.

Which way works best is a good question. If you have any interesting experimental results on this question, please let me know.

My third revision will allow both options. I will add more information to this answer when I have results about it.

Answer 2

During crossover, we have to consider two genomes that share a connection between the two same nodes in their personal neural networks. How do we detect this collision without iterating both genome's connection genes over and over again for each step of crossover? Easy: if both connections being examined during crossover share an innovation number, they are connecting the same two nodes because they received that connection from the same common ancestor.

Easy Example: If I am a genome with a specific connection gene with innovation number 'i', my children that take gene 'i' from me may eventually cross over with each other in 100 generations. We have to detect when these two evolved versions (alleles) of my gene 'i' are in collision to prevent taking both. Taking two of the same gene would cause the phenotype to probably loop and crash, killing the genotype.

Answer 3

Note: this more of an extended comment than an answer.

You encountered a problem I also just encountered whilst developing a NEAT version for javascript. The original paper published in ~2002 is very unclear.

The original paper contains the following:

Whenever a new gene appears (through structural mutation), a global innovation number is incremented and assigned to that gene. The innovation numbers thus represent a chronology of the appearance of every gene in the system. [..] ; innovation numbers are never changed. Thus, the historical origin of every gene in the system is known throughout evolution.

But the paper is very unclear about the following case, say we have two ; 'identical' (same structure) networks:

The networks above were initial networks; the networks have the same innovation ID, namely [0, 1]. So now the networks randomly mutate an extra connection.

Boom! By chance, they mutated to the same new structure. However, the connection ID's are completely different, namely [0, 2, 3] for parent1 and [0, 4, 5] for parent2 as the ID is globally counted.

But the NEAT algorithm fails to determine that these structures are the same. When one of the parents scores higher than the other, it's not a problem. But when the parents have the same fitness, we have a problem.

Because the paper states:

In composing the offspring, genes are randomly chosen from veither parent at matching genes, whereas all excess or disjoint genes are always included from the more fit parent, or if they are equally fit, from both parents.

So if the parents are equally fit, the offspring will have connections [0, 2, 3, 4, 5]. Which means that some nodes have double connections... Removing global innovation counters, and just assign id's by looking at node_in and node_out, you avoid this problem.

So when you have equally fit parents, yes you have optimized the algorithm. But this is almost never the case.

---

Quite interesting: in the newer version of the paper, they actually removed that bolded line! Older version here.

---

By the way, you can solve this problem by instead of assigning innovation ID's, assign ID based on node_in and node_out using pairing functions. This creates quite interesting neural networks when fitness is equal:

Answer 4

I can't provide a detailed answer, but the innovation number enables certain functionality within the NEAT model to be optimal (like calculating the species of a gene), as well as allowing crossover between the variable length genomes. Crossover is not necessary in NEAT, but it can be done, due to the innovation number.

I got all my answers from here:

http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf

It's a good read