ABSTRACT
Recently, distance-based exponential probability models, such as Mallows and Generalized Mallows, have demonstrated their validity in the context of estimation of distribution algorithms (EDAs) for solving permutation problems. However, despite their successful performance, these models are unimodal, and therefore, they are not flexible enough to accurately model populations with solutions that are very sparse with regard to the distance metric considered under the model.
In this paper, we propose using kernels of Mallows models under the Kendall's-tau and Cayley distances within EDAs. In order to demonstrate the validity of this new algorithm, Mallows Kernel EDA, we compare its performance with the classical Mallows and Generalized Mallows EDAs, on a benchmark of 90 instances of two different types of permutation problems: the quadratic assignment problem and the permutation flowshop scheduling problem. Experimental results reveal that, in most cases, Mallows Kernel EDA outperforms the Mallows and Generalized Mallows EDAs under the same distance. Moreover, the new algorithm under the Cayley distance obtains the best results for the two problems in terms of average fitness and computational time.
- A. Allahverdi, C. Ng, T. Cheng, and M. Y. Kovalyov. A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187(3):985 -- 1032, 2008.Google ScholarCross Ref
- K. Baker. Introduction to sequencing and scheduling. Wiley, 1974.Google Scholar
- P. A. N. Bosman and D. Thierens. Mult-objective optimization with diversity preserving mixture-based iterated density estimation evolutionary algorithms. Internation Journal of Approximate Reasoning, 31(3):259--289, 2002.Google ScholarCross Ref
- A. E. I. Brownlee, M. Pelikan, J. A. W. McCall, and A. Petrovski. An application of a multivariate estimation of distribution algorithm to cancer chemotherapy. In C. Ryan and M. Keijzer, editors, Proceedings of the 10th Genetic and Evolutionary Computation Conference, GECCO '08, pages 463--464, 2008. Google ScholarDigital Library
- J. Ceberio. Solving Permutation Problems with Estimation of Distribution Algorithms and Extensions Thereof. PhD thesis, Faculty of Computer Science, University of the Basque Country, December 2014.Google Scholar
- J. Ceberio, E. Irurozki, A. Mendiburu, and J. A. Lozano. A review on Estimation of Distribution Algorithms in Permutation-based Combinatorial Optimization Problems. Progress in Artificial Intelligence, 1(1):103--117, January 2012.Google ScholarCross Ref
- J. Ceberio, E. Irurozki, A. Mendiburu, and J. A. Lozano. A Distance-based Ranking Model Estimation of Distribution Algorithm for the Flowshop Scheduling Problem. IEEE Transactions on Evolutionary Computation, 18(2):286 -- 300, April 2014. Google ScholarDigital Library
- J. Ceberio, E. Irurozki, A. Mendiburu, and J. A. Lozano. Extending distance-based ranking models in estimation of distribution algorithms. In Proceedings of the 2014 IEEE Congress on Evolutionary Computation. IEEE, July 2014.Google ScholarCross Ref
- J. Ceberio, E. Irurozki, A. Mendiburu, and J. A. Lozano. A review of distances for the Mallows and Generalized mallows estimation of distribution algorithms. Computational Optimization and Applications, 2015.Google ScholarDigital Library
- J. Ceberio, A. Mendiburu, and J. A. Lozano. Introducing the Mallows Model on Estimation of Distribution Algorithms. In B.-L. Lu, L. Zhang, and J. T. Kwok, editors, Proceedings of International Conference on Neural Information Processing (ICONIP), Lecture Notes in Computer Science, pages 461--470. Springer, 2011. Google ScholarDigital Library
- J. Ceberio, A. Mendiburu, and J. A. Lozano. The Plackett-Luce Ranking Model on Permutation-based Optimization Problems. In Proceedings of the 2013 IEEE Congress on Evolutionary Computation, pages 494 -- 501, June 2013.Google ScholarCross Ref
- J. Ceberio, A. Mendiburu, and J. A. Lozano. The Linear Ordering Problem Revisited. European Journal of Operational Research, 241(3):686--696, 2014.Google ScholarCross Ref
- D. E. Critchlow, M. A. Fligner, and J. S. Verducci. Probability models on rankings. Journal of Mathematical Psychology, 35(3):294 -- 318, 1991.Google ScholarCross Ref
- M. Fligner and J. Verducci. Multistage ranking models. Journal of the American Statistical Association, 83(403):892--901, 1988.Google ScholarCross Ref
- M. A. Fligner and J. S. Verducci. Distance based ranking Models. Journal of the Royal Statistical Society, 48(3):359--369, 1986.Google Scholar
- B. Gao. Estimation of Distribution Algorithms for single- and multi-objective optimization. PhD thesis, School of Mathematics and Physics, The University of Queensland, 2014.Google Scholar
- S. Garcia, D. Molina, M. Lozano, and F. Herrera. A study on the use of non-parametric tests for analyzing the evolutionary algorithms' behaviour: a case study on the CEC'2005 Special Session on Real Parameter Optimization. Journal of Heuristics, 15(6):617--644, 2009. Google ScholarDigital Library
- J. Gupta and J. E. Stafford. Flow shop scheduling research after five decades. European Journal of Operational Research, 169(3):699--711, 2006.Google ScholarCross Ref
- E. Irurozki, B. Calvo, and J. A. Lozano. Sampling and learning Mallows and Generalized Mallows models under the Cayley distance. Technical report, University of the Basque Country UPV/EHU, 2014.Google Scholar
- E. Irurozki, B. Calvo, and J. A. Lozano. Sampling and learning the mallows and weighted mallows models under the Hamming distance. Technical report, University of the Basque Country UPV/EHU, 2014.Google Scholar
- E. Irurozki, J. Ceberio, B. Calvo, and J. A. Lozano. Mallows model under the ulam distance: a feasible combinatorial approach. In Workshop Book 2014 NIPS Conference, Montreal, Quebec, Canada, December 2014.Google Scholar
- S. Jiang, A. Ziver, J. Carter, C. Pain, A. Goddard, S. Franklin, and H. Phillips. Estimation of Distribution Algorithms for nuclear reactor fuel management optimisation. Annals of Nuclear Energy, 33(11--12):1039--1057, 2006.Google Scholar
- T. C. Koopmans and M. J. Beckmann. Assignment Problems and the Location of Economic Activities. Cowles Foundation Discussion Papers 4, Cowles Foundation for Research in Economics, Yale University, 1955.Google Scholar
- P. Larra\ naga and J. A. Lozano. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic Publishers, 2002.Google ScholarCross Ref
- G. Lebanon and Y. Mao. Non-Parametric Modeling of Partially Ranked Data. Journal of Machine Learning Research (JMLR), 9:2401--2429, 2008.Google Scholar
- P. H. Lee and P. L. H. Yu. Mixtures of weighted distance-based models for ranking data. In IEEE Proceedings of COMPSTAT'2010, pages 517--524, August 2010.Google ScholarCross Ref
- J. A. Lozano, P. Larra\ naga, I. Inza, and E. Bengoetxea. Towards a New Evolutionary Computation: Advances on Estimation of Distribution Algorithms (Studies in Fuzziness and Soft Computing). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006. Google ScholarDigital Library
- C. L. Mallows. Non-null ranking models. Biometrika, 44(1--2):114--130, 1957.Google Scholar
- J. McCall, A. E. I. Brownlee, and S. Shakya. Applications of distribution estimation using markov network modelling (DEUM). In S. Shakya and R. Santana, editors, Markov Networks in Evolutionary Computation, pages 193--207. Springer, 2012.Google ScholarCross Ref
- A. Mendiburu, J. Miguel-Alonso, J. A. Lozano, M. Ostra, and C. Ubide. Parallel EDAs to create multivariate calibration models for quantitative chemical applications. Journal of Parallel and Distributed Computing, 66(8):1002--1013, 2006. Google ScholarDigital Library
- H. Mühlenbein and G. Paaß. From Recombination of Genes to the Estimation of Distributions I. Binary Parameters. In Lecture Notes in Computer Science 1411: Parallel Problem Solving from Nature - PPSN IV, pages 178--187, 1996. Google ScholarDigital Library
- T. B. Murphy and D. Martin. Mixtures of distance-based models for ranking data. Computational Statistics & Data Analysis, 41(3--4):645--655, Jan. 2003. Google ScholarDigital Library
- M. Pelikan, D. E. Goldberg, and F. G. Lobo. A survey of optimization by building and using probabilistic models. Computational Optimization and Applications, 21(1):5--20, 2002. Google ScholarDigital Library
- J. M. Pe\ na, J. A. Lozano, and P. Larra\ naga. Globally multimodal problem optimization via an estimation of distribution algorithm based on unsupervised learning of Bayesian networks. Evolutionary Computation, pages 43--66, 2005. Google ScholarDigital Library
- J. Santamaria, J. Ceberio, R. Santana, A. Mendiburu, and J. Lozano. Introducing mixtures of Generalized Mallows in estimation of distribution algorithms. In X Congreso Espa\ nol de Metaheuristicas, Algoritmos Evolutivos y Bioinspirados - MAEB 2015, pages 19--25, Mérida-Almendralejo, Spain, February 2015.Google Scholar
- R. Santana, C. Bielza, P. Larranaga, J. A. Lozano, C. Echegoyen, A. Mendiburu, R. Armananzas, and S. Shakya. Mateda-2.0: Estimation of distribution algorithms in matlab. Journal of Statistical Software, 35(7):1--30, 2010.Google Scholar
- R. Santana, P. Larra\ naga, and J. A. Lozano. Mixtures of Kikuchi approximations. In J. Fürnkranz, T. Scheffer, and M. Spiliopoulou, editors, Machine Learning: ECML 2006, volume 4212 of Lecture Notes in Computer Science, pages 365--376. Springer Berlin Heidelberg, 2006. Google ScholarDigital Library
- R. Santana, P. Larra\ naga, and J. A. Lozano. Protein folding in simplified models with Estimation of Distribution Algorithms. IEEE Transactions On Evolutionary Computation, 12(4):418--438, 2008. Google ScholarDigital Library
- M. R. Soto, A. Ochoa, Y. González-Fernández, Y. Milanés, A. Álvarez, D. Carrera, and E. Moreno. Vine estimation of distribution algorithms with application to molecular docking. In S. Shakya and R. Santana, editors, Markov Networks in Evolutionary Computation, pages 175--190. Springer, 2012.Google ScholarCross Ref
Index Terms
Kernels of Mallows Models for Solving Permutation-based Problems
Recommendations
A preliminary study on EDAs for permutation problems based on marginal-based models
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computationEstimation of Distribution Algorithms are a class of evolutionary algorithms characterized by the use of probabilistic models. These algorithms have been applied successfully to a wide set of artificial and real-world problems, achieving competitive ...
Parameter-Less Population Pyramid for Permutation-Based Problems
Parallel Problem Solving from Nature – PPSN XVIAbstractLinkage learning is frequently employed in state-of-the-art methods dedicated to discrete optimization domains. Information about linkage identifies a subgroup of genes that are found dependent on each other. If such information is precise and ...
Introducing the mallows model on estimation of distribution algorithms
ICONIP'11: Proceedings of the 18th international conference on Neural Information Processing - Volume Part IIEstimation of Distribution Algorithms are a set of algorithms that belong to the field of Evolutionary Computation. Characterized by the use of probabilistic models to learn the (in)dependencies between the variables of the optimization problem, these ...
Comments