G-2024-47
First-improvement or best-improvement? An in-depth local search computational study to elucidate a dominance claim
, , , and BibTeX reference
Local search methods start from a feasible solution and improve it by successive minor modifications until a solution that cannot be further improved is encountered. They are a common component of most metaheuristics. Two fundamental local search strategies exist: first-improvement and best-improvement. In this work, we perform an in-depth computational study using consistent performance metrics and rigorous statistical tests on several classes of test problems considering different initialization strategies and neighborhood structures to evaluate whether one strategy is dominant over the other. The numerical results show that computational experiments previously reported in the literature claiming the dominance of one strategy over the other for the TSP can not be extrapolated to other problems. Still, our results reinforce the need for extensive experimentation to decide the most appropriate strategy for each specific problem and context since a rule of thumb does not seem to exist for deciding which local search strategy is the best in the general case.
Published August 2024 , 20 pages
Research Axes
Research applications
Document
G2447.pdf (500 KB)