Optimal algorithm re-initialization for combinatorial optimization

We propose a new iterative procedure to find the best time for re-initialization of meta-heuristic algorithms to solve combinatorial optimization problems. The sequence of algorithm executions with different random inizializations evolves at each iteration by either adding new independent executions or extending all existing ones up to the current maximum execution time. This is done on the basis of a criterion that uses a surrogate of the algorithm failure probability, where the optimal solution is replaced by the best so far one. Therefore, the new procedure can be applied in practice. We prove that, with probability one, the maximum time of current executions of the proposed procedure approaches, as the number of iterations diverges, the optimal value minimizing the expected time to find the solution. We apply the new procedure to several Traveling Salesman Problem instances with hundreds or thousands of cities, whose solution is known, and to some instances of a pseudo-Boolean problem. As base algorithm, we use different versions of an Ant Colony Optimization algorithm or a Genetic Algorithm. We compare the results from the proposed procedure with those from the base algorithm. This comparison shows that the failure probability estimated values of the new procedure are several orders of magnitude lower than those of the base algorithm for equal computation cost.