蚁群算法计算34个城市货郎担问题 python

"""" 蚁群算法 解决货郎担问题-----货郎从始城市出发走完34个城市，只能走一次（边和点），回到始发地，求最短路径 success """ import os print("当前目录是：",os.getcwd()) import numpy as np import matplotlib.pyplot as plt # 地图上的34个城市坐标 coordinates = np.array([[565.0,575.0],[25.0,185.0],[345.0,750.0],[945.0,685.0],[845.0,655.0], [880.0,660.0],[25.0,230.0],[525.0,1000.0],[580.0,1175.0],[650.0,1130.0], [1605.0,620.0],[1220.0,580.0],[1465.0,200.0],[1530.0, 5.0],[845.0,680.0], [725.0,370.0],[145.0,665.0],[415.0,635.0],[510.0,875.0],[560.0,365.0], [300.0,465.0],[520.0,585.0],[480.0,415.0],[835.0,625.0],[975.0,580.0], [1215.0,245.0],[1320.0,315.0],[1250.0,400.0],[660.0,180.0],[410.0,250.0], [420.0,555.0],[575.0,665.0],[1150.0,1160.0],[700.0,580.0]]) def getdistmat(coordinates): num = coordinates.shape[0] # 返回城市个数34 distmat = np.zeros((num,num)) # 创建初始矩阵 34 行 34 列 for i in range(num): for j in range(i,num): distmat[i][j] = distmat[j][i]=np.linalg.norm(coordinates[i]-coordinates[j]) # 画出各城市距离无向图矩阵 return distmat distmat = getdistmat(coordinates) numant = 40 #蚂蚁个数 numcity = coordinates.shape[0] #城市个数 alpha = 1 #信息素重要程度因子 beta = 5 #启发函数重要程度因子 rho = 0.1 #信息素的挥发速度 Q = 1 # 142行首次出现 iter = 0 # 起始迭代次数 itermax = 260 # 总迭代次数 # [1e10]*6 是 创建一个有6个10**10 的数的列表，np.diag将其转换成对角阵 （只有对角线有数） etatable = 1.0/(distmat+np.diag([1e10]*numcity)) # 启发函数矩阵，表示蚂蚁从城市i转移到城市j的期望程度 | 1.0/矩阵==1.0除以矩阵中每一个数后生成的矩阵 pheromonetable = np.ones((numcity,numcity)) # 信息素矩阵表，信息素越浓即值越大，蚂蚁越期望走此路径，意味着路程越短 pathtable = np.zeros((numant,numcity)).astype(int) #路径记录表 distmat = getdistmat(coordinates) #城市的距离矩阵 lengthaver = np.zeros(itermax) #各代路径的平均长度 lengthbest = np.zeros(itermax) #各代及其之前遇到的最佳路径长度 pathbest = np.zeros((itermax,numcity)) # 各代及其之前遇到的最佳路径长度 while iter < itermax: # 随机产生各个蚂蚁的起点城市编号 if numant <= numcity:#城市数比蚂蚁数多 pathtable[:,0] = np.random.permutation(range(0,numcity))[:numant] # 将（总蚂蚁个数）40以内的随机数赋值给路径记录表第一列 else: #蚂蚁数比城市数多，需要补足 pathtable[:numcity,0] = np.random.permutation(range(0,numcity))[:] pathtable[numcity:,0] = np.random.permutation(range(0,numcity))[:numant-numcity] length = np.zeros(numant) # 计算各个蚂蚁的路径距离 ''' 下面表示第一批40只蚂蚁走完全程分别的距离 ''' for i in range(numant): # i=0 下面表示第一个蚂蚁走完所有城市留下的印记 visiting = pathtable[i,0] # 当前所在的城市 #visited = set() #已访问过的城市，防止重复 #visited.add(visiting) #增加元素 unvisited = set(range(numcity))#未访问的城市 unvisited.remove(visiting) #删除元素 for j in range(1,numcity):#循环numcity-1次，访问剩余的numcity-1个城市 #每次用轮盘法选择下一个要访问的城市 listunvisited = list(unvisited) probtrans = np.zeros(len(listunvisited)) ######### # 以轮盘法随机选择城市编号 for k in range(len(listunvisited)): probtrans[k] = np.power(pheromonetable[visiting][listunvisited[k]],alpha)\ *np.power(etatable[visiting][listunvisited[k]],alpha) # 从已访问的城市到未访问的第一个城市的之间的距离（边）的信息素值乘以该边的期望程度 cumsumprobtrans = (probtrans/sum(probtrans)).cumsum() # 一维数组的cumsum() 结果是：[1,2,3,4,5]的cumsum() => [1,3,6,10,15] cumsumprobtrans -= np.random.rand() # np.random.rand()返回[0,1)之间的随机数 index=0 for n in cumsumprobtrans: if n>0: index=np.argwhere(cumsumprobtrans==n) index=int(index) break k = listunvisited[index] #下一个要访问的城市编号 使用轮盘法随机选择 ############ pathtable[i,j] = k unvisited.remove(k) #visited.add(k) length[i] += distmat[visiting][k] # distmat 城市距离矩阵 此句指第一个蚂蚁走的距离（下一个访问的城市与前面所有城市距离的加和） visiting = k length[i] += distmat[visiting][pathtable[i,0]] # 每一只蚂蚁的总路径距离包括最后一个城市和第一个城市的距离 #print length # 包含所有蚂蚁的一个迭代结束后，统计本次迭代的若干统计参数 lengthaver[iter] = length.mean() # mean()求矩阵各数和的平均值 if iter == 0: lengthbest[iter] = length.min() # 一维数组length 的最小值即第一次迭代走路距离最短的那只蚂蚁的距离 pathbest[iter] = pathtable[length.argmin()].copy() # argmin返回 np 数组中最小数索引 | 列表 b=a,a中数据的改变，b会有相同的变化；要使a、b互不影响，需用copy else: if length.min() > lengthbest[iter-1]: lengthbest[iter] = lengthbest[iter-1] pathbest[iter] = pathbest[iter-1].copy() else: lengthbest[iter] = length.min() pathbest[iter] = pathtable[length.argmin()].copy() # 更新信息素 changepheromonetable = np.zeros((numcity,numcity)) for i in range(numant): for j in range(numcity-1): changepheromonetable[pathtable[i,j]][pathtable[i,j+1]] += Q/distmat[pathtable[i,j]][pathtable[i,j+1]] # 表示对每两个城市之间距离的期望程度 changepheromonetable[pathtable[i,j+1]][pathtable[i,0]] += Q/distmat[pathtable[i,j+1]][pathtable[i,0]] pheromonetable = (1-rho)*pheromonetable + changepheromonetable iter += 1 #迭代次数指示器+1 #观察程序执行进度，该功能是非必须的 if (iter-1)%20==0: print (iter) # 做出平均路径长度和最优路径长度 fig,axes = plt.subplots(nrows=2,ncols=1,figsize=(12,10)) # 将图表分为上下两个图，总 宽和高分别为12,10 # 上图 axes[0].plot(lengthaver,'b',marker = u'') # b 表示线条为蓝色 有itermax 个点连成的线 axes[0].set_title('Average Length') #标题 axes[0].set_xlabel(u'iteration') # x 轴 u 表明“迭代次数”是unicode编码 # 下图 axes[1].plot(lengthbest,'b',marker = u'') # marker：标记点样式，'o','x'，也就是说这些符号会标示出曲线上具体的“点”，这样一来就易于观察曲线上那些地方是支撑点 axes[1].set_title('Best Length') axes[1].set_xlabel(u'iteration') fig.savefig('Average_Best.png',dpi=500,bbox_inches='tight') # dpi 指每英寸点数 bbox_inches='紧密' inches是英寸 plt.close() #作出找到的最优路径图 bestpath = pathbest[-1] plt.plot(coordinates[:,0],coordinates[:,1],'r.',marker=u'$\cdot$') # r 表示红色，'.' 表示用点表示城市坐标，marker$...$ 表