an introduction to Simulated Annealing

Simulated Annealing is a probability-based algorithm used for global optimization, inspired by the process of metal annealing.
It simulates the changes in the atomic state of metals during the cooling process after being heated.
Throughout the search process, the algorithm is controlled by a temperature parameter. When the temperature is very high, the algorithm may accept worse solutions rather than better ones. As the temperature decreases, it increasingly prefers better solutions.

The algorithm can be described as follows:

1. Initialization:
- Initial solution x
- Initial temperature T = T0
- Cooling coefficient α (0 < α < 1)
- Minimum temperature Tmin



2. while T > Tmin:
 for i = 1 to k (number of iterations per temperature):
 Generate new solution x' = neighbor(x)
 Calculate energy change ΔE = f(x') - f(x)
 if ΔE < 0:
 Accept new solution x = x'
 else:
 Accept x = x' with probability exp(-ΔE/T)
 Cool down T = α * T



3. Return the best solution found

A new solution is always accepted when ΔE < 0, meaning the algorithm is moving downhill.

Otherwise, it is attempting to move uphill.

This uphill move is accepted on the condition that a uniformly distributed random number in the interval [0, 1] is less than exp(-ΔE / T).

import math

import random

def simulated_annealing(initial_solution, cost_func, neighbor_func, T0, alpha, Tmin):

    current = initial_solution

    current_cost = cost_func(current)

    T = T0



    while T > Tmin:

        for _ in range(100):  # Number of iterations per temperature

            new_solution = neighbor_func(current)

            new_cost = cost_func(new_solution)

            delta = new_cost - current_cost



            if delta < 0 or random.random() < math.exp(-delta / T):

                current = new_solution

                current_cost = new_cost



        T *= alpha  # Cooling down



    return current, current_cost

# Example: Finding the minimum of a function

def cost(x):

    return x**2  # Simple quadratic function

def neighbor(x):

    return x + random.uniform(-1, 1)

best_solution, best_cost = simulated_annealing(10, cost, neighbor, 100, 0.95, 0.1)

print(f"Best solution: {best_solution}, Best cost: {best_cost}")