{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,25]],"date-time":"2026-08-25T10:08:36Z","timestamp":1787652516337,"version":"build-2736575974"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T00:00:00Z","timestamp":1702339200000},"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. Evol. Learn. Optim."],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>Global random search algorithms are characterized by using probability distributions to optimize problems. Among them, generative methods iteratively update the distributions by using the observations sampled. For instance, this is the case of the well-known Estimation of Distribution Algorithms. Although successful, this family of algorithms iteratively adopts numerical methods for estimating the parameters of a model or drawing observations from it. This is often a very time-consuming task, especially in permutation-based combinatorial optimization problems. In this work, we propose using a generative method, under the model-based gradient search framework, to optimize permutation-coded problems and address the mentioned computational overheads. To that end, the Plackett\u2013Luce model is used to define the probability distribution on the search space of permutations. Not limited to that, a parameter-free variant of the algorithm is investigated. Conducted experiments, directed to validate the work, reveal that the gradient search scheme produces better results than other analogous competitors, reducing the computational cost and showing better scalability.<\/jats:p>","DOI":"10.1145\/3628605","type":"journal-article","created":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T17:53:14Z","timestamp":1697824394000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Model-based Gradient Search for Permutation Problems"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7120-6338","authenticated-orcid":false,"given":"Josu","family":"Ceberio","sequence":"first","affiliation":[{"name":"University of the Basque Country UPV\/EHU, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1483-7998","authenticated-orcid":false,"given":"Valentino","family":"Santucci","sequence":"additional","affiliation":[{"name":"University for Foreigners of Perugia, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"e_1_3_3_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2018.8477774"},{"key":"e_1_3_3_3_1","doi-asserted-by":"publisher","DOI":"10.1162\/089976698300017746"},{"key":"e_1_3_3_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40137-4"},{"issue":"77","key":"e_1_3_3_5_1","first-page":"1","article-title":"Time for a change: A tutorial for comparing multiple classifiers through bayesian analysis","volume":"18","author":"Benavoli A.","year":"2017","unstructured":"A. Benavoli, G. Corani, J. Dem\u0161ar, and M. Zaffalon. 2017. Time for a change: A tutorial for comparing multiple classifiers through bayesian analysis. Journal of Machine Learning Research 18, 77 (2017), 1\u201336. Retrieved from http:\/\/jmlr.org\/papers\/v18\/16-305.html","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_3_6_1","volume-title":"Random Walks in Biology","author":"Berg H. C.","year":"1993","unstructured":"H. C. Berg. 1993. Random Walks in Biology. Princeton University Press."},{"key":"e_1_3_3_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45356-3_59"},{"key":"e_1_3_3_8_1","first-page":"287","volume-title":"Statistical Machine Learning and Combinatorial Optimization","author":"Berny A.","year":"2001","unstructured":"A. Berny. 2001. Statistical Machine Learning and Combinatorial Optimization. Springer Berlin, 287\u2013306."},{"key":"e_1_3_3_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3000905.3000948"},{"key":"e_1_3_3_10_1","doi-asserted-by":"publisher","DOI":"10.1162\/evco.1995.3.3.311"},{"key":"e_1_3_3_11_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015059928466"},{"key":"e_1_3_3_12_1","doi-asserted-by":"publisher","DOI":"10.2307\/2334029"},{"key":"e_1_3_3_13_1","unstructured":"E. Brochu V. M. Cora and N. de Freitas. 2010. A Tutorial on Bayesian Optimization of Expensive Cost Functions with Application to Active User Modeling and Hierarchical Reinforcement Learning. CoRR abs\/1012.2599 (2010). arXiv:1012.2599 http:\/\/arxiv.org\/abs\/1012.2599"},{"key":"e_1_3_3_14_1","doi-asserted-by":"publisher","DOI":"10.32614\/RJ-2016-017"},{"key":"e_1_3_3_15_1","volume-title":"Solving Permutation Problems with Estimation of Distribution Algorithms and Extensions Thereof","author":"Ceberio J.","year":"2014","unstructured":"J. Ceberio. 2014. Solving Permutation Problems with Estimation of Distribution Algorithms and Extensions Thereof. Ph. D. Dissertation. Faculty of Computer Science, University of the Basque Country (UPV\/EHU)."},{"key":"e_1_3_3_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2013.2260548"},{"key":"e_1_3_3_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-015-9740-x"},{"key":"e_1_3_3_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2013.6557609"},{"key":"e_1_3_3_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32937-1_8"},{"key":"e_1_3_3_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2496(91)90050-4"},{"key":"e_1_3_3_21_1","first-page":"i\u2013192","article-title":"Group representations in probability and statistics","volume":"11","author":"Diaconis P.","year":"1988","unstructured":"P. Diaconis. 1988. Group representations in probability and statistics. Lecture Notes-Monograph Series 11 (1988), i\u2013192. Retrieved from http:\/\/www.jstor.org\/stable\/4355560","journal-title":"Lecture Notes-Monograph Series"},{"key":"e_1_3_3_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCI.2006.329691"},{"key":"e_1_3_3_23_1","doi-asserted-by":"publisher","DOI":"10.5948\/UPO9781614440222"},{"issue":"3","key":"e_1_3_3_24_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 M. A.","year":"1986","unstructured":"M. A. Fligner and J. S. Verducci. 1986. Distance based ranking models. Journal of the Royal Statistical Society. Series B 48, 3 (1986), 359\u2013369.","journal-title":"Journal of the Royal Statistical Society. Series B"},{"key":"e_1_3_3_25_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1988.10478679"},{"key":"e_1_3_3_26_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY."},{"key":"e_1_3_3_27_1","unstructured":"N. Hansen. 2016. The CMA evolution strategy: A tutorial. CoRR abs\/1604.00772 (2016). arXiv:1604.00772 http:\/\/arxiv.org\/abs\/1604.00772"},{"key":"e_1_3_3_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICEC.1996.542381"},{"key":"e_1_3_3_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2016.7852234"},{"key":"e_1_3_3_30_1","doi-asserted-by":"publisher","DOI":"10.3150\/17-BEJ1017"},{"key":"e_1_3_3_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2738-0_3"},{"key":"e_1_3_3_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNN.1995.488968"},{"key":"e_1_3_3_33_1","unstructured":"D. P. Kingma and J. Ba. 2014. Adam: A method for stochastic optimization.arXiv:1412.6980. Retrieved from https:\/\/arxiv.org\/abs\/1412.6980"},{"key":"e_1_3_3_34_1","first-page":"2698","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Kleinberg B.","year":"2018","unstructured":"B. Kleinberg, Y. Li, and Y. Yuan. 2018. An alternative view: When does SGD escape local minima?. In Proceedings of the International Conference on Machine Learning. PMLR, 2698\u20132707."},{"key":"e_1_3_3_35_1","first-page":"3499","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Kool W.","year":"2019","unstructured":"W. Kool, H. Van Hoof, and M. Welling. 2019. Stochastic beams and where to find them: The gumbel-top-k trick for sampling sequences without replacement. In Proceedings of the International Conference on Machine Learning. PMLR, 3499\u20133508."},{"key":"e_1_3_3_36_1","volume-title":"Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation","author":"Larra\u00f1aga P.","year":"2001","unstructured":"P. Larra\u00f1aga and J. A. Lozano. 2001. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Springer Science & Business Media."},{"key":"e_1_3_3_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2020.100694"},{"key":"e_1_3_3_38_1","volume-title":"Individual Choice Behavior","author":"Luce R. D.","year":"1959","unstructured":"R. D. Luce. 1959. Individual Choice Behavior. Wiley, New York."},{"key":"e_1_3_3_39_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl632"},{"key":"e_1_3_3_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1967654.1967675"},{"key":"e_1_3_3_41_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/44.1-2.114"},{"key":"e_1_3_3_42_1","volume-title":"Analyzing and Modeling Rank Data","author":"Marden J. I.","year":"1996","unstructured":"J. I. Marden. 1996. Analyzing and Modeling Rank Data. CRC Press."},{"key":"e_1_3_3_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16729-4"},{"key":"e_1_3_3_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-010-9384-9"},{"key":"e_1_3_3_45_1","unstructured":"M. Meila K. Phadnis A. Patterson and J. A. Bilmes. 2012. Consensus ranking under the exponential model. In Proceedings of the 23rd Conference on Uncertainty in Artificial Intelligence (Vancouver BC Canada) (UAI\u201907). AUAI Press Arlington VA 285\u2013294."},{"key":"e_1_3_3_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02313422"},{"key":"e_1_3_3_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/3122009.3122027"},{"key":"e_1_3_3_48_1","doi-asserted-by":"publisher","DOI":"10.1162\/evco.1994.2.4.369"},{"key":"e_1_3_3_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58484-6_263"},{"issue":"10","key":"e_1_3_3_50_1","first-page":"193","article-title":"The analysis of permutations","volume":"24","author":"Plackett R. L.","year":"1975","unstructured":"R. L. Plackett. 1975. The analysis of permutations. Journal of the Royal Statistical Society 24, 10 (1975), 193\u2013202.","journal-title":"Journal of the Royal Statistical Society"},{"key":"e_1_3_3_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2022.3208110"},{"key":"e_1_3_3_52_1","doi-asserted-by":"crossref","unstructured":"S. Ruder. 2017. An overview of gradient descent optimization algorithms. CoRR abs\/1609.04747 (2016). arXiv:1609.04747 http:\/\/arxiv.org\/abs\/1609.04747","DOI":"10.1007\/978-3-662-46875-3_100836"},{"key":"e_1_3_3_53_1","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2019-1812"},{"key":"e_1_3_3_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2019.105998"},{"key":"e_1_3_3_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3377929.3398094"},{"key":"e_1_3_3_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36605-9_30"},{"key":"e_1_3_3_57_1","doi-asserted-by":"publisher","DOI":"10.1037\/h0070288"},{"key":"e_1_3_3_58_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2638566"},{"key":"e_1_3_3_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0014808"},{"key":"e_1_3_3_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2021.107533"},{"key":"e_1_3_3_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-011-3436-1"},{"key":"e_1_3_3_62_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:ANOR.0000039526.52305.af"}],"container-title":["ACM Transactions on Evolutionary Learning and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3628605","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3628605","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:03:44Z","timestamp":1750277024000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3628605"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,12]]},"references-count":61,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1145\/3628605"],"URL":"https:\/\/doi.org\/10.1145\/3628605","relation":{},"ISSN":["2688-299X","2688-3007"],"issn-type":[{"value":"2688-299X","type":"print"},{"value":"2688-3007","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,12]]},"assertion":[{"value":"2022-12-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-13","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-12","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}