蚁群算法的改进及仿真研究

《蚁群算法的改进及仿真研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、西安电子科技大学硕士学位论文蚁群算法的改进及仿真研究姓名：孔翔宇申请学位级别：硕士专业：应用数学指导教师：刘三阳20100101摘要摘要蚁群算法是一种新型的仿生类算法，具有较强的鲁棒性．它采用分布式计算机制，易于实现，已在众多领域取得了广泛的应用．本文主要围绕蚁群优化算法的理论及应用，就如何求解旅行商(TSP)Ih-]题、多目标优化问题进行了研究．本文的主要工作概括如下：首先针对蚁群算法存在停滞现象的缺点，提出一种基于动态权重的选择策略，以强化其全局搜索能力．改进的初始选择策略以信息素为主扩大搜索范围，迭代一定次

2、数后则以路径期望为主，从而提高蚁群算法的求解性能．并将改进后的蚁群算法与基本蚁群算法分别应用于旅行商问题(TSP)进行仿真实验．结果表明，改进后的算法具有优良的求解性能，可抑制算法过早收敛于次优解，有效防止了停滞现象．其次为保持多目标优化问题Pareto最优解的多样性，提出了一种新的蚁群算法．选择策略采用多信息素权重，信息素更新结合了局部信息素更新与全局信息素更新．其中，全局信息素更新采用了两个最好解．此外，通过设置外部集来存储Pareto解，并将改进的算法应用在双目标TSP上．仿真实验结果表明新方法比NSGA．

3、II和SPEA2更有效．关键词：蚁群优化算法；旅行商问题；多目标优化；双目标TSP；动态权重ABSTRACTAntColonyOptimizationalgorithm(ACO)isallalgorithmicapproach,inspiredbytheforagingbehavioroftherealanimals，whichhadbeenappliedtomanyproblems．Thedissertationfocusesontheprinciples，theory,andapplicationsofAnt

4、ColonyOptimizationalgorithm(aco)，especially,allin—deepandsystemicstudyonhowtoimprovethebasicACOalgorithm,parallelimplementationofACO，solvingtheproblemssuchastheTSPproblemandMultipleobjectiveoptimization．First，asisknownstagnationbehaviorisadisadvantageoftheant

5、colonyalgorithm．Adynamicweightbasedonselectstrategyisproposedtoenhanceitsglobalsearchingability．Thesearchrangeisinitiallyenlargedbythepheromonediffusion．Aftercertainiterations，thesearchrangeismainlyenlargedbypathexpectation．Asaresult,theperformanceoftheantcol

6、onyalgorithmisimproved。ThenewalgorithmandtheclassicalantcolonyalgorithmareappliedtotheTSPproblem．Numericalresultsshowthatthenewalgorithmisfeasibleandthestagnationbehaviorisavoided．Secondly,inordertopreservethediversityofParetooptimalsolutionsinmulti—objective

7、optimizationproblems，Anewantcolonyalgorithmisproposed．Intheproposedalgorithm,theselectionstrategyismulti-pheromone—weighted,andpheromoneupdateusesthecombinationoftheMealandglobalpheromoneupdate．Especially,theglobalpheromoneupdateadoptsthebestsolutionandthesec

8、ond-bestsolution．Inaddition,anexternalsetissetupoutsidetostoretheParetosolution,andtheimprovedalgorithmisusedtosolvethebi-cdtefionTSEAfterthesimulationexperiment,itisshownthatthenewalgori