  We propose a new iterative procedure to optimize the restart for
meta-heuristic algorithms to solve combinatorial optimization, which uses
independent algorithm executions. The new procedure consists of either adding
new executions or extending along time the existing ones. 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, it can be applied in practice. We prove that, with probability one,
the restart time of the proposed procedure approaches, as the number of
iterations diverges, the optimal value that minimizes the expected time to find
the solution. We apply the proposed restart procedure to several Traveling
Salesman Problem instances with hundreds or thousands of cities. As basic
algorithm, we used different versions of an Ant Colony Optimization algorithm.
We compare the results from the restart procedure with those from the basic
algorithm. This is done by considering the failure probability of the two
approaches for equal computation cost. This comparison showed a significant
gain when applying the proposed restart procedure, whose failure probability is
several orders of magnitude lower.
