The first simulated annealing example in Python is the same as the travellingSalesman()
described above but with the introduction of the cool variable, which can act as a kind of
temperature. We will use an exponential cooling decay based on the proportion of the
current step through the whole run: the current step relative to the total (i/m). The only
three differences in the Python function are the introduction of m, the total number of
steps as a floating point number; cool, the current effective temperature in the annealing
schedule; and a different score: this is now divided by cool before the exponent is taken.
The effect of this is that as the search proceeds cool diminishes exponentially from 1.0 to
cycles. Better distances will still always be accepted at any stage, but it will be
increasingly less likely for other scores to be accepted. Hence, the state will tend not to
jump out of a good solution towards the end, but initial exploration is unaffected.
m = float(numIter) # Use to calculate cool
for i in range(numIter): # could use xrange in Python 2
cool = exp(-i/m) # annealing schedule 'temperature'
a = randint(0, n-1)
b = randint(0, n-1)
route = prevRoute[:]
route[a] = prevRoute[b]
route[b] = prevRoute[a]
distance = getRouteLength(distanceData, route)
score = exp( (prevDistance - distance) / (scale*cool) ) # Adjusted
score
if score > uniform():
prevRoute = route
prevDistance = distance
if distance < bestDistance:
bestRoute = route[:]
bestDistance = distance
print('%5d Dist:%.5f Temp:%.5f' % (i, distance, cool))
return bestDistance, bestRoute
The function may be tested in exactly the same manner as the non-annealing version.
distances = calcCityDistances(cityCoords)
cities = list(cityCoords.keys())
dist, route = travellingSalesmanSimAnneal(distances, cities, 1000000)
print('%.3f %s' % (dist, '-'.join(route)))
With the appropriate number of search steps this will generally give the same result as
the previous function travellingSalesman(), although the last tested route will usually be
much closer to the best route than for the non-annealing version. Testing different numbers
of cycles will show that if the number of search steps is too small the annealing will ‘cool’
before a reasonable number of states have been sampled and the final result will not be the
best. Accordingly, it is critical to give the algorithm enough steps if the absolute optimum
is required. However, an advantage of simulated annealing compared to plain Monte Carlo
is its speed, so if all you want is a reasonably good solution in a reasonable time extra
steps may not be needed.
Do'stlaringiz bilan baham: