Temperature control for simulated annealing

Area of Science:

• Computational physics
• Statistical mechanics
• Optimization algorithms

Background:

• Simulated annealing is a probabilistic technique for approximating the global optimum of a given function.
• Determining an optimal cooling schedule is crucial for the efficiency and effectiveness of simulated annealing.
• Understanding the thermodynamic properties, such as entropy production, is key to analyzing annealing processes.

Purpose of the Study:

• To formulate an optimal cooling schedule for simulated annealing.
• To derive a differential equation governing the time-dependent temperature T(t).
• To investigate the long-term behavior of temperature, entropy production, and Kullback-Leibler entropy within this framework.

Main Methods:

• Formulation of a differential equation for the time-dependent temperature T(t) based on an optimal cooling schedule.
• Analysis of the derived differential equation to study the asymptotic behavior of T(t).
• Application of the methodology to specific examples, including a many-level system and the traveling salesman problem.

Main Results:

• An explicit time dependence for the temperature T(t) was obtained for the studied examples.
• The long-term behavior of temperature, entropy production, and Kullback-Leibler entropy were analyzed.
• Insights into simulated annealing based on Tsallis statistics were provided.

Conclusions:

• The derived differential equation provides a framework for understanding the dynamics of simulated annealing.
• The explicit solutions for T(t) in specific cases validate the proposed cooling schedule.
• The study offers a theoretical basis for optimizing simulated annealing and exploring its connection to non-extensive statistical mechanics.