一种自适应蚁群算法及其仿真研究_王颖

一种基于监工机制的改进蚁群算法朱会杰;王新晴;张红涛;赵洋;李艳峰【摘要】针对基本蚁群算法存在收敛速度慢、易陷入局部最优解等问题,受监工机制的启发,提出了监工蚁群算法,以监工距离作为评价标准,自适应地选择优良的蚂蚁更新信息素,提高了每次迭代中解的质量,指导之后的蚂蚁进行更好的学习.该算法选用优化的全局更新策略,使得信息素在进化前期增加较多,在后期增加较少;同时,自适应地将信息素的值限定在一定范围内,防止某条路径被选择的概率过大或者过小.该算法还添加了发散和收敛机制,当算法陷入局部最优解时,增加探索的概率,有助于跳出局部最优解.仿真结果表明,监工蚁群算法具有较高的全局寻优能力,减少了迭代次数,增强了算法的稳定性.【期刊名称】《解放军理工大学学报（自然科学版）》【年(卷),期】2014(015)002【总页数】6页(P165-170)【关键词】蚁群优化算法;监工机制;自适应;局部搜索;旅行商问题【作者】朱会杰;王新晴;张红涛;赵洋;李艳峰【作者单位】解放军理工大学野战工程学院,江苏南京210007;解放军理工大学野战工程学院,江苏南京210007;防空兵学院,河南郑州450052;解放军理工大学野战工程学院,江苏南京210007;解放军理工大学野战工程学院,江苏南京210007【正文语种】中文【中图分类】TP18蚁群算法是一种应用于组合优化问题的启发式搜索算法，该算法能够在较少的初始条件下，通过启发式搜索、全局优化迅速获得全局最优解，具有鲁棒性、正反馈性以及易与其他算法相结合等优点，已广泛用于解决NP(non-deterministics polynomial)问题，如网络通信、多目标分配、机器人路径规划、数据挖掘、参数辨识、图像处理等[1～5]。

由于蚁群算法采用随机概率选择和信息素正反馈策略，导致算法存在稳定性差、收敛速度慢、易陷入局部最优解等问题。

针对上述问题，本文提出一种基于监工机制的蚁群算法，该算法通过添加监工距离这一动态收敛标准，采用优化的信息素更新策略，促使蚂蚁选择优良的路径，以期取得良好的效果，为蚁群算法的改进提供一种新的思路。

基于蚁群算法的子阵级自适应多波束形成
张忠民;李蔚然
【期刊名称】《应用科技》
【年(卷),期】2022(49)1
【摘要】在大型阵列信号处理中,可以在子阵级进行数字波束扫描形成多波束,降低硬件成本和系统复杂度,其中子阵划分的优劣直接决定信号处理的性能。

针对子阵级多波束形成的问题,提出了一种基于蚁群算法的子阵划分最优策略,该策略将蚂蚁的迁移路径作为子阵划分方案,以峰值旁瓣电平为优化目标进行迭代搜索,使得子阵级自适应形成多波束方向图的旁瓣性能达到最优。

首先,分析了蚁群算法的基本原理,对子阵划分问题的解空间进行建模,设计最优策略并求解得子阵划分方案;然后采用线性约束最小方差准则(LCMV)计算子阵级权矢量,形成多波束方向图;最后通过对比分析了多波束方向图的性能。

仿真实验证明了所提算法得出的子阵划分以及激励匹配方案的有效性。

【总页数】7页(P83-89)
【作者】张忠民;李蔚然
【作者单位】哈尔滨工程大学信息与通信工程学院
【正文语种】中文
【中图分类】TN957.2
【相关文献】
1.基于伪随机码加权的非均匀天线阵自适应多波束形成方法
2.基于遗传算法的均匀子阵数字多波束形成研究
3.对称指数分布的子阵级多波束形成方法
4.基于SOCP 理论的子阵级干扰多波束形成方法
5.基于罚函数和特征空间的子阵级自适应波束形成
因版权原因，仅展示原文概要，查看原文内容请购买。

