模拟退火之 TSP 问题

本文最后更新于:4 年前

利用 Python 实现模拟退火算法解决 TSP 问题, 并画出最优路径图与每代适应度曲线图

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
# -*- coding: cp936 -*-
import math
import random
import time,os
from matplotlib.pyplot import *
import numpy as np

class Metal():
def __init__(self, data, temperature, descending):

self.temperature = temperature
self.descending = descending
self.change = range(0, len(data))
self.data = data
self.best = [[1,2], float("inf")]
self.x = self.best[0][:]
self.y = self.best[1]
self.HistoryY = []
self.Cm = cm.get_cmap('Greys')


def Smelt(self):
"""
开始冶炼
"""

NewY = self.Fx(self.change)

dE = self.y - NewY

if dE > 0 or math.e ** (dE / self.temperature) > random.uniform(0, 1):

self.y = NewY
self.x = self.change[:]

if self.y < self.best[1]:
self.best[0] = self.x
self.best[1] = self.y

os.system('cls')
print '当金属温度为', self.temperature, '℃时达到历史最佳路径, 长度为', self.best[1], '\n 路线为\n', self.best[0], '\n', '-'*100

self.HistoryY += [NewY]

self.temperature -= self.descending
self.RandX()


def Fx(self, xi):
"""
计算冶炼的程度
"""
start = 0
distance = 0.0
Xi=xi+[xi[0]]
#print len(Xi)
for end in range(1, len(Xi)):
distance += ((self.data[Xi[start]][1][0] * 1.0 - self.data[Xi[end]][1][0]) ** 2 + (self.data[Xi[start]][1][1] * 1.0 - self.data[Xi[end]][1][1]) ** 2) ** 0.5 #如果 data 的格式有变这里要改
start = end

return distance


def RandX(self):
"""
随机产生 2 个点,
一个为起点,一个为终点,
将这 2 点之间的路径倒置
"""

self.change = self.x[:]

start = random.randint(0, len(self.change))
end = random.randint(start, len(self.change))

self.change[start:end] = self.change[start:end][::-1]

#random.shuffle(self.change)


def PlotAndSave(self):
"""
冶炼结束时画出每温度下的 x 与 y
"""

plot(range(1, len(self.HistoryY) + 1), self.HistoryY)
title(str(self.x) + '\n\n' + str(self.y), fontsize = 7)

savefig('Max.jpg')

close('all')

xr = []
yr = []
for i in self.x:
xr += [self.data[i][1][0]]
yr += [self.data[i][1][1]]

xr = np.array(xr + [xr[0]])
yr = np.array(yr + [yr[0]])

x0 = xr[:2]
y0 = yr[:2]
xr = xr[1:]
yr = yr[1:]

quiver(x0[:-1], y0[:-1], x0[1:] - x0[:-1], y0[1:] - y0[:-1], scale_units = 'xy', angles = 'xy', scale = 1, color='r')
quiver(xr[:-1], yr[:-1], xr[1:] - xr[:-1], yr[1:] - yr[:-1], scale_units = 'xy', angles = 'xy', scale = 1)

savefig('Max_Road.jpg')
close('all')


time.clock()
#------------------------------------------------------------------参数设置------------------------------------------------------------------

data = [["*", [37, 52]],..., ["*", [30,40]]] #数据在这
temperature = 100 #金属初始温度
descending = 0.001 #降温幅度, 不是按百分比

#------------------------------------------------------------------参数设置------------------------------------------------------------------


metal = Metal(data, temperature, descending)
while metal.temperature > 1:

t = time.clock()
minute, second = divmod(t, 60)
hour, minute = divmod(minute, 60)

metal.Smelt()
print '当前金属温度为', metal.temperature, '℃', '此温度下最优路径长度为', metal.y, ' 花费时间 %02d:%02d:%02d' %(hour, minute, second), ' '*5,'\r',

print '\n路线为\n', metal.x
metal.PlotAndSave()
print
os.system('pause')

注意

  • 双击运行
  • 降温幅度较小, 会有更大概率得到较优值, 但是相应花费的时间也就越长.
  • Eil 51, 为例, 此网站给出的最优解为 426, 而我求出来的是 438.13.
  • 结果截图
    运行结果
    每温度最值
    最佳路径

所以, 代码的算法还是比较合理的.


来呀快活呀