自适应蚁群算法及其应用

陕西理工学院毕业论文（设计）第1页共24页自适应蚁群算法及其应用作者：杜贵平（陕西理工学院计算机系计算机科学与应用专业丙班，陕西汉中723000）指导教师：周涛老师[摘要]本文对标准蚁群算法、MMAS蚁群算法、自适应蚁群算法做了较详细系统的总结，其中主要讨论了自适应蚁群算法在DNA序列比对中的应用，主要的过程是：首先，我们设一个计分函数和一个得分策略，在任意给出一对DNA序列，建立一个序列比对矩阵。现由4只蚂蚁从左上角向右下角移动，并且最终到达右下角，那么这4只蚂蚁随意走出4条路径，根据4条路径得出4对等长的比对，再依照计分函数分别计算出4条路径的比对得分，再由5.3式进一步验证4条路径的平均得分值，取其中得分最高（即最优路径）路径；进行第二次信息素增量的调整，方法是根据蚂蚁所走过的方向和该方向上得分比例计算出来的，信息素的变化量利用矩阵来存储，那么下一次蚂蚁所选的路径就要根据以前在各条路径上的信息素浓度总和的大小选择移动方向，最终经过有限次迭代，蚂蚁就会找到一条最优路径，也就是一条与原来DNA最相似的DNA链。[关键词]标准蚁群算法，MMAS算法，自适应蚁群算法，DNA序列比对陕西理工学院毕业论文（设计）第2页共24页AdaptiveAnt-colonyAlgorithmandItsApplicationWriter:Gui-pingDu(Grade02,Class3,MajorComputerScienceandTechnology,DeptofComputerScienceandTechnology,ShaanxiUniversityOfTechnologyHanzhong,Shaanxi723000)Tutor:TaoZhouAbstract：Ant-colonyalgorithm,MMAS(Max-MinAnt-colonyAlgorithm)andadaptiveant-colonyalgorithmarediscussedinthispaper.DNAsequencealignmentisoneofimportanttoolsinbioinformaticsresearch.Wediscusstheprocessthatadaptiveant-colonyalgorithmisappliedinsequencealignmentmainly.First,wegiveascoringfunctionandscorepointsthestrategy,apairofDNAsequenceisgeneratedrandomlyandcreatesequencealignmentmatrix.4antsmovefromonleftangularorientationtorightunderangleandfinallyarrivestherightunderangle,Hence4-waysareobtainedand4sequencealignmentofsamelengthisobtainedtoo.Accordingtoscoringfunction,wecalculatethesescoringandmax-valueofthesesequencealignmentisthebestroute.;Second,informationelementareadjustedbyitsincreaseandarestoredininformationelementmatrix.Finally,Theroutethatantselectisaccordingwithinformationadjustment.Throughlimitingiterativetimes,AbestrouteisselectedandgettheresultthatthesetwoDNAchainsaresame.Keywords：StandardAnt-colonyalgorithm,(MMAS)Max-MinAnt-colonyAlgorithm,adaptiveant-colonyalgorithm,DNAsequencealignment陕西理工学院毕业论文（设计）第3页共24页目录1.引言……………………………………………………...……………………………………………..32标准蚁群算法…………………………………………………………………………...…….32.1标准蚁群算法的原理……………………………………………….………...32.2标准蚁群算法的实现………………………………………….…………...…52.3标准蚁群系统的优缺点………………………….………….........…......….72.3.1基本蚁群算法的优点............................................................82.3.2基本蚁群算法的缺点…........................................................93.标准蚁群算法和MMAS(max-minantsystem)蚁群算法….....83.1MMAS的概念…………………………………………………………...…………..…83.2AS与MMAS的对比………………………………………………………………..83.3MMAS和AS的区别………………………………………………………….….…83.4最好、最坏路径信息素全局更新策略…………………...………...133.5MMAS蚁群算法的特点…………………………………………………….…...104.自适应蚁群算法……………...……………………………………………………….….….104.1.自适应蚁群算法的概述………………………………………...…….….…114.2.自适应的信息更新策略………………………………………........………..114.2.1引题…………………………………………………………….…....….124.2.2改进的蚁群算法实现过程……………………….……….124.2.3自适应蚁群算法的稳定性和收敛性………….........135.自适应蚁群算法在DNA中的应用...........................................................................145.1序列比对…………………………………………..……………………..…….….…..14.5.2自适应蚁群算法和DNA的联系…………….……..……………….........156.结束语………………………………………………………………………..………………...….....22致谢………………………………………………………………………………………………………...23参考文献…………………………………………………………………………………..….……...…24陕西理工学院毕业论文（设计）第4页共24页一．引言在二十世纪九十年代初期，意大利M.Dorigo,V.Maniezzo,A.Colorni等人从蚂蚁觅食的自然现象中受到启发，经过大量的观察和实验发现,蚂蚁在觅食过程中留下了一种外激素，又叫信息激素，它是蚂蚁分泌的一种化学物质，蚂蚁在寻找食物的时候会在经过的路上留下这种物质,以便在回巢时不至于迷路,而且方便找到回巢的最好路径。由此，M.Dorigo等人首先提出了一种新的启发式优化算法，又叫蚁群系统(AntColonySystem)，这种算法是目前国内外启发式算法中的研究热点和前沿课题，被成功地运用于旅行商问题的求解，蚁群算法在求解复杂优化问题方面具有很大的优越性和广阔的前景。但是,根据观察实验发现，蚁群中的多个蚂蚁的运动是随机的，在扩散范围较大时，在较短时间内很难找出一条较好的路径，在算法实现的过程中容易出现停滞现象和收敛速度慢现象。在这种弊端的情况下，学者们提出了一种自适应蚁群算法，通过自适应地调整运行过程中的挥发因子来改变路径中信息素浓度,从而有效地克服传统蚁群算法中容易陷入局部最优解和收敛速度慢的现象。蚁群算法的主要特点是：正反馈、分布式计算，与某种启发式算法相结合，正反馈过程使得该方法能很快发现较好解；分布式易于并行实现，与启发式算法相结合，使得该方法易于发现较好解。初步的研究表明，蚁群算法是一种基于种群的鲁棒性较强的算法，具有许多优良的性质，为求解复杂的组合优化问题提供了一种新思路。二．标准蚁群算法2.1蚁群算法原理蚂蚁在外出觅食的过程中,不断地在经过的路径上释放信息激素以便和其他的蚂蚁进行联系，这种信息激素的浓度随着经过该路径的蚂蚁数量而增大，而蚂蚁在回巢或觅食时也会选择信息激素浓度较大的路径，这就会有更多的蚂蚁选择此路径，这就是一种正反馈现象。也就是说某一路径上经过的蚂蚁越多，则后来者选择该路径的概率就越大。人工蚁群算法是受到人们对自然界中真实的蚁群集体行为的研究成果的启发而提的，是一种基于种群的模拟进化算法，属于随机搜索算法。由意大利学者M.Dorigo等人首先提出M.Dorigo等人首次提出该方法时，充分利用了蚁群搜索食物的过程与著名的旅行商问题(TSP)之间的相似性，通过人工模拟蚂蚁搜索食物的过程(通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径)来求解TSP。为了区别于真实蚂蚁群体系统，称这种算法为“人工蚁群算法”，蚂蚁这类群居昆虫，虽然单个蚂蚁的行为极简单。但由这样的单个简单的个体所组成的蚁群群体却表现出极其复杂的行为，能够完成复杂的任务，而且，蚂蚁还能够适应环境的变化，如：在蚁群运动路线上突然出现障碍物时，蚂蚁能够很快地重新找到最优路径。蚁群是如何完成这些复杂的任务的呢?经过人们大量研究发现，蚂蚁个体之间是通过一种称之为外激素(pheromone)的物质进行信息传递从而能相互协作，完成复杂的任务。蚁群之所以表现出复杂有秩序的行为，个体之间的信息交流与相互协作起着重要的作用蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质。而且蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着该物质强度高的方向移动．蚁群算法往往在初期信息素匮乏，求解速度慢；而遗传算法具有快速随机的全局搜索能力，但对于系统中反馈信息的利用却无能为力。因此，人们尝试将蚁群算法与遗传算法融合，采用遗传生成信息素分布，利用蚁群算法求精确解，从而实现优势互补。在蚁群算法中采用逆转变异，能有效克服基本蚁群算法中计算时间较长的缺陷，在一定程度上提高算法的收敛速度。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。2．2蚁群算法的实现陕西理工学院毕业论文（设计）第5页共24页大家都知道，蚁群算法最成功的就是运用在TSP问题上，现在就对该问题简单的介绍一下，如何实现标准蚁群算法：设将M只蚂蚁放入到N个随机选择的城市，每只蚂蚁每一步的行动是根据一定的依据选择下一个它还没有访问的城市或者一个循环，蚂蚁选择下一个城市的主要依据是：()ijt----t时刻连接城市i和j的路径上残留信息的浓度，由算法本身提供的信息,---由城市i转移到城市j的起始信息，该起始信息是由要解决的问题给出的.为城市i到城市j的先验值，于是，t时刻位于城市i的蚂蚁k选择城市j为目标城市的概率是：()(),()()0ijijkininnkttjttallowedallowedkij否则P式2.1假如kijN其中-----残留信息的相对重要程度。-----期望值的相对重要程度。kiN所有可能的目标城市，即还没有访问的城市，为了避免对同一城市的多次访问，每制蚂蚁都保存一个列表tabu(k),用于记录到目前为止已经访问的城市。()kijtP-----