Hot questions for Using Neural networks in crossover

Question:

I am currently implementing the NEAT algorithm developed by Kenneth Stanley, taking the original paper as a reference.

In the section where the crossover method is described, one thing confuses me a little bit.

So, the above figure is illustrating the crossover method for NEAT. To decide from which parent a gene inherited, the paper says the following:

Matching genes are inherited randomly, whereas disjoint genes (those that do not match in the middle) and excess genes (those that do not match in the end) are inherited from the more fit parent.

For the matching genes (1 - 5) it's easy to understand. You just randomly inherit from either Parent1 or Parent2 (with 50% chance for both). But for the disjoint (6-8) and excess (9-10) genes you cannot inherit from the more fit parent because you only have those genes in either Parent1 or Parent2.

For example:

Parent1's fitness is higher than Parent2's. The disjoint gene 6 only exists in Parent2 (of course, because disjoint and excess genes only occur in one parent) So, you cannot decide to inherit this gene from the more fit parent. Same goes for all other disjoint and excess genes. You can only inherit those from the parent they exist in.

So my question is: Do you maybe inherit all matching genes from the more fit parent and just take over the disjoint and excess genes? Or do i missunderstand something here?

Thanks in advance.


Answer:

It might help to look at the actual implementation and see how it is handled. In the original C++ code here (look at lines 2085 onwards), the disjoint and excess genes from the unfit parent seem to be just skipped.

In your implementation, you could inherit disjoint and excess genes from the unfit parent but disable them with probability 1 so you can do pointwise mutations on them (toggle disabled to enabled) later on. However, this might result in significant genome bloat, so test and see what works.

Question:

I wrote a neural network and made a small application with things eating other things.

But I don't really know, how to make the thing genetic.

Currently I'm recording all the inputs and outputs from every individual every frame.

At the end of an generation, I then teach every knew individual the data from the top 10 best fitting individuals from prevous generations.

But the problem is, that the recorded data from a a pool of top 10 individuals at 100 generations, is about 50MB large. When I now start a new generation with 20 individuals I have to teach them 20x50MB. This process takes longer than 3 minutes, and I am not sure if this is what I am supposed to do in genetic neural networks. My approach works kind of good actually. Only the inefficiency bugs me. (Of course I know, I could just reduce the population.)

And I could't find me a solution to what I have to crossover and what to mutate. Crossovering and mutating biases and weights is nonsense, isn't it? It only would break the network, would't it? I saw examples doing just this. Mutating the weight vector. But I just can't see, how this would make the network progress reaching it's desired outputs.

Can somebody show me how the network would become better at what it is doing by randomly switching and mutating weights and connections? Would't it be the same, just randomly generating networks and hoping they start doing what they are supposed to do?

Are there other algorithms for genetic neural networks?

Thank you.


Answer:

