Simulated Annealing (SA)

Simulated Annealing (SA) is a local search algorithm that tries to avoid converging to a local optimum by sometimes accepting worse solutions. The probability to accept worse solutions declines over time based on a temperature schedule. At any point in time, the search has a so-called “temperature.” The higher the temperature, the more likely it is to accept a worse solution. Also, a worse solution is more likely to be accepted if its objective value is not much worse than the current solution. The temperature declines over time, usually in an exponential manner. We can consider SA as a randomized local search (RLS) to which the temperature-based acceptance was added.

Publications

• Sarah Louise Thomson, Gabriela Ochoa, Daan van den Berg, Tianyu LIANG (梁天宇), and Thomas Weise (汤卫思): Entropy, Search Trajectories, and Explainability for Frequency Fitness Assignment. 18th International Conference on Parallel Problem Solving from Nature (PPSN XVIII), September 14-18, 2024, Hagenberg, Austria, pages 377-392. Lecture Notes in Computer Science (LNCS), volume 15148. Berlin/Heidelberg, Germany: Springer.
  RLS, FFA, SA, local search, moptipy, Python, SA, more infos.
• Tianyu LIANG (梁天宇), Zhize WU (吴志泽), Jörg Lässig, Daan van den Berg, Sarah Louise Thomson, and Thomas Weise (汤卫思): Addressing the Traveling Salesperson Problem with Frequency Fitness Assignment and Hybrid Algorithms. Soft Computing 28(17-18):9495-9508. September 2024.
  TSP, logistics, RLS, FFA, local search, SA, moptipy, Python, more infos.