自适应的并行蚁群算法
陈崚;章春芳
【期刊名称】《小型微型计算机系统》
【年(卷),期】2006(27)9
【摘要】本文根据影响并行蚁群算法性能的关键因素,提出了一种自适应的并行蚁群算法.首先提出了基于适应度和基于距离选择的两种不同的信息交流策略,使得各处理机自适应地选择与之进行信息交换的处理机,然后采用自适应的更新策略进行信息素的更新.为了增强该算法的搜索能力,还根据解的多样性给出了自适应地调节处理机之间的信息交流周期的方法.在MPP处理机深腾1800上对TSP问题的实验结果表明了该算法在保证有效的加速比的同时,具有很好的收敛性.
【总页数】5页(P1695-1699)
【作者】陈崚;章春芳
【作者单位】扬州大学,信息工程学院计算机系,江苏,扬州,225009;南京大学,计算机软件新技术国家重点实验室,江苏,南京,210093;扬州大学,信息工程学院计算机系,江苏,扬州,225009
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.自适应并行蚁群算法在TCP网络速率控制中的应用 [J], 李向丽;周林成
2.并行设计任务调度的自适应蚁群算法 [J], 张金标;陈科
3.基于并行多种群自适应蚁群算法的聚类分析 [J], 高坚
4.并行蚁群算法中的自适应交流策略 [J], 陈崚;章春芳
5.自适应并行机制的改进蚁群算法 [J], 夏鸿斌;须文波;刘渊
因版权原因，仅展示原文概要，查看原文内容请购买。

求解自适应组合优化蚁群算法的研究
孙泽宇;邢萧飞
【期刊名称】《计算机工程与应用》
【年(卷),期】2009(045)035
【摘要】传统的组合优化蚁群算法在求解过程中要消耗大量的时间,极易陷入局部最优化求解等弊端,同时还会产生大量无用的冗余迭代码,运算效率低.对此,提出了自适应组合优化蚁群算法.通过对改变信息素的迭代、参数选择的分析和增加对信息素局部更新方式,提高了整个系统运算速度及收敛速度,扩充了优化的范围,克服了无用迭代码的产生,减少了停滞现象的出现.通过该算法对旅行商问题进行仿真实验,其结果表明了该算法的可行性和有效性.
【总页数】4页(P31-33,37)
【作者】孙泽宇;邢萧飞
【作者单位】洛阳理工学院,计算机与信息工程系,河南洛阳,471023;中南大学,信息科学与工程学院,长沙,410083;日本筑波大学计算机与科学系,日本,筑波,305-8573【正文语种】中文
【中图分类】TP18
【相关文献】
1.求解车辆行程优化问题的自适应蚁群算法研究 [J], 张颖;向永生
2.基于自适应蚁群算法的旅行商问题的求解 [J], 黄志华
3.求解TSP问题的自适应模拟退火蚁群算法 [J], 袁汪凰;游晓明;刘升;朱艳
4.自适应蚁群算法求解最短路径和TSP问题 [J], 易正俊;李勇霞;易校石
5.改进自适应蚁群算法求解集装箱装载瓦楞纸板问题 [J], 高林;姜旭辉;朱庆港因版权原因，仅展示原文概要，查看原文内容请购买。

基于蚁群算法多层次动态信息提取仿真研究王娅森;刘厚泉【期刊名称】《计算机仿真》【年(卷),期】2012(29)5【摘要】The research dynamic interest preference captures accuracy problems. For large data in the network structure caused by defects such as slow searching information, in order to be able to retrieve the user interest of more information, and proposes an improved ant colony algorithm user interests mode acquisition algorithm was presented for hierarchical structure, this paper firstly information website, according to the website and user interests have gra-dation , and then modified characteristics nf ant colony algorithm higher searching mechanism, using the ants foraging cycle from all levels for activities, the corresponding path pheromone strength, and timely implement pheromone up-date mechanism, thus obtains the user to the node preferences function values, again according to the user's interests mode. For value Simulation experiments show that the proposed method can effectively capture a user interests infor-mation , capture more accurate, is a kind of effective method.%研究动态信息偏好捕捉精确度问题.网络数据存在重复性信息和随机性强.针对互联网中的大量数据,而造成了有效的信息的查找速度慢等缺陷,为了能够快速的获取更多的用户比较感兴趣信息,提出了一种改进的蚁群算法用户兴趣模式获取技术.面向层次结构的信息网站,算法首先根据网站和用户兴趣所具有的层次性特征,然后采用改进的蚁群算法较高的寻优机制,利用蚂蚁的觅食周期活动,从各个层次求出相应路径的信息素浓度,并适时的实行信息素更新机制,从而得到用户对该结点的偏好函数值,再依据此值求得用户兴趣模式.仿真结果表明,提出的方法能够有效地捕捉出用户兴趣信息,捕捉精确度较高,是一种有效的方法,具有一定的推广价值.【总页数】4页(P133-135,195)【作者】王娅森;刘厚泉【作者单位】中国矿业大学计算机科学与技术学院,江苏徐州221116;中国矿业大学计算机科学与技术学院,江苏徐州221116【正文语种】中文【中图分类】TP391.9【相关文献】1.基于多层次细节模型的动态切削力仿真 [J], 何伟;宾鸿赞;张何军2.基于蚁群算法的无人机航迹规划及其动态仿真 [J], 王绪芝;姚敏;赵敏;胡中华3.基于动态自适应蚁群算法的航线规划仿真 [J], 张欢;吴军;彭芳4.基于仿真和蚁群算法的公交动态交通规划研究 [J], 夏立国5.基于改进蚁群算法的无人机遥感高程信息提取方法 [J], 张向涛因版权原因，仅展示原文概要，查看原文内容请购买。

