随机算法重启策略的构造及其在TSP中的应用

NP难解问题是计算机算法和理论界长期研究的课题。在求实NP难解问题时，随机算法的性能往往很不稳定。在以往的实验中，人们发现基于重启的优化方法可以提高Las Vegas算法的性能和稳定性。尽管它的思想比较直观，但对它的性能进行理论分析却并不容易，这在很大程度上限制了其应用。该文使用连续概率分布对算法性能分布建模，针对Las Vegas算法提出了一种高效的重启策略构造方法。该文从平均性能和稳定性两个角度分析了该方法的效率，同时通过将其应用于求解大规模旅行商问题（TSP）显示了其应用价值。

Designing Restart Strategy for Randomized Algorithms and Its Application in Solving the TSP

This paper focuses on improving the performance of randomized algorithms by exploiting the properties of their performance distributions. In previous research, it is found that strategies based on restart can dramatically improve the performance and stability of Las Vegas algorithms in many cases. Though this idea is rather simple, it is difficult to analyze their performance.This will greatly limit the application of restart strategies. In this paper, continuous probability functions are used to model the performance distribution of randomized algorithms, and an efficient designing method of restart strategy for Las Vegas algorithms is proposed. It is pointed out that if the performance of a randomized algorithm can be approximated by the lognormal distribution model, then the peak point of this distribution will be the best choice for setting restart period. The efficiency of this strategy is analyzed considering both the average performance and the stability. Experimental results in solving large traveling salesman problems (TSP) also verify our analysis.