# Discovering new robust local search algorithms with neuro-evolution

arXiv: https://arxiv.org/abs/2501.04747 · HTML: https://mlsanity.com/paper/2501.04747/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 39 references that are in the map.
- First posted on arXiv 8 Jan 2025.

## Builds on (most cited first, 7 of 7)

- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Graph Neural Network Guided Local Search for the Traveling Salesperson Problem](https://mlsanity.com/paper/2110.05291/) (2021)
- [Discovering Evolution Strategies via Meta-Black-Box Optimization](https://mlsanity.com/paper/2211.11260/) (2022)
- [Discovering Attention-Based Genetic Algorithms via Meta-Black-Box Optimization](https://mlsanity.com/paper/2304.03995/) (2023)
- [Learning to Control Local Search for Combinatorial Optimization](https://mlsanity.com/paper/2206.13181/) (2022)
- [Challenges in High-dimensional Reinforcement Learning with Evolution Strategies](https://mlsanity.com/paper/1806.01224/) (2018)
- [Neural Networks for Local Search and Crossover in Vehicle Routing: A Possible Overkill?](https://mlsanity.com/paper/2210.12075/) (2022)

## Abstract (arXiv)

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. The last version of this article is published in the journal SN Computer Science (Springer).