进化策略与蚁群算法融合的求解旅行商问题

2012年04月13日10:49:38 本网站我要评论(2)字号：T | T | T

关键字：应用

丛　爽，贾亚军
中国科学技术大学自动化系，安徽合肥

摘　　　要：针对进化策略收敛速度快但容易陷入早熟收敛以及较大较小蚂蚁系统求解能力强但收敛速度较慢的特点，将进化策略与较大较小蚂蚁系统融合，并利用较大较小蚂蚁系统求出每一步迭代的较优解，再对迭代出较优解进行进化策略中的变异操作来加快解的收敛速度。将所提出的算法应用到中国旅行商问题（ＣＴＳＰ）的实际应用中，其结果显示出优越性。

关　键　词：进化策略；蚁群算法；较大较小蚁群系统；中国旅行商问题

１　引　言
２０世纪６０年代初，德国的Ｒｅｃｈｅｎｂｅｒｇ等人提出了进化策略，其优点是［１３］：具有大范围全局搜索的能力；并行算法；搜索使用适应度函数作为评价函数，过程简单。但它同时也有自身的缺点：对于系统中上一代解的信息利用不够，当求解到一定范围时往往做大量无用的冗余迭代，即容易陷入早熟收敛，求较优解效率较低。蚁群算法是一种基于种群的模拟进化启发式算法。它是在对自然界中真实蚁群的集体行为研究的基础上，于２０世纪９０年代由意大利学者Ｄｏｒｉｇｏ等人首先提出。其优点是［４５］：蚁群算法作为对蚁群觅食行为的抽象，体现了群体行为的分布式特征；它是一种自组织算法；它是一种正反馈的算法。蚁群算法在解决一些小规模的ＴＳＰ问题时表现尚可令人满意。但随着问题规模的扩大，由于初期信息素的匮乏，很难在可接受的循环次数内找到较优解，收敛速度较慢。近年来不断有学者提出了许多改进算法［５］，如带精英策略的蚂蚁系统（ＡＳｅｌｉｔｅ），蚁群系统（ＡＣＳ），较大－较小蚂蚁系统（ＭＭＡＳ）等。针对进化策略和较大较小蚂蚁系统各自的优缺点，本文将进化策略与较大较小蚂蚁系统融合，利用ＭＭＡＳ生成迭代较优解，对迭代较优解采用进化策略中的变异操作，并将其应用到中国旅行商问题（ＣＴＳＰ）中。

登录网站后可下载文件

进化策略与蚁群算法融合的求解旅行商问题

相关阅读: