{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T21:59:45Z","timestamp":1757627985325,"version":"3.44.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T00:00:00Z","timestamp":1756425600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T00:00:00Z","timestamp":1756425600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["PRC - AAPG 2023 - Axe E.2 - CE23"],"award-info":[{"award-number":["PRC - AAPG 2023 - Axe E.2 - CE23"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Universit\u00e9 d'Angers"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>This paper explores a novel approach aimed at overcoming existing challenges in the realm of local search algorithms. Our aim is to improve the decision process that takes place within a local search algorithm so as to make the best possible transitions in the neighborhood at each iteration. To improve this process, we propose to use a neural network that has the same input information as conventional local search algorithms. In this paper, which is an extension of the work presented at EvoCOP2024, we investigate different ways of representing this information so as to make the algorithm as efficient as possible but also robust to monotonic transformations of the problem objective function. To assess the efficiency of this approach, we develop an experimental setup centered around NK landscape problems, offering the flexibility to adjust problem size and ruggedness. This approach offers a promising avenue for the emergence of new local search algorithms and the improvement of their problem-solving capabilities for black-box problems.<\/jats:p>","DOI":"10.1007\/s42979-025-04279-5","type":"journal-article","created":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T12:07:05Z","timestamp":1756469225000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Discovering New Robust Local Search Algorithms with Neuro-Evolution"],"prefix":"10.1007","volume":"6","author":[{"given":"Mohamed Salim","family":"Amri Sakhri","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adrien","family":"Go\u00ebffon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7040-5052","authenticated-orcid":false,"given":"Olivier","family":"Goudet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fr\u00e9d\u00e9ric","family":"Saubion","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cha\u00efma\u00e2","family":"Touhami","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,29]]},"reference":[{"key":"4279_CR1","unstructured":"Hoos HH, St\u00fctzle T. Stochastic local search: foundations and applications. 2004."},{"issue":"10","key":"4279_CR2","doi-asserted-by":"publisher","first-page":"3143","DOI":"10.1016\/j.cor.2005.11.022","volume":"34","author":"T Schiavinotto","year":"2007","unstructured":"Schiavinotto T, St\u00fctzle T. A review of metrics on permutations for search landscape analysis. Comput Oper Res. 2007;34(10):3143\u201353.","journal-title":"Comput Oper Res"},{"key":"4279_CR3","doi-asserted-by":"publisher","first-page":"688","DOI":"10.1016\/j.asoc.2015.01.047","volume":"30","author":"M Basseur","year":"2015","unstructured":"Basseur M, Go\u00ebffon A. Climbing combinatorial fitness landscapes. Appl Soft Comput. 2015;30:688\u2013704.","journal-title":"Appl Soft Comput"},{"key":"4279_CR4","first-page":"184","volume":"95","author":"T Jones","year":"1995","unstructured":"Jones T, Forrest S, et al. Fitness distance correlation as a measure of problem difficulty for genetic algorithms. ICGA. 1995;95:184\u201392.","journal-title":"ICGA"},{"issue":"1","key":"4279_CR5","volume":"2020","author":"O Vuculescu","year":"2020","unstructured":"Vuculescu O, Pedersen MK, Sherson JF, Bergenholtz C. Human search in a fitness landscape: how to assess the difficulty of a search problem. Complexity. 2020;2020(1): 780216.","journal-title":"Complexity"},{"key":"4279_CR6","doi-asserted-by":"crossref","unstructured":"Whitley D. Mk landscapes, NK landscapes, MAX-kSAT: a proof that the only challenging problems are deceptive. In: Proceedings of the 2015 annual conference on genetic and evolutionary computation. 2015. p. 927\u201334.","DOI":"10.1145\/2739480.2754809"},{"issue":"3","key":"4279_CR7","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","volume":"1","author":"F Glover","year":"1989","unstructured":"Glover F. Tabu search part i. ORSA J Comput. 1989;1(3):190\u2013206.","journal-title":"ORSA J Comput"},{"key":"4279_CR8","doi-asserted-by":"crossref","unstructured":"Louren\u00e7o HR, Martin OC, St\u00fctzle T. Iterated local search. In: Handbook of metaheuristics. Springer; 2003. p. 320\u201353.","DOI":"10.1007\/0-306-48056-5_11"},{"issue":"2","key":"4279_CR9","doi-asserted-by":"publisher","first-page":"40","DOI":"10.3390\/a14020040","volume":"14","author":"KM Malan","year":"2021","unstructured":"Malan KM. A survey of advances in landscape analysis for optimisation. Algorithms. 2021;14(2):40.","journal-title":"Algorithms"},{"key":"4279_CR10","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1007\/978-1-4419-1153-7_1167","volume":"62","author":"K S\u00f6rensen","year":"2013","unstructured":"S\u00f6rensen K, Glover F. Metaheuristics. Encyclopedia of Operations Research and Management Science. 2013;62:960\u201370.","journal-title":"Encyclopedia of Operations Research and Management Science"},{"issue":"1","key":"4279_CR11","doi-asserted-by":"publisher","first-page":"3","DOI":"10.3233\/IDA-2008-12102","volume":"12","author":"E \u00d6zcan","year":"2008","unstructured":"\u00d6zcan E, Bilgin B, Korkmaz EE. A comprehensive analysis of hyper-heuristics. Intell Data Anal. 2008;12(1):3\u201323.","journal-title":"Intell Data Anal"},{"issue":"6","key":"4279_CR12","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1145\/3459664","volume":"54","author":"E Talbi","year":"2022","unstructured":"Talbi E. Machine learning into metaheuristics: a survey and taxonomy. ACM Comput Surv. 2022;54(6):129\u2013112932.","journal-title":"ACM Comput Surv"},{"issue":"2","key":"4279_CR13","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/2076450.2076469","volume":"55","author":"HH Hoos","year":"2012","unstructured":"Hoos HH. Programming by optimization. Commun ACM. 2012;55(2):70\u201380.","journal-title":"Commun ACM"},{"issue":"2","key":"4279_CR14","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1016\/j.ejor.2021.04.032","volume":"296","author":"MK Mamaghan","year":"2022","unstructured":"Mamaghan MK, Mohammadi M, Meyer P, Karimi-Mamaghan AM, Talbi E. Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: a state-of-the-art. Eur J Oper Res. 2022;296(2):393\u2013422.","journal-title":"Eur J Oper Res"},{"key":"4279_CR15","doi-asserted-by":"crossref","unstructured":"Trafalis TB, Kasap S. Neural networks for combinatorial optimization. In: Floudas CA, Pardalos PM, editors. Encyclopedia of optimization, 2nd ed. 2009. p. 2547\u201355.","DOI":"10.1007\/978-0-387-74759-0_439"},{"key":"4279_CR16","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1073\/pnas.79.8.2554","volume":"79","author":"J Hopfield","year":"1982","unstructured":"Hopfield J. Neural networks and physical systems with emergent collective computational abilities. Proc Natl Acad Sci USA. 1982;79:2554\u20138.","journal-title":"Proc Natl Acad Sci USA"},{"key":"4279_CR17","first-page":"130","volume":"24","author":"Q Cappart","year":"2023","unstructured":"Cappart Q, Ch\u00e9telat D, Khalil EB, Lodi A, Morris C, Velickovic P. Combinatorial optimization and reasoning with graph neural networks. J Mach Learn Res. 2023;24:130\u2013113061.","journal-title":"J Mach Learn Res"},{"key":"4279_CR18","unstructured":"Hudson B, Li Q, Malencia M, Prorok A. Graph neural network guided local search for the traveling salesperson problem. In: The 10th international conference on learning representations, ICLR 2022, Virtual Event, April 25\u201329, 2022."},{"key":"4279_CR19","doi-asserted-by":"crossref","unstructured":"Willmes L, B\u00e4ck T, Jin Y, Sendhoff B. Comparing neural networks and kriging for fitness approximation in evolutionary optimization. In: Proceedings of the IEEE congress on evolutionary computation, CEC 2003, Canberra, December 8\u201312, 2003. IEEE; 2003. p. 663\u201370.","DOI":"10.1109\/CEC.2003.1299639"},{"key":"4279_CR20","doi-asserted-by":"crossref","unstructured":"Santana \u00cd, Lodi A, Vidal T. Neural networks for local search and crossover in vehicle routing: a possible overkill? In: Cir\u00e9 AA, editor. Integration of constraint programming, artificial intelligence, and operations research\u201420th international conference, CPAIOR 2023, Nice, May 29\u2013June 1, 2023, Proceedings. Lecture Notes in Computer Science, vol 13884. 2023. p. 184\u201399.","DOI":"10.1007\/978-3-031-33271-5_13"},{"key":"4279_CR21","doi-asserted-by":"crossref","unstructured":"Falkner JK, Thyssens D, Bdeir A, Schmidt-Thieme L. Learning to control local search for combinatorial optimization. In: Amini M, Canu S, Fischer A, Guns T, Novak PK, Tsoumakas G, editors. Machine learning and knowledge discovery in databases\u2014European conference, ECML PKDD 2022, Grenoble, September 19\u201323, 2022, Proceedings, Part V. Lecture Notes in Computer Science, vol 13717. 2022. p. 361\u201376.","DOI":"10.1007\/978-3-031-26419-1_22"},{"key":"4279_CR22","doi-asserted-by":"crossref","unstructured":"Veerapen N, Hamadi Y, Saubion F. Using local search with adaptive operator selection to solve the progressive party problem. In: Proceedings of the IEEE congress on evolutionary computation, CEC 2013, Cancun, 2013. p. 554\u201361.","DOI":"10.1109\/CEC.2013.6557617"},{"key":"4279_CR23","doi-asserted-by":"crossref","unstructured":"Lange R, Schaul T, Chen Y, Lu C, Zahavy T, Dalibard V, Flennerhag S. Discovering attention-based genetic algorithms via meta-black-box optimization. In: Proceedings of the genetic and evolutionary computation conference. 2023. p. 929\u201337.","DOI":"10.1145\/3583131.3590496"},{"key":"4279_CR24","doi-asserted-by":"crossref","unstructured":"Lange R, Schaul T, Chen Y, Zahavy T, Dalibard V, Lu C, Singh S, Flennerhag S. Discovering evolution strategies via meta-black-box optimization. In: Proceedings of the companion conference on genetic and evolutionary computation. 2023. p. 29\u201330.","DOI":"10.1145\/3583133.3595822"},{"issue":"2","key":"4279_CR25","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0022-5193(89)80019-0","volume":"141","author":"SA Kauffman","year":"1989","unstructured":"Kauffman SA, Weinberger ED. The NK model of rugged fitness landscapes and its application to maturation of the immune response. J Theor Biol. 1989;141(2):211\u201345.","journal-title":"J Theor Biol"},{"key":"4279_CR26","doi-asserted-by":"crossref","unstructured":"Goudet O, Amri\u00a0Sakhri MS, Go\u00ebffon A, Saubion F. Emergence of new local search algorithms with neuro-evolution. In: European conference on evolutionary computation in combinatorial optimization (Part of EvoStar). Springer; 2024. p. 33\u201348.","DOI":"10.1007\/978-3-031-57712-3_3"},{"issue":"2","key":"4279_CR27","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1162\/106365601750190398","volume":"9","author":"N Hansen","year":"2001","unstructured":"Hansen N, Ostermeier A. Completely derandomized self-adaptation in evolution strategies. Evol Comput. 2001;9(2):159\u201395.","journal-title":"Evol Comput"},{"key":"4279_CR28","doi-asserted-by":"crossref","unstructured":"M\u00fcller N, Glasmachers T. Challenges in high-dimensional reinforcement learning with evolution strategies. In: Parallel problem solving from nature\u2014PPSN XV: 15th international conference, Coimbra, September 8\u201312, 2018, Proceedings, Part II 15. Springer; 2018. p. 411\u201323.","DOI":"10.1007\/978-3-319-99259-4_33"},{"key":"4279_CR29","doi-asserted-by":"crossref","unstructured":"Ochoa G, Verel S, Tomassini M. First-improvement vs. best-improvement local optima networks of NK landscapes. In: International conference on parallel problem solving from nature. Springer; 2010. p. 104\u201313.","DOI":"10.1007\/978-3-642-15844-5_11"},{"key":"4279_CR30","doi-asserted-by":"crossref","unstructured":"Basseur M, Go\u00ebffon A. Hill-climbing strategies on various landscapes: an empirical comparison. In: Proceedings of the 15th annual conference on genetic and evolutionary computation. 2013. p. 479\u201386.","DOI":"10.1145\/2463372.2463439"},{"key":"4279_CR31","doi-asserted-by":"crossref","unstructured":"Beyer H-G. The theory of evolution strategies. 2001.","DOI":"10.1007\/978-3-662-04378-3"},{"key":"4279_CR32","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/s11047-020-09822-2","volume":"20","author":"S Tari","year":"2021","unstructured":"Tari S, Basseur M, Go\u00ebffon A. On the use of (1, $$\\lambda$$)-evolution strategy as efficient local search mechanism for discrete optimization: a behavioral analysis. Nat Comput. 2021;20:345\u201361.","journal-title":"Nat Comput"},{"key":"4279_CR33","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.2559634","author":"N Hansen","year":"2019","unstructured":"Hansen N, Akimoto Y, Baudis P. CMA-ES\/pycma on Github. Zenodo. 2019. https:\/\/doi.org\/10.5281\/zenodo.2559634.","journal-title":"Zenodo"},{"key":"4279_CR34","doi-asserted-by":"crossref","unstructured":"Tari S, Verel S, Omidvar, M. Pubo i: a tunable benchmark with variable importance. In: C\u00e1ceres LP, Verel S, editors. Evolutionary computation in combinatorial optimization\u201422nd European conference, EvoCOP 2022, Held as Part of EvoStar 2022, Madrid, April 20\u201322, 2022, Proceedings. Lecture notes in computer science, vol 13222. 2022. p. 175\u201390.","DOI":"10.1007\/978-3-031-04148-8_12"}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-025-04279-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-025-04279-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-025-04279-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T05:31:32Z","timestamp":1757482292000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-025-04279-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,29]]},"references-count":34,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2025,10]]}},"alternative-id":["4279"],"URL":"https:\/\/doi.org\/10.1007\/s42979-025-04279-5","relation":{},"ISSN":["2661-8907"],"issn-type":[{"type":"electronic","value":"2661-8907"}],"subject":[],"published":{"date-parts":[[2025,8,29]]},"assertion":[{"value":"22 August 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 August 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 August 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all authors, the corresponding author, Olivier Goudet, states that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Research involving human and\/or animals"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Informed consent"}}],"article-number":"780"}}