蚁算法解决TSP问题详细讲解（含python代码）
蚁算法解决TSP 问题详细讲解（含python 代码）
蚁算法解决TSP 问题详细讲解（含python 代码）
（⼀）TSP 问题
TSP问题：旅⾏商问题，即TSP问题（Traveling Salesman Problem），给定⼀组城市和每对城市之间的距离，商家从其中⼀个城市出发，要求每个城市都要经过且每个城市经过⼀次，最后回到起点城市，求解商家访问这些城市的最短路径。
（⼆）蚁算法
（1）蚁算法简单介绍
蚁算法简介：蚁算法是对⾃然界蚂蚁的寻径⽅式进⾏模似⽽得出的⼀种仿⽣算法：蚂蚁在运动过程中，能够在它所经过的路径上留下信息素(pheromone)的物质进⾏信息传递，⽽且蚂蚁在运动过程中能够感知这种物质，并以此指导⾃⼰的运动⽅向。
当有很多蚂蚁觅⾷时，刚开始每个蚂蚁会随机选择⼀条路径，并在该路径中释放信息素，路径短的蚂蚁要⽐路径长的更先到达⽬的地，往返的频率也更快，所有该路径上的信息素更浓。信息素也会随着时间
会有部分挥发。当下⼀代蚂蚁觅⾷时，下⼀代蚂蚁会选择信息素浓度⾼的路径⾛，⽽选择该路径的蚂蚁最多，⼜会释放更多的信息素，因此由⼤量蚂蚁组成的蚁集体⾏为便表现出⼀种信息正反馈现象：某⼀路径上⾛过的蚂蚁越多，则后来者选择该路径的概率就越⼤。蚁算法具有分布计算、信息正反馈和启发式搜索的特征，本质上是进化算法中的⼀种启发式全局优化算法。
（2）蚁算法解决TSP 问题基本原理
在蚁算法中，蚂蚁的⾏⾛路径表⽰待优化问题的可⾏解，整个蚂蚁体的所有路径构成待优化问题的解空间。算法基本原理如下：
（1）根据具体问题设置蚂蚁种数量AntCount，分头并⾏搜索。
（2）每只蚂蚁完成⼀次周游后，在⾏进的路上释放信息素，信息素量与解的质量成正⽐。
（3）蚂蚁路径的选择（当前城市i到下⼀城市j)根据信息素浓度Tij ，同时考虑两点之间的距离ij(ij为城市i和城市j之间距离的倒数），采⽤随机的局部搜索策略。这使得距离较短的边，其上的信息素量较⼤，后来的蚂蚁选择该边的概率也较⼤。
（4）每只蚂蚁只能⾛合法路线（经过每个城市1次且仅1次），为此设置禁忌表(即以前⾛过的城市列表）来控制。
（5）所有蚂蚁都搜索完⼀次就是迭代⼀次，每迭代⼀次就对所有的边做⼀次信息素更新，原来的蚂蚁死掉，新的蚂蚁进⾏新⼀轮搜索。注意，同⼀代的蚂蚁互相之间不会受到之前蚂蚁留下的信息素浓度的影响，计算到下⼀城市j的概率时所⽤到T是上⼀代蚂蚁留下的信息素。第⼀代蚂蚁⽤的信息素是初始值为1，所有城市之间信息素浓度⼀样。
（6）更新信息素包括原有信息素的蒸发和经过的路径上信息素的增加。
（7）达到预定的迭代步数，或出现停滞现象（所有蚂蚁都选择同样的路径，解不再变化），则算法结束，以当前最优解作为问题的最优解。
（3）蚁算法的核⼼步骤
3.1 路径构建
路径构建包括初始城市的选择和下⼀个到达城市的选择。每个蚂蚁都随机选择⼀个城市作为其出发城市，并维护⼀个路径记忆表(候选集列表candidate，是⼀个Antcount-citycount⼆维矩阵），⽤来存放蚂蚁依次经过的城市。
蚂蚁在当前所在城市选择下⼀个城市时，转移概率是有两部分组成，⼀个是信息素浓度Tij ，另⼀个是当前城市到下⼀城市的距离ij。是信息素重要程度因⼦，是启发函数重要程度因⼦。其中t时刻，蚂蚁k
从i城市到j城市的转移概率是按照下列公式来进⾏计算的：
ηηpij ηαβ
3.2 信息素更新
迭代过程中，问题空间中的所有路径上的信息素都会发⽣改变。其中第⼀部分是信息素的蒸发，（rho)是挥发因⼦，代表信息素的挥
发速度。然后，所有的蚂蚁根据⾃⼰构建的路径长度在它们本轮经过的边上释放信息素，公式如下：
等式右边第⼀部分代表了信息素⾃⾝挥发后剩余的信息素，第⼆部分是每只蚂蚁经过城市i到城市j留下的信息素。在⼀次迭代中，每只蚂蚁经过城市i到城市j都会留下信息素，在该次迭代结束后，所有蚂蚁留下的信息素总和即为该路径信息素的增量。注意，同⼀代的蚂蚁互相之间不会受到之前蚂蚁留下的信息素浓度的影响，计算到下⼀城市j的概率时所⽤到T是上⼀代所有蚂蚁留下的信息素。
（三）代码分析
（1）设置参数
#蚂蚁数量
AntCount = 100
#城市数量
city_count = len (city_name )
剑网3任务alpha = 1  # 信息素重要程度因⼦
beta = 2  # 启发函数重要程度因⼦
rho = 0.1 #挥发速度
iter  = 0  # 迭代初始值
MAX_iter = 200  # 最⼤迭代值
鲁滨逊漂流记主要内容
（2）距离矩阵
建⽴⼀个citycount-citycount⼆维数组，存放每对城市之间的距离。注意，因为要根据距离矩阵求启发函数ij(ij为城市i和城市j之间距离的倒数），所有距离矩阵的对⾓线不能为0，我把对⾓线设置为10000，其实只要不为零就可以。
#Distance 距离矩阵音箱声音小
city_count = len (city_name )
Distance = np .zeros ((city_count , city_count ))
for  i in  range (city_count ):
for  j in  range (city_count ):
if  i != j :
Distance [i ][j ] = math .sqrt ((city_condition [i ][0] - city_condition [j ][0]) ** 2 + (city_condition [i ][1] - city_condition [j ][1]) ** 2)
else :
四不伤害
Distance [i ][j ] = 100000
（3）设置信息素矩阵和蚂蚁路径矩阵
建⽴⼀个citycount-citycount⼆维的信息素矩阵pheromonetable，存放每对城市之间的信息素。初始信息素矩阵，全是为1组成的矩阵。在每次迭代之后，更新该信息素矩阵。
建⽴⼀个AntCount-city_count⼆维矩阵candidate，在每次迭代中，存放所有蚂蚁的路径(⼀只蚂蚁⼀个路径)。
建⽴⼀个MAX_iter-city_count⼆维矩阵path_best，存放的是相应的，每次迭代后的最优路径，每次迭代只有⼀个值。建⽴⼀个⼀维数组distance_best，存放每次迭代的最优距离。
ρηη
# 初始信息素矩阵，全是为1组成的矩阵
pheromonetable = np.ones((city_count, city_count))
# 候选集列表，存放100只蚂蚁的路径(⼀只蚂蚁⼀个路径),⼀共就Antcount个路径，⼀共是蚂蚁数量*31个城市数量
candidate = np.zeros((AntCount, city_count)).astype(int)
# path_best存放的是相应的，每次迭代后的最优路径，每次迭代只有⼀个值
path_best = np.zeros((MAX_iter, city_count))
# 存放每次迭代的最优距离
distance_best = np.zeros( MAX_iter)
（4）当前城市选择下⼀城市
蚂蚁由当前城市i选择到下⼀个城市j。⾸先建⽴⼀个列表 unvisit存放还未访问过的城市，每次访问⼀个城市之后，把该城市从unvisit ⾥⾯移除。由当前城市选择下⼀个城市时，使⽤概率函数分别计算当前城市到还未访问的所有城市之间概率。 累计概率，赌选择下⼀次个城市。
# second：选择下⼀个城市选择
for i in range(AntCount):
# 移除已经访问的第⼀个元素
unvisit =list(range(city_count))# 列表形式存储没有访问的城市编号
visit = candidate[i,0]# 当前所在点，第i个蚂蚁在第⼀个城市
for j in range(1, city_count):#访问剩下的city_count个城市，city_count次访问
protrans = np.zeros(len(unvisit))#每次循环都更改当前没有访问的城市的转移概率矩阵1*30,1*29,
# 下⼀城市的概率函数
for k in range(len(unvisit)):
# 计算当前城市到剩余城市的（信息素浓度^alpha）*（城市适应度的倒数）^beta
# etable[visit][unvisit[k]],(alpha+1)是倒数分之⼀，pheromonetable[visit][unvisit[k]]是从本城市到k城市的信息素
protrans[k]= np.power(pheromonetable[visit][unvisit[k]], alpha)* np.power(
etable[visit][unvisit[k]],(alpha +1))
# 累计概率，赌选择
cumsumprobtrans =(protrans /sum(protrans)).cumsum()
cumsumprobtrans -= np.random.rand()
# 求出离随机数产⽣最近的索引值
k = unvisit[list(cumsumprobtrans >0).index(True)]
# 下⼀个访问城市的索引值
candidate[i, j]= k
length[i]+= Distance[visit][k]
visit = k  # 更改出发点，继续选择下⼀个到达点
length[i]+= Distance[visit][candidate[i,0]]#最后⼀个城市和第⼀个城市的距离值也要加进去
（5）更新信息素
每迭代⼀次之后，更新所有城市之间的信息素。⾸先建⼀个信息素的增加量矩阵，存放该次迭代后每条路径的信息素增量。每条路径上的信息素等于信息素⾃⾝挥发后剩余的信息素加上每只蚂蚁经过城市i到城市j留下的信息素。
注意，更新信息素其实有三种⽅式。我选择的是第⼀种：△τ=Q/L,Q为常数，描述蚂蚁释放信息素的浓度，L为每只蚂蚁周游中所⾛路径的总长度。即每只蚂蚁从城市i到城市j之间信息素的增量等于Q除以周游中所⾛路径的长度。对于同⼀只蚂蚁，所有的路径上（任意两个城市之间）△τ是⼀样的。
#信息素的增加量矩阵
changepheromonetable = np.zeros((city_count, city_count))
for i in range(AntCount):
for j in range(city_count -1):
# 当前路径⽐如城市23之间的信息素的增量：1/当前蚂蚁⾏⾛的总距离的信息素
changepheromonetable[candidate[i, j]][candidate[i][j +1]]+= Q / length[i]
#Distance[candidate[i, j]][candidate[i, j + 1]]
#最后⼀个城市和第⼀个城市的信息素增加量
changepheromonetable[candidate[i, j +1]][candidate[i,0]]+= Q / length[i]
#信息素更新的公式：
pheromonetable =(1- rho)* pheromonetable + changepheromonetable
iter+=1
（6）30城市的坐标.txt
下⾯是30城市的坐标，⼤家建⼀个‘30城市的坐标.txt’⽂件然后放到和代码同⽬录下就可以啦。
1,41,94
2,37,84
3,53,67
4,25,62
5,7,64
6,2,99
7,68,58
8,71, 44
9,54,62
10,83,69
11,64,60
12,18,54
13,22,60
14,83,46
15,91,38
16,25,38
17,24,42
18,58,69
19,71,71
20,74,78
21,87,76
22,18,40
23,13,40
24,82,7
25,62,32
26,58,35
27,45,21
28,41,26
29,44,35
30,4,50
（7) 完整代码
#蚁算法解决TSP
import numpy as np
import matplotlib.pyplot as plt
import matplotlib
import math
import random
city_name =[]
city_condition =[]
with open('30城市的坐标.txt','r',encoding='UTF-8')as f:
lines = f.readlines()
lines = f.readlines()
#调⽤readlines()⼀次读取所有内容并按⾏返回list给lines
#for循环每次读取⼀⾏
2020抖音火爆昵称for line in lines:
line = line.split('\n')[0]桂林必去的景点
line = line.split(',')
city_name.append(line[0])
city_condition.append([float(line[1]),float(line[2])])
city_condition = np.array(city_condition)#获取30城市坐标
#Distance距离矩阵
city_count =len(city_name)
Distance = np.zeros((city_count, city_count))
for i in range(city_count):
for j in range(city_count):
if i != j:
Distance[i][j]= math.sqrt((city_condition[i][0]- city_condition[j][0])**2+(city_condition[i][1]- city_condition[j][1])**2) else:
Distance[i][j]=100000
# 蚂蚁数量
AntCount =100
# 城市数量
city_count =len(city_name)
# 信息素
alpha =1# 信息素重要程度因⼦
beta =2# 启发函数重要程度因⼦
rho =0.1#挥发速度
iter=0# 迭代初始值
MAX_iter =200# 最⼤迭代值
Q =1
# 初始信息素矩阵，全是为1组成的矩阵
pheromonetable = np.ones((city_count, city_count))
# 候选集列表，存放100只蚂蚁的路径(⼀只蚂蚁⼀个路径),⼀共就Antcount个路径，⼀共是蚂蚁数量*31个城市数量
candidate = np.zeros((AntCount, city_count)).astype(int)
# path_best存放的是相应的，每次迭代后的最优路径，每次迭代只有⼀个值
path_best = np.zeros((MAX_iter, city_count))
# 存放每次迭代的最优距离
distance_best = np.zeros( MAX_iter)
# 倒数矩阵
etable =1.0/ Distance
while iter<  MAX_iter:
# first：蚂蚁初始点选择
if AntCount <= city_count:
#np.random.permutation随机排列⼀个数组的
candidate[:,0]= np.random.permutation(range(city_count))[:AntCount]
else:
m =AntCount -city_count
n =2
candidate[:city_count,0]= np.random.permutation(range(city_count))[:]
while m >city_count:
candidate[city_count*(n -1):city_count*n,0]= np.random.permutation(range(city_count))[:]
m = m -city_count
n = n +1
candidate[city_count*(n-1):AntCount,0]= np.random.permutation(range(city_count))[:m]
length = np.zeros(AntCount)#每次迭代的N个蚂蚁的距离值
# second：选择下⼀个城市选择
for i in range(AntCount):
# 移除已经访问的第⼀个元素
unvisit =list(range(city_count))# 列表形式存储没有访问的城市编号

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。