THERMOSTATISTICAL PERSISTENCY - A POWERFUL IMPROVING CONCEPT FOR SIMULATED ANNEALING ALGORITHMS

We propose a new heuristic method to solve 0-1 optimisation problems. Basically, the method is an extension of the simulated annealing algorithm. At a given temperature, approximations of the variable value expectations are computed. This information allows to fix the variables as the temperature decreases, so that the size of the problem is progressively reduced. It follows a significant improvement compared with pure simulated annealing: we obtain better solutions in less CPU time. Variable value expectations can be estimated by simulation procedures. In the special case of unconstrained 0-1 optimisation problems, estimates can be obtained by solving an analytic system. Two problems are examined: the travelling salesman problem and the minimisation of an unconstrained 0-1 quadratic function.