An Experimental Comparison of Algebraic Crossover Operators for Permutation Problems
Issue title: Special issue of the 25th RCRA International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion
Guest editors: Thomas Eiter, Marco Maratea and Mauro Vallati
Affiliations: [a] Department of Mathematics and Computer Science, University of Perugia, Italy. marco.baioletti@unipg.it | [b] Department of Mathematics and Computer Science, University of Florence, Italy. gabriele.dibari@unifi.it | [c] Department of Mathematics and Computer Science, University of Perugia, Italy. alfredo.milani@unipg.it | [d] Department of Humanities and Social Sciences, University for Foreigners of Perugia, Italy. valentino.santucci@unistrapg.it
Correspondence:
[*]
Address for correspondence: Department of Humanities and Social Sciences, University for Foreigners of Perugia, Italy
Abstract: Crossover operators are very important components in Evolutionary Computation. Here we are interested in crossovers for the permutation representation that find applications in combinatorial optimization problems such as the permutation flowshop scheduling and the traveling salesman problem. We introduce three families of permutation crossovers based on algebraic properties of the permutation space. In particular, we exploit the group and lattice structures of the space. A total of 34 new crossovers is provided. Algebraic and semantic properties of the operators are discussed, while their performances are investigated by experimentally comparing them with known permutation crossovers on standard benchmarks from four popular permutation problems. Three different experimental scenarios are considered and the results clearly validate our proposals.
