The use of crossovers in Genetic Algorithm

If crossover is excluded from genetic algorithms, they become something between the gradient descent and the simulated annealing. The main effect of crossover consists in the exchange of parts of different solutions. If an optimization task can be loosely decomposed into somewhat independent subtasks, and this decomposition is reflected in genes, then crossover will increase performance of GAs. For example, if there is a function f(x,y)=g(x)+h(y), and x and y are encoded consequently in the genome, and e.g. g(x) has larger influence, then the part of genome that stands for x will be optimized in the first place, and it will become nearly the same for the whole population thanks to crossover. After this, h(y) term will be optimized. That is, crossover helps to loosely decompose the task into subtasks without prior knowledge (but dependent on the encoding scheme), if it is possible (otherwise it will yield no benefit, or even will make search less efficient). This is actually the main additional metaheuristic of GAs in comparison with other metaheuristic optimization methods.

Double-point crossover (or other more clutter types of crossover) can be more beneficial, if the most crucial parts of solutions are encoded in the middle of the genome or if they are placed in separate locations. The simplest example is the function f(x,y,z)=h(x,z)+r(y)+g(z), where h(x,z) has the highest influence, and genes encode the string xyz. Single-point crossover will prefer to take x from one parent, and z from another parent. However, (x,z) determine the solution quality together. If one individual will occasionally have optimal components (x*,z*), they will not appear simultaneously in its children after single-point crossover, so it will be more difficult for these parts of the genome to stabilize.

Solved by user21224 (231 )
Jan 28, 2014 at 13:14