|
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 PythonStep 1: Understanding Simulated AnnealingSimulated 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 FunctionThe 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.
Python
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 FunctionThe neighbor function generates a new candidate solution by making a small random change to the current solution.
Python
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 AlgorithmNow 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.
Python
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 AlgorithmDefine the problem domain, set the parameters, and run the Simulated Annealing algorithm.
Python
# 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 PythonHere’s the complete code with all the steps combined:
Python
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}')
OutputIteration 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...
|
