A Versatile Genetic Algorithm System in Ada: Implementation and Applications
Max Edwards
While experimenting with the Travelling Salesperson Problem using the graphical fitness-history display facility, it was quickly realised that the commonly used Partially Matched Crossover method for permutation chromosomes, as described by in Davis 1985 (and Goldberg 1989, p170), appears to give very poor performance in most cases. This in spite of the success which other researchers claim to have had with it (Goldberg 1989 p172). A possible reason may be that the method seems to create children bearing insufficient resemblance to either parent, serving on the most part to return an almost completely random-looking pair of children if the parents are even slightly different.
The reaction to this discovery was to implement two other reordering crossover operators, ORDER and CYCLE (both also described in Goldberg 1989, p170 et. seq.), as well as an experimental, slightly modified version of the basic PMX algorithm, in which one of the parents is first shifted until its first allele is the same as that of the other parent. It was hoped that by doing this the children produced would be more like their parents, but it was subsequently concluded that no discernible improvement was achieved, and by far the most effective permutation crossover method encountered was found to be the ORDER algorithm; these conclusions were initially drawn after a basic comparison of the fitness-history plots and final fitness values of simple TSP GA's using each of the four crossover operators involved. The choice of the ORDER method as best crossover operator was later confirmed by runs of the Meta-level TSP-parameter set optimisation GA, which favoured it on eight out of the nine meta-runs performed (see results in next chapter).
The problems associated with performing crossover (or "recombination") between permutation strings are widely documented, and there is potential for experimentation with many more suggested methods. For example, Darrell Whitley (in Whitley 1989a) presents an "edge-based recombination operator", which he claims gives offspring consisting of 95-99% of the parents' edges (pairs of numbers). The implementation and testing of this operator would be a very useful addition to the VAGAS system.
Regarding crossover in general, there are a number of possible alterations to the basic method, and one which could easily be implemented in VAGAS is "clone reduction" (Davis 1987 p69), whereby if a child chromosome is a clone of one of its parents it is thrown away and a new one generated. This would prevent convergence in populations which have an unhealthily high number of similar possibly sub-optimal chromosomes.