Geometric crossover for the permutation representation

Issue title: Evolutionary Computation – A Journey in Computational Logic in Italy – Dedicated to Prof. Alberto Martelli

Article type: Research Article

Authors: Moraglio, Alberto | Poli, Riccardo

Affiliations: School of Computing and Centre for Reasoning, University of Kent, Canterbury, UK | School of Computer Science and Electronic Engineering, University of Essex, Colchester, UK

Note: [] Corresponding author. E-mail: [email protected], [email protected] (A. Moraglio); [email protected] (R. Poli).

Abstract: Geometric crossovers are a class of representation-independent search operators for evolutionary algorithms that are well-defined once a notion of distance over a solution space is defined. In this paper we explore the specialisation of geometric crossovers to the permutation representation analysing the consequences of the availability of more than one notion of distance. Also, we study the relations among distances and build a rational picture in which pre-existing recombination operators for permutations fit naturally. Lastly, we illustrate the application of geometric crossover to the Travelling Salesman Problem (TSP).

Keywords: Evolutionary algorithms, crossover, permutations, theory

DOI: 10.3233/IA-2011-0004

Journal: Intelligenza Artificiale, vol. 5, no. 1, pp. 49-63, 2011