一种快速全局优化的改进蚁群算法及仿真
段海滨;王道波
【期刊名称】《信息与控制》
【年(卷),期】2004(33)2
【摘要】在介绍基本蚁群算法原理的基础上 ,对其作了许多改进以提高其全局优化寻优速度 ,并给出了详尽的新算法编程仿真实现步骤 ,最后将未改进的基本蚁群算法与本文改进后的蚁群算法分别应用于TSPLIB中的Att5 32TSP问题进行了仿真实验 .仿真研究表明 ,改进后的算法具有优良的全局优化性能。

【总页数】4页(P241-244)
【关键词】蚁群算法;启发式仿生进化算法;全局优化;仿真
【作者】段海滨;王道波
【作者单位】南京航空航天大学自动化学院
【正文语种】中文
【中图分类】O242.23;TP391.9
【相关文献】
1.一种改进的快速传输控制协议及其在OPNET下的仿真实现 [J], 翟鹏;刘锋
2.一种改进蚁群算法的仿真研究 [J], 李金汉;杜德生
3.一种基于改进全局信息素更新效率的蚁群算法及仿真 [J], 叶仕通;万智萍
4.一种改进蚁群算法的无人机避险方法仿真研究 [J], 吴学礼;贾云聪;张建华;甄然
5.一种改进蚁群算法的移动机器人快速路径规划算法研究 [J], 谭会生;廖雯;贺迅宇
因版权原因，仅展示原文概要，查看原文内容请购买。

基于智能蚁群算法的路径规划与优化研究智能蚁群算法是一种基于自然界中蚂蚁寻路行为的优化算法。

它模拟了蚂蚁在寻找食物时的规律和策略，通过大量的蚁群个体之间的交流和协作，不断寻找最优路径。

在路径规划和优化领域，智能蚁群算法已经被广泛应用，并且在很多问题中获得了非常良好的效果。

优化问题是人类在计算机科学、工程学、生物学等众多领域中面临的问题之一。

在这些领域中，优化的问题通常都可以被看做是寻找最优解的问题。

不过，由于优化问题的复杂度非常高，特别是在实际应用中，通常会面临着大量的约束条件、未知的参数和非线性问题等复杂情况。

这时候，智能蚁群算法优化算法就起到了重要作用。

通过模拟蚂蚁在寻找食物时的行为和策略，智能蚁群算法能够有效的解决一些复杂的优化问题。

相比于传统的优化算法，智能蚁群算法具有以下的优点。

首先，智能蚁群算法具有较好的鲁棒性。

由于该算法模拟自然界中的动物寻路行为，蚁群个体之间输入输出非常简单，因此算法具有很高的兼容性和鲁棒性。

即使在某个蚁群个体出现失效的情况下，整个算法系统也不会因此而崩溃。

其次，智能蚁群算法能够自适应。

蚂蚁在寻找食物时，会根据周围环境的变化来自适应调整自己的行为和策略。

在智能蚁群算法中，每个蚂蚁节点也会根据自身的数据来调整自己的路径搜索策略，达到更优的效果。

最后，智能蚁群算法聚类效果良好。

在寻找食物时，蚂蚁节点会通过一个简单的信息传递机制来寻找最优食物位置。

在计算机算法中，智能蚁群算法也会通过这种信息传播方式来避免重复搜索，并且提高搜索效率。

在路径规划和优化问题中，智能蚁群算法也被广泛应用。

对于一个定位的问题场景来说，智能蚁群算法可以有效的寻找到最短路径。

在蚁群行动过程中，逐渐建立了路径信息素分布模型，已经过的路径留下的信息仍会影响后续的选择，从而获得更加优秀的解。

在实际应用中，智能蚁群算法可以用于非常多的应用场景。

例如，在交通出行中，可以利用智能蚁群算法来进行路径规划和优化；在机器人路径规划中，也可以利用智能蚁群算法来确定最优路径；在电力系统中，可以利用智能蚁群算法来优化发电和输电效率。

