Artificial Intelligence: Simulated Annealing

Simulated Annealing (SA) is a probabilistic technique used for finding an approximate solution to an optimization problem. It is particularly useful for large search spaces where finding the exact solution is impractical. The algorithm is inspired by the annealing process in metallurgy.

Step-by-Step Simulated Annealing in Python

Step 1: Understanding Simulated Annealing

Simulated Annealing is inspired by the annealing process in metallurgy. The key idea is to use a "temperature" parameter that gradually decreases over time, allowing the algorithm to explore the solution space more freely at high temperatures and refine the search as the temperature cools down.

Step 2: Defining the Objective Function

The objective function is the function we want to optimize (minimize or maximize). For this example, we'll use the Rastrigin function, which is a common benchmark function for optimization algorithms.

import random

def get_neighbor(x, step_size=0.1):
    neighbor = x[:]
    index = random.randint(0, len(x) - 1)
    neighbor[index] += random.uniform(-step_size, step_size)
    return neighbor​

Step 3: Creating the Neighbor Function

The neighbor function generates a new candidate solution by making a small random change to the current solution.

import random

def get_neighbor(x, step_size=0.1):
    neighbor = x[:]
    index = random.randint(0, len(x) - 1)
    neighbor[index] += random.uniform(-step_size, step_size)
    return neighbor​

Step 4: Implementing the Simulated Annealing Algorithm

Now we'll implement the Simulated Annealing algorithm. The main components are initializing the solution, updating the temperature, generating new candidates, and deciding whether to accept them.

def simulated_annealing(objective, bounds, n_iterations, step_size, temp):
    # Initial solution
    best = [random.uniform(bound[0], bound[1]) for bound in bounds]
    best_eval = objective(best)
    current, current_eval = best, best_eval
    scores = [best_eval]

    for i in range(n_iterations):
        # Decrease temperature
        t = temp / float(i + 1)
        # Generate candidate solution
        candidate = get_neighbor(current, step_size)
        candidate_eval = objective(candidate)
        # Check if we should keep the new solution
        if candidate_eval < best_eval or random.random() < math.exp((current_eval - candidate_eval) / t):
            current, current_eval = candidate, candidate_eval
            if candidate_eval < best_eval:
                best, best_eval = candidate, candidate_eval
                scores.append(best_eval)

        # Optional: print progress
        if i % 100 == 0:
            print(f"Iteration {i}, Temperature {t:.3f}, Best Evaluation {best_eval:.5f}")

    return best, best_eval, scores​

Step 5: Running the Algorithm

Define the problem domain, set the parameters, and run the Simulated Annealing algorithm.

# Define problem domain
bounds = [(-5.0, 5.0) for _ in range(2)]  # for a 2-dimensional Rastrigin function
n_iterations = 1000
step_size = 0.1
temp = 10

# Perform the simulated annealing search
best, score, scores = simulated_annealing(objective_function, bounds, n_iterations, step_size, temp)

print(f'Best Solution: {best}')
print(f'Best Score: {score}')​

Implementation of Simulated Annealing in Python

Here's the complete code with all the steps combined:

import math
import random

# Objective function: Rastrigin function
def objective_function(x):
    return 10 * len(x) + sum([(xi**2 - 10 * math.cos(2 * math.pi * xi)) for xi in x])

# Neighbor function: small random change
def get_neighbor(x, step_size=0.1):
    neighbor = x[:]
    index = random.randint(0, len(x) - 1)
    neighbor[index] += random.uniform(-step_size, step_size)
    return neighbor

# Simulated Annealing function
def simulated_annealing(objective, bounds, n_iterations, step_size, temp):
    # Initial solution
    best = [random.uniform(bound[0], bound[1]) for bound in bounds]
    best_eval = objective(best)
    current, current_eval = best, best_eval
    scores = [best_eval]

    for i in range(n_iterations):
        # Decrease temperature
        t = temp / float(i + 1)
        # Generate candidate solution
        candidate = get_neighbor(current, step_size)
        candidate_eval = objective(candidate)
        # Check if we should keep the new solution
        if candidate_eval < best_eval or random.random() < math.exp((current_eval - candidate_eval) / t):
            current, current_eval = candidate, candidate_eval
            if candidate_eval < best_eval:
                best, best_eval = candidate, candidate_eval
                scores.append(best_eval)

        # Optional: print progress
        if i % 100 == 0:
            print(f"Iteration {i}, Temperature {t:.3f}, Best Evaluation {best_eval:.5f}")

    return best, best_eval, scores

# Define problem domain
bounds = [(-5.0, 5.0) for _ in range(2)]  # for a 2-dimensional Rastrigin function
n_iterations = 1000
step_size = 0.1
temp = 10

# Perform the simulated annealing search
best, score, scores = simulated_annealing(objective_function, bounds, n_iterations, step_size, temp)

print(f'Best Solution: {best}')
print(f'Best Score: {score}')​

Output:

Iteration 0, Temperature 10.000, Best Evaluation 53.95166
Iteration 100, Temperature 0.099, Best Evaluation 49.75767
Iteration 200, Temperature 0.050, Best Evaluation 49.74828
Iteration 300, Temperatu...​