Factoradic Representation for Permutation Optimisation

Olivier Regnier-Coudert and John McCall

Abstract. It is known that different classes of permutation problems are more easily solved by selecting a suitable representation. In particular, permutation representations suitable for Estimation of Distribution algorithms (EDAs) are known to present several challenges. Therefore, it is of interest to investigate novel representations and their properties. In this paper, we present a study of the factoradic representation which offers new modelling insights through the use of three algorithmic frameworks, a Genetic Algorithm (GA) and two EDAs. Four classic permutation benchmark problems are used to evaluate the factoradic-based algorithms in comparison with published work with other representations. Our experiments demonstrate that the factoradic representation is a competitive approach to apply to permutation problems. EDAs and more specifically, univariate EDAs show the most robust performance on the benchmarks studied. The factoradic representation also leads to better performance than adaptations of EDAs for continuous spaces, overall similar performance to integer-based EDAs and occasionally matches results of specialised EDAs, justifying further study.

Keywords: Estimation of Distribution Algorithms, Factoradics, Permutation

LNCS 8672, p. 332 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer International Publishing Switzerland 2014