蚁群算法优化策略综述

《蚁群算法优化策略综述》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、蚁群算法优化策略综述【摘要】对于求解TSP问题，新型的启发式算法一一蚁群算法,是成功解决此类问题核心的算法之一。本文简耍介绍了儿种启发式算法并引出蚁群算法，并对蚁群算法基本原理、常用算法进行了深入的研究，并介绍了一种新的优化策略。【关键词】TSP问题；蚁群算法；优化策略AntColonyAlgorithmOptimizationStrategyReviewSunQianZhangJinWangYu-xiang(ContemporaryEducationTechnologyCenterofNorthw

2、estUniversityShanxiXi?an710069)【Abstract】Asanewantcolonyalgorithmheuristicalgorithmhasbeensuccessful1yappliedtosolveTSPproblems.Thisarticlebrieflydescribesseveralheuristicalgorithmsandleadsantcolonyalgorithm,andthebasicprinciplesofantcolonyalgorithm,co

3、mmonlyusedalgorithmsin-depthstudy,andintroducesanewoptimizationstrategy.【Keywords】tspproblem；antcolonyalgorithm；optimizationstrategy1引言蚁群算法源于1992年一篇博士论文提出的模拟蚂蚁寻找食物所选路径的概率型找寻最优解的方案，这种算法本质是基于一定规则的随机运行来寻找最优方案，模仿蚂蚁寻找和搬运食物时释放信息素的机理，不断优化行走路线，在算法实现屮执行时间越长，所获得

4、的路径就越可能接近最优路径。蚁群优化算法己应用于许多组合优化问题，例如二次分配问题，还有很多实变量动力学问题、随机问题、多目标并行的实现等方面，但在实际算法中需要避免的一个问题是过早收敛的问题，算法在执行中很快陷入到了局部最优解的搜索，难以实现广度搜索。因此，在标准算法基础上出现了优化算法，这些优化算法主体通过对丁•信息素的调节，防止过早收敛问题。在优化算法中核心在于平衡广度搜索与深度搜索，保证算法的执行效率、有效性。本文通过对目前常见的蚁群优化算法进行综合分析与比较，较为清晰的梳理出常见优化算法的

5、特点，有助于在解决实际问题中选择合适方法以及算法优化。2常见蚁群算法的优化算法标准蚁群算法存在收敛慢、易停滞、运算时间长等缺陷，后续对其做了一系列的改进，以解决该算法存在的问题，产生了许多改进型算法。下面将介绍三种最典型的改进算法：蚁群系统算法（ACS）、最大最小蚁群系统算法（MMAS）、具冇变异特征的蚁群算法。2.1蚁群系统算法蚁群系统算法（ACS）是对蚁群算法（AC）的改进，这些改进包括：蚂蚁选择的状态转移规则；全局最优更新规则仅运用于属于最优解路径上的信息素；对所有的路径的信息量进行局部更新规

6、则（LocalUpdatingRule）。在ACS中，全局更新只是运用在每一次循环中走最优解路径的蚂蚁，而不再运用与所有的蚂蚁。在所有的蚂蚁搜完成了一次循环后，全局更新才会执行。2.2最大最小蚁群系统算法最大最小蚁群系统算法（Max-MinAntSystem,MMAS）是解决TSP>QAP等问题的经典蚁群优化算法之一，其结果要优于一般的蚁群算法。MMAS与ACS一样都只允许在每次迭代中表现最好的蚂蚁更新其路径上的信息素，这样做可以防止算法过早的出现停滞现象。而MMAS与ACS相比不同的地方在于防止这

7、种停滞现象的方法。MMAS的做法为：限定信息素浓度允许值的上下限，并且采用平滑机制。在算法启动时，MMAS将所有路径上的信息素浓度初始化为最大值。在每次循环之后，只有在最佳路线上的蚂蚁进行信息素的更新，并将其保持在一个高的水平上，其他之路上的信息素将会按照信息素残留度降低浓度。2.3与变异结合的蚁群算法吴庆洪等人提出了一种优化蚁群算法——具有变异特征的蚁群算法。其核心思想为采用逆转变异方式,随机地进行变异,以增大进化时所需的信息量，从而克服传统蚁群算法收敛较慢的问题。这种变异机制之所以会具有较快的收

8、敛速度，是因为它充分利用了2-0PT交换法简洁高效的特点。3蚁群算法优化的新策略对蚁群算法所作的优化是在已有的改进型算法——ACS算法的基础上进行的，下文即将描述的优化途径也都是在前人所做改良（即ACS已有的改良途径）的基础上作的更进一步的改进。3.1路径选择机制的改良在ACS的路径选择策略中，我们需要对ij边上已有的信息进行有效的利用，而对于变量q的设左，存在着很大的偶然性使得我们不能很有效地利用已有信息。对此，为了进一步对已有知识加以充分利用，新变量(刀ijk)/