I'm not entirely familiar with all the terminology, so please excuse any errors on that part. I decided to write a program that uses an evolutionary (?) algorithm to go from a random string of characters to a target string.
It works fine, but I noticed something that I don't understand. If I use 'asexual' reproduction, i.e. each string clones itself and then mutates with some probability, the convergence to the solution is much slower, and sometimes doesn't converge at all, but gets trapped, at say an average fitness of ~0.8. This doesn't make sense to me, since the mutation should make it trend towards the optimum, right?
However, if I instead use crossover, e.g. I pick two parents and do a uniform mix of characters and then like normal mutate the child with some probability the convergence is not only practically guaranteed, it is also orders of magnitude faster. I don't think this can explained solely by the fact that the child gets to "mutate more" since both its parents are also mutated in the previous generation.
Could someone please explain the role of crossover, and why it allows for much faster convergence in algorithms such as these?
The role of crossover in genetic algorithms is to spread the beneficial mutations of population members that let them achieve a high fitness value to more members of the population.
The key is that only the fit members of the population crossover with each other and thereby spread beneficial mutations to more members of the population with the intent that the offespring (/new members) might also benefit from the mutation of the parent. Thereby crossover leads to a spreading of mutations that lead to a higher fitness value spread throughout the population - leading to your observed faster convergence.
Take for example a neural network that plays a jump and run video game and is optimized with a genetic algorithm. One member might have received a high fitness score through a mutation that makes him jump over obstacles. Another member might have received a high fitness score through a mutation that makes him collect lifes on the map. Crossing over fit parent members spreads the beneficial mutations faster than if the rest of the population would need to learn these fitness increasing mutations itself by chance.