基于动态启发算子的双种群蚁群算法及其应用尹元元;游晓明;许明乐;刘升【摘要】针对传统蚁群优化(ACO)算法容易陷入局部最优、收敛速度慢等问题,提出一种基于动态启发算子的双种群蚁群算法.提出了基于已有路径的动态随机启发函数,避免算法陷入局部最优;引入新种群,并通过共享信息素实现种群间的交互,调整两种群参数,加快算法收敛速度.提出的算法应用于移动机器人路径规划仿真实验,结果证明了改进算法的有效性.【期刊名称】《传感器与微系统》【年(卷),期】2018(037)009【总页数】3页(P158-160)【关键词】蚁群优化算法;路径规划;动态启发函数;双种群【作者】尹元元;游晓明;许明乐;刘升【作者单位】上海工程技术大学电子电气工程学院,上海201600;上海工程技术大学电子电气工程学院,上海201600;上海工程技术大学电子电气工程学院,上海201600;上海工程技术大学机械工程学院,上海201600【正文语种】中文【中图分类】TP3910 引言许多智能算法用于解决移动机器人路径规划问题，并取得了很好的效果，其中蚁群优化(ant colony optimization,ACO)算法首先成功解决了旅行商问题[1]，其后在组合优化领域得到了广泛应用[2～4]。

然而，蚁群算法在解决路径规划问题时存在收敛速度慢、易陷入局部最优解等问题。

为了提高算法的收敛速度，唐良等人[5]引入了方向启发，加强搜索限定搜索范围为从起点到终点的椭圆区域。

柳长安等人[6]提出了根据目标点自适应函数作为启发因子，加快了算法收敛速度。

文献[7]通过建立双蚁群完全交叉算法，解决复杂凹形障碍环境下的机器人路径规划问题，仿真实验结果证明了该算法的有效性。

文献[8]引入双种群独立搜索，保证解的多样性的同时，提高算法收敛速度。

文献[9]采用两个蚁群分别进行进化求解，并定期交换优良解，增加了解的多样性。

本文算法采用双种群A与B，首先由蚁群A构造一条完整路径，在该路径上随机选取两点作为种群B的起点和终点，重新规划两点之间的路径，并比较两段路径优劣，判断是否进行该段解的替换，并全局更新种群B规划所得路径的信息素。

基于改进蚁群算法的机器人全局路径规划
王艳春;郭永峰;夏颖;王洋洋
【期刊名称】《电子科技》
【年(卷),期】2024(37)5
【摘要】针对传统蚁群算法存在初始信息素缺乏、收敛速度慢以及无法有效躲避障碍物等问题,文中提出了一种基于改进蚁群算法的全局路径规划。

引入正态分布函数改进传统启发函数,提高了算法效率,缩短了算法收敛所需时间。

自适应调整信息素挥发系数,限定信息素范围,避免过早收敛。

对算法路径平滑处理,缩短路径长度,从而实现机器人的全局路径规划。

仿真结果表明,在20×20环境下,文中算法平均迭代次数比传统蚁群算法减少了28代,收敛速度更快。

平均拐点减少了33.3%,使路径更为平滑,克服了初始信息素缺乏,加快了收敛速度,减少了拐点数量,能够有效躲避环境中的障碍物,证明了该算法的可行性。

【总页数】7页(P88-94)
【作者】王艳春;郭永峰;夏颖;王洋洋
【作者单位】齐齐哈尔大学通信与电子工程学院
【正文语种】中文
【中图分类】TP242.6
【相关文献】
1.基于改进蚁群算法的煤矿救援机器人全局路径规划研究
2.基于改进蚁群算法的机器人全局路径规划研究
3.基于改进蚁群算法的移动机器人全局路径规划
4.基于改进蚁群算法的四足巡检机器人全局路径规划方法
因版权原因，仅展示原文概要，查看原文内容请购买。

基于云模型的自适应蚁群算法改进研究刘争艳;李絮;王慧玲【期刊名称】《计算机工程与应用》【年(卷),期】2016(052)019【摘要】To overcome the slow convergence and local extrema of ant colony algorithm, the cloud model theory is adopted to regulate reasonably the degree of randomness of the ant colony algorithm. Several adaptive strategies are proposed for the parameters of the ant colony algorithm and the cloud model, and for the optimum path determination. Meanwhile, the evaluation algorithm of pheromone distribution is proposed. Simulation results for multiple TSP validate the efficiency and stability of the proposed algorithm.%为了解决蚁群算法易早熟于局部最优及收敛速度慢的问题，采用云模型理论来合理调控蚁群算法的随机性程度，分别提出针对蚁群算法参数、云模型参数以及较优路径判定的自适应调整策略，同时提出信息素分布状态的评价算法。

针对多个TSP问题进行仿真实验，结果验证了提出的算法的高效性与稳定性。

