蚁群算法的改进及其在TSP问题中的应用.doc

《蚁群算法的改进及其在TSP问题中的应用.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、蚁群算法的改进及其在TSP问题中的应用雷德明吴智铭上海交通大学自动化研究所200030上海摘要：在过去的10多年，蚁群算法（ACO）的研究和应用取得了很大的进展，大量结果证明了算法的有效性和在某些领域的优势。算法的基本缺陷：搜索时间过长和容易陷入局部解也得到了一定程度的解决，提出了一些有效的方法。但问题并未完全消除。本文首先分析了ACO中产生停滞现象的原因，然后给出了一种解决方案，通过直接交换部分边上的信息素和合理设定每条边的信息素挥发率，来克服算法停滞现象。仿真结果表明上述方法是可行和有效的。关键词：蚁群算法信息素旅行商问题TheImprovementofAntColonyOpt

2、imizationAlgorithmanditsApplicationtoTSPproblemLeiDemingWuZhiming(ShanghaiJiaotongUniversity,InstituteofAutomation,20030,Shanghai)Abstract:TheresearchesandapplicationsonACOalgorithmhavemadegreatprogressesinthepastmorethantenyears.Anumberofresultsprovethevalidityofthealgorithmanditsadvantagesin

3、somefields.Itsbasicshortcomings,whicharelongsearchingtimeandeasilyjumpingintolocaloptimalsolution,alsohavebeenovercomepartiallyandsomeeffectivemethodsareintroduced.However,theproblemsaren’tcompletelysolved.Thispaperfirstanalyzesthegroundsproducingstagnationandthenintroducesanewsolutionforexclu

4、dingstagnation,whichincludesthedirectexchangeofpheromoneonsomeedgesanddynamicallysettingevaporationrateforeachedge.Thesimulationresultsdemonstratethattheaboveapproachisreasonableandefficient.Keyword:AntColonyOptimizationalgorithmpheromoneTSPproblem1．引论蚁群算法（ACO）是受自然界中蚂蚁搜索食物行为启发而提出的一种智能优化算法。单个蚂蚁

5、是脆弱的，但整个蚁群的群居生活却能完成许多单个个体无法承担的工作，蚂蚁间借助于信息素这种化学物质进行信息的交流和传递，并表现出正反馈现象：某段路径上经过的蚂蚁越多，该路径被重复选择的概率就越高。正反馈机制和通讯机制是蚁群算法的两个重要基础。正反馈作用能加快算法的搜索，也会导致算法出现停滞现象，而通讯机制能使个体相互协作，有利于算法搜索到更优解。目前，该算法在组合优化包括TSP,QAP等、车辆路径问题、电力系统中故障点的估计以及通讯网络等诸多领域得到应用。蚁群算法是一种本质并行的算法，和其它智能算法不同，其搜索时间比较长，新解的产生不是直接在已有解的基础上通过变换如GA的交叉算子而得

6、到的，和其他算法一样，该算法也容易陷于局部最优解，使搜索停滞。本文给出了一种改进方案，通过直接交换部分边上的信息素和合理设定每条边的信息素挥发速度，来避免算法出现停滞现象。仿真结果表明新方法是可行和有效的。2．蚁群算法基本原理和遗传算法不同，关于蚁群算法的介绍往往要结合具体问题进行，通常选择的问题是TSP问题。该问题可以描述如下：设有个城市集，任意两个城市之间的距离为，求一条经过每个城市仅一次的路径，使得最小表示t时刻位于城市的蚂蚁的个数，为蚂蚁的总数。表示t时刻边上的信息素量，＝(为常数)。随着时间的推移，新的信息素加进来，旧的信息素要挥发，表示信息素的挥发快慢。当所有蚂蚁完成一

7、次周游后，各条边上的信息素按下式调整：（1）(2)表示本次周游中路径上的信息素增量，初始时刻，＝0。表示第只蚂蚁在周游过程中释放在边上的信息素。（3）为常数，表示本次周游第只蚂蚁所形成的回路的长度。蚂蚁在周游时，向那个城市转移由转移概率决定。（4）其中＝表示蚂蚁当前能选择的城市集合，为禁忌表，它记录蚂蚁已路过的城市，用来说明人工蚂蚁的记忆性。是某种启发信息。在TSP问题中，。体现了信息素和启发信息对蚂蚁决策的影响。蚁群算法基本的运行过程是这样的：只蚂蚁同时从某个城市出