Typically, genetic algorithms for neural networks are used as an alternative to training with back-propagation. So there is no training phase (trying to combine various kinds of supervised training with evolution is an interesting idea, but isn't done commonly enough for there to be any standard methods that I know of).

In this context, crossover and mutation of weights and biases makes sense. It provides variation in the population. A lot of the resulting neural networks (especially early on) won't do much of anything interesting, but some will be better. As you keep selecting these better networks, you will continue to get better offspring. Eventually (assuming your task is reasonable and such) you'll have neural networks that are really good at what you want them to do. This is substantially better than random search, because evolution will explore the search space of potential neural networks in a much more intelligent manner.

So yes, just about any genetic neural network algorithm will involve mutating the weights, and perhaps crossing them over as well. Some, such as NEAT, also evolve the topology of the neural network and so allow mutations and crossovers that add or remove nodes and connections between nodes.

Question:

Why specifically is it used?

I know it increases variation which may help explore the problem space, but how much does it increase the probability of finding the optimal solution/configuration in time? And does it do anything else advantageous?

And does it necessarily always help, or are there instances in which it would increase the time taken to find the optimal solution?


Answer:

As Patrick Trentin said, crossover improve the speed of convergence, because it allows to combine good genes that are already found in the population.

But, for neuro-evolution, crossover is facing the "permutation problem", also known as "the competing convention problem". When two parents are permutations of the same network, then, except in rare cases, their offspring will always have a lower fitness. Because the same part of the network is copied in two different locations, and so the offspring is losing viable genes for one of these two locations.

for example the networks A,B,C,D and D,C,B,A that are permutations of the same network. The offspring can be:

A,B,C,D (copy of parent 1)           
D,C,B,A (copy of parent 2)

A,C,B,D OK
A,B,C,A
A,B,B,A 
A,B,B,D
A,C,B,A
A,C,C,A
A,C,C,D

D,B,C,A OK
D,C,B,D
D,B,B,A 
D,B,B,D
D,B,C,D
D,C,C,A
D,C,C,D

So, for this example, 2/16 of the offspring are copies of the parents. 2/16 are combinations without duplicates. And 12/16 have duplicated genes.

The permutation problem occurs because networks that are permutations one of the other have the same fitness. So, even for an elitist GA, if one is selected as parent, the other will also often be selected as parent.

The permutations may be only partial. In this case, the result is better than for complete permutations, but the offspring will, in a lot of cases, still have a lower fitness than the parents.

To avoid the permutation problem, I heard about similarity based crossover, that compute similarity of neurons and their connected synapses, doing the crossing-over between the most similar neurons instead of a crossing-over based on the locus.

When evolving topology of the networks, some NEAT specialists think the permutation problem is part of a broader problem: "the variable lenght genome problem". And NEAT seems to avoid this problem by speciation of the networks, when two networks are too differents in topology and weights, they aren't allowed to mate. So, NEAT algorithm seems to consider permuted networks as too different, and doesn't allow them to mate.

A website about NEAT also says:

However, in another sense, one could say that the variable length genome problem can never be "solved" because it is inherent in any system that generates different constructions that solve the same problem. For example, both a bird and a bat represent solutions to the problem of flight, yet they are not compatible since they are different conventions of doing the same thing. The same situation can happen in NEAT, where very different structures might arise that do the same thing. Of course, such structures will not mate, avoiding the serious consequence of damaged offspring. Still, it can be said that since disparate representations can exist simultaneously, incompatible genomes are still present and therefore the problem is not "solved." Ultimately, it is subjective whether or not the problem has been solved. It depends on what you would consider a solution. However, it is at least correct to say, "the problem of variable length genomes is avoided."

Edit: To answer your comment.

You may be right for similarity based crossover, I'm not sure it totally avoids the permutation problem.

About the ultimate goal of crossover, without considering the permutation problem, I'm not sure it is useful for the evolution of neural networks, but my thought is: if we divide a neural network in several parts, each part contributes to the fitness, so two networks with a high fitness may have different good parts. And combining these parts should create an even better network. Some offspring will of course inherit the bad parts, but some other offspring will inherit the good parts.

Like Ray suggested, it could be useful to experiment the evolution of neural networks with and without crossover. As there is randomness in the evolution, the problem is to run a large number of tests, to compute the average evolution speed.

About evolving something else than a neural network, I found a paper that says an algorithm using crossover outperforms a mutation-only algorithm for solving the all-pairs shortest path problem (APSP).

Edit 2:

Even if the permutation problem seems to be only applicable to some particular problems like neuro-evolution, I don't think we can say the same about crossover, because maybe we are missing something about the problems that don't seem to be suitable for crossover.

I found a free version of the paper about similarity based crossover for neuro-evolution, and it shows that:

  • an algorithm using a naive crossover performs worse than a mutation-only algorithm.

  • using similarity based crossover it performs better than a mutation-only algorithm for all tested cases.

  • NEAT algorithm sometimes performs better than a mutation-only algorithm.

Crossover is complex and I think there is a lack of studies that compare it with mutation-only algorithms, maybe because its usefulness highly depends:

  • of its engineering, in function of particular problems like the permutation problem. So of the type of crossover we use (similarity based, single point, uniform, edge recombination, etc...).

  • And of the mating algorithm. For example, this paper shows that a gendered genetic algorithm strongly outperforms a non-gendered genetic algorithm for solving the TSP. For solving two other problems, the algorithm doesn't strongly outperforms, but it is better than the non-gendered GA. In this experiment, males are selected on their fitness, and females are selected on their ability to produce a good offspring. Unfortunately, this study doesn't compare the results with a mutation-only algorithm.

Question:

I'm trying to implement the NEAT Algorithm using c#, based off of Kenneth O. Stanley's paper. On page 109 (12 in the pdf) it states "Matching genes are inherited randomly, whereas disjoint genes (those that do not match in the middle) and excess genes (those that do not match in the end) are inherited from the more fit parent." Does this mean that the child will always have the exact structure that the more fit parent has? It seems like the only way the structure could differ from crossover was if the two parents were equally fit.


Answer:

If by "structure' you mean the sequence of genes then yes, that's correct, the child will start with the same sequence of genes as its more-fit parent. The sequence in the child can be different from both of its parents' structures only if both parents are equally fit.

Even though the initial sequence of genes in the child is the same as the more-fit parent, the attributes (weight, enablement) within those genes won't necessarily be identical to the attributes in the more-fit parent. Matched genes (those with the same "innovation number" in the parents) can be taken into the child from the either parent, and the attributes of a matched gene in the less-fit parent might not be identical to the attributes of that gene in the more-fit parent.