Classical sorting embedded in genetic algorithms for improved permutation search
Vladimir Estivill‐Castro, Rodolfo Torres-Velázquez · 2002
A sorting algorithm defines a path in the search space of n! permutations based on the information provided by a comparison predicate. Our generic mutation operator for hybridization is a hill-climber and follows the path traced by any sorting algorithm. Our proposal adds exploitation capability to the mutation operator. Mutation requests swaps to construct and test new permutations, while the sorting algorithm supplies suggestions for swapping pairs as comparison to perform. The need to compare pairs of items in sorting is fulfilled by evaluating a guiding function. This novel HGA-sorting hybrid, instantiated with Insertion Sort, dramatically improves previous results for a benchmark of experiments of the Error-Correcting Graph Isomorphism.