【总页数】5页(P68-71,83)【作者】刘争艳;李絮;王慧玲【作者单位】阜阳师范学院计算机与信息工程学院，安徽阜阳 236037;阜阳师范学院计算机与信息工程学院，安徽阜阳 236037;阜阳师范学院计算机与信息工程学院，安徽阜阳 236037【正文语种】中文【中图分类】TP18【相关文献】1.基于云模型理论的蚁群算法改进研究 [J], 段海滨;王道波;于秀芬;朱家强2.基于云模型的模糊自适应蚁群算法研究 [J], 李絮;刘争艳3.一种基于云模型的自适应蚁群算法 [J], 李絮;郭英;刘争艳4.基于云模型的参数自适应蚁群遗传算法 [J], 牟峰;王慈光;袁晓辉;薛锋5.一种基于云模型改进蚁群聚类算法的研究 [J], 谢彦峰;米伟因版权原因，仅展示原文概要，查看原文内容请购买。

基于蚁群算法的物流配送优化研究随着互联网的快速发展，电商的崛起，物流配送也逐渐成为一个重要的话题。

高效的物流配送系统可以大幅缩短货物运输时间，降低物流成本，提升企业竞争力。

然而，如何实现这一目标，却是一个艰巨的挑战。

基于蚁群算法的物流配送优化研究，成为了当前的一项热门课题。

一、蚁群算法的概念蚁群算法是一种模拟蚂蚁群集在食物源之间搜索路径的算法。

它模拟了蚂蚁的行为，通过蚂蚁在空间中留下的信息素以及蚂蚁本身的搜索、移动、辨别等行为来寻找最优解。

在物流配送问题中，提供给蚂蚁的信息素包括地理位置、道路拓扑等基础信息，以及配送订单等业务信息。

对于每一个配送订单，蚂蚁根据任务的距离、紧急程度等信息决定路径和配送的优先级，以此实现效率最大化的配送策略。

二、蚁群算法的应用蚁群算法已被广泛应用于各种优化问题中，如TSP（旅行商问题）、VRP（车辆路径问题）、FJSP（柔性作业车间调度问题）等。

在物流配送中，蚁群算法主要应用于：1、配送路径规划传统的配送路径规划方法往往基于启发式算法或运筹学等理论，它们尝试通过给定的约束条件生成一组可接受的配送路线。

但实际配送问题往往具有极其复杂的业务约束，使得制定一种可行的算法变得异常困难。

而蚁群算法在此方面表现出色，它可以很好地处理高度复杂的路径规划问题，通过大量迭代和试错来求解最优解。

2、车辆调度在物流配送中，车辆调度是一项非常重要的工作。

由于客户需求的不同，每个车辆的负载量、行驶距离以及配送耗时都必须考虑到。

在传统的车辆调度算法中，往往采用“分区贪心法”或“遗传算法”等方法，但它们都可能会导致调度的不确定性。

而蚁群算法则可以在保证配送质量的同时，实现车辆调度的高效性。

3、全局多目标优化物流配送本质上是一种复杂的全局多目标优化问题。

在许多情况下，如何在达到最佳配送质量的同时，最大化配送效率，是物流配送中需要解决的难点。

而蚁群算法则可以帮助企业实现可持续发展，通过动态调整配送策略，不断提高配送质量的同时，实现物流成本的最小化。

一种自适应多种群的PSO算法
夏学文;王博建;金畅;何国良;谢承旺;魏波
【期刊名称】《系统仿真学报》
【年(卷),期】2016(28)12
【摘要】针对粒子群算法易早熟收敛、逃离局部最优能力差、精度低等缺点,提出了一种自适应多种群PSO算法(Self-adaptive Multi-swarm Particle Swarm Optimization,SMPSO)。

算法通过多个子种群独立进化和自适应重组操作既保持了种群多样性又实现了子种群间的信息共享与交互;同时,通过对粒子历史最优解进行周期性采样与统计,进而指导算法进行探测操作,不仅增强算法的全局搜索能力,也提高其跳出局部最优的能力;最后,引入了两种局部搜索策略提升了算法的收敛速度和求解精度。

通过和其它PSO算法在标准测试函数和工程应用的实验对比表明,SMPSO在逃逸能力、收敛速度和求解精度上有显著提高。

【总页数】10页(P2887-2895)
【作者】夏学文;王博建;金畅;何国良;谢承旺;魏波
【作者单位】华东交通大学软件学院智能优化与信息处理研究所;武汉大学计算机学院
【正文语种】中文
【中图分类】TP301
【相关文献】
1.一种新的双种群PSO-DE混合算法
2.基于种群多样性的自适应PSO算法求解VRPSPD问题
3.基于多种群的自适应迁移PSO算法
4.一种自适应调整种群子代数量\r与步长的优化算法——爆米花算法
5.一种非线性动态自适应惯性权重PSO算法
因版权原因，仅展示原文概要，查看原文内容请购买。

