On the Use of Second Order Neighbors to Escape from Local Optima

E. Contreras-Torres, L. Hernando, M. Torralbo, J. A. Lozano

Designing efficient local search based algorithms requires to consider the specific properties of the problems. We introduce a simple and efficient strategy, the Extended Reach, that escapes from local optima obtained from a best improvement local search and apply it to different combinatorial optimization problems. This strategy is based on two landscape properties. First, it considers that a local optimum is usually located in the frontier of its own attraction basin, and thus, it is enough to inspect the second order neighbors to reach a solution inside an attraction basin of a better local optimum. Second, we extend previous results used to discard solutions without the need of being evaluated. Efficient ways of evaluating the second order neighbors are also presented, reducing significantly the computation cost. Experimental results on random and benchmark instances show that our strategy, indeed, escapes from local optima despite its simplicity.

Keywords: Combinatorial optimization, local search algorithms, local optima, attraction basins.

Scheduled

Heuristics and Metaheuristics
November 10, 2023  4:00 PM
CC3: Room 1

P-NP Decomposition of the Linear Ordering Problem: Landscape Analysis and Applications

X. Benavides Canta, J. Ceberio, J. A. Lozano, L. Hernando

Matheurística basada en la búsqueda local aplicada a un problema de ruteo de vehículos de recogida y entrega en el contexto de salud en casa.

I. Pemberthy, J. C. Rivera, C. Jussien Guéret, H. Al Hasan