The Plackett-Luce ranking model on permutation-based optimization problems
- 1 June 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 1089778X,p. 494-501
Abstract
Estimation of distribution algorithms are known as powerful evolutionary algorithms that have been widely used for diverse types of problems. However, they have not been extensively developed for permutation-based problems. Recently, some progress has been made in this area by introducing probability models on rankings to optimize permutation domain problems. In particular, the Mallows model and the Generalized Mallows model demonstrated their effectiveness when used with estimation of distribution algorithms. Motivated by these advances, in this paper we introduce a Thurstone order statistics model, called Plackett-Luce, to the framework of estimation of distribution algorithms. In order to prove the potential of the proposed algorithm, we consider two different permutation problems: the linear ordering problem and the flowshop scheduling problem. In addition, the results are compared with those obtained by the Mallows and the Generalized Mallows proposals. Conducted experiments demonstrate that the Plackett-Luce model is the best performing model for solving the linear ordering problem. However, according to the experimental results, the Generalized Mallows model turns out to be very robust obtaining very competitive results for both problems, especially for the permutation flowshop scheduling problem.Keywords
This publication has 30 references indexed in Scilit:
- Estimation of distribution algorithm for permutation flow shops with total flowtime minimizationComputers & Industrial Engineering, 2011
- An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problemsComputers & Operations Research, 2009
- EDA-RL2009
- Bayesian inference for Plackett-Luce ranking models2009
- An application of a multivariate estimation of distribution algorithm to cancer chemotherapy2008
- Dependency trees, permutations, and quadratic assignment problem2007
- Estimation of distribution algorithms for nuclear reactor fuel management optimisationAnnals of Nuclear Energy, 2006
- Probability models on rankingsJournal of Mathematical Psychology, 1991
- Multistage Ranking ModelsJournal of the American Statistical Association, 1988
- The Analysis of PermutationsJournal of the Royal Statistical Society Series C: Applied Statistics, 1975