Idioma:

Delayed improvement local search

Amaral, Heber F. ; Urrutia, Sebastián ; Hvattum, Lars M.

Journal of heuristics, 2021-10, Vol.27 (5), p.923-950 [Periódico revisado por pares]

New York: Springer US

Texto completo disponível

Citações Citado por

Enviar para

Título:
Delayed improvement local search
Autor: Amaral, Heber F. ; Urrutia, Sebastián ; Hvattum, Lars M.
Assuntos: Algorithms ; Artificial Intelligence ; Calculus of Variations and Optimal Control; Optimization ; Heuristic methods ; Integer programming ; Iterative methods ; Linear programming ; Management Science ; Mathematics ; Mathematics and Statistics ; Neighborhoods ; Operations Research ; Operations Research/Decision Theory ; Search methods ; Traveling salesman problem
É parte de: Journal of heuristics, 2021-10, Vol.27 (5), p.923-950
Descrição: Local search is a fundamental tool in the development of heuristic algorithms. A neighborhood operator takes a current solution and returns a set of similar solutions, denoted as neighbors. In best improvement local search, the best of the neighboring solutions replaces the current solution in each iteration. On the other hand, in first improvement local search, the neighborhood is only explored until any improving solution is found, which then replaces the current solution. In this work we propose a new strategy for local search that attempts to avoid low-quality local optima by selecting in each iteration the improving neighbor that has the fewest possible attributes in common with local optima. To this end, it uses inequalities previously used as optimality cuts in the context of integer linear programming. The novel method, referred to as delayed improvement local search, is implemented and evaluated using the travelling salesman problem with the 2-opt neighborhood and the max-cut problem with the 1-flip neighborhood as test cases. Computational results show that the new strategy, while slower, obtains better local optima compared to the traditional local search strategies. The comparison is favourable to the new strategy in experiments with fixed computation time or with a fixed target.
Editor: New York: Springer US
Idioma: Inglês

Voltar para lista de resultados

Realização: Logos de Redes Sociais:

Delayed improvement local search

Amaral, Heber F. ; Urrutia, Sebastián ; Hvattum, Lars M.

New York: Springer US

Buscando em bases de dados remotas. Favor aguardar.