{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T16:00:36Z","timestamp":1740153636552,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,7,16]],"date-time":"2022-07-16T00:00:00Z","timestamp":1657929600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,16]],"date-time":"2022-07-16T00:00:00Z","timestamp":1657929600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100014440","name":"ministerio de ciencia, innovaci\u00f3n y universidades","doi-asserted-by":"publisher","award":["PID2019-104966GB-I00\/AEI\/10.13039\/501100011033","PID2019-104933GB-I00\/AEI\/10.13039\/501100011033"],"award-info":[{"award-number":["PID2019-104966GB-I00\/AEI\/10.13039\/501100011033","PID2019-104933GB-I00\/AEI\/10.13039\/501100011033"]}],"id":[{"id":"10.13039\/100014440","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014440","name":"ministerio de ciencia, innovaci\u00f3n y universidades","doi-asserted-by":"publisher","award":["PID2019-106453GA-I00\/AEI\/10.13039\/501100011033","BCAM Severo Ochoa accreditation SEV-2017-0718"],"award-info":[{"award-number":["PID2019-106453GA-I00\/AEI\/10.13039\/501100011033","BCAM Severo Ochoa accreditation SEV-2017-0718"]}],"id":[{"id":"10.13039\/100014440","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003086","name":"eusko jaurlaritza","doi-asserted-by":"publisher","award":["IT1504-22","IT-1252-19"],"award-info":[{"award-number":["IT1504-22","IT-1252-19"]}],"id":[{"id":"10.13039\/501100003086","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003086","name":"eusko jaurlaritza","doi-asserted-by":"publisher","award":["GIU20\/054","PRE_2021_2_0224"],"award-info":[{"award-number":["GIU20\/054","PRE_2021_2_0224"]}],"id":[{"id":"10.13039\/501100003086","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003086","name":"eusko jaurlaritza","doi-asserted-by":"publisher","award":["BERC 2022-2025"],"award-info":[{"award-number":["BERC 2022-2025"]}],"id":[{"id":"10.13039\/501100003086","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Memetic Comp."],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Estimation of Distribution Algorithms have been successfully used to solve permutation-based Combinatorial Optimization Problems. In this case, the algorithms use probabilistic models specifically designed for codifying probability distributions over permutation spaces. One class of these probability models are distance-based exponential models, and one example of this class is the Mallows model. In spite of its practical success, the theoretical analysis of Estimation of Distribution Algorithms for permutation-based Combinatorial Optimization Problems has not been developed as extensively as it has been for binary problems. With this motivation, this paper presents a first mathematical analysis of the convergence behavior of Estimation of Distribution Algorithms based on Mallows models. The model removes the randomness of the algorithm in order to associate a dynamical system to it. Several scenarios of increasing complexity with different fitness functions and initial probability distributions are analyzed. The obtained results show: a) the strong dependence of the final results on the initial population, and b) the possibility to converge to non-degenerate distributions even in very simple scenarios, which has not been reported before in the literature.<\/jats:p>","DOI":"10.1007\/s12293-022-00371-y","type":"journal-article","created":{"date-parts":[[2022,7,16]],"date-time":"2022-07-16T06:02:40Z","timestamp":1657951360000},"page":"305-334","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A mathematical analysis of EDAs with distance-based exponential models"],"prefix":"10.1007","volume":"14","author":[{"given":"Imanol","family":"Unanue","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mar\u00eda","family":"Merino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jose A.","family":"Lozano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,7,16]]},"reference":[{"issue":"1","key":"371_CR1","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.mathsocsci.2011.08.008","volume":"64","author":"A Ali","year":"2012","unstructured":"Ali A, Meil\u0103 M (2012) Experiments with Kemeny ranking: What works when? Math Soc Sci 64(1):28\u201340","journal-title":"Math Soc Sci"},{"key":"371_CR2","unstructured":"Baluja S (1994) Population-based incremental learning. A method for integrating genetic search based function optimization and competitive learning. Tech rep"},{"issue":"2","key":"371_CR3","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00303169","volume":"6","author":"J Bartholdi","year":"1989","unstructured":"Bartholdi J, Tovey CA, Trick MA (1989) Voting schemes for which it can be difficult to tell who won the election. Soc Choice Welfare 6(2):157\u2013165","journal-title":"Soc Choice Welfare"},{"issue":"4","key":"371_CR4","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1162\/evco.1996.4.4.361","volume":"4","author":"T Blickle","year":"1996","unstructured":"Blickle T, Thiele L (1996) A comparison of selection schemes used in evolutionary algorithms. Evol Comput 4(4):361\u2013394","journal-title":"Evol Comput"},{"issue":"2","key":"371_CR5","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1109\/TEVC.2013.2260548","volume":"18","author":"J Ceberio","year":"2014","unstructured":"Ceberio J, Irurozki E, Mendiburu A, Lozano JA (2014) A distance-based ranking model estimation of distribution algorithm for the flowshop scheduling problem. IEEE Trans Evol Comput 18(2):286\u2013300","journal-title":"IEEE Trans Evol Comput"},{"key":"371_CR6","doi-asserted-by":"crossref","unstructured":"Ceberio J, Mendiburu A, Lozano JA (2011) Introducing the Mallows model on estimation of distribution algorithms. In: International Conference on Neural Information Processing, Springer, pp 461\u2013470","DOI":"10.1007\/978-3-642-24958-7_54"},{"key":"371_CR7","volume-title":"Theory of Convex Structures","author":"ML van De Vel","year":"1993","unstructured":"van De Vel ML (1993) Theory of Convex Structures, vol 50. Elsevier, Amsterdam"},{"key":"371_CR8","volume-title":"A Probabilistic Theory of Pattern Recognition","author":"L Devroye","year":"2013","unstructured":"Devroye L, Gy\u00f6rfi L, Lugosi G (2013) A Probabilistic Theory of Pattern Recognition, vol 31. Springer Science & Business Media, Berlin"},{"issue":"3","key":"371_CR9","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1162\/EVCO_a_00095","volume":"21","author":"C Echegoyen","year":"2013","unstructured":"Echegoyen C, Mendiburu A, Santana R, Lozano JA (2013) On the taxonomy of optimization problems under estimation of distribution algorithms. Evol Comput 21(3):471\u2013495","journal-title":"Evol Comput"},{"key":"371_CR10","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.tcs.2015.04.015","volume":"598","author":"C Echegoyen","year":"2015","unstructured":"Echegoyen C, Santana R, Mendiburu A, Lozano JA (2015) Comprehensive characterization of the behaviors of estimation of distribution algorithms. Theoret Comput Sci 598:64\u201386","journal-title":"Theoret Comput Sci"},{"issue":"2","key":"371_CR11","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s00355-011-0603-9","volume":"40","author":"P Emerson","year":"2013","unstructured":"Emerson P (2013) The original Borda count and partial voting. Soc Choice Welfare 40(2):353\u2013358","journal-title":"Soc Choice Welfare"},{"issue":"1","key":"371_CR12","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.jctb.2005.06.010","volume":"96","author":"YQ Feng","year":"2006","unstructured":"Feng YQ (2006) Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets. J Comb Theory, Series B 96(1):67\u201372","journal-title":"J Comb Theory, Series B"},{"issue":"3","key":"371_CR13","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1111\/j.2517-6161.1986.tb01420.x","volume":"48","author":"MA Fligner","year":"1986","unstructured":"Fligner MA, Verducci JS (1986) Distance based ranking models. J Roy Stat Soc: Ser B (Methodol) 48(3):359\u2013369","journal-title":"J Roy Stat Soc: Ser B (Methodol)"},{"key":"371_CR14","first-page":"465","volume":"12","author":"C Gonz\u00e1lez","year":"2000","unstructured":"Gonz\u00e1lez C, Lozano JA, Larra\u00f1aga P (2000) Analyzing the population based incremental learning algorithm by means of discrete dynamical systems. Complex Systems 12:465\u2013479","journal-title":"Complex Systems"},{"key":"371_CR15","doi-asserted-by":"crossref","unstructured":"Gonz\u00e1lez C, Lozano JA, Larra\u00f1aga P (2002) Mathematical modeling of discrete estimation of distribution algorithms. In: Estimation of Distribution Algorithms, Springer, pp 147\u2013163","DOI":"10.1007\/978-1-4615-1539-5_6"},{"issue":"4","key":"371_CR16","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1109\/4235.797971","volume":"3","author":"GR Harik","year":"1999","unstructured":"Harik GR, Lobo FG, Goldberg DE (1999) The compact genetic algorithm. IEEE Trans Evol Comput 3(4):287\u2013297","journal-title":"IEEE Trans Evol Comput"},{"issue":"1\/2","key":"371_CR17","doi-asserted-by":"publisher","first-page":"81","DOI":"10.2307\/2332226","volume":"30","author":"MG Kendall","year":"1938","unstructured":"Kendall MG (1938) A new measure of rank correlation. Biometrika 30(1\/2):81\u201393","journal-title":"Biometrika"},{"key":"371_CR18","doi-asserted-by":"crossref","unstructured":"Krejca MS, Witt C (2020) Theory of estimation-of-distribution algorithms. In: Theory of Evolutionary Computation, Springer, pp 405\u2013442","DOI":"10.1007\/978-3-030-29414-4_9"},{"key":"371_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-1539-5","volume-title":"Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation","author":"P Larra\u00f1aga","year":"2002","unstructured":"Larra\u00f1aga P, Lozano JA (2002) Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, vol 2. Springer Science & Business Media, Berlin"},{"issue":"1\/2","key":"371_CR20","doi-asserted-by":"publisher","first-page":"114","DOI":"10.2307\/2333244","volume":"44","author":"CL Mallows","year":"1957","unstructured":"Mallows CL (1957) Non-null ranking models. Biometrika 44(1\/2):114\u2013130","journal-title":"Biometrika"},{"key":"371_CR21","unstructured":"Meil\u0103 M, Phadnis K, Patterson A, Bilmes J (2007) Consensus ranking under the exponential model. In: Proceedings of the 23rd Conference on Uncertainty in Artificial Intelligence, pp 285\u2013294"},{"issue":"4","key":"371_CR22","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1162\/evco.1999.7.4.353","volume":"7","author":"H M\u00fchlenbein","year":"1999","unstructured":"M\u00fchlenbein H, Mahnig T (1999) FDA-A scalable evolutionary algorithm for the optimization of additively decomposed functions. Evol Comput 7(4):353\u2013376","journal-title":"Evol Comput"},{"key":"371_CR23","doi-asserted-by":"crossref","unstructured":"M\u00fchlenbein H, Paa G (1996) From recombination of genes to the estimation of distributions I. Binary parameters. In: International Conference on Parallel Problem Solving from Nature, Springer, pp 178\u2013187","DOI":"10.1007\/3-540-61723-X_982"},{"key":"371_CR24","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.cie.2019.02.017","volume":"130","author":"R P\u00e9rez-Rodr\u00edguez","year":"2019","unstructured":"P\u00e9rez-Rodr\u00edguez R, Hern\u00e1ndez-Aguirre A (2019) A hybrid estimation of distribution algorithm for the vehicle routing problem with time windows. Comput Ind Eng 130:75\u201396","journal-title":"Comput Ind Eng"},{"issue":"1","key":"371_CR25","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1162\/1063656053583414","volume":"13","author":"JL Shapiro","year":"2005","unstructured":"Shapiro JL (2005) Drift and scaling in estimation of distribution algorithms. Evol Comput 13(1):99\u2013123","journal-title":"Evol Comput"},{"key":"371_CR26","unstructured":"Sloane N The On-Line Encyclopedia of Integer Sequences. http:\/\/oeis.org"},{"key":"371_CR27","doi-asserted-by":"crossref","unstructured":"Sturm C (2009) M\u00e9moire sur la r\u00e9solution des \u00e9quations num\u00e9riques. In: Collected Works of Charles Fran\u00e7ois Sturm, Springer, pp. 345\u2013390","DOI":"10.1007\/978-3-7643-7990-2_29"},{"key":"371_CR28","unstructured":"Tsutsui S (2006) Node histogram vs. edge histogram: A comparison of probabilistic model-building genetic algorithms in permutation domains. In: Proceedings of the IEEE Conference on Evolutionary Computation CEC, IEEE, pp 1939\u20131946"},{"key":"371_CR29","doi-asserted-by":"crossref","unstructured":"Unanue I, Merino M, Lozano JA (2019) A mathematical analysis of EDAs with distance-based exponential models. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp 429\u2013430","DOI":"10.1145\/3319619.3321969"},{"key":"371_CR30","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/6229.001.0001","volume-title":"The Simple Genetic Algorithm: Foundations and Theory","author":"MD Vose","year":"1999","unstructured":"Vose MD (1999) The Simple Genetic Algorithm: Foundations and Theory, vol 12. MIT Press, Cambridge"},{"issue":"3","key":"371_CR31","first-page":"479","volume":"24","author":"F Wang","year":"2019","unstructured":"Wang F, Li Y, Zhou A, Tang K (2019) An estimation of distribution algorithm for mixed-variable newsvendor problems. IEEE Trans Evol Comput 24(3):479\u2013493","journal-title":"IEEE Trans Evol Comput"},{"key":"371_CR32","doi-asserted-by":"crossref","unstructured":"Witt C (2021) On crossing fitness valleys with majority-vote crossover and estimation-of-distribution algorithms. In: Proceedings of the 16th ACM\/SIGEVO Conference on Foundations of Genetic Algorithms, pp 1\u201315","DOI":"10.1145\/3450218.3477303"},{"issue":"1","key":"371_CR33","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1109\/TEVC.2003.819431","volume":"8","author":"Q Zhang","year":"2004","unstructured":"Zhang Q (2004) On stability of fixed points of limit models of univariate marginal distribution algorithm and factorized distribution algorithm. IEEE Trans Evol Comput 8(1):80\u201393","journal-title":"IEEE Trans Evol Comput"},{"issue":"2","key":"371_CR34","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1109\/TEVC.2003.820663","volume":"8","author":"Q Zhang","year":"2004","unstructured":"Zhang Q, M\u00fchlenbein H (2004) On the convergence of a class of estimation of distribution algorithms. IEEE Trans Evol Comput 8(2):127\u2013136","journal-title":"IEEE Trans Evol Comput"}],"container-title":["Memetic Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12293-022-00371-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12293-022-00371-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12293-022-00371-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,29]],"date-time":"2024-09-29T06:56:42Z","timestamp":1727593002000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12293-022-00371-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,16]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["371"],"URL":"https:\/\/doi.org\/10.1007\/s12293-022-00371-y","relation":{},"ISSN":["1865-9284","1865-9292"],"issn-type":[{"type":"print","value":"1865-9284"},{"type":"electronic","value":"1865-9292"}],"subject":[],"published":{"date-parts":[[2022,7,16]]},"assertion":[{"value":"14 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 July 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}