结合邻域耦合机制与双边滤波的双蚁群算法.pdf
《结合邻域耦合机制与双边滤波的双蚁群算法.pdf》由会员分享,可在线阅读,更多相关《结合邻域耦合机制与双边滤波的双蚁群算法.pdf(15页珍藏版)》请在咨信网上搜索。
1、计算机科学与探索Journal of Frontiers of Computer Science and Technology1673-9418/2023/17(09)-2092-15doi:10.3778/j.issn.1673-9418.2205099结合邻域耦合机制与双边滤波的双蚁群算法吴立胜1,游晓明1+,刘升21.上海工程技术大学 电子电气工程学院,上海 2016202.上海工程技术大学 管理学院,上海 201620+通信作者 E-mail:摘要:针对蚁群算法在求解旅行商问题(TSP)中收敛速度慢且易陷入局部最优等问题,提出一种结合邻域耦合机制与双边滤波的双蚁群算法(NBACO)。首
2、先,算法通过战斗力指数将蚁群动态分成士兵蚁与指挥蚁,士兵蚁主要负责提高算法的求解精度,指挥蚁主要负责提高算法的收敛速度,两类蚂蚁分工合作从而有效平衡算法的求解精度与收敛速度。其次,采用邻域耦合机制,当指挥蚁经过公共区间时,在公共区间及其邻域动态散布微量的信息素,以增大对蚂蚁的吸引力,增加蚂蚁选择公共区间及其邻域的概率,从而提高算法的收敛速度。进一步,当算法陷入局部最优时,引入基于基尼不纯度的双边滤波策略,动态削弱当前最优路径上的信息素浓度,进而缩小最优路径与其邻域路径的信息素浓度差,在下一次迭代时增大蚂蚁选择其他非最优路径的概率,从而帮助算法摆脱局部最优。最后,对大量TSP实例进行仿真,实验结
3、果表明改进后的蚁群算法有效平衡了算法求解精度和收敛速度。关键词:蚁群算法;邻域耦合机制;双边滤波;基尼不纯度;旅行商问题(TSP)文献标志码:A中图分类号:TP18Dual Ant Colony Optimization with Neighborhood Coupling Mechanism and BilateralFilteringWU Lisheng1,YOU Xiaoming1+,LIU Sheng21.School of Electronic and Electrical Engineering,Shanghai University of Engineering Science,
4、Shanghai 201620,China2.School of Management,Shanghai University of Engineering Science,Shanghai 201620,ChinaAbstract:To overcome the slow convergence and premature stagnation of the ant colony algorithm in solving travelingsalesman problem(TSP),a dual ant colony optimization with neighborhood coupli
5、ng mechanism and bilateralfiltering(NBACO)is proposed.Firstly,the ant colony is dynamically divided into soldier ants and commanding antsby the combat power index.The soldier ants are mainly responsible for improving the solution accuracy of thealgorithm,and the commander ants are mainly responsible
6、 for improving the convergence speed of the algorithm.And these two kinds of ants coordinate together to balance the relationship between the accuracy and convergencespeed of the algorithm effectively.Secondly,to increase the choosing possibility of the public path in the algorithm,a neighborhood co
7、upling mechanism is used to disseminate a little pheromone both in the public area and itsneighborhood adaptively when the commanding ants visit this area,so that a high convergence speed of thealgorithm is achieved,which can increase the probability of ants choosing public area and its neighborhood
8、.基金项目:国家自然科学基金(61673258,61075115);上海市自然科学基金(19ZR1421600)。This work was supported by the National Natural Science Foundation of China(61673258,61075115),and the Natural ScienceFoundation of Shanghai(19ZR1421600).收稿日期:2022-05-24修回日期:2022-08-25吴立胜 等:结合邻域耦合机制与双边滤波的双蚁群算法智能优化算法是一种模仿自然界生物行为的元启发式算法,常见的智能优化算
9、法有遗传算法1、粒子群算法2、果蝇算法3和蚁群优化4等。由于智能优化算法具有稳定性强、灵活性高等特点,其在解决旅行商问题(traveling salesman problem,TSP)5、路径规划问题6等问题上发挥了令人满意的效果,大量学者使用蚁群算法求解TSP以进一步验证算法性能。20 世 纪 90 年 代,意 大 利 著 名 学 者 Dorigo 和Maniezzo等人通过对自然界蚂蚁的群体觅食行为进行模拟,将蚂蚁所走的路径映射为待优化问题的可行解,进而提出了蚂蚁系统(ant system,AS)7去求解TSP,但该算法求解精度不足且易陷入局部最优。于是,Dorigo 在此基础上提出了蚁群
10、系统(ant colonysystem,ACS)8,与 AS相比,ACS采用信息素全局更新与局部更新两种方式,求解TSP时在一定程度上提高了算法求解精度。同时期,Stutzle等人为了避免信息素更新过多而使算法陷入停滞状态,提出了最大最小蚂蚁系统(MAX-MIN ant system,MMAS)9,其通过给信息素范围设定最大值与最小值,将信息素浓度控制在合理范围内,避免信息素过度累积或挥发而使算法陷入局部最优。以上经典蚁群算法虽然有较高的求解能力,但随着求解TSP规模的增加,仍然会面临收敛速度较慢、算法求解精度需进一步提高等问题。针对以上问题,大量学者提出了自己的改进策略并通过 TSP来验证其
11、性能。其中孟祥萍等人10通过引入方向信息素概念,对寻优过程中较短路径上的信息素进一步强化,以增大蚂蚁选择较短路径的概率。赵鑫等人11在基本蚁群算法中引入遗忘因子,通过对遗忘因子的调整来修正局部信息素的权重与全局信息素的更新,从而提高算法的运行效率。以上改进蚁群算法在求解TSP时,其收敛速度虽有一定的提高,但很难得到更高精度的解,在求解精度等方面还有待进一步提升。针对此问题,许凯波等人12引入一种局部优化策略,即当最优解连续若干次迭代后没有改善时,使用随机插入法对局部最优解中城市的排序进行调整,以扩大算法的搜索范围。杜鹏桢等人13提出一种面向对象的多角色蚁群算法,不同角色的蚁群对不同类别的城市执
12、行不同的搜索机制,同时采用 2-opt策略对最优解进行局部优化以增强算法的鲁棒性。陈颖杰等人14对每次迭代后的最优路径进行变异操作,尝试寻找更优路径,同时当算法停滞时使用信息素回滚策略,以加强蚂蚁搜索能力,使算法更容易跳出局部最优。以上改进蚁群算法在求解TSP时虽然都能够提升算法求解精度,但其收敛速度有待进一步提高。针对此问题,冯振辉等人15引入一种具有较强全局搜索能力的扩展型蚂蚁对路径进行搜索,以增加算法的求解精度。同时提出一种刺激响应分工模型,对蚂蚁个体的信息素更新策略进行改进,以平衡算法的收敛时间与全局搜索能力。张德惠等人16通过将蚁群算法与猫群算法相融合,借鉴猫群分类思想对蚂蚁进行分组
13、,并且通过信息素全局更新机制以缩短算法运行时间。潘晗等人17提出一种动态导向策略,在迭代前期增加属于最大生成树的动态信息素,以增加算法多样性;在迭代后期增加属于最小生成树上的信息素,以提高算法收敛速度。以上改进蚁群算法虽然取得一定的成果,但在求解大规模TSP时,算法在平衡求解精度与收敛速度等方面还有待进一步提高。因此,本文提出结合邻域耦合机制与双边滤波的双蚁群算法(dual ant colonyoptimization with neighborhood coupling mechanism andbilateral filtering,NBACO)并通过 TSP 来验证其性能。首先根据战斗力
14、指数将蚁群动态划分为士兵蚁与指挥蚁,两类蚂蚁分别进行不同的局部信息素更新以执行不同的功能。其中,士兵蚁寻优时随机性较强,以保证算法的多样性;指挥蚁寻优时目的性较强,以保证算法的收敛速度,两类蚂蚁分工合作从而Furthermore,while the algorithm falls into a local optimum,a bilateral filtering strategy based on Gini impurity isintroduced to dynamically decrease the pheromone of the current optimal path.In th
15、is strategy,the pheromoneconcentration difference between the optimal path and its neighboring paths is reduced,which can greatly help thealgorithm get rid of the local optimum and increase the probability of ants choosing other non-optimal paths at thenext iteration.Finally,from a large number of T
16、SP instances,the experimental results show that the improved antcolony algorithm can balance the solution accuracy and convergence speed of the algorithm effectively.Key words:ant colony algorithm;neighborhood coupling mechanism;bilateral filtering;Gini impurity;travelingsalesman problem(TSP)2093Jou
17、rnal of Frontiers of Computer Science and Technology计算机科学与探索2023,17(9)有效提升算法性能。为提高两类蚂蚁的协同效率,进而提出邻域耦合机制,其是指迭代过程中当指挥蚁遇到公共区间时,即蚂蚁当前最优路径与最差路径的相同路径片段,在公共区间及其邻域动态散布微量的信息素,以吸引蚂蚁在公共区间周围进行探索,从而提高算法的导向性。进一步,随着算法迭代次数的增加,当基尼不纯度低于阈值时,表明此时种群多样性较低。为防止信息素过度累积而使算法陷入停滞状态,本文采用双边滤波策略以降低最优路径上的信息素浓度,使之与周围路径信息素浓度差减小,增加蚂蚁选
18、择其他路径的概率,从而增强算法跳出局部最优的能力。结合本文实验结果可得,NBACO相比传统蚁群算法以及其他最新改进算法在求解TSP时解的精度以及收敛速度都有一定的提高。1相关工作1.1ACS的路径构建在ACS8中,蚂蚁构建路径时引入了伪随机状态转移规则,该随机选取机制可提高算法求解精度,其构建公式如下:S=argmaxjallowedijij,q q0Pij,qq0(1)ij=1dij(2)式(1)中,ij表示蚂蚁在经过城市i与城市j时所留下的信息素浓度,q0(0q01)是一个伪随机因子,其影响蚂蚁探索新路径还是搜索至今最优路径,q是一个均匀分布在0,1内的随机数。式(2)中,ij代表算法启发
19、式信息,dij代表城市i与城市 j 之间的欧式距离,代表期望启发式因子。Pij为传统蚁群算法的概率状态表达式,其采用轮盘赌的方式选择路径,更新方式如式(3)所示:Pkij(t)=ij(t)ij(t)lallowedij(t)ij(t),j allowed0,j allowed(3)式(3)中,为信息素启发式因子,若偏小,蚂蚁探索当前非最优路径的可能性增加,算法多样性随之增加;为期望启发式因子,若偏大,蚂蚁在下一次选择路径时优先选择最短路径,算法收敛速度随之提高。allowed代表位于城市i的蚂蚁k可以选择的下一个城市的集合。其他因子与式(1)、式(2)意义相同。1.2信息素更新每只蚂蚁遍历一次
20、完整哈密顿回路之后,需按式(4)对其走过的路径进行信息素局部更新,其作用是缩小最优路径与非最优路径之间的信息素浓度差,以增加算法的多样性,更新方式如式(4)所示:ij=(1-)ij+0(4)式(4)中,代表信息素局部挥发因子,其取值范围在(0,1)之间。局部挥发因子过小易使算法陷入局部最优,过大则会影响蚂蚁对最优路径的探索。0为信息素初始浓度,ij为城市i和城市j之间的信息素浓度。在所有蚂蚁遍历所有回路之后,算法还会对最优路径进行一次全局信息素更新,其更新方式如下:ij=(1-)ij+ij(5)ij=1Lgb(6)式(5)中,ij是至今最优路径上信息素的增量。为信息素全局挥发因子,当全局挥发因
21、子偏小时,易使算法陷入局部最优,难以得到更优解;偏大时,则会使算法收敛速度下降。式(6)中,Lgb是蚂蚁找到的最优路径的长度。1.3基尼不纯度基尼不纯度是机器学习中的一个专业术语,其作为衡量系统混乱程度的一种标准,可以用来表示集合的不确定性。基尼不纯度越高,代表集合的不确定性就越大;基尼不纯度越低,代表集合的不确定性就越小。当基尼不纯度为0时,则表示集合中所有解的类别一致。2改进的蚁群算法(NBACO)2.1启发式寻迹经典蚁群算法在求解TSP时,由于其收敛速度和求解精度之间的矛盾会削弱蚂蚁搜索解的能力,导致算法难以得到更高精度的解。针对此问题,本节提出启发式寻迹策略以提高算法性能,其可描述为将
22、蚂蚁动态划分成士兵蚁与指挥蚁,它们在寻优时分别执行不同的功能,指挥蚁保证算法的收敛速度,士兵蚁保证算法的求解精度,两类蚂蚁分工合作从而平衡算法的收敛速度与求解精度。2.1.1自适应分级首先,每次迭代完成后通过式(7)计算每只蚂蚁的战斗力指数。其次,根据战斗力指数Hi对蚂蚁进2094吴立胜 等:结合邻域耦合机制与双边滤波的双蚁群算法行自适应分级,高于分级指标k的蚂蚁为指挥蚁,低于分级指标k的蚂蚁则为士兵蚁,分级指标k的实验见 3.1.2 小节。战斗力指数Hi的计算公式如式(7)所示:Hi=Lengthmin+Lengthlast_min2Lengthi(7)式(7)中,Lengthmin代表蚂蚁
23、至今所得最短路径长度,Lengthlast_min代表上一次迭代中蚂蚁所得最短路径长度,Lengthi代表第i次迭代中蚂蚁所得的路径长度。由式(7)可知,蚂蚁的战斗力指数值Hi越大,其在第i次迭代中所走的路径长度Lengthi越小,表明蚂蚁在本次迭代中得到更优解。本文综合考虑上一次迭代中最优路径与全局最优路径对蚂蚁进行动态划分,兼顾局部搜索能力与全局搜索能力,以平衡算法多样性与收敛速度,从而更加全面评价每只蚂蚁性能。相较于其他分级方法,如在文献16中,将蚂蚁所走的路径升序排列,排名靠前的蚂蚁定义为跟踪蚁,剩下的即为搜索蚁。此方法虽然也将蚂蚁分成两类,但仅仅依据当代最优路径值划分蚁群,不易准确反
24、映蚂蚁的信息,存在一定的局限性。且其更加强调全局最优的作用,易因划分不精确从而导致算法陷入停滞状态。而NBACO 结合至今最优路径与上一次最优路径长度综合判定,可以更加精确地对蚂蚁进行动态划分,从而保证搜索效率。2.1.2基于战斗力指数的信息素更新蚁群算法中,信息素浓度对蚂蚁选择路径起着十分重要的作用,然而传统 ACS的局部信息素更新方式不能够很好地体现每条路径上的信息素浓度差异,易使算法出现收敛速度慢等问题,故本小节对蚂蚁的局部信息素更新方式进行改进。当蚂蚁完成路径构建后,不同蚂蚁采用不同的局部信息素更新方式以执行不同的功能,其中,士兵蚁按式(8)进行局部信息素更新,指挥蚁按式(9)进行局部
25、信息素更新。ij=(1-)ij+H10(8)ij=(1-)ij+H20(9)式(8)、式(9)中,ij表示城市i与城市j之间的信息素浓度,0表示初始信息素浓度,表示信息素局部挥发因子,H1表示士兵蚁的战斗力指数,H2表示指挥蚁的战斗力指数。在改进局部信息素更新方式中,将不同蚂蚁的战斗力指数作为其选择信息素更新机制的依据。由于指挥蚁战斗力指数大于士兵蚁战斗力指数,故在整个算法运行过程中,指挥蚁在信息素局部更新时占的权重相对较大,其走过的路径对蚂蚁的吸引力也相对较大,故其导向性更强,能够提高收敛速度;士兵蚁所占的权重相对较小,其走过的路径对蚂蚁的吸引力也相对较小,故其随机性更强,能够增加算法解的多
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 结合 邻域 耦合 机制 双边 滤波 双蚁群 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。