Python Programming for Biology: Bioinformatics and Beyond

Function minimisation by simulated annealing

In the next example we return to the function minimisation previously discussed. Here by

using  simulated  annealing  the  final  solutions  will  focus  much  more  precisely  on  the

optimum  value  compared  to  plain  Monte  Carlo,  given  that  there  will  be  more  chance  of

refinement  and  less  chance  of  sub-optimal  jumps.  The  Python  is  very  similar  to  the

previous monteCarlo function. Again, there is only the introduction of a few extra values

to calculate and the application of the cooling schedule: n is the number of iterations, cool

---

is the effective temperature and prob is now different because the difference in values is

scaled by cool prior to exponentiation.

def simAnneal(numIter, testFunc, spread=0.1, nDims=2):

n = float(numIter)

bestPoint = uniform(-1.0, 1.0, nDims)

bestValue = testFunc(bestPoint)

prevPoint = bestPoint

prevValue = bestValue

for i in range(numIter):

cool = exp(-i/n)

testPoint = normal(prevPoint, spread, nDims)

value = testFunc(testPoint)

prob = exp( (prevValue-value) / cool ) # Adjusted acceptance score.

if prob > uniform():

prevPoint = testPoint

prevValue = value

if value < bestValue:

bestPoint = testPoint

bestValue = value

pointStr = ' '.join(['%.3f' % p for p in testPoint])

print('%5d T:%.3f %s value:%e' % (i, cool, pointStr, value))

return bestValue, bestPoint

We can test with both the plain Monte Carlo and the simulated annealing optimisers to

compare and contrast their performance:

numSteps = 100000

simAnneal(numSteps, testFunc)

monteCarlo(numSteps, testFunc)