A framework for analyzing sub-optimal performance of local search algorithms

DOI10.1007/S10589-009-9290-1MaRDI QIDQ548682zbMATH OpenOpenAlexFDO

Authors Alexander G. Nikolaev, Shane N. Hall, Darrall Henderson, Sheldon H. Jacobson

Publication date 30 June 2011

Published in Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10589-009-9290-1

zbMATH Keywords

simulated annealingconvergencetabu searchtravelling salesman problemLin-Kernighan-Helsgaun algorithmfinite-time performance

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Integer programming (90C10)

Recommendations

• Using Markov chains to analyze the effectiveness of local search algorithms
• Visiting near-optimal solutions using local search algorithms
• scientific article; zbMATH DE number 1054958
• Analyzing the performance of local search algorithms using generalized hill climbing algorithms
• Theoretical aspects of local search.

Cites work

• scientific article; zbMATH DE number 3770836 (Why is no real title available?)
• scientific article; zbMATH DE number 3638844 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1016966 (Why is no real title available?)
• scientific article; zbMATH DE number 1062113 (Why is no real title available?)
• scientific article; zbMATH DE number 3305564 (Why is no real title available?)
• A class of convergent generalized hill climbing algorithms
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• An empirical study of a new metaheuristic for the traveling salesman problem
• Finite-time performance analysis of static simulated annealing algorithms
• Handbook of metaheuristics
• On the convergence of generalized hill climbing algorithms
• Stochastic local search. Foundations and applications.
• TSPLIB—A Traveling Salesman Problem Library
• Tabu search performance on the symmetric travelling salesman problem
• The Theory and Practice of Simulated Annealing
• Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing
• Using Markov chains to analyze the effectiveness of local search algorithms

Cited in

(8)

• Visiting near-optimal solutions using local search algorithms
• ParadisEO-MO: from fitness landscape analysis to efficient local search algorithms
• On the analysis of trajectory-based search algorithms: when is it beneficial to reject improvements?
• Subthreshold-seeking local search
• Using Markov chains to analyze the effectiveness of local search algorithms
• Analyzing the complexity of finding good neighborhood functions for local search algorithms
• An experimental analysis of local minima to improve neighbourhood search.
• Analyzing the performance of local search algorithms using generalized hill climbing algorithms

Describes a project that uses

Uses Software

• Tabu search
• LKH
• TSPLIB

This page was built for publication: A framework for analyzing sub-optimal performance of local search algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q548682)