揭示有效局部搜索的最小条件，证明局部寻优比盲目搜索更高效。
Minimal Conditions for Beneficial Neighbourhood Search and Local Descent
- 提出邻域局域性与接近最优时代价降低概率，支撑局部搜索优势
- 证明局部盲搜在达到目标代价t时，期望步数少于纯盲搜
- 实验表明越接近最优，越应尽早切换至局部下降策略
本文研究支持有益局部搜索所需的邻域性质。我们证明，邻域局域性以及趋向最优时代价降低的概率，足以保证在单步搜索中，通过邻居搜索找到改进解的概率高于盲目搜索，这是首个给出此类证明的研究。相关概念在可满足性问题和旅行商问题中得到验证。其次，针对给定代价目标t，研究了盲搜与局部下降结合的局部盲搜策略，并给出了多种条件下，使用局部盲搜达到优于t的代价所需期望步数小于盲搜的证明。实验表明，当目标代价t趋近最优时，局部盲搜应在更低的起始代价下切换至局部下降。
原文摘要 · Abstract (English)
This paper investigates what properties a neighbourhood requires to support beneficial local search. We show that neighbourhood locality, and a reduction in cost probability towards the optimum, support a proof that search among neighbours is more likely to find an improving solution in a single search step than blind search. This is the first paper to introduce such a proof. The concepts underlying these properties are illustrated on a satisfiability problem class, and on travelling salesman problems. Secondly, for a given cost target t, we investigate a combination of blind search and local descent termed local blind descent, and present various conditions under which the expected number of steps to reach a cost better than t using local blind descent, is proven to be smaller than with blind search. Experiments indicate that local blind descent, given target cost t, should switch to local descent at a starting cost that reduces as t approaches the optimum.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。