算法蚁群算法-原理-思路-步骤-程序实现算法历史蚁群优化算法在图中介绍为寻找优化路径的概率型算法。 它是cqdxh Dorigo于1992年在他的博士论文中提出的，其灵感来源于蚂蚁在寻找食物的过程中发现路径的行为。 蚁群算法是一种仿真进化算法，初步研究表明，该算法具有许多优良的性质。 针对PID控制器的参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值模拟结果表明蚁群算法具有新的模拟进化优化方法的有效性和应用价值。
在现实世界中，(初始状态)每只蚂蚁在一定范围内随机游走，在通过的路径上留下信息素，从而达到不断把相关的食物信息反馈给蚁群)。 如果其他蚂蚁发现了它的路径，这些母蚂蚁就不再保持原来的随机游走，很可能遵循这个路径** ((一个路径上的信息素越多，其他蚂蚁越有可能选择这个路径(* ) )。 如果他们通过这条路径最终发现食物，他们会继续通过这条路径增加信息素。 由于通过这个途径信息素在增加，最终所有的蚂蚁都会找到食物。
在算法原理蚁群算法实验中，每只蚂蚁都是先开始寻找食物，而不事先告诉它们食物在哪里，然后让蚂蚁找到食物，方法是遍历空间上的所有点再次，让蚂蚁找到寻找食物的最短路径一旦一只找到食物，就会向环境释放信息素，吸引其他蚂蚁，越来越多的蚂蚁会找到食物。 但是，也有蚂蚁不像其他蚂蚁那样总是重复同样的道路。 他们会另辟蹊径。 **开辟比原来其他道路更短的道路，更多的蚂蚁会被吸引到这条更短的道路上。 *最后，随着时间的推移运行，最短的路径可能会被很多蚂蚁重复。
假设，dij为节点i到节点j距离，节点i、j上的信息素含量用ij(t)表示。先选定一个起始节点，将所有u个蚂蚁放在起点处，所有路径上信息素含量相同，蚂蚁k根据各条路径上信息素分布的大小选择下一个移动节点，加入禁忌表List来记录每一只蚂蚁经过节点的顺序，防止蚂蚁再次经过该节点，蚂蚁经过所有指定的节点即完成了一次算法的迭代。在蚂蚁搜索路径节点的过程中，t时刻下，蚂蚁k从节点i移动至节点j的移动概率p为：
其中，allowedk表示蚂蚁k从当前节点移动到下一个所有可能经过节点的集合。依据上述内容为信息素启发式因子，代表路径上信息素存在的多少，信息素多表示该路径通过的蚂蚁多，反之少量蚂蚁通过。为期望启发因子，表示蚂蚁在选择该路径节点重要性的考虑，其值越大，说明移动到此点的几率越大，启发式函数ij(t)计算方法为：
由上式可以看出启发函数ij(t)和dij对于每一只蚂蚁成反比关系，节点之间的距离越长，启发函数的值越小。当所有的蚂蚁完成一次循环后，各个城市间链接路径上的信息素浓度需进行更新。首先是信息素挥发，其次是蚂蚁在它们所经过的边上释放信息素，其中为信息素挥发系数，且01，计算公式为：
也就是说
(I，j )在Lk上时
=dij，蚂蚁构建的路径长度dij越小，路径上的各边缘获得更多信息素，以后迭代中被其他蚂蚁选择的可能性越高。 蚂蚁每次循环结束后，都会清空禁忌表，回到原城市，准备下一次周游。
此外，通过更新和改进信息素规则和启发函数，可以缩小全局路径和理论最佳路径之间的差异。
算法步骤1.对相关参数进行初始化，如蚁群规模（蚂蚁数量）u、信息素重要程度因子、启发函数重要程度因子、信息素挥发因子、信息素释放总量Q、最大迭代次数itermax。
2.构建解空间，将各个蚂蚁随机地置于不同的出发点，计算每个蚂蚁k（k=1,2,3…m）下一个待访问城市，直到所有蚂蚁访问完所有城市。
3.更新信息苏计算每个蚂蚁经过路径长度Lk(k=1,2,…，m），记录当前迭代次数中的最优解（最短路径）。同时，对各个城市连接路径上信息素浓度进行更新。
4.判断是否终止若iteritermax，则令iter=iter+1,清空蚂蚁经过路径的记录表，并返回步骤2；否则，终止计算，输出最优解。
程序为defgetdistmat(coordinates ) :num=coordinates.shape(0) distmat=NP.zeros ) (52， 52 ) ) forIinrange ) ) num ) : dist mat [ I ] [ j ]=dist mat [ j ] [ I ]=NP.Lina LG.norm (cooordinates [ I ]
oordinates.shape[0] // 城市个数alpha = 1 // 信息素重要程度因子beta = 5 // 启发函数重要程度因子rho = 0.1 // 信息素的挥发速度Q = 1//信息素释放总量iter = 0//循环次数itermax = 275//循环最大值etatable = 1.0 / (distmat + np.diag([1e10] * numcity)) // 启发函数矩阵，表示蚂蚁从城市i转移到矩阵j的期望程度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] 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) # 计算各个蚂蚁的路径距离 for i in range(numant): visiting = pathtable[i, 0] # 当前所在的城市 unvisited = set(range(numcity)) # 未访问的城市,以集合的形式存储{} unvisited.remove(visiting) # 删除元素；利用集合的remove方法删除存储的数据内容 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() cumsumprobtrans -= np.random.rand() k = listunvisited[(np.where(cumsumprobtrans > 0)[0])[0]] # 元素的提取（也就是下一轮选的城市） pathtable[i, j] = k # 添加到路径表中（也就是蚂蚁走过的路径) unvisited.remove(k) # 然后在为访问城市set中remove（）删除掉该城市 length[i] += distmat[visiting][k] visiting = k length[i] += distmat[visiting][pathtable[i, 0]] # 蚂蚁的路径距离包括最后一个城市和第一个城市的距离 # 包含所有蚂蚁的一个迭代结束后，统计本次迭代的若干统计参数 lengthaver[iter] = length.mean() if iter == 0: lengthbest[iter] = length.min() pathbest[iter] = pathtable[length.argmin()].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 print("iter(迭代次数):", iter)# 做出平均路径长度和最优路径长度fig, axes = plt.subplots(nrows=2, ncols=1, figsize=(12, 10))axes[0].plot(lengthaver, 'k', marker=u'')axes[0].set_title('Average Length')axes[0].set_xlabel(u'iteration')axes[1].plot(lengthbest, 'k', marker=u'')axes[1].set_title('Best Length')axes[1].set_xlabel(u'iteration')fig.savefig('average_best.png', dpi=500, bbox_inches='tight')plt.show()# 作出找到的最优路径图bestpath = pathbest[-1]plt.plot(coordinates[:, 0], coordinates[:, 1], 'r.', marker=u'$cdot$')plt.xlim([-100, 2000])plt.ylim([-100, 1500])for i in range(numcity - 1): m = int(bestpath[i]) n = int(bestpath[i + 1]) plt.plot([coordinates[m][0], coordinates[n][0]], [coordinates[m][1], coordinates[n][1]], 'k')plt.plot([coordinates[int(bestpath[0])][0], coordinates[int(n)][0]], [coordinates[int(bestpath[0])][1], coordinates[int(n)][1]], 'b')ax = plt.gca()ax.set_title("Best Path")ax.set_xlabel('X axis')ax.set_ylabel('Y_axis')plt.savefig('best path.png', dpi=500, bbox_inches='tight')plt.show()
[1]yqdxwz,娇气的大山,吴迪,杜战其.改进型蚁群算法在路径规划中的研究[J].制造业自动化,2020,42(02):55-59.
[2]xhdtk,fdhxc,耍酷的哈密瓜,hxdxte,zgdcc.蚁群算法的基本原理及应用综述[J].轻工科技,2018,34(03):69-72.
[3]程序算法https://blog.csdn.net/haoxun03/article/details/104209214haoxun03
在已有程序上做了修改与补充。