Different ways to produce the same network in NEAT

Question

I have an interesting example for the NEAT and want to clarify what behavior is correct from NEAT's perspective and why (why the opposite is wrong, what are the consequences of choosing the different one).

So let we have an initial network of 3 nodes and 2 edges:

Initial Condition

Nodes: [A, B, C]
Edges: {
1: A->B
2: B->C
}

---

1st Gen

Then in the 1-st generation we get 2 mutants:

Mutant 1 (edge 1 got split)

Nodes: [A, B, C, D]
Edges: {
1: A->B DIS
2: B->C
3: A->D
4: D->B
}

Mutant 2 (edge 2 got split)

Nodes: [A, B, C, E]
Edges: {
1: A->B
2: B->C DIS
5: B->E
6: E->C
}

---

2nd Gen

In the second generation 2 if we mutate Mutant 1 (by splitting edge 2) and mutate Mutant 2 (by splitting edge 1) which result should we get?

Hypothesis 1: the same result:

Nodes: [A, B, C, D, E]
Edges: {
1: A->B DIS
2: B->C DIS
3: A->D
4: D->B
5: B->E
6: E->C
}

or...

Hypothesis 2: Two new mutants:

Nodes: [A, B, C, D, F]
Edges: {
1: A->B DIS
2: B->C DIS
3: A->D
4: D->B
7: B->F
8: F->C
}

and

Nodes: [A, B, C, E, G]
Edges: {
1: A->B DIS
2: B->C DIS
5: B->E
6: E->C
9: A->G
10: G->B
}

---

In case the second hypothesis is correct, how does it deal with crossover in the next run? Say these 2 mutants are breeded. We get :

Breeding in 2nd Hypothesis

Nodes: [A, B, C, D, E, F, G]
Edges: {
1: A->B DIS
2: B->C DIS
3: A->D
4: D->B
5: B->E
6: E->C
7: B->F
8: F->C
9: A->G
10: G->B
}

Looks like a too complicated genome for the 3-rd generation, doesn't it?

In case the first option is correct then actually innovation numbers are somewhat redundant in NEAT and can be done differently. We can have node list as a list of strings (node names). Then instead of assigning the innovation number to an edge we can use string value calculated like HASH(fromNodeName + toNodeName). That way whenever the new link is created in any generation between 2 nodes it gets the same innovation number name for it. When the node is created (by splitting an edge) its name can be taken right from the edge getting split and the innovation names of 2 new edges can be calculated like HASH(fromNodeName + splitEdgeName) and HASH(splitEdgeName + toNodeName). That way the algorithm has no global variables, no shared list of all innovations and can be simply parallelized

Answer 1

So let's first draw the network in each case, for better visualizing the problem:

Initial:
┌─┐
│A│
└┬┘
┌▽┐
│B│
└┬┘
┌▽┐
│C│
└─┘

1st Generation:

1st Gen
Mutation #1   Mutation #2
┌────┐        ┌────┐
│A   │        │A   │
└┬──┬┘        └┬───┘
┌▽┐ ┆         ┌▽───┐
│D│ ┆DIS      │B   │
└┬┘ ┆         └┬──┬┘
┌▽───┐        ┌▽┐ ┆
│ B  │        │E│ ┆DIS
└┬───┘        └┬┘ ┆
┌▽───┐        ┌▽───┐
│ C  │        │ C  │
└────┘        └────┘

2nd Generation

1st Hypothesis (Same Result)
┌────┐
│A   │
└┬──┬┘
 ┆ ┌▽┐
DIS│D│
 ┆ └┬┘
┌───▽┐
│B   │
└┬──┬┘
 ┆ ┌▽┐
DIS│E│
 ┆ └┬┘
┌───▽┐
│C   │
└────┘

In order to converge the 2 mutations like this, we would need to:

• Somehow make topology accessible globally.
• Make one mutation search for the population, looking for an occurrence of a similar split.

Both items go against the principle of evolution, as only 2 mating individuals should trade genetic information.

2nd Hypothesis (Two Mutants)
┌────┐   ┌────┐
│A   │   │A   │
└┬──┬┘   └┬──┬┘
 ┆ ┌▽┐    ┆ ┌▽┐
DIS│D│   DIS│G│
 ┆ └┬┘    ┆ └┬┘
┌───▽┐   ┌───▽┐
│B   │   │B   │
└┬──┬┘   └┬──┬┘
 ┆ ┌▽┐    ┆ ┌▽┐
DIS│F│   DIS│E│
 ┆ └┬┘    ┆ └┬┘
┌───▽┐   ┌───▽┐
│C   │   │C   │
└────┘   └────┘

Yes. This 2nd approach is the most usual. Each mutation generates a completely new gene.

┌────┐
│A   │
└┬──┬┘
┌▽┐┌▽┐
│8││D│
└─┘└┬┘
┌───▽┐
│B   │
└┬──┬┘
┌▽┐┌▽┐
│u││F│
└─┘└┬┘
┌───▽┐
│C   │
└────┘

---

Looks like a too complicated genome for the 3-rd generation, doesn't it?

And yes. A 3rd generation could theoretically come up like this complicated genome.[1]

┌───────┐
│A      │
└┬──┬──┬┘
┌▽┐┌▽┐ ┆
│G││D│DIS
└┬┘└┬┘ ┆ 
┌▽──▽───┐
│B      │
└┬──┬──┬┘
┌▽┐┌▽┐ ┆ 
│F││E│DIS
└┬┘└┬┘ ┆
┌▽──▽───┐   
│C      │   
└───────┘   

But keep in mind that more complex structures are naturally harder to train and therefore will not survive if the performance does not justify the complexity.

[1] - Usually disjoint genes and excess genes (those that do not match) are chosen from the fittest parent. However, in (very specific) cases where 2 parents have the same fit, it could be chosen randomly.

Main source: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.28.5457&rep=rep1&type=pdf

---

In the end, you propose an interesting method, to use hashes instead of integers for identifying genes. This is a bold suggestion, and I'm not an expert, so this part is mostly opinionated:

I believe original genes numeration idea is:

• Inspired on the natural genes sequencing
• For assuring uniqueness genes identifications
• And tracking history changes, just like Git.

But it could also work using a hash.

On one side, that could be a great feature, for allowing distant relatives to breed with consistency. On the other side, distant relatives tend to have a very different structure and the gene might not be so relevant to them.

I encourage you to test it. And if it works better than the vanilla, you should release a paper!