# EB-GLS: An Improved Guided Local Search Based on the Big Valley Structure

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Sep 2017.

## Built on by (most cited first, 6 of 6)

- [Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model](https://mlsanity.com/paper/2401.02051/) (2024)
- [In-the-loop Hyper-Parameter Optimization for LLM-Based Automated Design of Heuristics](https://mlsanity.com/paper/2410.16309/) (2024)
- [Generalizable Heuristic Generation Through LLMs with Meta-Optimization](https://mlsanity.com/paper/2505.20881/) (2025)
- [A New Parallel Cooperative Landscape Smoothing Algorithm and Its Applications on TSP and UBQP](https://mlsanity.com/paper/2401.03237/) (2024)
- [Using Multi-modal Large Language Model to Boost Fireworks Algorithm's Ability in Settling Challenging Optimization Tasks](https://mlsanity.com/paper/2511.03137/) (2025)
- [RouteRepair: Instance-Level Failure Diagnosis and Targeted Repair in LLM-Based Automated Heuristic Design for Routing Optimization](https://mlsanity.com/paper/2609.11452/) (2026)

## Abstract (arXiv)

Local search is a basic building block in memetic algorithms. Guided Local Search (GLS) can improve the efficiency of local search. By changing the guide function, GLS guides a local search to escape from locally optimal solutions and find better solutions. The key component of GLS is its penalizing mechanism which determines which feature is selected to penalize when the search is trapped in a locally optimal solution. The original GLS penalizing mechanism only makes use of the cost and the current penalty value of each feature. It is well known that many combinatorial optimization problems have a big valley structure, i.e., the better a solution is, the more the chance it is closer to a globally optimal solution. This paper proposes to use big valley structure assumption to improve the GLS penalizing mechanism. An improved GLS algorithm called Elite Biased GLS (EB-GLS) is proposed. EB-GLS records and maintains an elite solution as an estimate of the globally optimal solutions, and reduces the chance of penalizing the features in this solution. We have systematically tested the proposed algorithm on the symmetric traveling salesman problem. Experimental results show that EB-GLS is significantly better than GLS.