Simmulated Annealing is a method for solving unconstrained and bound-constrained optimization problems. The method models the physical process of heating a material and then slowly lowering the temperature to decrease defects, thus minimizing the system energy.
import random
import math
"""
minimizing
Observation:
* each node should generate the same number of neighbors
* be aware of poor performance under spiky neighborhoods
* yields better results than local search and multisstart search after t time
* should not be used on TSP or similar problems
This example will sort the digits 0123456789 #note that 0 will be removed from the integer
"""
class Node:
def __init__(self, value):
# **IMPLEMENT**
# The node must contain a cost value
self.cost = int(value)
self.neighbors = None
@property
def neigh(self):
if self.neighbors:
return self.neighbors
else:
self.neighbors = self.generate_neighbors()
return self.neighbors
def generate_neighbors(self):
# **IMPLEMENT**
# generate neighbors
value = str(self.cost)
return [value[:i-1]+value[j-1]+value[i:j-1]+value[i-1]+value[j:] for i in range(1,len(value)) for j in range(i+1,len(value)+1)]
def initial_temp():
# **IMPLEMENT**
# f.ex upper bound on (max cost - min cost)
return 987654321.0
def dependant_initial_t( temperature,node,neighbor ):
# Increase the temperature to make this neighbor a very likely choice
# This function may not decrease the temperature
x = temperature/(node.cost-neighbor.cost+1)*math.log1p(100/99)
return temperature/x if 1>x>0 else temperature
def reduce_t( temperature,repetitions ):
# common function for temperatur reduction
return temperature/math.log(repetitions+2,2)
def sa( start_node ):
node = start_node
d = len( start_node.neigh ) # number of repetitions pr temperature value
temperature = initial_temp( )
repetitions = 0
while temperature>0.001 and node.cost > 123456789:
neighbor = Node(random.choice( node.neigh )) # choose random neigh
if neighbor.cost < node.cost:
node = neighbor
else:
annealing = random.uniform(0,1)
if annealing < math.pow(math.e,-(neighbor.cost-node.cost)/temperature):
node = neighbor
repetitions += 1
if repetitions<d:
# set a dependant initial temperature
temperature = dependant_initial_t( temperature,node,neighbor )
if repetitions%d==0:
temperature = reduce_t( temperature,repetitions )
#end while
return node.cost
print sa( Node(value='5647382910') )