Alternative Representations for Codifying Solutions in Permutation-Based Problems

Since their introduction, Estimation of Distribution Algorithms (EDAs) have proved to be very competitive algorithms to solve many optimization problems. However, despite recent developments, in the case of permutation-based combinatorial optimization problems, there are still many aspects that deserve further research. One of them is the influence of the codification employed to represent the solutions on the overall performance of the algorithm. When considering classical EDAs, optimizing permutation problems is challenging, and specific mechanisms are needed to hold the restrictions associated with the permutation nature of solutions.In this paper, in addition to the permutation-vector codification, we investigate alternative representations to describe solutions of permutation problems in the context of EDAs. In order to evaluate their influence, we adopted a classical EDA and conducted an experimental study on two different permutation problems and representations for codifying solutions. The results revealed a narrow relationship between the type of combinatorial problem optimized and the selected representation used to codify its solutions. Moreover, the results point out that choosing the appropriate representation to codify solutions of the given permutation problem is critical for the performance of the algorithm.