Siddhant Academy

Comprehensive Guide to Simulated Annealing

Siddhant Bhattarai's photo
Siddhant Bhattarai
·

5 min read

Simulated Annealing (SA) is a powerful optimization algorithm inspired by the physical process of annealing in metallurgy. Here's everything you need to know about it:

1. What is Simulated Annealing?

Simulated Annealing (SA) is a probabilistic optimization algorithm used to find the global minimum (or maximum) of a cost function. It is particularly useful for solving optimization problems with many local minima, where traditional methods may get stuck.

  • Inspiration: The algorithm is inspired by the annealing process in metallurgy, where a material is heated and then slowly cooled to remove defects and minimize the system's energy.

  • Key Idea: SA tries to escape local minima by accepting worse solutions with a certain probability, which decreases over time as the "temperature" decreases.

2. How Simulated Annealing Works

Simulated Annealing works by:

  1. Initialization: Start with an initial solution and a high "temperature".

  2. Perturbation: Generate a neighboring solution by making a small random change.

  3. Acceptance Criteria:

    • If the new solution is better, accept it.

    • If the new solution is worse, accept it with a probability pp that depends on the "temperature" and the difference in cost.

    • The acceptance probability is calculated as:

  4. Cooling Schedule: Gradually decrease the temperature.

  5. Stopping Criterion: Stop when the temperature becomes very low or after a fixed number of iterations.

3. Mathematical Principles Behind Simulated Annealing

Energy Function and Boltzmann Probability

Simulated Annealing is based on the Boltzmann distribution, which describes the probability of a system being in a certain state at a given temperature:

  • E = energy (or cost function in optimization).

  • T = temperature.

  • k = Boltzmann constant (usually set to 1 in optimization).

At high temperatures, the system explores the search space freely, but as the temperature decreases, the system "settles" into low-energy states (optimal solutions).

4. Key Factors to Consider

  1. Initial Temperature (T0):

    • A higher initial temperature allows the algorithm to explore the solution space more widely.

  2. Cooling Schedule:

    • Determines how fast the temperature decreases (e.g., exponential, linear, logarithmic).

    • A slow cooling schedule improves the chances of finding the global minimum but increases computation time.

  3. Neighborhood Function:

    • Defines how new candidate solutions are generated (e.g., small random perturbations).

  4. Stopping Criteria:

    • Common criteria include:

      • Reaching a minimum temperature.

      • No improvement after a fixed number of iterations.

  5. Number of Iterations at Each Temperature:

    • The number of attempts at generating new solutions at a given temperature.

5. Types of Problems Solved by Simulated Annealing

Simulated Annealing is typically used for combinatorial and continuous optimization problems:

  • Traveling Salesman Problem (TSP): Find the shortest route visiting all cities.

  • Job Scheduling: Allocate tasks to resources in an optimal way.

  • Circuit Design: Minimize wire length in chip design.

  • Machine Learning: Hyperparameter tuning for complex models.

  • Operations Research: Solve problems with constraints and large solution spaces.

6. Applications of Simulated Annealing

  • Manufacturing: Optimize production schedules and layouts.

  • Finance: Portfolio optimization.

  • Data Science: Hyperparameter optimization and feature selection.

  • Physics and Chemistry: Protein folding, molecular energy minimization.

  • Game Development: Solve pathfinding and resource allocation problems.

7. Advantages and Disadvantages of Simulated Annealing

Advantages

  • Avoids local minima: Can escape local minima by probabilistically accepting worse solutions.

  • Simple implementation: Easy to implement with a customizable cooling schedule.

  • Versatility: Can be applied to both combinatorial and continuous optimization problems.

Disadvantages

  • Sensitive to hyperparameters: Performance depends on the choice of initial temperature, cooling schedule, and neighborhood function.

  • Slow convergence: May take a long time to reach the global optimum, especially with a slow cooling schedule.

  • No guarantee of global optimality: There is no absolute guarantee that the global optimum will be reached.

8. Performance Metrics for Simulated Annealing

  • Cost Function Value: The final value of the cost function after the optimization process.

  • Convergence Time: The time taken to reach the final solution.

  • Success Rate: Percentage of times the algorithm reaches the global minimum in multiple runs.

  • Number of Accepted Solutions: Tracks how often new solutions are accepted.

  • Exploration vs Exploitation: Evaluates whether the algorithm balances exploration of new solutions and exploitation of good solutions.

9. Python Code Example: Simulated Annealing for Function Minimization

Below is an example using Simulated Annealing to minimize a simple quadratic function:

Python Code

import numpy as np
import matplotlib.pyplot as plt

# Objective function: (x - 3)^2 + 4
def objective_function(x):
    return (x - 3)**2 + 4

# Simulated Annealing function
def simulated_annealing(objective_func, x0, T0, cooling_rate, max_iter):
    x = x0  # Initial solution
    T = T0  # Initial temperature
    best_solution = x
    best_cost = objective_func(x)

    history = []  # To track cost history

    for i in range(max_iter):
        # Generate a new candidate solution by random perturbation
        x_new = x + np.random.uniform(-1, 1)
        cost_new = objective_func(x_new)
        cost_current = objective_func(x)

        # Accept new solution with a certain probability
        if cost_new < cost_current or np.random.rand() < np.exp(-(cost_new - cost_current) / T):
            x = x_new
            if cost_new < best_cost:
                best_solution = x_new
                best_cost = cost_new

        # Cool down temperature
        T = T * cooling_rate
        history.append(best_cost)

        # Stopping criteria
        if T < 1e-6:
            break

    return best_solution, best_cost, history

# Initial values
x0 = 10  # Initial guess
T0 = 100  # Initial temperature
cooling_rate = 0.95  # Cooling rate
max_iter = 1000  # Number of iterations

# Run simulated annealing
best_solution, best_cost, cost_history = simulated_annealing(objective_function, x0, T0, cooling_rate, max_iter)

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

# Plot cost history
plt.plot(cost_history)
plt.xlabel('Iterations')
plt.ylabel('Cost')
plt.title('Simulated Annealing Cost Convergence')
plt.show()

Explanation of the Code

Output

  • Best Solution: Approximately x = 3.

  • Best Cost: Approximately 4 (the global minimum of the function).

10. Summary

Simulated Annealing is a versatile optimization algorithm inspired by physical annealing. It is widely used for solving complex optimization problems where traditional methods fail. The success of Simulated Annealing depends on:

  • A well-tuned initial temperature and cooling schedule.

  • A proper balance between exploration (high temperature) and exploitation (low temperature).

By mastering Simulated Annealing, you can solve challenging optimization problems in areas such as scheduling, routing, and hyperparameter tuning.