禁忌搜索算法实现31个城市的TSP旅行商问题
程序员文章站
2022-05-20 20:24:54
...
研究生专业课上的一门实验，当初做的时候其实迷迷糊糊的，参照了一些网友的思想完成了该篇实验。
但本次是在全邻域内搜索，当初实现局部邻域搜索的时候，结果并不是那么理想，所以有朋友有好的想法可以一起分享分享。
#-*-coding:gb2312-*-
# 禁忌搜索算法实现31个城市TSP问题
import random
import math
import matplotlib.pyplot as plt
global m, best, tl, ca # m 城市个数 best全局最优 tl初始禁忌长度 ca最大候选集的个数
global time, spe # time 迭代次数, spe特赦值
best = float('Inf') # 全局最优初始化为正无穷
m = 31
tl = int(round(math.sqrt(m*(m-1)/2), 0))
spe = 10
time = 250
ca = 200
tabu = [[0] * (m) for i in range(m)] # 声明并初始化禁忌表
best_way = [0] * m
now_way = [0] * m # best_way 最优解 now_way当前解
dis = [[0] * (m) for i in range(m)] # 使用邻接矩阵存储两城市之间的距离
p = [] # 存放31个城市的坐标
class no: # 该类表示每个点的坐标
def __init__(self, x, y):
self.x = x
self.y = y
def draw(t,re): # 该函数用于描绘解t的路线图以及迭代过程图
# 路线图
x = [0] * (m + 1)
y = [0] * (m + 1)
for i in range(m):
x[i] = p[t[i]].x
y[i] = p[t[i]].y
x[m] = p[t[0]].x
y[m] = p[t[0]].y
plt.plot(x, y, color='r', marker='*')
plt.show()
# 迭代过程图
A = [i for i in range(time)] # 横坐标
B = re[:] # 纵坐标
plt.xlim(0,time)
plt.xlabel("迭代次数",fontproperties="SimSun")
plt.ylabel("路径长度",fontproperties="SimSun")
plt.title("适应度进化曲线",fontproperties="SimSun")
plt.plot(A, B, '-')
plt.show()
def mycol(): # 城市坐标输入
coordinate = [[1304, 2312], [3639, 1315], [4177, 2244], [3712, 1399], [3488, 1535], [3326, 1556],
[3238, 1229], [4196, 1004], [4312, 790], [4386, 570], [3007, 1970], [2562, 1756],
[2788, 1491], [2381, 1676], [1332, 695], [3715, 1678], [3918, 2179], [4061, 2370],
[3780, 2212], [3676, 2578], [4029, 2838], [4263, 2931], [3429, 1908], [3507, 2367],
[3394, 2643], [3439, 3201], [2935, 3240], [3140, 3550], [2545, 2357], [2778, 2826], [2370, 2975]
]
for i in coordinate:
p.append(no(i[0], i[1]))
def get_dis(a, b): # 返回a，b两城市的直线距离
return math.sqrt((p[a].x - p[b].x) * (p[a].x - p[b].x) + (p[a].y - p[b].y) * (p[a].y - p[b].y))
def get_value(t): # 计算解t的路线长度
ans = 0.0
for i in range(1, m):
ans += dis[t[i]][t[i - 1]]
ans += dis[t[0]][t[m - 1]]
return ans
def cop(a, b): # 把b数组的值赋值a数组
for i in range(m):
a[i] = b[i]
def rand(g): # 随机生成初始解
vis = [0] * m
on = 0
while on < m:
te = random.randint(0, m - 1) # 产生一个代表城市序号的随机数
if (vis[te] == 0): # 如果当前选出的随机数其对应位置的值为1代表已被选中，则跳过；否则，将当前数加入初始解中
vis[te] = 1
g[on] = te
on += 1
def greedy(g):
# 使用贪婪算法产生初始解,从第一个城市CR出发,寻找与其直线距离最短的城市NR并标记,令CR=dis_index，然后继续寻找与CR距离最近的城市并标记，直到所有的城市被标记完
# 初始解的第一个出发城市由随机数产生
#temp = [random.randint(0, m-1)]
temp = [0] # 固定从第一个城市出发,产生的解唯一
count = 1
CR = temp[0]
while count < m:
distance = [0] * m # 存储CR与其他城市的距离
cop(distance, dis[CR])
distance.sort() # 对当前城市与其他城市的距离进行排序
distance = distance[1:] # 排除掉为0的城市到自己的距离
dis_index = dis[CR].index(distance[0]) # 将距离最短城市的下标找出
i = 1
while dis_index in temp: # 如果当前距离最短的城市已在初始解里，则找次小的
dis_index = dis[CR].index(distance[i])
i += 1
temp.append(dis_index)
count += 1
CR = dis_index
cop(g, temp)
def init(): # 初始化函数
global best
for i in range(m):
for j in range(m):
if i == j:
continue
value = get_dis(i, j)
dis[i][j] = value # 初始化所有城市之间的直线距离
dis[j][i] = value
#rand(now_way) # 生成初始解作为当前解
greedy(now_way)
now = get_value(now_way) # 计算初始解的长度
cop(best_way, now_way) # 将当前的初始解及其长度赋给最佳解
best = now
def slove(): # 迭代函数
global best, now_way
temp = [0] * m # 中间变量记录交换结果
a = 0
b = 0 # 记录交换城市下标
ob_way = [0] * m
cop(ob_way, now_way)
ob_value = get_value(now_way) # 暂存邻域最优解
for i in range(1, m): # 搜索所有邻域
for j in range(1, m):
if (i + j >= m): break
if (i == j): continue
cop(temp, now_way)
temp[i], temp[i + j] = temp[i + j], temp[i] # 交换
value = get_value(temp)
if (value <= best and tabu[i][i + j] < spe): # 如果优于全局最优且禁忌长度小于特赦值
cop(best_way, temp)
best = value
a = i
b = i + j # 更新全局最优且接受新解
cop(ob_way, temp)
ob_value = value
elif (tabu[i][i + j] == 0 and value < ob_value): # 如果优于邻域中的最优解则暂存邻域最优解
cop(ob_way, temp)
ob_value = value
a = i
b = i + j # 接受新解的坐标
cop(now_way, ob_way) # 更新当前解
for i in range(m): # 更新禁忌表
for j in range(m):
if (tabu[i][j] > 0):
tabu[i][j] -= 1
tabu[a][b] = tl # a,b被选中，重置a，b两个交换城市的禁忌值
return best # 每次迭代完毕后，返回最优路径长度
# *************************入口函数*************************
if __name__ == "__main__":
record = [0] * time # record每次产生的最优解的路径长度
mycol() # 数据输入
init() # 数据初始化
for i in range(time): # 控制迭代次数
value = slove()
record[i] = value / pow(10, 4)
print("路线总长度：", round(best, 3)) # 打印最优解距离保留三位小数
print("具体路线：", best_way) # 打印路线，以序列表示
draw(best_way, record) # 路线图与迭代过程图
随机产生初始解：
路线总长度： 17090.424
具体路线： [0, 28, 10, 5, 4, 22, 24, 25, 27, 26, 30, 29, 23, 17, 2, 21, 20, 19, 18, 16, 15, 3, 7, 8, 9, 1, 6, 12, 11, 13, 14]
贪婪算法产生初始解
路线总长度： 16561.835
具体路线： [6, 5, 4, 3, 15, 22, 10, 11, 13, 14, 0, 28, 30, 29, 26, 27, 25, 24, 19, 23, 18, 16, 17, 20, 21, 2, 7, 8, 9, 1, 12]