蚁群算法解决多城市最短路径问题

c0d3n4m · 发表于 2022-5-16 09:01

1、 蚁群算法
2.1引言
  相信大家在日常的生活中都见过蚂蚁觅食的过程，但有没有思考过对于蚂蚁来说，觅食的过程中路径又是怎么选择的呢？如何选择才能使得自身的能量消耗最小呢？
2.2蚁群算法简介
蚁群算法的基本原理来源于自然界中蚂蚁觅食的最短路径原理，它是由意大利学者Dorigo M等人再1991年首次提出，并将其成功运用于TSP问题等复杂优化问题。后经过科学家们的不断发展与探索，蚁群算法被广泛应用于优化离散组合优化问题中；指派问题、二次规划、job-shop，图着色、通讯网络路由选择、电力系统故障检测、图像处理等。
蚁群算法源自对自然界中蚂蚁觅食行为的深刻观察与探索。科学家发现，蚂蚁种群可以在有障碍的环境下找到一条最短觅食路径。出现这一神奇现象的原因并不是因为某只蚂蚁在指挥全局，而是依靠整个蚂蚁种群的信息传递机制。蚂蚁在经过的路径上会释放一种气味信号——信息素。后来的蚂蚁会根据信息素浓度来选择路径，选择信息素浓度高的路径作为自己的觅食路径。在所有可能的路径中，距离最短的路径由于往返距离短，单位时间内通过的蚂蚁数量会多于其他的路径，因此此路径的信息素浓度也会高于其他路径，这会吸引更多的蚂蚁选择这一路径，形成正反馈，一段时间后，整个蚂蚁种群就能沿最短路径觅食了。
每只蚂蚁并不需要知道全局的信息。他们只根据眼前的局部信息，使用简单的规则进行决策。这样，在蚁群集体里，复杂的智能行为会自然涌现。大自然给予我们启示：如果个体都遵循相同的简单规则，就有可能在宏观层面创造出一种集体智慧。

图2.1 蚁群觅食图

2.2 蚁群算法的实现
2.2.1基本思想
  蚁群算法中，每只蚂蚁走过的路径代表一个可行解，所有蚂蚁走过的路径构成待求解问题的解空间。算法的基本思想是通过‘人工蚂蚁’模拟自然界中的蚂蚁觅食过程来实现最优解的求解。
（1）人工蚂蚁在路径上释放信息素
（2）较短路径上的信息素浓度较大
（3）最优解对应路径上的信息素浓度随时间推移越来越大。
（4）整个人工蚁群通过正反馈集中到最优路径上。
2.2.2 算法实现
  1、构建路径
  最短路径求解过程中，路径构建包括初始城市的选择和下一个到达城市的选择。每个蚂蚁都随机选择一个城市作为其出发城市，并维护一个路径记忆表，用来存放该蚂蚁依次经过的城市（此为人工蚂蚁与自然界蚂蚁的区别）。
蚂蚁在构建路径的每一步中，按照轮盘赌法选择下一个要到达的城市。其中t时刻，蚂蚁k从i城市到j城市的转移概率是按如下列公式来进行计算：

2、信息素的更新
迭代过程中，问题空间中的所有路径上的信息素都会发生改变。其中第一部分是信息素的蒸发；然后，所有的蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素，公式如下：

等式右边第一项表示信息素挥发后剩余的信息素量，第二项表示每只蚂蚁经过路径ij留下的信息素。其有以下三种常见的模型。蚁周模型在每只蚂蚁走完全部路径后，进行信息素更新，利用全局信息进行更新，蚁量和蚁密模型则是在蚂蚁走过一步（一段路径）后进行更新，利用的是局部信息进行更新。

图2.2 信息素更新模型

2.2.3 算法流程
蚁群算法流程图如下：

图2.4算法流程图

2.3 代码实现
附件2
2.4运行结果

图2.5 最终轨迹图

图2.6 迭代过程

  本文来自笔者日常的学习笔记，限于读者水平，难免会有错误，欢迎批评指正。

蚁群算法.pdf
271.1K
· 百度网盘

		自动登录	找回密码
密码			立即注册

蚁群算法解决多城市最短路径问题

本帖子中包含更多资源