What effect do crossover probabilities have in Genetic Algorithms/Genetic Programming?

Question

Can any one give an example of crossover probability? I would like to know what is the benefits of determining crossover probability, and also what effect it has in genetic algorithms or genetic programming.

Answer 1

Crossover probability doesn't have a benefit by definition. It is merely a parameter that allows you to adjust the behavior of a genetic algorithm. Lowering the crossover probability will let more individuals continue in the next generation unchanged. This may or may not have a positive effect when solving certain problems. I created a small experiment in HeuristicLab with a genetic algorithm applied to the TSP. The genetic algorithm was repeated 10 times for each probability on a small instance of the TSPLIB (bays29). As you can see in the image below, it is rather difficult to recognize a pattern. I also uploaded the algorithm and experiment, you can open and experiment with these files for yourself in HeuristicLab. The experiment includes a quality chart for each run and further analysis so you can check convergence behavior if you like.

It is also likely that the chosen strategy is too simple and thus failed to show an effect. In the experiment the parents that were not subject to crossover were also selected by fitness proportional selection. So a high quality individual would dominate the population very fast. A different strategy could be to select only the crossed parents by fitness-proportional selection and the remaining parents randomly. Results can be seen here (algorithm and experiment);

You can make your own modifications and experiment with the results.

A related answer can be found here: What is Crossover Probability & Mutation Probability in Genetic Algorithm or Genetic Programming?

Answer 2

I don't know exactly what you're asking. Crossover probability is just the probability of applying the crossover operator -- any real number in the range [0.0, 1.0] is an example.

There is no single best setting either. It depends on a large number of factors and complex interrelations with other settings in the algorithm. For instance, if you have a generational GA, you want there to be some probability that the parents can survive unmodified. Otherwise, you can lose good solutions. So you might set the crossover rate to something somewhat low like 0.7. On the other hand, an algorithm like CHC is very strongly elitist -- it always keeps the best solutions it has found, so there's more incentive to use crossover to search more broadly, and it therefore sets the probability to 1.0. Other algorithms depend entirely on mutation and set the crossover rate to 0.0. The most typical values for genetic algorithms are pretty high -- maybe 0.8 to 1.0. Genetic programming tends to use lower values quite often, maybe as low as 0.3 or 0.4.

But this is all sort of beside the point. You have to design an algorithm to support some goal. Figuring out how often to do crossover should be a decision you make because of some reason. If all you do is take an off-the-shelf genetic algorithm and dump some random parameters in there, it isn't likely to work all that well.