{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:32:22Z","timestamp":1750221142598,"version":"3.41.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,7,26]],"date-time":"2018-07-26T00:00:00Z","timestamp":1532563200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2018,12,31]]},"abstract":"<jats:p>Permutation problems are combinatorial optimization problems whose solutions are naturally codified as permutations. Due to their complexity, motivated principally by the factorial cardinality of the search space of solutions, they have been a recurrent topic for the artificial intelligence and operations research community. Recently, among the vast number of metaheuristic algorithms, new advances on estimation of distribution algorithms (EDAs) have shown outstanding performance when solving some permutation problems. These novel EDAs implement distance-based exponential probability models such as the Mallows and Generalized Mallows models. In this article, we present a Matlab package, perm_mateda, of estimation of distribution algorithms on permutation problems, which has been implemented as an extension to the Mateda-2.0 toolbox of EDAs. Particularly, we provide implementations of the Mallows and Generalized Mallows EDAs under the Kendall\u2019s-\u03c4, Cayley, and Ulam distances. In addition, four classical permutation problems have also been implemented: Traveling Salesman Problem, Permutation Flowshop Scheduling Problem, Linear Ordering Problem, and Quadratic Assignment Problem.<\/jats:p>","DOI":"10.1145\/3206429","type":"journal-article","created":{"date-parts":[[2018,7,26]],"date-time":"2018-07-26T11:58:04Z","timestamp":1532606284000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Algorithm 989"],"prefix":"10.1145","volume":"44","author":[{"given":"Ekhine","family":"Irurozki","sequence":"first","affiliation":[{"name":"Intelligent Systems Group, Basque Center for Applied Mathematics (BCAM), Bizkaia, Spain"}]},{"given":"Josu","family":"Ceberio","sequence":"additional","affiliation":[{"name":"Intelligent Systems Group, Faculty of Computer Science, University of the Basque Country UPV\/EHU, Gipuzkoa, Spain"}]},{"given":"Josean","family":"Santamaria","sequence":"additional","affiliation":[{"name":"Intelligent Systems Group, Faculty of Computer Science, University of the Basque Country UPV\/EHU, Gipuzkoa, Spain"}]},{"given":"Roberto","family":"Santana","sequence":"additional","affiliation":[{"name":"Intelligent Systems Group, Faculty of Computer Science, University of the Basque Country UPV\/EHU, Gipuzkoa, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7271-1931","authenticated-orcid":false,"given":"Alexander","family":"Mendiburu","sequence":"additional","affiliation":[{"name":"Intelligent Systems Group, Faculty of Computer Science, University of the Basque Country UPV\/EHU, Gipuzkoa, Spain"}]}],"member":"320","published-online":{"date-parts":[[2018,7,26]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2015.09.050"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2016.09.013"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-017-9323-3"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1186\/1756-0381-1-6"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.34.2.180.12302"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1389095.1389179"},{"key":"e_1_2_2_7_1","volume-title":"Pitsoulis","author":"Burkard Rainer E.","year":"1998","unstructured":"Rainer E. Burkard , Eranda \u00c7ela , Panos M. Pardalos , and Leonidas S . Pitsoulis . 1998 . The Quadratic Assignment Problem. Springer . Rainer E. Burkard, Eranda \u00c7ela, Panos M. Pardalos, and Leonidas S. Pitsoulis. 1998. The Quadratic Assignment Problem. Springer."},{"key":"e_1_2_2_9_1","first-page":"1","article-title":"A review on estimation of distribution algorithms in permutation-based combinatorial optimization problems","volume":"1","author":"Ceberio Josu","year":"2012","unstructured":"Josu Ceberio , Ekhine Irurozki , Alexander Mendiburu , and Jose A. Lozano . 2012 . A review on estimation of distribution algorithms in permutation-based combinatorial optimization problems . Progr. Artific. Intell. 1 , 1 (Jan. 2012), 103--117. Josu Ceberio, Ekhine Irurozki, Alexander Mendiburu, and Jose A. Lozano. 2012. A review on estimation of distribution algorithms in permutation-based combinatorial optimization problems. Progr. Artific. Intell. 1, 1 (Jan. 2012), 103--117.","journal-title":"Progr. Artific. Intell."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2013.2260548"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-015-9740-x"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24958-7_54"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2001576.2001660"},{"volume-title":"Proceedings of the IEEE Congress on Evolutionary Computation. 494--501","author":"Ceberio Josu","key":"e_1_2_2_14_1","unstructured":"Josu Ceberio , Alexander Mendiburu , and Jose A. Lozano . 2013. The plackett-luce ranking model on permutation-based optimization problems . In Proceedings of the IEEE Congress on Evolutionary Computation. 494--501 . Josu Ceberio, Alexander Mendiburu, and Jose A. Lozano. 2013. The plackett-luce ranking model on permutation-based optimization problems. In Proceedings of the IEEE Congress on Evolutionary Computation. 494--501."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2014.09.041"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2739480.2754741"},{"key":"e_1_2_2_17_1","unstructured":"Jean C. de Borda. 1781. Memoire sur les elections au scrutin. Histoire de l\u2019Academie Royale des Science. L'Imprimerie Royale. Jean C. de Borda. 1781. Memoire sur les elections au scrutin. Histoire de l\u2019Academie Royale des Science. L'Imprimerie Royale."},{"key":"e_1_2_2_18_1","volume-title":"Liens-ecole Normale Sup\u00e9rieure, and Tayuan Huang","author":"Deza Michael","year":"1998","unstructured":"Michael Deza , Liens-ecole Normale Sup\u00e9rieure, and Tayuan Huang . 1998 . Metrics on permutations, a survey. In Journal of Combinatorics, Information and System Sciences. Citeseer . Michael Deza, Liens-ecole Normale Sup\u00e9rieure, and Tayuan Huang. 1998. Metrics on permutations, a survey. In Journal of Combinatorics, Information and System Sciences. Citeseer."},{"volume-title":"Group Representations in Probability and Statistics","author":"Diaconis Persi","key":"e_1_2_2_19_1","unstructured":"Persi Diaconis . 1988. Group Representations in Probability and Statistics . Institute of Mathematical Statistics , Hayward, CA . Persi Diaconis. 1988. Group Representations in Probability and Statistics. Institute of Mathematical Statistics, Hayward, CA."},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1111\/j.2517-6161.1986.tb01420.x","article-title":"Distance based ranking models","volume":"48","author":"Fligner Michael A.","year":"1986","unstructured":"Michael A. Fligner and Joseph S. Verducci . 1986 . Distance based ranking models . J. Roy. Stat. Soc. 48 , 3 (1986), 359 -- 369 . Michael A. Fligner and Joseph S. Verducci. 1986. Distance based ranking models. J. Roy. Stat. Soc. 48, 3 (1986), 359--369.","journal-title":"J. Roy. Stat. Soc."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1988.10478679"},{"key":"e_1_2_2_22_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Co., New York, NY. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Co., New York, NY."},{"key":"e_1_2_2_23_1","volume-title":"Proceedings of an International Conference on Genetic Algorithms and Their Applications","volume":"154","author":"David","unstructured":"David E. Goldberg and Robert Lingle Jr. 1985. Alleles loci and the traveling salesman problem . In Proceedings of an International Conference on Genetic Algorithms and Their Applications , Vol. 154 . Lawrence Erlbaum, Hillsdale, NJ, 154--159. David E. Goldberg and Robert Lingle Jr. 1985. Alleles loci and the traveling salesman problem. In Proceedings of an International Conference on Genetic Algorithms and Their Applications, Vol. 154. Lawrence Erlbaum, Hillsdale, NJ, 154--159."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2005.02.001"},{"key":"e_1_2_2_25_1","volume-title":"Fourier theoretic probabilistic inference over permutations. J. Mach. Learn. Res. 10 (May","author":"Huang Jonathan","year":"2009","unstructured":"Jonathan Huang , Carlos Guestrin , and Leonidas Guibas . 2009. Fourier theoretic probabilistic inference over permutations. J. Mach. Learn. Res. 10 (May 2009 ), 997--1070. Jonathan Huang, Carlos Guestrin, and Leonidas Guibas. 2009. Fourier theoretic probabilistic inference over permutations. J. Mach. Learn. Res. 10 (May 2009), 997--1070."},{"volume-title":"Proceedings of the Analysis on Rank Data Workshop on Neural Information Processing System (NIPS\u201914)","author":"Irurozki Ekhine","key":"e_1_2_2_27_1","unstructured":"Ekhine Irurozki , Borja Calvo , and Jose A. Lozano . 2014. Mallows model under the ulam distance: A feasible combinatorial approach . In Proceedings of the Analysis on Rank Data Workshop on Neural Information Processing System (NIPS\u201914) . University of the Basque Country. Ekhine Irurozki, Borja Calvo, and Jose A. Lozano. 2014. Mallows model under the ulam distance: A feasible combinatorial approach. In Proceedings of the Analysis on Rank Data Workshop on Neural Information Processing System (NIPS\u201914). University of the Basque Country."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v071.i12"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11009-016-9506-7"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00500-016-2241-8"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12293-015-0172-z"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.anucene.2006.03.012"},{"key":"e_1_2_2_33_1","volume-title":"Beckmann","author":"Koopmans Tjalling C.","year":"1955","unstructured":"Tjalling C. Koopmans and Martin J . Beckmann . 1955 . Assignment Problems and the Location of Economic Activities. Cowles Foundation Discussion Papers 4. Cowles Foundation for Research in Economics, Yale University . Tjalling C. Koopmans and Martin J. Beckmann. 1955. Assignment Problems and the Location of Economic Activities. Cowles Foundation Discussion Papers 4. Cowles Foundation for Research in Economics, Yale University."},{"key":"e_1_2_2_34_1","volume-title":"Lozano","author":"Larra\u00f1aga Pedro","year":"2002","unstructured":"Pedro Larra\u00f1aga and Jose A . Lozano . 2002 . Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic Publishers . Pedro Larra\u00f1aga and Jose A. Lozano. 2002. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic Publishers."},{"volume-title":"Towards a New Evolutionary Computation: Advances on Estimation of Distribution Algorithms (Studies in Fuzziness and Soft Computing)","author":"Lozano Jose A.","key":"e_1_2_2_35_1","unstructured":"Jose A. Lozano , Pedro Larra\u00f1aga , I\u00f1aki Inza , and Endika Bengoetxea . 2006. Towards a New Evolutionary Computation: Advances on Estimation of Distribution Algorithms (Studies in Fuzziness and Soft Computing) . Springer-Verlag New York, Inc. , Secaucus, NJ . Jose A. Lozano, Pedro Larra\u00f1aga, I\u00f1aki Inza, and Endika Bengoetxea. 2006. Towards a New Evolutionary Computation: Advances on Estimation of Distribution Algorithms (Studies in Fuzziness and Soft Computing). Springer-Verlag New York, Inc., Secaucus, NJ."},{"volume-title":"Individual Choice Behavior","author":"Luce R. Duncan","key":"e_1_2_2_36_1","unstructured":"R. Duncan Luce . 1959. Individual Choice Behavior . Wiley , New York . R. Duncan Luce. 1959. Individual Choice Behavior. Wiley, New York."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/44.1-2.114"},{"key":"e_1_2_2_38_1","first-page":"392","article-title":"Tractable search for learning exponential models of rankings","volume":"5","author":"Mandhani Bhushan","year":"2009","unstructured":"Bhushan Mandhani and Marina Meila . 2009 . Tractable search for learning exponential models of rankings . J. Mach. Learn. Res. 5 (2009), 392 -- 399 . Bhushan Mandhani and Marina Meila. 2009. Tractable search for learning exponential models of rankings. J. Mach. Learn. Res. 5 (2009), 392--399.","journal-title":"J. Mach. Learn. Res."},{"volume-title":"Markov Networks in Evolutionary Computation","author":"McCall John","key":"e_1_2_2_39_1","unstructured":"John McCall , Alexander E. I. Brownlee , and Siddhartha Shakya . 2012. Applications of distribution estimation using markov network modelling (DEUM) . In Markov Networks in Evolutionary Computation , S. Shakya and R. Santana (Eds.). Springer , 193--207. John McCall, Alexander E. I. Brownlee, and Siddhartha Shakya. 2012. Applications of distribution estimation using markov network modelling (DEUM). In Markov Networks in Evolutionary Computation, S. Shakya and R. Santana (Eds.). Springer, 193--207."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2006.03.001"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993377"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013500812258"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.riai.2017.05.002"},{"key":"e_1_2_2_44_1","first-page":"193","article-title":"The analysis of permutations","volume":"24","author":"Plackett Robin L.","year":"1975","unstructured":"Robin L. Plackett . 1975 . The analysis of permutations . J. Roy. Stat. Soc. 24 , 10 (1975), 193 -- 202 . Robin L. Plackett. 1975. The analysis of permutations. J. Roy. Stat. Soc. 24, 10 (1975), 193--202.","journal-title":"J. Roy. Stat. Soc."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2004.08.006"},{"volume-title":"Proceedings of the X Congreso Espa\u00f1ol de Metaheuristicas, Algoritmos Evolutivos y Bioinspirados (MAEB\u201915)","author":"Santamaria Josian","key":"e_1_2_2_46_1","unstructured":"Josian Santamaria , Josu Ceberio , Roberto Santana , Alexander Mendiburu , and Jose A. Lozano . 2015. Introducing mixtures of generalized mallows in estimation of distribution algorithms . In Proceedings of the X Congreso Espa\u00f1ol de Metaheuristicas, Algoritmos Evolutivos y Bioinspirados (MAEB\u201915) . 19--25. Josian Santamaria, Josu Ceberio, Roberto Santana, Alexander Mendiburu, and Jose A. Lozano. 2015. Introducing mixtures of generalized mallows in estimation of distribution algorithms. In Proceedings of the X Congreso Espa\u00f1ol de Metaheuristicas, Algoritmos Evolutivos y Bioinspirados (MAEB\u201915). 19--25."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v035.i07"},{"volume-title":"Markov Networks in Evolutionary Computation","author":"Soto Marta","key":"e_1_2_2_48_1","unstructured":"Marta Soto , Alberto Ochoa , Yasser Gonz\u00e1lez-Fern\u00e1ndez , Yanely Milan\u00e9s , Adriel \u00c1lvarez , Diana Carrera , and Ernesto Moreno . 2012. Vine estimation of distribution algorithms with application to molecular docking . In Markov Networks in Evolutionary Computation , S. Shakya and R. Santana (Eds.). Springer , 175--190. Marta Soto, Alberto Ochoa, Yasser Gonz\u00e1lez-Fern\u00e1ndez, Yanely Milan\u00e9s, Adriel \u00c1lvarez, Diana Carrera, and Ernesto Moreno. 2012. Vine estimation of distribution algorithms with application to molecular docking. In Markov Networks in Evolutionary Computation, S. Shakya and R. Santana (Eds.). Springer, 175--190."},{"volume-title":"The Vehicle Routing Problem","author":"Toth Paolo","key":"e_1_2_2_49_1","unstructured":"Paolo Toth and Daniele Vigo . 2001. The Vehicle Routing Problem . Society for Industrial and Applied Mathematics . Paolo Toth and Daniele Vigo. 2001. The Vehicle Routing Problem. Society for Industrial and Applied Mathematics."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2004.1330991"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71618-1_59"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2017.02.034"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3206429","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3206429","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:10Z","timestamp":1750208890000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3206429"}},"subtitle":["perm_mateda: A Matlab Toolbox of Estimation of Distribution Algorithms for Permutation-based Combinatorial Optimization Problems"],"short-title":[],"issued":{"date-parts":[[2018,7,26]]},"references-count":50,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12,31]]}},"alternative-id":["10.1145\/3206429"],"URL":"https:\/\/doi.org\/10.1145\/3206429","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2018,7,26]]},"assertion":[{"value":"2016-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}