蚁群算法及应用研究 .docx

蚁群算法及应用研究 蚁群算法及应用研究 摘要：该文首先介绍了蚁群算法原理并通过实例说明，然后以旅行商问题为例建立了数学模型，通过信息素更新的策略不同，介绍了三种蚁群算法模型。最后总结了蚁群算法的特点，为其应用提供依据。 关键词：蚁群算法；数学模型；流程 中图分类号：TP18 文献标识码：A 文章编号：1009-304435-8055-03 1 蚁群算法概述 通过对社会性动物的自组织行为进行研究发现，虽然它们的能力和智能都很低，但是它们能通过相互协调、分工、合作来最好最快地完成觅食、迁徙等复杂行为，比方说蚁群，能够在没有任何先知条件下找到从蚁穴到食物源的最短路径，而且有能力随着环境的变化而变化，搜索到新的最短路径。因此这些行为引来越来越多研究者关注，通过对这种行为进行数学建模和仿真，演化成许多解决传统复杂优化问题的新方法，也就是群智能算法。蚁群算法是群智能理论研究领域中的一种主要的算法，其是模拟蚂蚁群落食物采集过程而产生的搜索算法，并成功应用于许多离散优化问题。 20世纪90年代意大利学者Dorigo M等人提出蚁群算法【1】，其灵感来自于现实生活中单个蚂蚁的能力和智能很低，但在自然界蚂蚁的觅食过程中，蚁群总是能在遇到障碍物时选择较短路径，尤其是它们在没有任何先知条件下可以找到从蚁穴到食物源的最短路径。并且在周围的环境发生改变的情况下，蚁群也能很快找到新的最短路径。原来当蚂蚁经过一个还没有走过的路口时，会随机的挑选一条路径前进，并且在经过的路上分泌一种称为信息素的化学物质，而且还能够感知其存在和浓度。越多蚂蚁经过的路径上的信息素越浓，其它蚂蚁就会向信息素浓度高的地方靠近【2】。于是，蚂蚁经过越多的路径，后来的蚂蚁选择的概率就越大。由于信息素具有挥发性，距离较短路径上的信息素浓度较高，距离较长路径上的信息素浓度随着时间会渐渐减弱。如此不断循环，就可以找到最短路径。 蚂蚁算法是一种群智能优化算法，由于其引入了正反应和并行机制，该算法具有自主搜索能力，鲁棒性强，不需要人工干预，容易与其他方法相结合。虽然蚂蚁算法的理论根底薄弱，但其开展迅速，问世以来就解决了许多实际问题，比方旅行商问题、二次规划、车辆路径问题、车间作业调度问题、图像处理等优化问题，具有广阔的应用前景，并成为前沿性课题和研究热点。 2 蚁群算法的原理 在蚁群算法中，为了实现对真实蚂蚁觅食的群体行为，将真实蚂蚁抽象为人工蚂蚁，具有如下特点【1】： 能够像真实蚂蚁一样在经过的路径上留下信息素，而且使信息素随着时间挥发，在选择路径时不会被前面人工蚂蚁留存的信息所局限。 人工蚂蚁并不能处在连续的空间，而是离散的空间，所以它们的运动也是从一个点到另一个点的转换。 人工蚂蚁具有一定的智能，可以从问题的特征中得到启发，依据规率而不是仅仅靠概率搜索最优路径。 蚁群算法包括根本蚁群算法、蚁群系统、最大-最小蚂蚁系统、最优-最差蚂蚁系统。根本蚁群算法中每只人工蚂蚁均独立的搜索可行解，当它到达一个未曾经历过的节点时，就会根据概率函数随机地选择继续移动的下一条路径，并在该路径上释放信息素。选择路径短的蚂蚁走得快，经过的路径上留下的信息素就多。如此不停地搜索，最优解路径上的信息素浓度会越来越高，会有更多的蚂蚁选择该路径，而其他路径由于信息素会随着时间慢慢挥发，从而只有最优解路径的浓度最高，整个蚁群都会集中在该路径上，并得到最优解。图1是一个基于蚁群算法的人工蚂蚁系统搜索最短路径的例如图。 由上面例如可以看出，蚂蚁算法是一种随机搜索算法，其寻优的过程包含两个阶段：一是适应阶段，初时信息素相同，随着信息素不断的积累，性能好的解的信息素浓度就高，性能不太好的解的信息素浓度就低。在初始情况信息不明的情况下，适应阶段会比拟漫长，影响了求优的速度。二是协作阶段，各个候选解之间不断地进行信息的交流，不断地最优解收敛。在适应阶段的根底上，这个阶段会较快速。 3 蚁群算法的数学模型 蚁群算法被成功地应用于许多实际问题，其中最著名的是解决旅行商问题。在此以该问题为例说明根本蚁群算法的数学模型和实现过程。 旅行商问题又称为货郎担问题，是最根本的路线问题：当有n个城市，一个旅行者由其中某一个需市作为起点出发，需要不重复地经过所以结点后回到原点，求其最短路线。当城市数等于24个时，只需要1s时间就可以计算完成，但随着城市数增加，计算难度呈几何级数增大，当城市数增加到30个时，计算时间需要10年多，计算难度很大。在这里用蚁群算法来解决。城市个数用n表示， 2 规定每只蚂蚁选择的城市必须是不曾到过的，只有到达过所有的城市后才到回到出发城市。所以在这里为每只蚂蚁建立一个禁忌表tabuk，将第k只蚂蚁访问过的城市放入禁忌表中，禁忌表不是固定不变的，随着第k只蚂蚁的运动进行动态调整。 3 每只蚂蚁选择要访问的下一个城门需要通过概率函数来实现，概率函数并不是随机的，而是与两个城市间的距离和两个城市间的信息素大小有关的。其概率选择函数如式。 表示期望启发式因子，反映蚂蚁选择路径受启发函数影响的大小。值越大，启发函数对蚂蚁选择路径的影响越大，反之亦然。 随着时间流逝，路径上如果遗留的信息素太多就消弱启发信息的作用，所以在每只蚂蚁每访问完一个城市或者访问完所有城市后，需要更新信息素。其更新策略为： 5 蚁群算法的特点 通过分析蚁群算法原理并以实际问题建立数学模型并应用，可以得出其具有以下优点： 1 具有分布式计算和正反应机制特点。分布式计算能够实现多台计算机同时计算，提高了求解速度；正反应机制增强信息素的作用，能够较快地搜索到优化解，节省时间。 2 鲁棒性强，只需对模型稍作改动，就可以对其他各类问题进行优化。 3 为了改善算法性能，较容易与其它启发式算法结合使用。 4 个体之间可以进行信息交换，而且通信开销增较小。 虽然蚁群算法已应用于许多实际问题，而且具有许多优点，但同样也有缺陷： 1 该算法的初阶搜索时间较长影响了搜索效率。这主要是因为，在初始时刻每条路径上的信息素是一样的，只有随着时间的 增加，在信息正反应的作用下，才能表达出各条路径的差异最终求解较优解。但这个过程一般需要的时间比拟长，尤其是在求解大规模优化问题时，占用时间很长，影响了效率。 2 该算法比拟容易收敛到局部最优解。这主要是因为正反应的作用下，加速了信息素的沉积，当还没有找到全局最优解时，所有个体就可能搜索到了完全一致的解，但这只是局部最优解，而使算法无法再进行进一步的搜索。 尽管蚁群算法具有这样的缺陷，但只要找到原因还是可以解决的，比方适当增减信息素正反应影响，与其它算法相结合等等。该文通过对蚁群算法的分析为后期对其改良应用提供了良好的根底。 参考文献： 【1】 段海滨.蚁群算法原理及其应用M .北京：科学出版社，2005. 【2】 汪定伟，王俊伟，王洪峰，等.智能优化方法M.北京：高等教育出版社，2007. 【3】 马良，朱刚，宁爱兵.蚁群优化算法M.北京：科学出版社，2021.