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 the analysis.