巡回セールスマン問題などの問題を解決するためにシミュレーテッド アニーリングを使用しています。満足のいく解決策が得られましたが、解決策空間内のパス (つまり、アルゴリズムが解決策に到達するために取ったステップ) を知りたいと思います。 、最適な旅程から、かなり最適な旅程まで。
つまり、巡回セールスマン問題の場合は次のようになります。
- 都市間のランダムな旅程から始めます
- ステップ 1: 都市 AC と EF の間のパスが交換されました
- ステップ 2: 都市 GU と SQ の間のパスがスワップされました
- ...
- 都市間のかなり最適な旅程で終わる
シミュレーテッド アニーリングを使用して、最適化プロセスの各ステップを保存し、システムに加えられた各変更を 1 つずつたどって、最終的にその特定のソリューションにつながった方法はありますか? それとも、これはシミュレーテッド アニーリングの仕組みに反しますか?
これは、巡回セールスマンの例を使用してhttps://github.com/perrygeo/simanneal/blob/master/simanneal/anneal.pyから非常にわずかに変更された、@perrygeo による優れたシミュレーテッド アニーリング アルゴリズムです: https://github.com /perrygeo/simanneal/blob/master/examples/salesman.py (すべての変更の後に、""" で始まる 1 行のコメントが続きます)
from __future__ import division
from __future__ import print_function
from __future__ import absolute_import
from __future__ import unicode_literals
import copy
import math
import sys
import time
import random
def round_figures(x, n):
"""Returns x rounded to n significant figures."""
return round(x, int(n - math.ceil(math.log10(abs(x)))))
def time_string(seconds):
"""Returns time in seconds as a string formatted HHHH:MM:SS."""
s = int(round(seconds)) # round to nearest second
h, s = divmod(s, 3600) # get hours and remainder
m, s = divmod(s, 60) # split remainder into minutes and seconds
return '%4i:%02i:%02i' % (h, m, s)
class Annealer(object):
"""Performs simulated annealing by calling functions to calculate
energy and make moves on a state. The temperature schedule for
annealing may be provided manually or estimated automatically.
"""
Tmax = 25000.0
Tmin = 2.5
steps = 50000
updates = 100
copy_strategy = 'deepcopy'
def __init__(self, initial_state):
self.initial_state = initial_state
self.state = self.copy_state(initial_state)
def set_schedule(self, schedule):
"""Takes the output from `auto` and sets the attributes
"""
self.Tmax = schedule['tmax']
self.Tmin = schedule['tmin']
self.steps = int(schedule['steps'])
def copy_state(self, state):
"""Returns an exact copy of the provided state
Implemented according to self.copy_strategy, one of
* deepcopy : use copy.deepcopy (slow but reliable)
* slice: use list slices (faster but only works if state is list-like)
* method: use the state's copy() method
"""
if self.copy_strategy == 'deepcopy':
return copy.deepcopy(state)
elif self.copy_strategy == 'slice':
return state[:]
elif self.copy_strategy == 'method':
return state.copy()
def update(self, step, T, E, acceptance, improvement):
"""Prints the current temperature, energy, acceptance rate,
improvement rate, elapsed time, and remaining time.
The acceptance rate indicates the percentage of moves since the last
update that were accepted by the Metropolis algorithm. It includes
moves that decreased the energy, moves that left the energy
unchanged, and moves that increased the energy yet were reached by
thermal excitation.
The improvement rate indicates the percentage of moves since the
last update that strictly decreased the energy. At high
temperatures it will include both moves that improved the overall
state and moves that simply undid previously accepted moves that
increased the energy by thermal excititation. At low temperatures
it will tend toward zero as the moves that can decrease the energy
are exhausted and moves that would increase the energy are no longer
thermally accessible."""
elapsed = time.time() - self.start
if step == 0:
print(' Temperature Energy Accept Improve Elapsed Remaining')
print('%12.2f %12.2f %s ' % \
(T, E, time_string(elapsed)))
else:
remain = (self.steps - step) * (elapsed / step)
print('%12.2f %12.2f %7.2f%% %7.2f%% %s %s' % \
(T, E, 100.0 * acceptance, 100.0 * improvement,
time_string(elapsed), time_string(remain)))
def anneal(self):
"""Minimizes the energy of a system by simulated annealing.
Parameters
state : an initial arrangement of the system
Returns
(state, energy): the best state and energy found.
"""
step = 0
self.start = time.time()
steps = [] ### initialise a list to save the steps taken by the algorithm to find a good solution
# Precompute factor for exponential cooling from Tmax to Tmin
if self.Tmin <= 0.0:
raise Exception('Exponential cooling requires a minimum "\
"temperature greater than zero.')
Tfactor = -math.log(self.Tmax / self.Tmin)
# Note initial state
T = self.Tmax
E = self.energy()
prevState = self.copy_state(self.state)
prevEnergy = E
bestState = self.copy_state(self.state)
bestEnergy = E
trials, accepts, improves = 0, 0, 0
if self.updates > 0:
updateWavelength = self.steps / self.updates
self.update(step, T, E, None, None)
# Attempt moves to new states
while step < self.steps:
step += 1
T = self.Tmax * math.exp(Tfactor * step / self.steps)
a,b = self.move()
E = self.energy()
dE = E - prevEnergy
trials += 1
if dE > 0.0 and math.exp(-dE / T) < random.random():
# Restore previous state
self.state = self.copy_state(prevState)
E = prevEnergy
else:
# Accept new state and compare to best state
accepts += 1
if dE < 0.0:
improves += 1
prevState = self.copy_state(self.state)
prevEnergy = E
steps.append([a,b]) ### append the "good move" to the list of steps
if E < bestEnergy:
bestState = self.copy_state(self.state)
bestEnergy = E
if self.updates > 1:
if step // updateWavelength > (step - 1) // updateWavelength:
self.update(
step, T, E, accepts / trials, improves / trials)
trials, accepts, improves = 0, 0, 0
# Return best state and energy
return bestState, bestEnergy, steps ### added steps to what should be returned
def distance(a, b):
"""Calculates distance between two latitude-longitude coordinates."""
R = 3963 # radius of Earth (miles)
lat1, lon1 = math.radians(a[0]), math.radians(a[1])
lat2, lon2 = math.radians(b[0]), math.radians(b[1])
return math.acos(math.sin(lat1) * math.sin(lat2) +
math.cos(lat1) * math.cos(lat2) * math.cos(lon1 - lon2)) * R
class TravellingSalesmanProblem(Annealer):
"""Test annealer with a travelling salesman problem.
"""
# pass extra data (the distance matrix) into the constructor
def __init__(self, state, distance_matrix):
self.distance_matrix = distance_matrix
super(TravellingSalesmanProblem, self).__init__(state) # important!
def move(self):
"""Swaps two cities in the route."""
a = random.randint(0, len(self.state) - 1)
b = random.randint(0, len(self.state) - 1)
self.state[a], self.state[b] = self.state[b], self.state[a]
return a,b ### return the change made
def energy(self):
"""Calculates the length of the route."""
e = 0
for i in range(len(self.state)):
e += self.distance_matrix[self.state[i-1]][self.state[i]]
return e
if __name__ == '__main__':
# latitude and longitude for the twenty largest U.S. cities
cities = {
'New York City': (40.72, 74.00),
'Los Angeles': (34.05, 118.25),
'Chicago': (41.88, 87.63),
'Houston': (29.77, 95.38),
'Phoenix': (33.45, 112.07),
'Philadelphia': (39.95, 75.17),
'San Antonio': (29.53, 98.47),
'Dallas': (32.78, 96.80),
'San Diego': (32.78, 117.15),
'San Jose': (37.30, 121.87),
'Detroit': (42.33, 83.05),
'San Francisco': (37.78, 122.42),
'Jacksonville': (30.32, 81.70),
'Indianapolis': (39.78, 86.15),
'Austin': (30.27, 97.77),
'Columbus': (39.98, 82.98),
'Fort Worth': (32.75, 97.33),
'Charlotte': (35.23, 80.85),
'Memphis': (35.12, 89.97),
'Baltimore': (39.28, 76.62)
}
# initial state, a randomly-ordered itinerary
init_state = list(cities.keys())
random.shuffle(init_state)
reconstructed_state = init_state
# create a distance matrix
distance_matrix = {}
for ka, va in cities.items():
distance_matrix[ka] = {}
for kb, vb in cities.items():
if kb == ka:
distance_matrix[ka][kb] = 0.0
else:
distance_matrix[ka][kb] = distance(va, vb)
tsp = TravellingSalesmanProblem(init_state, distance_matrix)
# since our state is just a list, slice is the fastest way to copy
tsp.copy_strategy = "slice"
state, e, steps = tsp.anneal()
while state[0] != 'New York City':
state = state[1:] + state[:1] # rotate NYC to start
print("Results:")
for city in state:
print("\t", city)
### recontructed the annealing process
print("")
print("nbr. of steps:",len(steps))
print("Reconstructed results:")
for s in steps:
reconstructed_state[s[0]], reconstructed_state[s[1]] = reconstructed_state[s[1]], reconstructed_state[s[0]]
while reconstructed_state[0] != 'New York City':
reconstructed_state = reconstructed_state[1:] + reconstructed_state[:1] # rotate NYC to start
for city in reconstructed_state:
print("\t", city)
移動が行われるたびに保存すると、実際に追跡可能なステップの膨大なリストが作成されます。ただし、特に高温で、アルゴリズムが解空間内のさまざまな位置を探索してジャンプする方法を明らかに模倣しています。
よりまっすぐに収束するステップを取得するには、ステップ節約ラインを移動できます。
steps.append([a,b]) ### append the "good move" to the list of steps
下
if E < bestEnergy:
これまでに見つかった最良のソリューションを実際に改善する手順のみが保存されます。ただし、ステップの最終的なリストは、旅程を再構築するのに役立ちません (ステップが欠落しています)。
この問題は絶望的で、シミュレーテッド アニーリングの仕組みに固有のものですか? それとも、ランダムから準最適への収束ステップ リストを構築できる希望はありますか?