蚁群算法优化策略综述
蚁群算法源于1992年一篇博士论文提出的模拟蚂蚁寻找食物所选路径的概率型找寻最优解的方案，这种算法本质是基于一定规则的随机运行来寻找最优方案，模仿蚂蚁寻找和搬运食物时释放信息素的机理，不断优化行走路线，在算法实现中执行时间越长，所获得的路径就越可能接近最优路径。
【摘要】对于求解TSP问题，新型的启发式算法——蚁群算法，是成功解决此类问题核心的算法之一。本文简要介绍了几种启发式算法并引出蚁群算法，并对蚁群算法基本原理、常用算法进行了深入的研究，并介绍了一种新的优化策略。
【关键词】TSP问题,蚁群算法,优化策略
1引言
蚁群优化算法已应用于许多组合优化问题，例如二次分配问题，还有很多实变量动力学问题、随机问题、多目标并行的实现等方面，但在实际算法中需要避免的一个问题是过早收敛的问题，算法在执行中很快陷入到了局部最优解的搜索，难以实现广度搜索。因此，在标准算法基础上出现了优化算法，这些优化算法主体通过对于信息素的调节，防止过早收敛问题。在优化算法中核心在于平衡广度搜索与深度搜索，保证算法的执行效率、有效性。本文通过对目前常见的蚁群优化算法进行综合分析与比较，较为清晰的梳理出常见优化算法的特点，有助于在解决实际问题中选择合适方法以及算法优化。
2常见蚁群算法的优化算法
标准蚁群算法存在收敛慢、易停滞、运算时间长等缺陷，后续对其做了一系列的改进，以解决该算法存在的问题，产生了许多改进型算法。下面将介绍三种最典型的改进算法：蚁群系统算法（ACS）、最大最小蚁群系统算法（MMAS）、具有变异特征的蚁群算法。
2.1蚁群系统算法
蚁群系统算法（ACS）是对蚁群算法（AC）的改进，这些改进包括：蚂蚁选择的状态转移规则；全局最优更新规则仅运用于属于最优解路径上的信息素；对所有的路径的信息量进行局部更新规则（LocalUpdatingRule）。在ACS中，全局更新只是运用在每一次循环中走最优解路径的蚂蚁，而不再运用与所有的蚂蚁。在所有的蚂蚁搜完成了一次循环后，全局更新才会执行。
2.2最大最小蚁群系统算法
最大最小蚁群系统算法（Max-MinAntSystem，MMAS）是解决TSP、QAP等问题的经典蚁群优化算法之一，其结果要优于一般的蚁群算法。MMAS与ACS一样都只允许在每次迭代中表现最好的蚂蚁更新其路径上的信息素，这样做可以防止算法过早的出现停滞现象。而MMAS与ACS相比不同的地方在于防止这种停滞现象的方法。MMAS的做法为：限定信息素浓度允许值的上下限，并且采用平滑机制。在算法启动时，MMAS将所有路径上的信息素浓度初始化为最大值。在每次循环之后，只有在最佳路线上的蚂蚁进行信息素的更新，并将其保持在一个高的水平上，其他之路上的信息素将会按照信息素残留度降低浓度。
2.3与变异结合的蚁群算法
吴庆洪等人提出了一种优化蚁群算法——具有变异特征的蚁群算法。其核心思想为采用逆转变异方式，随机地进行变异，以增大进化时所需的信息量，从而克服传统蚁群算法收敛较慢的问题。这种变异机制之所以会具有较快的收敛速度，是因为它充分利用了2-OPT交换法简洁高效的特点。
3蚁群算法优化的新策略
对蚁群算法所作的优化是在已有的改进型算法——ACS算法的基础上进行的，下文即将描述的优化途径也都是在前人所做改良（即ACS已有的改良途径）的基础上作的更进一步的改进。
3.1路径选择机制的改良
在ACS的路径选择策略中，我们需要对ij边上已有的信息进行有效的利用，而对于变量q的设定，存在着很大的偶然性使得我们不能很有效地利用已有信息。对此，为了进一步对已有知识加以充分利用，新变量（∑ijk）/m被引入用以替代变量q，其中∑ijk表示上一次循环中选择路径ij的蚂蚁个体的总数。在q0确定的情况下，∑ijk将伴随着算法的运行而随之增大，从而使蚂蚁个体能在下一次路径选择中优先利用已有的信息来选择将要前往的城市，进一步地提高了算法的搜索性能。
3.2全局信息素更新机制的改进
对于信息素的全局更新，我们不仅仅要运用在每一次循环中走最优解路径的蚂蚁，还要运用与每一次循环中最差的蚂蚁使用。但是对于最差蚂蚁的全局更新规则与走最优解路径蚂蚁的规则不同，其更新规则采用如下的公式：？子ij（t）←（1-？着）×？子ij（t）+？着×△？子ij（t）；
其中，？着为区间（0，1）上的参数；而△？子ij（t）则用如下的公式计算：
△？子ij（t）=Q/L-Q/L’若ij路径是算法已求出的最差路径的一部分
或=0若ij路径不是已求出的最差路径的一部分；
在ACS算法的基础上，增加对最差的蚂蚁采用以上的更新机制，能更有效地模拟蚂蚁在自然界的觅食过程中分泌的信息素，能准确得出路径长度与时间之间的关系，可使得更多的已有知识被利用，同时在后续的循环中能够增加好的路径被选择的概率并减少差的路径被选择的概率，这样算法的性能可以大大提高。
3.3增加最小信息素浓度设置
MMAS给每一条支路都设置了一个最小信息素浓度，在算法运行过程中，各个支路的信息素浓度不会降到？子min以下。这样保证了即使没有任何一只蚂蚁选择走某条路径，在再一次的循环中这条路径依然有一定的概率被选中，从而避免了一些可能存在的好的路径被过载地抛弃，同时也避免了算法过早地收敛。设置了一个最小信息素浓度？子min，它的计算公式为：
？子min=1/[2n？（1-？籽）？L]；
n表示当前问题的城市节点数，？籽为信息素残留度，L为算法运算到当前为止，已求出的最优路径的长度；为了保证所有路径上的信息素浓度不低于？子min，每当一次循环中的信息素局部及全局更新完成后，就需要比较？子ij和？子min，如果？子ij<？子min，则将？子ij强行设置为？子min。
3.4杂交算子的引入
遗传算法具有良好的搜索能力，引入了杂交算子来对现有的所有解进行重组，这样可以发现潜在的更好的解。我们现在尝试一种新的增强解的方法：杂交算子被引入到ACS算法中，以对在算法运行过程中产生的新的解进行杂交，并充分利用当前所知的所有路径信息，两者结合可以发现更好的解，从而对最终我们希望得到的结起了增强作用。
4结束语
蚁群算法作为组合优化的经典算法，在实际问题的应用中仍然存在一些问题，这些问题需要进一步研究。
（1）正反馈机制的建立，启发函数的定义，求解问题递增式的进行，以及最优解与问题定义中的现实世界的情况相对应等问题需要考虑。
（2）在开始运行蚁群算法求解问题时，需要对大量的变量进行初始化，这些变量的初始值会对算法的性能产生较大的影响。然而这些变量初始值的选取方法和原则在目前还没有一个理论上的依据，只能在多次实验中积累经验从而选择比较好的值。因此在初始化变量的最佳值设置问题上还有待进一步的研究。
参考文献
[1]Dorigo，M.Optimization，LearningandNaturalAlgorithms.PhDthesis，DipartimentodiElettronica，PolitecnicodiMilano，page140，1992.
[2]Dorigo，M.，Maniezzo，V.，Colorni，A.TheAntSystem：optimizationbyacolonyofcoorperatingagents.IEEETransactionsonSMC，1996，26（1）：28～41.
[3]Stuetzle，T.，Hoos，H.TheMAX-MINAntSystemandLocalSearchfortheTravelingSalesmanProblem.ProceedingsofICE’97-1997IEEE4thInternationalConferenceonEvolutionaryComputation.IEEEPress，1997：308～313.
[4]吴庆洪，张纪会，徐心和.具有变异特征的蚁群算法.计算机研究与发展，1999，36（10）.
[5]詹士昌，徐婕，吴俊.蚁群算法中有关算法参数的最优选择[J].科技通报，2003，19（5）：381～386.
[6]Michalewicz，Z.GeneticAlgorithms+DataStructure=EvolutionPrograms.Berlin：Springer-Verlag，1996.
[7]elib.zib.de/pub/Packages/mp-testdata/tsp/tsplib/tsplib.html.
[8]Dorigo，M.，Gambardella，L.M.AntColoniesFortheTravelingSalesmanProblem.BioSystems（43）：73～81，1997.
相关期刊推荐：《微型机与应用》
《微型机与应用》是一本具有28年历史的计算机专业技术期刊，由华北计算机系统工程研究所（原信息产业部电子第六研究所）主办。该刊紧密结合我国计算机发展与应用的需要，及时报道国家相关的技术经济政策、国内外信息技术最新成果、在各行业及生活、娱乐中的应用技术。该刊尤以其技术性、实用性强而深受广大工程技术人员、科技工作者、大专院校师生、企事业管理人员以及电脑爱好者的欢迎。本刊曾用刊名：信息化纵横。
《微型机与应用》栏目设置
本刊主要栏目：综述与评论、软件天地、硬件纵横、网络与通信、应用奇葩、技术与方法、图形与图像。
《微型机与应用》期刊数据库收录情况/影响因子
《微型机与应用》为全国优秀科技期刊，被“万方数据—数字化期刊群”、“中国知网-中国期刊全文数据库”、“中国知网-中国科技期刊精品数据库”等重要数据库收录，并为《中国学术期刊综合评价数据库》来源期刊，历年被《中国无线电电子学文摘》、《中国电子科技文摘》等收录。
上一篇：网上银行密钥远程解锁方案研究
