Simulated Annealing
Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space. It is often used when the search space is discrete (e.g., all tours that visit a given set of cities). For problems where finding an approximate global optimum is more important than finding a precise local optimum in a fixed amount of time, simulated annealing may be preferable to alternatives such as gradient descent.
This work implementing simulated annealing to solve the Traveling Salesman Problem (TSP) between US state capitals. Briefly, the TSP is an optimization problem that seeks to find the shortest path passing through every city exactly once. In our example the TSP path is defined to start and end in the same city (so the path is a closed loop).
function SIMULATED-ANNEALING(problem,schedule) returns a solution state
inputs: problem, a problem
schedule, a mapping from time to “temperature”
current ← MAKE-NODE(problem.INITIAL-STATE)
for t = 1 to ∞ do
T ← schedule(t)
if T = 0 then return current
next ← a randomly selected successor of current
ΔE ← next.VALUE - current.VALUE
if ΔE > 0 then current ← next
else current ← next only with probability eΔE/T
function GENETIC-ALGORITHM(population, FITNESS-FN) returns an individual
inputs: population, the initial random population of individuals
FITNESS-FN, a function that measures the fitness of an individual
repeat
population ← [MUTATE(RECOMBINE(SELECT(2, population, FITNESS-FN)))
for i in population]
until some individual is fit enough, or enough time has elapsed
return the best individual in population, according to FITNESS-FN
function SELECT(ρ, population, FITNESS-FN) returns a set of ρ individuals
selection ← a uniform random sample of 2 * ρ individuals from population
return the top ρ individuals in selection, ranked by FITNESS-FN
function RECOMBINE(x, y) returns an individual
inputs: x,y, parent individuals
n ← LENGTH(x)
crossover ← random integer from 0 to n
return APPEND(x[0:crossover], y[crossover: n])
function GENETIC-ALGORITHM(population,FITNESS-FN) returns an individual
inputs: population, a set of individuals
FITNESS-FN, a function that measures the fitness of an individual
repeat
new_population ← empty set
for i = 1 to SIZE(population) do
x ← RANDOM-SELECTION(population,FITNESS-FN)
y ← RANDOM-SELECTION(population,FITNESS-FN)
child ← REPRODUCE(x,y)
if (small random probability) then child ← MUTATE(child)
add child to new_population
population ← new_population
until some individual is fit enough, or enough time has elapsed
return the best individual in population, according to FITNESS-FN
function REPRODUCE(x, y) returns an individual
inputs: x,y, parent individuals
n ← LENGTH(x); c ← random number from 1 to n
return APPEND(SUBSTRING(x, 1, c),SUBSTRING(y, c+1, n))