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}')
Implement Simulated Annealing in Python
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.