Skip to content

Instantly share code, notes, and snippets.

@ademar111190
Last active February 6, 2022 19:08
Show Gist options
  • Save ademar111190/6892184 to your computer and use it in GitHub Desktop.
Save ademar111190/6892184 to your computer and use it in GitHub Desktop.
Simulated Annealing Python Implementation, thanks to S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, Vlado Cerny and Antonio Carlos de Lima Júnior.
#!/usr/bin/python
__author__ = "Ademar Alves de Oliveira"
__copyright__ = "Copyright 2013, Ademar"
__credits__ = ["S. Kirkpatrick", "C. D. Gelatt", "M. P. Vecchi", "A. C. L. Junior", "Diego Queiroz"]
__license__ = "GPL"
__version__ = "1.1"
__maintainer__ = "Ademar Alves"
__email__ = "ademar111190@gmail.com"
from random import random
from random import uniform
from random import randrange
from math import exp
from time import time
# constante de boltzman
boltzman = 1.3806488e-23
# Function that performs a disturbance in the s solution
# s the array with current solution
# min the min value to new array item value, default -100
# max the max value to new array item value, default 100
def disturb(s, min=-100, max=100):
sDisturbed = list(s)
index = randrange(0, len(sDisturbed))
sDisturbed[index] = uniform(min, max)
return sDisturbed
# only a print
def printIfneed(param, verbose):
if(verbose):
print param
# function the function to calcule the sI, send it as pointer to function
# s0 initial setup, send it as array
# max maximum number of iterations, default is 100
# dis maximum number of disorders per iteration, default is 100
# disMin the min value to disorders item value, default -100
# disMax the max value to disorders item value, default 100
# hits maximum number of hits per iteration, default is 100
# t0 initial temperature, default is 100
# a temperature reduction rate, default is 1
# verbose show log, default is False
def simulatedAnnealing(function, s0, max=100, dis=100, disMax=100, disMin=-100, hits=100, t0=100, a=1, verbose=False):
init = time()
printIfneed("init as " + str(init) + " s0=" + str(s0), verbose)
s = s0
iterations = 0
t = t0
while True:
disorders = 0
successCount = 0
while True:
si = disturb(s, min=disMin, max=disMax)
deltaFunction = function(*s) - function(*si)
if(deltaFunction <= 0.0 or (exp(-deltaFunction / boltzman * t) > random())):
printIfneed("change: " + str(s) + " to: " + str(si), verbose)
s = si
successCount = successCount + 1
disorders = disorders + 1
printIfneed("disorders: " + str(disorders) + ", success: " + str(successCount) + " temperature: " + str(t) , verbose)
if(successCount >= hits or disorders > dis):
break
t = t - a
iterations = iterations + 1
if (successCount == 0 or iterations > max or t <= 0.0):
break
printIfneed(str(iterations) + " iterations in " + str(time() - init) + " milisseconds", verbose)
return s
# examples to implement:
def goodexample(x):
return -(x**2)
def goodExample2(x, y):
return x - y
print simulatedAnnealing(goodexample, [5.0], verbose=True)
print "second example:"
print simulatedAnnealing(goodExample2, [33.0, 4.0], max=200, dis=200, disMax=300, disMin=-300, hits=200, t0=200, a=1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment