蚁群算法原理简述.docVIP

蚁群算法原理简述 蚁群算法的背景信息 根据蚂蚁“寻找食物”的群体行为，意大利著名学者 等于1991年在法国巴黎召开的第一届欧洲人工生命会议上最早提出了蚁群算法的基本模型。1992年，Dorigo M又在其博士学位论文中进一步阐 明了蚁群算法的核心思想。 蚁群算法是一种基于种群的启发式仿生进化系统。蚁群算法最早成功应用于解决著名的旅行商问题,该算法采用了分布式正反馈并行计算机制，易于与其他方法结合，而且具有较强的鲁棒性。 蚁群算法创立十多年来,无论在算法理论还是在算法应用方面都取得了很多突破性研究进展。它已经从单纯地解决对称拓展到解决非对称、指派问题以及车间作业调度问题等。尤其是近几年来，这种新兴的仿生优化算法已经显示出强大的生命力和广阔的发展前景。 蚁群算法的原理 自然界中的蚂蚁是没有视觉的，既不知道向何处寻找食物，也不知道发现食物后如何返回自己的巢穴，它仅仅依赖于同类散发在周围环境中的特殊物质—信息素的轨迹，来决定自己何去何从。但是尽管没有任何先验的知识，但蚂蚁们还是有能力找到从其巢穴到食物源的最佳路径。所以大量研究发现，同一蚁群中的蚂蚁能感知信息素及其强度，后来的蚂蚁会倾向于朝信息素浓度高的方向移动，而移动留下的信息素又会对原有信息素进行加强，后续的蚂蚁而后续的蚂蚁选择该路径的可能性也越大。由于在相同时间段 内越短的路径会被越多的蚂蚁访问,所以后续的蚂蚁选择较短路径的可能性也越大,最后所有的蚂蚁都走最短的那条路径。 应该指出，以蚁群为基础的方法能够有效地寻找较短的路径，但不一定是最短的路径。不过，对于那些难于获得最优解的问题，如那些NP难题，这种近于最优的解法常常已经是绰绰有余了。事实上，随着城市数目的增多，寻找精确解很快就会变成一个无法对付的问题。 蚁群算法的模型 下面以求解平面上个城市的为例来简要地介绍一下用于的基本蚁群算法。蚁群算法模型个城市的即为寻找通过个城市各一次且最后回到出发点的最短路径。 假设有个城市，只蚂蚁，令表示城市之间距离，表示在时刻城市之间路径上残留信息素强度。蚂蚁在行进的过程中，根据各条路径上残留信息素强度来决定下一步行进的路径，用表示在时刻蚂蚁由城市转移到城市的概率，则有： 表示蚂蚁下一步允许的城市集，列表为蚂蚁的禁忌表。当所有个城市都被列入到中时，蚂蚁游历了所有城市，现回到出发点便完成了一次遍历，则蚂蚁所经过的路径就是该的一个可行解。是启发式因子，表示蚂蚁从城市行进到城市的期望程度，通常取的倒数；分别表示信息素和启发式因子在方程中相对重要程序；当所有蚂蚁完成一次遍历之后，各路径上的信息素再根据式2进行全局更新： 其中，表示挥发系数，表示持久性系数，表示本次迭代后信息素的增量，表示第只蚂蚁在本次迭代中残留在边上的信息素量。根据信息素不同的更新策略，提出了三种不同的蚁群算法模型，即模型、模型及模型。它们的主要区别在于模型及模型中利用的是局部信息，即蚂蚁完成一步后更新路径上的信息素；而在模型中利用的是整体信息，即蚂蚁完成一次遍历后更新整条路径上的所有信息素。由于模型中信息增量考虑了全局变化，所以在求解时具有较好性能，通常作为蚁群算法的基本模型。 算法的具体实现 参数初始化。令时间，设置为常数，。 循环次数. 蚂蚁的禁忌表索引号。 蚂蚁的数目。 蚂蚁个体根据状态转移概率式1所计算的概率选择元素并前进，。 修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素，并把该元素移动到蚂蚁个体的禁忌表中。 若集合C中元素未遍历完，km,则跳转到第4步， 否则执行第8步。 根据式2和式3更新每条路径上信息量。 若满足结束条件，则循环结束并输出程序计算结果，否则清空禁忌表并跳转到第2步。 改进的蚁群算法 通过实验，我们发现标准蚁群算法在求解过程中存在容易陷入局部最优解的问题。为此，本文提出一种改进的自适应蚁群算法对此进行改进。 5.1 信息素的更新 采用自适应伪随机比率来选择下一座城市，即对于位于城市的蚂蚁，按式4选择下一座城市： 其中为上一致分布的随机数，它越小，系统随机选择下一个城市的概率就越大，一般取表示城市与城市之间的信息素量；表示城市与城市之间的启发式因子，表示启发式因子的相对重要程度，由式1确定。 全局信息素更新: 改变为： 当 为当前全局最优解的长度，为信息素的挥发系数，是一个也迭代次数成正比的函数，为常数。即完成信息激素更新后，将每条边上的信息素浓度限制在之间，避免某些边上的信息素过大，减小图上各边的信息素的差距，从而扩大解的有哪些信誉好的足球投注网站空间。 结束语 蚁群算法是近年来产生的一种源于大自然生物世界的新的启发式优化方法。通过以上对蚁群算法的基本原理及其实际应用的介绍可以发现该算法有如下主要特点:a