Crossover operators for permutations equivalence between position and order-based crossover

摘要

In the context of genetic algorithms, the use of permutation-based representations has worked out more conveniently than the classical binary encoding for some scheduling and combinatorial problems such as the Travelling Salesman Problem. In Aguado et al. (2007, Certified genetic algorithms: crossover operators for permutations, Vol. 4739 of Lecture notes in Computer Science, pp. 282–289), we implemented in Coq several genetic operators proposed in Davis (1991, Handbook of Genetic Algorithms) and Syswerda (1985, Schedule optimization using Genetic algorithms, Handbook of Genetic Algorithms, pp. 332–349) to deal with the chromosomes of problems where the individuals are encoded as permutations; in these cases we specifically implemented the so-called operators pbx and obx. In Aguado et al. (2007, Generalización de los cruces basados en el orden y en la posición. Una implementación verificada, In Proceedings of CLEI 2007), we define with an axiomatic implementation two new operators gen_pbx and gen_obx which generalize the previous ones. In this article, we formally specify the relation between these operators when restricted to the case of permutations without repetition. We also propose a new crossover operator which actually combines the genetic material from both parents in each child. Experimental results confirm that the use of one or another crossover makes no significant difference.