skip to main content
10.1145/2739480.2754741acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
research-article

Kernels of Mallows Models for Solving Permutation-based Problems

Authors Info & Claims
Published:11 July 2015Publication History

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.

References

  1. 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 ScholarGoogle ScholarCross RefCross Ref
  2. K. Baker. Introduction to sequencing and scheduling. Wiley, 1974.Google ScholarGoogle Scholar
  3. 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 ScholarGoogle ScholarCross RefCross Ref
  4. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  5. 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 ScholarGoogle Scholar
  6. 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 ScholarGoogle ScholarCross RefCross Ref
  7. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  8. 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 ScholarGoogle ScholarCross RefCross Ref
  9. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  10. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  11. 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 ScholarGoogle ScholarCross RefCross Ref
  12. J. Ceberio, A. Mendiburu, and J. A. Lozano. The Linear Ordering Problem Revisited. European Journal of Operational Research, 241(3):686--696, 2014.Google ScholarGoogle ScholarCross RefCross Ref
  13. D. E. Critchlow, M. A. Fligner, and J. S. Verducci. Probability models on rankings. Journal of Mathematical Psychology, 35(3):294 -- 318, 1991.Google ScholarGoogle ScholarCross RefCross Ref
  14. M. Fligner and J. Verducci. Multistage ranking models. Journal of the American Statistical Association, 83(403):892--901, 1988.Google ScholarGoogle ScholarCross RefCross Ref
  15. M. A. Fligner and J. S. Verducci. Distance based ranking Models. Journal of the Royal Statistical Society, 48(3):359--369, 1986.Google ScholarGoogle Scholar
  16. 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 ScholarGoogle Scholar
  17. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  18. J. Gupta and J. E. Stafford. Flow shop scheduling research after five decades. European Journal of Operational Research, 169(3):699--711, 2006.Google ScholarGoogle ScholarCross RefCross Ref
  19. 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 ScholarGoogle Scholar
  20. 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 ScholarGoogle Scholar
  21. 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 ScholarGoogle Scholar
  22. 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 ScholarGoogle Scholar
  23. 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 ScholarGoogle Scholar
  24. P. Larra\ naga and J. A. Lozano. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic Publishers, 2002.Google ScholarGoogle ScholarCross RefCross Ref
  25. G. Lebanon and Y. Mao. Non-Parametric Modeling of Partially Ranked Data. Journal of Machine Learning Research (JMLR), 9:2401--2429, 2008.Google ScholarGoogle Scholar
  26. 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 ScholarGoogle ScholarCross RefCross Ref
  27. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  28. C. L. Mallows. Non-null ranking models. Biometrika, 44(1--2):114--130, 1957.Google ScholarGoogle Scholar
  29. 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 ScholarGoogle ScholarCross RefCross Ref
  30. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  31. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  32. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  33. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  34. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  35. 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 ScholarGoogle Scholar
  36. 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 ScholarGoogle Scholar
  37. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  38. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  39. 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 ScholarGoogle ScholarCross RefCross Ref

Index Terms

  1. Kernels of Mallows Models for Solving Permutation-based Problems

            Recommendations

            Comments

            Login options

            Check if you have access through your login credentials or your institution to get full access on this article.

            Sign in
            • Published in

              cover image ACM Conferences
              GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation
              July 2015
              1496 pages
              ISBN:9781450334723
              DOI:10.1145/2739480

              Copyright © 2015 ACM

              Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

              Publisher

              Association for Computing Machinery

              New York, NY, United States

              Publication History

              • Published: 11 July 2015

              Permissions

              Request permissions about this article.

              Request Permissions

              Check for updates

              Qualifiers

              • research-article

              Acceptance Rates

              GECCO '15 Paper Acceptance Rate182of505submissions,36%Overall Acceptance Rate1,669of4,410submissions,38%

              Upcoming Conference

              GECCO '24
              Genetic and Evolutionary Computation Conference
              July 14 - 18, 2024
              Melbourne , VIC , Australia

            PDF Format

            View or Download as a PDF file.

            PDF

            eReader

            View online with eReader.

            eReader