分类号学号2003612100232学校代码1 0 4 8 7硕士学位论文一个改进的蚁群聚类优化算法及其仿真实验研究学位申请人罗增琦学科专业：计算机应用技术指导教师：陈传波教授答辩日期：2006年4月25日A Thesis Submitted in Partial Fulfillment of the Requirements for the Degree of Master of EngineeringStudy on An Improved Algorithm And SimulationExperiment Based on Ant Colony ClusteringCandidate:Luo ZengqiMajor:Computer Application TechnologySupervisor:Prof.Chen ChuanboHuazhong University of Science&TechnologyWuhan 430074,P.R.ChinaApril,2006摘要群体智能以分布性、简单性、灵活性和鲁棒性得到了越来越广泛的关注。

蚁群聚类算法是数据挖掘算法的一种，它起源于科学家对群体性昆虫的观察和研究。

Lumer和Faieta将Deneubourg提出的基本模型成功地推广应用到聚类分析。

LF算法仍然存在一些局限性，它的算法机制无法将偶然堆叠在一起的簇分开，造成了聚类结果往往纯度不高，严重影响了查准率。

为了克服LF算法的缺点，通过结合模糊聚类算法，提出了一种改进的蚁群聚类算法。

该算法回溯到Deneubourg的基本模型，通过引入相似因子、相异因子的概念，改变观察分数f的计算方法，进而达到影响拾起放下概率的目的。

相似因子大小由邻域内选定对象所属的等价分类的大小决定，相异因子大小由邻域内与不包含该对象的一个最大的等价分类的大小决定。

在这种方法下，蚂蚁具备从感官上初步划分存在于邻域内的数据对象的能力，以此作为进行下一步决策的依据。

