Analysis of Random Restart and Iterated Improvement for Global Optimization with Application to the Traveling Salesman Problem

The optimization method employing iterated improvement with random restart (I2R2) is studied. Associated with each instance of an I2R2 search is a fundamental polynomial, $$f(x) - o_{0}x + p_{1}x^{2} + \cdots + p_{d}x^{d+1} - 1,$$ in which the coefficient p k is the probability of starting a search k improvement steps from a local minimum. The positive root η of f can be used to calculate the convergence and speedup properties of that instance. Since the coefficients of f are naturally related to the search, it is possible to estimate them online if an a priori estimate of the size θ of the goal basin is available, for example by analysis or prior experience. In this case, the runtime statistical estimate of η converges many times faster than the estimates of the coefficients themselves. The foregoing is illustrated with an application to the traveling salesman problem (TSP) using the k-change as the improvement discipline. Among other things, it is shown that a k-change improvement can be affected by k 2-changes, that θ =1 for convex city sets, and that good estimates of θ can be made from a reduced TSP related to the given one.