蚁群算法及其应用研究

1、蚁群算法及其应用研究赵天男,王晓红(渤海大学信息科学工程学院,辽宁锦州121000摘要:蚁群算法是一种新型的模拟进化算法,是受到真实蚁群的觅食机制的启发而提出的。介绍了蚁群算法的基本原理和工作机制,并分别就蚁群算法的理论和应用进行了阐述,包括蚁群算法改进的不同算法以及蚁群算法在各个领域中的应用,并进一步给出了研究重点和发展方向。关键词:蚁群算法;优化问题;应用研究中图分类号:TP312文献标识码:A文章编号:1672-7800(201006-0034-021蚁群算法的基本原理真实的蚂蚁有能力在没有任何可见提示下找出从蚁穴到食物源的最短路径,并能随环境的变化而变化搜索出新的路径,产生新的选择,蚁

2、群算法也是通过模拟真实蚁群的这一特征进行工作的。1.1蚂蚁的觅食行为像蚂蚁这类群居昆虫,虽然没有视觉,却能找到从蚁穴到食物源的最短路径。单只蚂蚁的行为及其简单,在蚁群觅食的过程中释放信息素,通过对路径上信息素强度的感知来选择所要行进的方向,并传递信息。当遇到新的障碍物时,信息素轨迹会被障碍物暂时性阻断,蚂蚁会随机地选择下一步的方向,重新构建起新的连续的信息素路径。随着时间的推移,选择短路径的蚂蚁越来越多,留下的信息素浓度也会加强,从而使后继的蚂蚁以较大的概率选择短路径。他们这种自催化过程形成的信息正反馈机制使得他们可以找到新的最短路径。1.2蚁群算法的基本原理蚁群算法是受到真实蚁群集体行为的启

3、发而得到的新型优化算法,人工蚂蚁和真实蚂蚁存在异同。人工蚂蚁和真蚂蚁的蚂蚁一样,是一群相互合作的个体并且他们有着共同的任务,他们都是通过使用信息素进行间接通讯,而且人工蚂蚁利用了真实蚂蚁觅食行为中的自催化机制。但人工蚁群也存在真蚂蚁所不具有的一些特性,蚁群这种记忆并非存储于蚂蚁个体,而是分布在路径上。人工蚂蚁实质上是由一个离散状态到另一个离散状态的跃迁。信息素的释放时间是根据不同情况而改变的。为了提高系统总体上的性能,蚁群被赋予了其他的功能,如局部优化、原路返回等。蚁群算法最初是应用在对称的旅行商问题,下面对求解旅行商问题进行简单的说明。旅行商问题就是指给定n 个城市,并给出两两城市间的距离,

4、要求确定一条经过各城市最短的路径。蚂蚁根据城市的距离和连接边上信息素浓度为变量的概率函数选择下一城市。为了满足问题的约束条件,在完成一次循环前,不允许蚂蚁选择已经访问过的城市,需要由禁忌表控制。完成循环后,路径上都会留下浓度不同的信息素,我们可以通过对信息素浓度的强度,选择出最短路径。算法的基本流程图如图1所示 。图1基本流程图初始时刻,各条路径上的信息素量相等,设ij (0=C (C 为常数。蚂蚁k (1,2,m 在运动过程中根据各条路径上的信息素决定转移方向。蚂蚁系统所使用的状态转移规则被称为随机比例规则,它给出了位于城市i 的蚂蚁k 选择移动到城市j 的概率。在t 时刻,蚂蚁k 在城市i

5、 选择城市j 的转移概率P ij k (t 为:软件导刊Software Guide第9卷%第6期作者简介:赵天男(1985-,女,辽宁本溪人,渤海大学信息科学工程学院硕士研究生,研究方向为计算机网络;王晓红(1983-,男,山西吕梁人,渤海大学信息科学工程学院硕士研究生,研究方向为虚拟现实。第6期P ij k(t=ij(tij(tSallowed kis(tis(t,jallowed k0otherwise(1其中ij表示为边(i,j上的信息素轨迹强度;ij表示为边(i,j的能见度,反映由城市i转移到城市j的启发程度,这个量在蚂蚁系统的运行过程中不改变。蚁群算法中只有那些属于最短路径上的边的

6、信息素才被得到增强。这种规则和伪随机比例规则的使用都是为了让算法的寻优过程更具有指导性,最短路径的寻找始终是在当前找到的最短路径的附近进行。在所有的蚂蚁遍历完n个城市之后,各路径上信息素量根据式(2进行更新。ij(t+1=·ij(t+ij(t,t+1ij(t,t+1=mk=1ij k(t,t+1(2ij(t,t+1表示第k只蚂蚁在时刻(t,t+1留在(i,j上的信息素的量,它的值根据蚂蚁表现的优劣程度而定。路径越短,信息素释放的就越多。根据具体算法的不同,表达式也可以不同,要根据具体问题选择不同的表达形式。蚁密和蚁量系统模型仅在于的不同。在蚁密系统模型中,一只蚂蚁在经过路径(i, j

7、上释放的信息素量为每单位长度Q,在蚁量模型中,蚂蚁在经过路径上释放的信息素量为每单位长度Q/dij。而在蚁周模型中,与上述两种模型的ij k表达式不同,ij k(t,t+n表示更新蚂蚁k所走的路径,(t,t+n表示蚂蚁经过n步完成一次循环,具体的更新值由式(3所示:ij k(t,t+n=Q/L k(3蚂蚁k在本次循环中经过路径(i,j否则在蚁密和蚁量系统中,蚂蚁建立方案的同时释放信息素,是局部的更新。而在蚁周系统中,是在蚂蚁已经完全建立了轨迹后再释放信息素,是利用了整体的信息。根据一系列标准测试问题上运行的实验表明,蚁周算法的性能优于其他两种算法。因此,蚁周算法模型往往被称为蚂蚁系统,另外两种

8、模型不被使用。2改进的蚁群优化算法近年来,蚁群优化算法研究主要集中在改善蚁群算法的性能方面。改进的方法主要是在搜索控制的具体方面不同,但这些算法都是基于蚂蚁找出最优解来指导蚂蚁搜索的过程。(1带精英策略的蚂蚁系统(Ant System with elitist strate-gy是最早的改进蚂蚁系统。在这个系统中,为了使到目前所找出的最优解在下一循环中对蚂蚁更有吸引力,在每次循环之后给予最优解以额外的信息素量,这样的解被称为全局最优解,找出这个解的蚂蚁被称为精英蚂蚁。但是该系统存在缺点,若在进化过程中,解的总质量提高了,解元素之间的差异减小了,将导致选择概率的差异也随之减小,使得搜索过程不会集

9、中到所找出的最优解附近,阻止了对更优解的进一步搜索。(2基于优化排序的蚂蚁系统(Rank-Based Bersion of Ant System:将遗传算法中排序的概念扩展应用到蚂蚁系统中,当每只蚂蚁都生成一条路径后,蚂蚁按路径长度排序,蚂蚁对激素轨迹量更新的贡献根据该蚂蚁的排名进行加权。只考虑w 只最好的蚂蚁,而且要以有效避免上述的某些局部极优路径被很多蚂蚁过分重视的情况发生。(3最大最小蚂蚁系统(Max-Min Ant System与蚁群系统相似,为了充分利用循环最优解和到目前为止找出的最优解,在每次循环之后,只有一只蚂蚁进行信息素更新。这只蚂蚁可能是找出当前循环中最优解的蚂蚁,也可能是找

10、出从实验开始以来最优解的蚂蚁。而在蚂蚁系统中,对所有蚂蚁走过的路径都进行信息素更新。为了避免搜索的停滞,把每个解的元素上的信息素轨迹量的值域范围限制在Min,Max区间内。在蚂蚁系统中的信息素轨迹量不被限制,使得一些路径上的轨迹量远高于其他边,蚂蚁都沿着同条路径移动,组织了进一步搜索更优解的行为。(4最优-最差蚂蚁系统(Best-Worst Ant System。该算法在蚁群算法的基础上进一步增强了搜索过程的指导性,使得蚂蚁的搜索更集中于当前所找出的最好路径的领域内。蚁群算法的任务就是引导问题的解向着全局最优的方向不断进化。该算法的思想就是对最优解进行更大限度的增强,而对最差解进行削弱,使得属

11、于最优路径的边与属于最差路径的边之间的信息量差异进一步增大,从而使蚂蚁的搜索行为更集中于最优解的附近。蚁群算法还可以与其他智能优化算法相融合,取长补短,改进和完善算法的性能。目前蚁群算法可以与遗传算法、粒子群算法等进行融合,更有效的解决一些问题。3蚁群算法在优化问题中的应用蚁群算法最初被用经典的组合优化问题,随着研究的深入,应用范围不断扩大,现在应用到静态组合优化问题、动态组合优化问题、连续空间优化问题、以及其他领域。下面分别介绍了在不同领域中的应用:3.1在静态组合优化中的应用蚁群算法最先应用于旅行商问题(TSP问题,它是组合优化中研究最多的NP问题之一,该问题主要是在n个城市中,必须访问每

12、个城市且每个城市只能访问一次,最后回到起始城市,寻找最短路径。目前,求解TSP问题的方法有很多,穷举搜索法、最近邻算法、插入算法等,也有其他优化算法,例如:模拟退火算法、遗传算法、神经网络算法、禁忌算法等。许多研究表明,应用群算优化算法求解TSP问题要优于其他的方法。二次分配问题(QAP指的是分配n个设备给n个地点使得分配代价最小。事实上,QAP问题是一般化的TSP问题。车间任务调度问题(JSP指的是一组M台机器和一组T 个任务,任务有一组制定的将在这些机器上执行的操作序列组成。还有许多问题,像车辆路线问题(VRP、图着色问题(GCP、有序排列问题(SOP、最短的公共父序列问题(SCS等。赵天

13、男,王晓红:蚁群算法及其应用研究35··3.2在动态组合优化中的应用在动态组合优化问题中,问题的解是随时间而变化的。蚁群算法在解决动态组合优化问题中主要是通信网络。在国际上Schoonderwerd 等人首先将蚁群算法应用于路由问题,White 等人将蚁群算法运用在单对单点和单对多点的有向连接的网络路由中,而Dicarogy 等人基于蚁群算法设计了自适应的路由算法。在国内,开展了基于蚁群算法的QoS 路由调度方法的研究。4结束语蚁群算法问世至今已有十多年的时间,其理论和应用都有了很大的进步,蚁群算法从最初求解旅行商问题开始,已经逐步发展为一个优化工具,并且较为成功地应用到科

14、学和工程中的多个领域。众多研究已经证明,蚁群算法具有很强的发现较好解的能力,因为该算法不仅利用了正反馈原理,而且是一种本质并行的算法,不同个体之间不断进行信息交流和传递,从而能够相互协作。蚁群算法相对于各种比较成熟的计算智能方法来说,它的数学离了基础相对薄弱,缺乏具备普遍意义的理论性分析。算法中涉及的各种参数设置也没有确切的理论依据,通常都是通过经验来确定。因此,蚁群算法还有许多问题需要解决,它的应用也有待进一步的发掘。蚁群算法还有许多要研究的地方,主要是:进一步的研究算法收敛性的分析,得出更强的收敛性证明并得出收敛速度将会加速算法的发展;蚁群算法的理论性分析和参数的设置;蚁群算法的应用领域的

15、扩展,应用较多的是静态组合优化问题,改进并将其应用于动态组合优化问题和连续优化问题是值得探索的。参考文献:1DORIGO M ,GAMBARDELLA L M.Ant colony system :a coopera -tive learning approach to the traveling salesman problem J .IEEE Transactions on Evolutionary Computation ,1997(1.2DORIGO M ,MANIEZZO V ,COLORNI A.Ant system :optimization by a colon of coop

16、erating agents.IEEE Transactions on Systems ,Man and Cybernetics ,PartB ,1996(1.3COLORM A ,DORIGO M ,MANIEZZO V.Distributed optimization by ant colonies C .Proc of the First European conf.On Artificial Life ,Paris ,France Elsevier Publishing ,1991.4李士勇.蚁群优化算法及其应用研究进展J .计算机测量与控制,2003(12.5温文波,杜维.蚁群算法综

17、述J .石油化工自动化,2002(1.6姜长园.蚁群算法的理论及应用J .计算机时代,2004(6.7倪庆剑,邢汉承.蚁群算法及其应用研究进展J .计算机应用与软件,2008(8.(责任编辑:周晓辉C 语言中浮点数存储异常的研究与实践田耕,成平广(重庆教育学院计算机科学系,重庆400067摘要:通过对浮点数存储方式的分析,指出了浮点数在C 语言编程过程中出现的不足,并采用3种方法巧妙地进行弥补和解决,对C 语言学习者有一定的指导作用和参考意义。关键词:C 语言;浮点数;存储格式;改进中图分类号:TP312文献标识码:A文章编号:1672-7800(201006-0036-031问题的提出在科学计算中,时常会出现实数的运算,而实数在计算机中以浮