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 given an initialization method (random or greedy) cannot be extrapolated to other problems. Still, our results highlight the need for thorough experimentation and stress the importance of examining instance feature spaces and optimization landscapes to choose the best strategy for each problem and context, as no rule of thumb seems to exist for identifying the best local search strategy in the general case.

中文翻译：

---

第一次改进还是最佳改进？一项深入的本地搜索计算研究，以阐明支配地位主张


本地搜索方法从可行的解决方案开始，并通过连续的微小修改对其进行改进，直到遇到无法进一步改进的解决方案。它们是大多数元启发式方法的常见组成部分。存在两种基本的本地搜索策略：first-improvement 和 best-improvement。在这项工作中，我们使用一致的性能指标和严格的统计测试对几类测试问题进行深入的计算研究，考虑不同的初始化策略和邻域结构，以评估一种策略是否优于另一种策略。数值结果表明，先前在文献中报道的计算实验声称在给定初始化方法（随机或贪婪）的情况下，一种策略对 TSP 的主导地位，不能外推到其他问题。尽管如此，我们的结果强调了进行彻底实验的必要性，并强调了检查实例特征空间和优化环境以为每个问题和上下文选择最佳策略的重要性，因为在一般情况下，似乎不存在确定最佳本地搜索策略的经验法则。