The Simulated Annealing algorithm is commonly used when we’re stuck trying to optimize solutions that generate local minimum or local maximum solutions, for example, the Hill-Climbing algorithm. So we use the Simulated Annealing algorithm to have a better solution to find the global maximum or global minimum.
It’s called Simulated Annealing because it’s modeling after a real physical process of annealing something like a metal. When you heat a particular metal, there’s a lot of energy there, and you can move things around quite systematically. But over time, as the system cools down, it eventually settles into a final position.
We’re going to simulate that process of some high-temperature systems, where things can move around quite frequently but, over time, decreasing that temperature until we eventually settle at an ultimate solution.
In this Python code, we will have an algorithm to find the global minimum, but you can easily modify this to find the global maximum.
First, we have to determine how we will reduce the temperature on each iteration. In this example, we will start with a temperature of 90 degrees, and we will decrease the current temperature by 0.01 linearly until we reach the final temperature of 0.1 degrees.
initial_temp = 90 final_temp = .1 alpha = 0.01 current_temp = initial_temp
Then we will set the initial state and set it as the solution. You can set it up as a particular state or generate it randomly.
current_state = initial_state solution = current_state
Now, we will repeat this process until the current temperature is less than the final temperature.
while current_temp > final_temp
For each iteration, we will get a random neighbor of the current state (the following state that we can go from the current state).
neighbor = random.choice(self.get_neighbors())
Then we calculate the differences between the neighbor and the current state.
cost_diff = self.get_cost(self.current_state) = self.get_cost(neighbor)
If the new solution is better, we will accept it.
if cost_diff > 0: solution = neighbor
If the new solution is not better, we will still accept it if the temperature is high. With this approach, we will use the worst solution in order to avoid getting stuck in local minimum. But we will get a neighbor that is not that bit worse than the current state. We can determine that with the following probability equation:
if random.uniform(0, 1) < math.exp(cost_diff / current_temp): solution = neighbor
The next step is to decrement the current temperature according to the
current_temp -= alpha
So at the very end, we just return to whatever the current state happens to be.
This is the big picture for Simulated Annealing algorithm, which is the process of taking the problem and continuing with generating random neighbors. We’ll always move to a neighbor if it’s better than our current state. But even if the neighbor is worse than our current state, we’ll sometimes move there depending the temperature and how bad it is.
import random import math def simulated_annealing(initial_state): """Peforms simulated annealing to find a solution""" initial_temp = 90 final_temp = .1 alpha = 0.01 current_temp = initial_temp # Start by initializing the current state with the initial state current_state = initial_state solution = current_state while current_temp > final_temp: neighbor = random.choice(get_neighbors()) # Check if neighbor is best so far cost_diff = get_cost(self.current_state) = get_cost(neighbor) # if the new solution is better, accept it if cost_diff > 0: solution = neighbor # if the new solution is not better, accept it with a probability of e^(-cost/temp) else: if random.uniform(0, 1) < math.exp(cost_diff / current_temp): solution = neighbor # decrement the temperature current_temp -= alpha return solution def get_cost(state): """Calculates cost of the argument state for your solution.""" raise NotImplementedError def get_neighbors(state): """Returns neighbors of the argument state for your solution.""" raise NotImplementedError
And as a result, the goal of this whole process is that as we begin to try and find our way to the global maximum or the global minimum, we can dislodge ourselves if we ever get stuck at a local maximum or a local minimum in order to eventually make our way to exploring the best solution. And then as the temperature decreases, eventually we settle there without moving around too much from what we’ve found to be the globally best thing that we can do thus far.