基于优化成熟度的自适应蚁群优化算法郭小芳【摘要】通过深入分析蚁群算法中信息素更新系数对算法寻优能力与收敛速度的影响,定义了平均路径相似度(ATS)来表征寻优过程的成熟程度,据此自适应调整信息素更新系数,以提高算法收敛速度,并避免陷入局部最优.经过与典型蚁群算法在多个旅行商问题测试用例上进行比较,表明新算法具有更好的效果.【期刊名称】《西北师范大学学报（自然科学版）》【年(卷),期】2010(046)006【总页数】5页(P37-41)【关键词】蚁群优化;平均路径相似度;自适应参数控制【作者】郭小芳【作者单位】江苏科技大学,计算机科学与工程学院,江苏,镇江,212003【正文语种】中文【中图分类】TP301.6蚁群优化(Ant Colony Op timization,简称ACO)是Dorigo M受蚁群觅食行为的启发提出的一种新型的群智能优化算法[1,2],该算法在解决著名的NP问题——旅行商问题(TSP)以及一些复杂的优化组合问题上取得了很好的效果,受到越来越多国内外学者的重视,并提出一系列改进策略,以进一步提高该算法的性能.比较著名的有Bullnheimer等人提出的基于排序的蚂蚁系统(RAS)[3],Stützle等人提出的最大最小蚂蚁系统(MMAS)[4],Dorigo和 Gambardella提出的Ant-Q算法[5]以及 Ant-Q的改进版本——蚁群系统(ACS).其中,ACS算法设计了信息素的全局更新和局部更新两种规则,是性能最优的ACO算法之一[6].在处理规模较大的问题时,与其他计算智能算法一样,ACS算法也存在收敛较慢和容易陷入局部最优的问题[7].通过合理地设置ACS算法中的一系列控制参数,可以缓解收敛速度与搜索停滞之间的矛盾.然而,目前对参数选择没有严格的理论依据,根据经验和试验来选取合适的最佳取值通常与具体问题相关,普适性不高[8].因此,设计出一种自适应参数调整的策略对提高算法收敛速度、求解精度以及增强算法的普适性有着重要的意义.笔者在ACS框架下,定义了平均路径相似度(A TS)表征寻优过程的成熟程度,据此自适应调整信息素更新系数,提出改进的自适应ACS算法.经过与典型蚁群算法在多个旅行商问题测试用例上进行对比测试,验证了新的算法具有较快收敛速度与较强的全局寻优能力. 1.1 ACS算法描述以求解TSP为背景介绍ACS算法,具体步骤如下.1)初始化.设置所有边上信息素的初始值,并将所有蚂蚁放置到随机选择的初始城市上.2)构建路径.每只蚂蚁应用伪随机比例状态转移构建出一条路径.当蚂蚁k位于城市r,它将根据(1)式选择城市s作为下一个城市进行转移:其中,τ(r,u)表示城市r和u之间路径上的信息素浓度;μ(r,u)表示启发信息,即城市 r 和 u之间距离的倒数;JK(r)表示未被访问的城市集合;β是平衡信息素和距离启发信息影响力的系数;q是分布在[0,1]之间的随机数;q0为固定参数.若q≤q0,蚂蚁将选择相应边的信息素与启发信息乘积最大的城市进行转移;否则将按照(2)式选择城市转移:以上过程将重复执行直到所有蚂蚁都构建完成一条完整路径.3)局部信息素更新.在构建路径时,蚂蚁将按照(3)式对刚经过的边(r,s)上的信息素进行更新:其中,ρ为局部信息素挥发比例系数;τ0是信息素的初始值.4)全局信息素更新.当所有蚂蚁都构造出一条完整路径后,对最优路径上所有边进行全局信息素更新:其中,α表示全局信息素挥发比例系数;Δτ定义为其中,Lbest表示最优路径的长度;best-tour表示最优路径中所有城市的集合.5)返回步骤2)重复执行,直到算法满足终止条件.1.2 相关参数分析信息素更新的目的是加强较优的路径,削弱较差的路径,以引导搜索快速向较优路径周围收敛.然而,在经过一定次数的迭代后,信息素将集中分布在较少的几条较优路径上,蚂蚁选择其他路径的概率大大降低,此时算法极易陷入局部最优.如何恰当地使用信息素更新规则,将成为实现算法快速收敛并跳出局部最优的关键.对于ACS算法来说,全局信息素更新控制系数α取值越大,最优路径上的信息素积累越快,可以加快收敛速度,却容易陷入局部最优;而局部信息素更新控制系数ρ若取值较大,可提高搜索的随机性,但导向性不强,收敛速度较慢.如图1所示,α和ρ分别取较大值和较小值时,求解TSP(测试实例采用eil 76,见表1)时所得的最优路径长度随迭代次数的变化情况,其中横轴代表迭代次数,纵轴代表每次迭代的最优路径长度.从图1中可以看出,在前100次迭代中,α取较大值0.25的收敛速度要快于取最小值0.05.然而,随着迭代次数增加,α取最小值有更好的全局搜索能力,表现为在算法运行后期有更强的收敛能力,获得更优的解.从图2中可以看出,在初始阶段,ρ取较小值,信息素挥发的速率慢,有利于信息素在较短路径上的积累,因此收敛速度快;然而,在算法优化接近成熟阶段,ρ取较大值才能保证较好的全局搜索能力,因为此时需要以较快的速率对较短路径上的信息素进行挥发,保持路径的多样性,才能避免搜索陷入局部解而停滞.在ACS算法优化的初始阶段,为了提高算法的收敛速度,必须在较短路径上释放较多的信息素,此阶段α的取值应该较大,而的ρ取值应该较小.当算法优化进入“成熟”阶段,即大量信息素集中于几条较短路径上时,较短路径上的信息素应该挥发减少,以避免搜索陷入局部最优解,开拓更多新的路径.因此,此阶段α的取值应该较小,而ρ的取值应该较大.由上文分析可知,算法需要判断当前优化所处状态是否“成熟”,实现对α和ρ自适应调整.(6)式和(7)式分别表示对α和ρ的取值进行调整的一般形式:其中,φ是算法优化成熟度的指示器.2.1 基于路径相似度的优化成熟度的判断在算法的初始阶段,蚂蚁群体构建出来的路径差异较大.随着全局信息素的更新,算法的优化过程逐渐进入成熟状态后,信息素的分布逐渐集中到较短的路径上,蚂蚁将向较短路径上进行转移,此时蚂蚁构建出来的路径相似度会很高.可以根据所有路径与最短路径的相似程度来判断算法优化的成熟程度,文中定义一种“平均路径相似度(sAT)”来进行度量.sAT的计算步骤如下:1)每只蚂蚁k分别计算自身构建出来的路径Tk与当前最优路径 Tbest之间的相似度 s(Tk,Tbest)如下:其含义是 Tk与 Tbest公共边的数目.2)计算平均路径相似度sAT:其中m和n分别是蚂蚁数量和所有城市的数量.2.2 自适应调整的实现用上述sAT量化算法优化成熟程度,对α和ρ的取值进行调整,具体实现方法如下: 在优化的初始阶段,sAT值较小,要求α值较大ρ值较小来加速收敛.当sAT逐渐增大,优化进入了成熟阶段,此时要求α值较小而ρ值较大,以削弱较短路径对蚂蚁的吸引力.因此,aα取值应该为负,而aρ应该为正.这两个系数的大小还决定了α和ρ取值作线性变换的斜率.综上所述,在ACS算法框架下提出改进的基于优化成熟度的自适应蚁群算法(AACS 算法),算法流程如图3所示.为了检验AACS算法的普适性和有效性,使用传统ACS算法与之在 TSPL IB中的4个基准实例进行对比测试,如表1所示.试验设置在每个测试实例上运行100次,每次以5 000次迭代次数作为算法的终止条件.3.1 解路径质量比较由表2可以看出,AACS的解全面优于ACS.在规模最小的o liver 30实例中,AACS 在100次运行中均找到全局最优解,ACS也得到了不错的结果.但随着问题规模的增大,AACS的优越性越来越明显,在eil 51和eil 76实例上找到全局最优解的次数远远高于ACS,而且AACS求解的标准方差更小,即稳定性更高.值得注意的是,在eil 101实例中,ACS已经难以求得已知最优解,而AACS依然保持较好的性能,这得益于在算法成熟阶段对参数和的自适应调整,使得搜索能及时跳出局部最优解,保持开拓新路径的能力.3.2 收敛特性比较图4给出了ACS与AACS在迭代过程中最优路径长度的变化情况,图中横轴代表迭代次数,纵轴代表最优路径长度.其中,图4a,b,c和d分别是oliver 30,eil 51,eil 76和eil 101实例上的测试结果.可以看出,在 oliver 30和 eil 51实例中, AACS在算法前期的收敛速度明显快于ACS,这是因为AACS算法自适应调整得到较大的α值和较小的ρ值来强化最优路径,促进算法的快速收敛.这种效果在eil 76和eil 101中不是很明显,但AACS在优化过程后期相比ACS具有更强的收敛能力,这是由于AACS在算法成熟阶段依然能保持解的多样性.3.3 全局搜索能力比较图5展示了AACS与ACS运行100次(每次迭代次数为5 000),寻找到全局最优次数的累积分布图.其中横轴代表迭代次数,纵轴代表在优化到当前迭代次数时,100次试验累计能够找到全局最优的次数.图5a,b,c和d分别是oliver 30,eil 51,eil 76和eil 101实例上的测试结果.可以看出,在4个实例中AACS均以更快的速度找到更多的次数的全局最优解.由于oliver 30实例的规模较小,因此两种算法的曲线比较接近,但随着实例规模的增大,AACS的全局搜索能力与ACS相比越来越突出.在 eil 51和 eil 76实例中,ACS的曲线在算法后期显得很平缓,这说明ACS算法所发现的全局最优解大多数是在算法前期发现的,这是由于ACS算法在优化后期容易陷入局部最优解的固有缺点所导致的.AACS算法则不同,在整个优化过程曲线都保持快速上升的趋势,这说明无论在优化前期还是后期,AACS都保持着良好的全局搜索能力,不易进入停滞状态,求解的精度更高.【相关文献】[1] COLORIN I A,DORIGO M,MAN IEZZO V. Distributed op timization by ant colonies[M]// Proceedings of the First European Conference on A rtificial L ife.Paris:Pearson Education Limited, 1991:134-142.[2] DORIGO M,MAN IEZZO V,COLORIN I A.Ant system:op timization by a colony of cooperating agents[J].IEEE Transaction on Systems,M an and Cybernetics—PartB,1996,26(1):29-41.[3] BULLNHEIM ER B,HARL R F,STRAUSSC.A new rank based version of the ant system-a computational study[J].Central European Journal of Operations Research and Econom ic,1999,7(1): 25-38.[4] STÜTZL E T,HOOS H.M ax-min ant system and local search fo r the traveling salesman p roblem[M]// Proceedings of the 1997 IEEE International Conference on Evolutionary Com putation. Indianapolis:Pearson Education Limited,1997: 309-314.[5] GAMBARDELLA L M,DORIGO M.Ant-Q:a reinforcement learning app roach to the traveling salesman p roblem[J]. Proceed ings of ML-95. Califo rnia:Pearson Education Limited,1995:252-260.[6] DORIGO M,GAMBARDELLA L M.Ant colony system:a cooperative learning app roach to the traveling salesman p roblem[J].IEEE Transaction on Evolutionary Computation,1997,1(1):53-66.[7] 陈崚,沈洁,秦玲,等.基于分布均匀度的自适应蚁群算法[J].软件学报,2003,14(8):1379-1387.[8] 蒋玲艳,张军,钟树鸿.蚁群算法的参数分析[J].计算机工程与应用,2007,43(20):31-36.[9] 王书明,刘玉兰,王家映.蚁群算法[J].工程地球物理学报,2008,34(19):71-76.[10] 杨洁,杨胜,曾庆光,等.基于信息素强度的蚁群算法[J].计算机应用,2007,22(11):41-44.。