Crossover operations, parental solutions

The crossover operation replaces some of the elements in each parent solution with those in the other. For example, in one-point crossover, with parents PI and P2 represented by real-valued vectors, and with the crossover point after the third component, the parents and offspring are as shown here for a five-variable problem ... 

Once mutation has been performed the fitter of parent and child is selected and the process repeats. There can, of course, be no possibility of applying a crossover operator when the complete population consists of just one solution, so mutation is the only genetic operator available. 

The crossover operation is the heart of the method. Technically, it is the simple exchange of parts of strings between pairs of solutions, but it has a large impact on the effectiveness of the search, since it allows exploration of regions of the search space not accessible to either of the two parent solutions. Through crossover operations, solutions can cooperate in the sense that favorable features... 

Specialized genetic operators here consist of multimode mutation and two different variants of crossover. The first crossover is a heuristic modification of the two-point crossover the second crossover operator seeks to combine the general characteristics of the parental individuals with the qualities of the best known solution. 

GP is suitable for evolving symbolic expressions in functional programming languages such as Lisp (a brief introduction to Lisp is available in Chapter 8). For example, the two parent solutions used to illustrate the crossover operator in Figure 7.24 could be written in Lisp as... 

The GA Phase it consists in appl dng a modified crossover operator on the set of optimal paths generated by the ACO algorithm after N iterations in order to improve the quality of solution found by the ants. The key idea of our proposed erossover operator consists in selecting two common nodes M and N1 from two parent paths PI and P2 and comparing the three sub-parts of PI and P2 existing (7) before Al, (2) between the two selected nodes A1 and 7V2, and (i) after the second node N2. The best parts are selected to form the new path. 

Fig. 2 Illustration of the most basic genetic crossover operations, i.e. single point (top line) and two point crossover. Horizontal bars represent parent (left) and children trial solution vectors.

When there are constraints, GAs face a fundamental difficulty, namely that many crossover or mutation operators rarely yield feasible offspring, even if the parents are feasible. This can lead to a population with an excessive number of infeasible solutions. To alleviate this problem, GAs often include a penalty function in/(see Section 8.4) to measure fitness. A value must be chosen for the penalty weight, however. If this is too small, the original problem of too many infeasible solutions remains, and if it is too large, the search tends to reject points with small infeasibilities, even if they are close to an optimal solution. 

---