论文标题
迈向TSP模拟退火的平均病例运行时的下限
Towards a Lower Bound for the Average Case Runtime of Simulated Annealing on TSP
论文作者
论文摘要
我们分析了模拟退火（SA），以解决旅行销售人员问题的简单随机实例。我们的分析表明，Hajek理论上最佳的冷却时间表探索了远离全球最佳距离的解决方案集的成员。我们获得了SA在这些随机实例中获得的最终旅行的预期长度的下限。此外，我们还获得了其方差期望值的上限。这些界限假设描述SA的马尔可夫链是静止的，这种情况在实践中并非真正存在。因此，我们还制定了边界扩展到非平稳情况的条件。这些界限是通过将旅行长度分布与相关分布进行比较来获得的。此外，我们为这两个分布之间似乎存在的随机优势关系提供了数值证据，并在这个方向上提出了一个猜想。如果证明，此猜想意味着SA远离全局最佳距离，当执行任何子指数数量的迭代时，概率很高。这将表明SA至少需要呈指数式的许多迭代才能达到具有非趋势概率的全局最优值。
We analyze simulated annealing (SA) for simple randomized instances of the Traveling Salesperson Problem. Our analysis shows that the theoretically optimal cooling schedule of Hajek explores members of the solution set which are in expectation far from the global optimum. We obtain a lower bound on the expected length of the final tour obtained by SA on these random instances. In addition, we also obtain an upper bound on the expected value of its variance. These bounds assume that the Markov chain that describes SA is stationary, a situation that does not truly hold in practice. Hence, we also formulate conditions under which the bounds extend to the nonstationary case. These bounds are obtained by comparing the tour length distribution to a related distribution. We furthermore provide numerical evidence for a stochastic dominance relation that appears to exist between these two distributions, and formulate a conjecture in this direction. If proved, this conjecture implies that SA stays far from the global optimum with high probability when executed for any sub-exponential number of iterations. This would show that SA requires at least exponentially many iterations to reach a global optimum with nonvanishing probability.
