A method for evaluating the effectively global exploration in the cost space is introduced and the result is used for an adaptive stopping criterion in optimization by local search heuristics. As an example, an adaptive cooling schedule in simulated annealing (SA) is properly designed and its performance is empirically examined on the Euclidean traveling salesman problem. The present adaptive SA outperforms a conventional non‐adaptive one both in quality and in stability. The performance seems to be affected by the total number of search steps and by the final temperature; the parameters used for an conventional standard design of cooling schedule seem to influence the performance indirectly, only through the former two factors. © 2004 American Institute of Physics