Topological crossover for the permutation representation

ABSTRACT

Topological crossovers are a class of representation-independent operators that are well-defined once a notion of distance over the solution space is defined. In this paper we explore how the topological framework applies to the permutation representation and in particular analyze the consequences of having more than one notion of distance available. Also, we study the interactions among distances and build a rational picture in which pre-existing recombination/crossover operators for permutation fit naturally. Lastly, we also analyze the application of topological crossover to TSP.

REFERENCES

• 1: Bäck T, Fogel DB, Michalewicz Z (2000) Evolutionary Computation 1: Basic Algorithms and Operators. IOP Publishing, Bristol, UKT.
• 2: Thomas Back , David B. Fogel , Zbigniew Michalewicz, Handbook of Evolutionary Computation, IOP Publishing Ltd., Bristol, UK, 1997
• 3: Alberto Caprara, Sorting by reversals is difficult, Proceedings of the first annual international conference on Computational molecular biology, p.75-83, January 20-23, 1997, Santa Fe, New Mexico, United States [doi>10.1145/267521.267531]
• 4: Deza M and Huang T (1998) Metrics on permutations, a survey, J. Combinatorics, Information and System Sciences 23, pages 173--185.
• 5: Fox B R and McMahon M B (1991) Genetic Operators for Sequencing Problems In G J E Rawlins, editor, Foundations of Genetic Algorithms, pages 284--300. Morgan Kaufmann.
• 6: Glover F and Kochenberger G (2002) Handbook of Metaheuristics. Kluwer Academic.
• 7: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 8: Kececioglu J and Sankoff D (1995) Exact and approximate algorithms for sorting by reversals, with applications to genome rearrangement. Algorithmica, 13, pages 180--210.
• 9: Moraglio A and Poli R (2004) Topological interpretation of crossover. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2004), pages 1377--1388.
• 10: Radcliffe N J (1992) Nonlinear genetic representations. In R. Manner and B. Manderick, editors, Proceedings of the 2 nd Conference on Parallel Problems Solving from Nature, pages 259--268. Morgan Kaufmann.
• 11: Radcliffe N J (1994) The Algebra of Genetic Algorithms, Annals of Maths and Artificial Intelligence 10, pages 339--384.
• 12: Solomon A, Sutcliffe P, Lister R (2003) Sorting Circular Permutations by Reversals. WADS 2003, pages 319--328
• 13: John Paul C. Vergara, Sorting by bounded permutations, Virginia Polytechnic Institute & State University, Blacksburg, VA, 1998

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Design, Theory

Keywords:
crossover, permutations, theory