Abstract

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. , we implemented in Coq several genetic operators proposed in Davis and Syswerda 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. , 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