SAGA: Demonstrating the Benefits of Commonality-Based Crossover Operators in Simulated Annealing
Stephen Y. Chen · 2003
The crossover operator is traditionally viewed as the distinguishing feature and primary strength of a genetic algorithm. This multi-parent operator can recombine the useful features of two parent solutions into a single “super” offspring. However, a new analysis suggests that the primary benefit of crossover operators is the preservation of common components. In creating an offspring solution, crossover can focus its changes on the uncommon components of its two parents. This focus is a surprisingly important feature of genetic algorithms. To demonstrate the contribution of preserving common components to the search process of genetic algorithms, this feature has been isolated and transferred to simulated annealing. Results on the Travelling Salesman Problem indicate that the preservation of common components can lead to significant improvements in the performance of simulated annealing.