蚁群算法的改进研究与应用

1、. . . . 中图分类号：O224 论文编号：学科分类号：110.7480 密级： 公 开 理工大学硕 士 学 位 论 文蚁群算法的改进研究与应用弓英瑛专业名称： 应 用 数 学 研究方向： 优化理论与应用 导师： 许 峰 教 授 导师单位：理工大学理学院答辩委员会主席：论文答辩日期： 年 月 日理工大学研究生处年 月 日31 / 45A Dissertation in Applied MathematicsResearch and Application of Improved Ant Colony AlgorithmCandidate:GongYingying Supervisor:Xu

2、 FengSchool of ScienceAnhui University of Science and TechnologyNo.168, Shungeng Road, Huainan, 232001, P.R.CHINA独 创 性 声 明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作与取得的研究成果。据我所知，除了文中特别加以标注和致的地方以外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 理工大学 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示意。学位论文作者签名：_ 日期： 年 月 日学位论

3、文使用授权书本学位论文作者完全了解 理工大学 有保留、使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属于 理工大学 。学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权理工大学可以将学位论文的全部或部分容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（的学位论文在解密后适用本授权书）学位论文作者签名： 签字日期： 年 月 日导师签名： 签字日期： 年 月 日摘要蚁群优化算法是一种群体智能算法，是自然界中蚂蚁群落在寻找食物过程的模拟，是一种新兴的智能进化算法，是专门解决离散的棘手的问题，在许多应用中，充分

4、展示了其优点，在算法的改进方面也取得了很好的成果。与积极的反馈、自组织、分布式、强健、易与其他算法相结合的优势，蚁群算法往往陷入局部最优解，收敛速度慢，对初始解的要求比较高。从理论上讲，适当转换后改进的蚁群算法可以使任何组合优化问题得到更快地解决。本文在蚁群算法和模拟退火算法的基础上对他们进行混合改进，并考虑目标函数梯度的因素，促使算法快速全局收敛；另外，在夹角优化方面也作了相关改进，考虑方向夹角对算法的影响程度，都得到了很好的结果。根据蚁群算法的特点，本文提出了基于目标函数梯度的模拟退火蚁群算法和夹角优化的蚁群算法。数值分析和实验表明：改进的新算法不仅具有原算法的优点，而且提高了算法的速度。

5、新算法应用于旅行商与路径规划问题，新算法的优越性得到了验证。本文所做工作如下：1. 简要介绍了蚁群算法的产生背景意义与研究现状，归纳论文所研究的容与意义。2. 简要介绍了蚁群算法的基本原理、算法步骤与流程，最后分析了算法的优缺点等。3. 首先简要介绍了模拟退火算法的基本原理和算法的过程，然后介绍了一种基于目标函数的梯度模拟退火蚁群算法的基本原理和算法流程，最后给出新算法对问题优化的实验结果。4. 首先简要介绍路径规划问题，然后介绍夹角优化的蚁群算法的基本原理和算法流程，最后给出新算法对路径规划问题优化的结果。图 13 表 1参 33关键词：蚁群算法；模拟退火算法；梯度；夹角优化分类号：O224

6、AbstractAnt colony algorithm is a kind of swarm intelligence optimization algorithm. It is a new intelligent evolutionary algorithm which is a similar to the process of ant communities in search of food in nature. And it is an ideal method for solving difficult discrete problems. It fully demonstrat

7、ed its advantages in many applications and obtained good results in terms of improved algorithms.Ant colony algorithm has the advantage of positive feedback, self-organization, distributed, robust, easy to combine with other algorithms. But often trapped in local optimal solution, convergence is slo

8、w, the initial solution is relatively high. Theoretically, It will more quickly resolve any combinatorial optimization problems, if the ant colony algorithm to make the appropriate changes. This article has been improved on hybrid ant colony algorithm and simulated annealing algorithm combines. It t

9、akes into account the objective function gradient of this factor so that global convergence to getting better. In addition, It also made related improvements in the angle optimization. For example, it takes into account the influence of the angle between the direction of the algorithm and the result

10、s have been very good.This paper put forward algorithm which is simulated annealing and ant colony hybrid algorithm based on the gradient of objective function and ant colony algorithm in the angle optimization.The numerical analysis and experiment show that the improved new algorithm not only posse

11、sses the advantages of the original algorithm, but also improve the running speed of the algorithm. Applied to the problem of TSP and path planning, The superiority of the new algorithm is verified.The paper contains following tasks:1. This paper briefly introduces the background and significance of

12、 research status of ant colony algorithm, and it also describes the content and significance of the study.2. Briefly introduces the basic principles of ant colony algorithm flow algorithm, it also introduces the advantages and disadvantages of the algorithm and so on.3. First introduces the basic pr

13、inciple and algorithm flow of simulated annealing algorithm, Then introduces the basic principles and the algorithm flow of simulated annealing and ant colony hybrid algorithm based on the gradient of objective function, Finally, we gave the experimental results on the new algorithm for solving prob

14、lems of the TSP .4. First, a brief introduction path planning problem, Then introduces the basic principles and the algorithm flow of ant colony algorithm in the angle optimization, Finally, we gave the experimental results on the new algorithm for solving problems of the path planning.Figure 13 tab

15、le 1 reference 33Keywords:ant colony algorithm, simulated annealing algorithm, gradient, angle optimizationChinese books catalog: O224目 录摘要IAbstractII插图或附表清单VIII引 言IX1绪 论11.1 蚁群算法生成背景和意义11.2蚁群算法的研究现状11.3 论文的研究意义和容21.3.1 论文的研究意义21.3.2 论文的主要容22 蚁群算法的原理与过程42.1 蚁群算法的基本原理42.2 蚁群算法的算法流程62.3蚁群算法的优缺点93基于目标函

16、数梯度的模拟退火蚁群算法113.1模拟退火算法的基本原理和算法流程113.2基于目标函数梯度的模拟退火蚁群算法123.2.1 混合算法的基本原理123.2.2 算法流程133.3实例与分析164夹角优化的蚁群算法与在路径规划中的应用184.1对路径规划问题的描述184.2夹角优化的蚁群算法184.2.1 方向夹角194.2.2 基本原理214.2.3 改进后的算法流程224.3实例与分析25总结27参考文献28致 30作者简介与读研期间主要科研成果31ContentsAbstractThe list of illustrations and scheduleIntroduction1 Exor

17、dium11.1 Background and significance of ant colony algorithm.11.2Research status of ant colony algorithm11.3 Research significance and main research contents21.3.1 Research significance21.3.2 Main research contents22 Structural principles and algorithms of ant colony algorithm42.1 The basic principl

18、es of ant colony algorithm.42.2 Algorithm flow of ant colony algorithm62.3Advantages and disadvantages of the ant colony algorithm93 Simulated annealing and ant colony hybrid algorithm based on the gradient of objective function113.1 The basic principles and algorithms of simulated annealing algorit

19、hm113.2 Simulated annealing and ant colony hybrid algorithm based on the gradient of objective function123.2.1 The basic principle of hybrid algorithm123.2.2 Algorithm flow133.3 Cases and Analysis164 Ant colony algorithm in the angle optimization and its application184.1 Path planning problem184.2 A

20、nt colony algorithm in the angle optimization184.2.1 Orientation angle194.2.2Fundamental principle214.2.3The improved algorithm flow224.3 Cases and Analysis25Summarization27References28Acknowledgements30Brief introduction of author31插图或附表清单相关图：图1：蚂蚁路径寻优过程图2：蚁群算法的流程图图3：模拟退火算法的流程图图4：基于目标函数梯度的模拟退火蚁群算法流

21、程图图5：改进算法的最优路径图6：改进算法的各代最短距离和平均距离图7：路径规划模型图8：方向夹角启发信息图9：夹角示意图图10：夹角优化蚁群算法流程图图11：常规蚁群算法和夹角优化蚁群算法所得最优路径图12：常规蚁群算法路程进化图图13：夹角优化蚁群算法路进化图相关表：表1：改进算法与常规算法优化结果对比引 言旅行商问题和路径规划问题属于完全问题，是世界七强之一的数学问题。蚁群算法是一种新兴的群智能概率型搜索算法，在解决这类问题中起到了重要作用，本文在常规的蚁群算法基础上对其做了两方面的改进。这种改进使我们更快速准确地找到最优解，实验证明这种改进算法具有有效性。常规的蚁群算法只根据信息素的强

22、度和道路的可见度进行信息素的更新，产生一定的概率，蚂蚁再按照这个概率来选择下一条较短路径，因此，最初路径的选择显得尤为重要，容易产生停滞现象，陷于局部最优。在此，我们让蚁群算法和模拟退火算法相结合，再加入目标函数梯度这个因素，弥补蚁群算法的缺陷和不足。在优化过程中，根据目标函数的梯度动态地控制信息素浓度和回火过程，并以旅行商问题为例，根据数值实验结果对新算法的全局收敛性和解的质量进行了评测。在路径规划问题中，各路径之间存在方向夹角，因而，解决此问题时充分考虑到方向夹角的大小，夹角越小的线段就越有可能是最优路线的一部分，在进行优化的过程中，通过计算方向夹角的余弦值确定其大小，将其加入信息素的更新

23、公式，以保证更好地找到最短路径。1绪 论1.1 蚁群算法生成背景和意义人工智能在1980年的20世纪，整整10年的繁荣经历1，因为该方法并没有脱离传统的计算障碍，所以再次迎接着新的挑战。人工智能的前景变得再次灰暗起来，同时，生命科学的迅速发展正以前所未有的速度发生着，人工智能的研究开始从经典逻辑计算的束缚走向新的非经典计算路径。这种情况下，研究者们对一些社会性动物2-5（蚂蚁、蜜蜂、鱼、鸟等）的自组织行为产生了兴趣，许多学者利用数学建模和计算机仿真技术，产生了“群智能”。个体行为的社会性昆虫虽然简单、随机，但它们完全可以互相团结一致地完成一些看似特别复杂的行为，比如筑巢、迁徙、觅食，鸟类在没有

24、管理和控制的情况下，可以齐心协力得飞行，并建立起温暖的窝，蚂蚁觅食的时候，无论有多少障碍，他们总可以找到从蚁巢到食物源的最短路径。如今，蚂蚁的这种寻找食物的行为最为引人注目。目前，蚁群算法是一种群体智能理论的重要算法6，是蚂蚁从居住地出发到寻找食物源的过程的一种模拟算法，并已成功地应用于许多离散的问题。来自公开文献的资料显示，在国际群体智能计算领域，蚁群算法已经成为一个热门的研究方向。1.2蚁群算法的研究现状遗传算法、进化规划、进化策略7等等，都是人们通过仿生学的研究得出解决复杂优化问题的新方法，仿生学的出现使得人们在生物进化研究方面有了新的方法和研究方向，由于生物特有的独特天性和特点，群落行

25、为的产生具有一定的规律，这为学者们研究生物学提供了可贵的材料，因此出现了基于群智能理论的蚁群算法，它最早由意大利学者提出，蚁群算法包括三种基本算法8-9：。与其他启发式算法相比，这三种算法仅仅容易解决小规模问题。因此，的重点研究工作之一是算法性能的改进，最早的改进方法是精英策略10，随后出现了多种其他常用的改进方法：改进信息素设定机制以与将与遗传算法、模拟退火算法相结合等。随着社会的进步，特别是智能理论和应用算法研究和发展，学者们已经取得了很大进展，试图将其应用于现实实践中，并取得了意想不到的成果。目前，蚁群算法的应用研究主要应用于网络规划、物流配送、生产调度11等。尽管蚁群算法理论的应用方法

26、研究还处于初级阶段，一些领域，一些课题还需要更深入的研究，需要人们更深入的探讨，但是，从未来发展趋势来看12，群智能的研究对人类社会的发展越来越重要了，是未来计算机研究和发展的一个重要方向。1.3 论文的研究意义和容1.3.1 论文的研究意义要解决一些实际优化问题，蚁群算法给出了很好的解决方案，但并不是那么完美，会因为初始启发信息不足而引起收敛速度慢的特点，易陷入停滞等不良后果，对与这些不足，本文对其算法进行了改进和实验，改进的目的在于提高解的质量和算法的各方面性能，主要包括以下几个方面：(1) 将蚁群算法和模拟退火算法相结合形成模拟退火蚁群算法，这种混合算法将大大提高解的质量；(2) 在混合

27、的基础上充分考虑目标函数的梯度这一因素，当目标函数梯度过小时，加强当前最优解对应的信息素，使算法快速收敛，当目标函数梯度过大时，引入回火策略以提高解的质量33，实验结果表明，这一改进后的混合算法的收敛速度和解有更大程度的改善；(3) 在路径规划问题中，各路径之间存在方向夹角，因而，解决此问题时充分考虑到方向夹角的大小，在小角度的路线上越有可能是最短路径的一部分，方向夹角越小，选择该路径的概率就越大。所以，进行计算时，通过计算方向夹角余弦值，从起始点开始寻找与其连接的线段形成较小夹角的那条路线，依次寻找，便可求出最短路径。如今，蚁群算法作为群智能算法的一种新型进化算法，已经在智能领域13表现出了

28、极为强大的生命力，对于解决各种复杂优化问题都显示了它的卓越之处，由于它本身也存在许多缺陷14，因此蚁群算法改进方面的研究对解决这些实际优化问题具有重要意义，并能更好地推动智能算法的不断发展和完善，本文对蚁群算法的改进方面进行了严格的理论分析和完整的数值实验，对整个群智能理论体系起到了巨大的推动作用，其本身也具有重要的理论研究价值和实践意义。1.3.2 论文的主要容本论文主要包含以下几方面：1. 首先简要介绍了蚁群算法的意义产生的背景和研究的现状的研究，总结了研究的意义和论文的主要容。2. 分析了蚁群算法的结构，包括蚁群算法的基本原理、参数设置和算法分析，算法的过程和优缺点等。3. 阐述了模拟退

29、火算法的基本原理和算法流程，然后介绍基于目标函数梯度的模拟退火蚁群混合算法的基本原理和算法流程，并给出新算法对TSP问题优化的实验结果。4. 概要介绍了路径规划问题，然后论述夹角优化的蚁群算法的基本原理和算法流程，最后给出改进后的算法对路径规划问题的优化结果。2 蚁群算法的原理与过程2.1 蚁群算法的基本原理蚁群算法中的虚拟蚂蚁吸收了大自然中真实蚂蚁的行为特征。众所周知，蚂蚁的个体行为显得简单而又无序，再加上蚂蚁的视觉发育不完整甚至有些蚂蚁没有视觉，然而集体组织活动时却能快速有效地找到食物源15，除此之外，当运动路径上突然出现障碍物时，蚂蚁还能绕过障碍并重新找到最短路径，这些复杂的行为充分体现

30、了其群体的高度智能性，这是为什么呢？这种现象引起了学者们的兴趣，生物学和仿生学早期关于蚂蚁行为的研究发现，蚂蚁在运动过程中会分泌一种叫做信息素的化学物质16，这时，其它蚂蚁会有所感知，它们的行为会受到影响，正是这种信息的传输来引导着蚂蚁前进的方向。蚂蚁在寻找食物的过程中，如果从巢到食物源的距离很短，那么蚂蚁从巢到食物源，然后再返回巢的时间就短，这表明，在同一时间，较短路径的蚂蚁会分泌和积累更多的信息素。愈多的蚂蚁，留下的信息素（随着时间的增长而减少）也是愈多，另外，随后的蚂蚁能够感知前面的蚂蚁信息素留下的多少来指导它的方向，所以某条路径上的信息素多了，蚂蚁选择这条路的可能性比较大。简单来说，蚁

31、群算法的基本原理在于以下三点：(1) 蚂蚁能连续不断地释放信息素；(2) 蚂蚁能感知小围区域状况；(3) 蚂蚁释放出的信息素随时间逐步减少。在此，我们可以使用图像来说明蚂蚁的搜索原则和机制：. 图1 蚂蚁路径寻优过程Fig1 The procedure of searching the shortest path如图1所示，表示蚁穴，表示事物，表示障碍物，蚂蚁从到有两条路径，分别是和，长度分别是和，并对蚂蚁可以走的距离做出规定，即单位时间蚂蚁走一个单位长度，刚开始所有道路上都没有信息素，所以蚂蚁最初选择路径的概率是一样的。当时，如图1(b) 所示，只蚂蚁从出发，以一样的概率选择和，因此，各方向

32、有只蚂蚁行走。当时，如图1(c) 所示，沿着的第一组蚂蚁到达并准备返回，而第二组在的中点处。当时，如图1(d) 所示，两组蚂蚁在点相遇，且和的信息素数量一样，此时，第一组返回的只蚂蚁到达点并以等概率分别走向、，第二组蚂蚁依然走向。当时，如图1(e) 所示，沿着返回的只蚂蚁到达，另只在中点处，还有第二组中在中点和点处各只蚂蚁。当时，如图1(f) 所示，前只蚂蚁又回到点并再次面临向左还是向右的选择，此时，经过的蚂蚁数量为，而经过的蚂蚁数量为，明显的信息素多于，这条路线会出现更多的蚂蚁。按照这个过程不断循环下去，路径越短，信息素积累就越多，久而久之，它们信息素数量的差距将越来越明显，路径将会有更多的

33、蚂蚁出现，如果时间足够长，最终所有的蚂蚁都会毫无偏向地选择这条路线。2.2 蚁群算法的算法流程蚁群算法是一种广义型的随机优化方法17，像其他模型进化算法，是通过候选解组成的群体，以确定最优解的进化过程，选择一条搜索路径最初只是随机的概率，重复这个过程，成为一个有规律的搜索，并逐步接近“更好的”解决方案。最终达到全局最优。在整个算法过程，人工模拟蚂蚁不同于真实蚂蚁的是：蚂蚁具有记忆性，也就是说一只蚂蚁选择过的路径在下次搜索时就不会再被选择，为了方便计算，我们建立禁忌表来代表蚂蚁访问过的城市。旅行商问题的解决有效使用了蚁群算法，下面介绍其基本算法：已知有只蚂蚁,座城市,表示城市到之间的距离，表示到

34、的可见度，表示时刻在路上的信息素强度，也可以把理解为访问完城市之后立刻访问城市的期望程度，表示启发式信息可，也就是说，从路径直接走到的期望程度与两条路径之间的距离成反比。每只蚂蚁按照如下过程建构一条行走路线：(1) 根据某些规则，它们会依照概率选择一个城市作为起点，我们把蚂蚁放到该城市；(2) 蚂蚁利用启发式信息和信息素强度，以一定的概率选择下一个允许访问的城市（表示蚂蚁下一个要走的城市），这里用禁忌表来控制不允许访问的城市（设表示第只蚂蚁的禁忌表，表示中第个元素）；(3) 蚂蚁行走一周返回起始城市后，在每一条路径上会留下信息素。初始时刻，每条路径上的信息素相等可设为常数，即，蚂蚁在运动过程中

35、根据信息素数量的变化而移动，我们用表示在时刻蚂蚁由路径转移到的概率，则： (1)由于信息素随着时间发生改变，故蚂蚁完成一次循环后，各路上的信息素也将进行更新： (2) (3) (4)其中，和分别表示信息素和可见度的影响性，表示信息素的残留系数，表示第只蚂蚁在路径上的信息素，表示路径上的信息素增长量，表示第只蚂蚁走完一圈的路线长度，为常数。根据具体情况可以有不同的表达方式。曾给出了三种不同类型，分别为、，它们的区别在于不同的表达(4)，在模型中：(5)在模型14中：(6)我们通常把第一种模型看作基本的模型，因为它考虑的是整体信息，解决问题的性能相对好。经过以上的分析，蚁群算法的基本步骤总结如下：

36、(1) 初始化参数，将只蚂蚁放在个结点上；(2) 据式(1)计算每只蚂蚁移动到下一结点的概率，并根据其概率进行选择下一个结点；(3) 蚂蚁遍历一周后计算路径长度，按式(3)更新信息素增量；(4) 所有路径的信息素更新按式(2)进行；(5) 重复2至4步，直至满足迭代终止条件输出最好解。综上分析可知，蚁群算法的基本流程图如下：图2 蚁群算法流程图Fig2 The flowchart of ant colony algorithm2.3蚁群算法的优缺点蚁群算法是一种典型的概率算法18，随机性较强，况且各参数的设定通常由试验方法确定与人的经验密切相关，缺乏一定的精确性。目前来看，蚁群算法在许多领域都

37、有广泛的应用并取得了良好的成果，但是它自身也存在一些缺陷。下面对蚁群算法的优缺点进行简单地归纳总结。蚁群算法的优点：(1) 与其它启发式优化算法相比，蚁群算法具有较强的鲁棒性。(2) 具有本质并行性，易于并行实现。(3) 可以随意地与多种启发式算法自由组合，以提高解的性能。蚁群算法的缺点：(1) 如果不能恰当地设置参数，很容易导致慢收敛速度和质量较差的解。(2) 基本蚁群算法计算量大，需要很久才能求出解。(3) 初始信息素的缺乏，会导致收敛速度慢，并且易陷入局部最优。(4) 容易出现停滞，搜索到一定程度，所有个体的解决方案完全一样，没有进一步搜索解空间，不利于找到更好的解决方案。3基于目标函数

38、梯度的模拟退火蚁群算法3.1模拟退火算法的基本原理和算法流程模拟退火算法是基于迭代算法的一种启发式随机搜索算法19，最早的思想由等人于1953年提出20。它源于物理中对固体退火过程的模拟，分为升温、平衡、冷却三个阶段，先将固体加温至充分高，再让其渐渐冷却，升温时粒子变为无序状能增大，冷却时粒子变得有序，能逐渐减小。由此过程，可将模拟退火算法应用于求解组合优化问题，此时，将能模拟为目标函数，温度对应于控制参数，并用冷却控制表控制算法进程。该算法的基本思想是从一给定解开始的，从邻域中随机生成另一个解，接受准则允许的目标函数恶化在有效围，它由一控制参数决定，算法由初始解和控制参数初值开始反复进行“生

39、成新解计算目标函数值的差接受或拒绝”这一迭代过程，它对应着固体在某恒定高温下趋于热平衡的过程，减少了控制参数，系统越来越趋于平衡状态，最终的系统状态对应于优化问题的整体最优解，需要指出的是，由于固体退火缓慢冷却可以使固体在所有温度下达到热平衡，因此，控制参数必须缓缓衰减才能保证优化问题趋于整体最优解。在判断新解是否被接受，我们通常使用准则来判断是否为新解：若目标函数值的差，则接受作为当前解；否则，若，则接受作为新解，否则舍弃。模拟退火算法的基本流程如下：(1) 参数初始化。给定初始温度（足够大）和退火速度，初始解与目标函数；(2) 随机扰动产生新解，计算；(3) 若，作为当前解；否则，若，为新

40、解，否则舍弃，仍为当前解；(4) 对进行缓慢降温，重复步骤2至3，直至满足迭代条件。模拟退火算法的流程图如下：图3 模拟退火算法流程图Fig3 The flowchart of simulated annealing algorithm3.2基于目标函数梯度的模拟退火蚁群算法3.2.1混合算法的基本原理通过以上对蚁群算法和模拟退火算法基本原理的研究可知，蚁群算法的优点是正反馈、自组织、分布式，缺点是易限于局部最优解，收敛速度慢。模拟退火算法的优点是算法简单、鲁棒性强、具有全局搜索能力，特别适用于复杂的非线性问题，缺点是对初始解有很强的依赖性，当系统不使用反馈信息，在一定程度上的解是大量的冗余迭

41、代造成的，精确率低。因此根据各自的优缺点可以将两种智能优化算法根据某种法则相融合或在某种优化算法中引入其它优化思想，形成混合优化算法，可以充分发挥智能算法各自的优点，扬长避短，以便取得时间性能和优化性能的双赢，提高算法各方面的性能。模拟退火算法和蚁群算法混合的基本思路是：第一，利用模拟退火算法得到一些更好的解，在其路径上留下信息素，其它东西不变；第二，根据蚁群算法让蚂蚁进行一次周游；第三，采用模拟退火算法在邻域寻找另外一个解，找到的这个解有可能变坏，为了简化计算可限定一个目标函数变坏的围，若路径长度差，接受新解，否则舍弃。3.2.2 算法流程考虑到模拟退火算法和蚁群算法各自的特点，许多学者先后

42、提出了基于模拟退火算法和蚁群算法的混合智能优化算法16。许智宏提出一种模拟退火蚁群并行算法17。波提出了一种基于模拟退火机制的蚁群算法，该算法在高温阶段以高概率加入更新集，在低温阶段采用回火策略18。常规的模拟退火蚁群算法不考虑目标函数的变化率，只是采用固定的更新信息素的方法和降温的方法，这就有可能产生冗余迭代，并且在一定程度上影响了解的质量。本文提出了一种基于目标函数梯度的模拟退火蚁群混合算法，在优化过程中，根据目标函数的梯度动态地控制信息素浓度和回火过程，并根据数值实验结果对新算法的全局收敛性和解的质量进行了评测。该混合算法充分考虑了目标函数的梯度，当目标函数的梯度较小时，加强当前最优解对

43、应的信息素，这相当于在“平坦”之处加快搜索速度，使算法加快收敛；当目标函数的梯度过大时，引入回火策略19，即在“陡峭”之处放缓搜索速度，以提高解的质量。并用改进的算法求解旅行商问题，结果表明，与常规的模拟退火蚁群算法相比，新算法的收敛速度和解的质量均得到很大的改善。在本文中，设退火函数为（），在完成一轮搜索与信息素更新后，进行退火即降温，降温过程中，当系统温度较高时，较差的解将以较高的概率进入更新集，导致路径上的信息素分布更加广泛，避免出现早熟；随着的降低，接受较差解的概率将逐渐减小，导致路径上的信息素分布集中，算法将快速收敛，我们鼓励过早收敛，采用较小的，这样可以缩短找到更好解的时间以提高效

44、率，但是，这样会增大落入局部极值点的风险。因此，为了解决这个问题，我们在算法中引入回火机制，回火是指将温度略微升高后再降温的策略。回火的温度围设为，若，将温度升高至，重新进行算法迭代，当再次时，这一过程称为回火过程，重复此过程，可以根据设定进行多次回火，回火次数设为，最大回火次数。考虑目标函数梯度的具体方法是：定义 (7)其中 (8) (9)表示向量的第个分量。对于离散优化问题，不存在梯度，则 (10) (11) (12)其中，分别表示父代和子代个体。当小于设定的阈值(通常取为)时，根据(2)式加强信息素；当大于设定的阈值(通常取为)时，采用回火策略。基于目标函数梯度的模拟退火蚁群混合算法的流

45、程如下：步骤1 初始化参数：；步骤2 利用模拟退火算法计算出一个较优解，在这个路径上留下信息素；步骤3 按上述方式，根据目标函数梯度加强信息素，并采用回火策略；步骤4 将只蚂蚁放在个结点处，并对每只蚂蚁按式(1)的概率选择下一个结点，完成一次循环；步骤5 在邻域找另外一个解，若，接受新解，否则舍弃；步骤6依据模拟退火原理，采用回火策略，直至，输出最优解，若，转步骤2；下图4是改进算法的框架示意图：图4 改进算法流程图Fig4 The flowchart of improved algorithm3.3实例与分析模拟退火蚁群混合算法已被应用于TSP、车间调度问题和机器人路径规划问题等18-21。

46、下面将本文提出的算法应用于我国31个省会、直辖市和自治区首府间的TSP，以测试算法的性能。初始化参数为：最大迭代次数200，。最新研究成果表明，上述TSP问题的理论最优解为15377km，常规模拟退火蚁群混合算法的最优解为15601。本文算法的最优解平均为15438，某次优化的最优路径与各代平均距离、最短距离见图5和图6。图5改进算法的最优路径Fig5 the optimal path of improved algorithm图6改进算法的各代最短距离和平均距离Fig6 the shortest distance and the average distance each generatio

47、n表1中给出了本文的改进算法与常规模拟退火蚁群算法20优化的对比结果，当算法优化结果与其最优解的误差小于15%时视为收敛。表1 改进算法与常规算法优化结果对比Table 1 Improved algorithm results were compared with the conventional algorithm optimization平均迭代次数收敛次数最优解平均解标准差常规算法16412155421560187.4改进算法12218154201543836.2从表中的对比结果可以看出，考虑目标函数梯度的模拟退火蚁群混合算法不仅显著加快了收敛速度，还在一定程度上提高了解的质量。4夹角优

48、化的蚁群算法与在路径规划中的应用4.1对路径规划问题的描述根据规划的目的是不同的，路径规划可分为多车辆路径规划和单个车辆路径规划21-24，前者主要用于车队调度和交通管制，后者多用于各种导航系统，主要研究的问题是在给定的城市道路网中如何寻找从起始点到目标点的一段最佳行驶路线，即最短路线。它实现了智能车辆的导航功能，是任务规划中最为基础也是最为重要的部分，本章的核心任务是对单车辆路径规划问题进行研究（后面提到的路径规划问题均为单车辆路径规划问题）。我们给定一个带权的有向图，其中是包含个节点的节点集，是包含条边的集合，是中从节点到的边，是边的非负权值。假设、分别作为中的出发点和目标点，则所谓的路径

49、规划问题就是指在带权有向图中，寻找从指定的出发点到目标点的一条具有最小权值总和的路径。在如何解决路径规划问题这方面，近年来国外学者已经做了大量的研究26，这其中包括蚁群算法、人工势场法、启发式搜索算法、神经网络算法、模糊算法、遗传算法27等等。这些算法都取得了一些较好的实验结果，本章将对蚁群算法进行改进引入夹角这一因素来解决路径规划问题。4.2夹角优化的蚁群算法我们知道蚁群算法是一种典型的概率随机搜索算法，许多研究表明28，蚁群算法在求解实际问题时容易出现两个问题：一是停滞现象；二是当所求问题规模较大时，需要很长的搜索时间，即收敛到全局最优解的搜索时间长。针对这两个问题，各国学者不断对蚁群算法

50、进行了改进和研究以期提高算法的性能29，这些改进的算法包括：带精英策略的蚁群算法（简称）、基于优化排序的蚁群算法（简称）、最大-最小蚁群算法等。这些算法都是围绕全局收敛和提高算法收敛速度这两点进行的，但是这两者是矛盾的统一体，不可能同时达到，因此要更好地改进蚁群算法必须充分考虑它的启发信息。问题中要求每个城市必须且只经过一次，为了避免重复我们需要建立禁忌表来记下蚂蚁已经走过的道路，以加快搜索速度节约时间，但是，在解决路径规划问题中，需要找到从起始点到目标点的最短路径，若是建立禁忌表，路线一旦偏离目标点，会使搜索陷入无路可走的地步，然而若是不使用禁忌表，该禁令的解除将很难制定策略，如算法复杂的问

51、题。所以，在我们改进的蚁群算法中，摒弃禁忌表的使用，同时加入一种新的启发式信息：方向夹角。4.2.1 方向夹角蚁群算法中最重要的部分就是给每只蚂蚁添加启发信息，引导它们感知信息素的多少以便更快地寻找最短路径，下面就介绍本章提出的一种启发信息：带方向夹角的全局搜索信息。解决路径规划问题，起始点和目标点的位置是已知的，如路径规划是显示在图7，我们可以考虑空间几何关系作为启发式信息。图7 路径规划模型Fig7 Path planning model如图7所示的路径规划模型，起始点和目标点是已知的，图中的边构造出的是所有的可行路径，这些边的交点就是所有的可行路径点，现需要规划出一条路径使得起始点和目标

52、点之间的距离最短。一条可行路径是包括起始点和目标点在的个顺序连接的路径点所表示：。在此我们假设起始点为，目标点为，并且和之间有边（可行路径）相连接。那么对可行路径的优化模型为：，其中表示路径点和之间的路线长度。为了解决上述路径规划问题，我们使用蚁群算法中的基本模型蚁周系统（ant-cycle system）模型，它利用的是整体信息，解决问题的性能较好，在蚁周系统模型中，蚂蚁在路径到上释放的信息素浓度为，且 (13)式中为启发信息的相对重要性，即相对程度；为常数；为蚂蚁所走的从起始点到目标点的路径总长度。若是蚂蚁走的路径总长度越短即越小，则信息素浓度越大，被选中该路径的概率也就越大，符合蚂蚁寻路

53、规则。为了使蚂蚁更快的有目的地寻找到最短路径，我们给它加入一双“眼睛”即方向夹角启发信息函数，引导蚂蚁的搜索方向。假设城市道路网络平面示意图如图8所示：图8 方向夹角启发信息Fig8 The angle between the direction of heuristic information不妨设所求路线是起点到终点的一条最短路，我们认为与夹角越小的路径段越有可能是全局最优路径的一部分，由于和相连接的点是点和点，不难看出，有向线段和的夹角小于线段和线段之间的夹角，因此，首先选择节点；同理，与相连的节点是和，优先选择节点；同理，优先选择。那么所选择的路线为，事实上，这条路线已经是最短路径。然

54、而，在电子地图中每个图元都有一个经纬度坐标30，利用经纬度坐标可以求出方向夹角的余弦值。在此，我们假设起点的坐标为，终点的坐标为，途经点的坐标，线段和的夹角为（方向夹角），将线段的长度记为，线段的长度记为，线段的长度记为，如图9所示：图9 夹角示意图Fig9 Schematic of angle则有 (14)式中。4.2.2 基本原理在本文的路径规划问题中，由于为路径点和之间的有向路径线段长度，为连接起始点和目标点的有向线段，为与之间的夹角，与夹角越小的线段就越可能是最优路线的一部分，也就是说越小，选择该路径的概率就越大，所以，进行计算时，通过计算方向夹角余弦值，从起始点开始寻找与其连接的线段形成较小夹角的那条路线，依次寻找，便可求出最短路径。蚁群算法的原启发式信息，表示示到的可见度，现加入夹角启发信息后，启发信息计算式修改为： (15)其中，为所有与当前路径点之间有路径线段相连接的路径点所组成的集合，为该集合中的元素个数。蚂蚁由路径转移到的概率为： (16)其中，和分别表示信息素和启发式信息的影响性。实际问题中，如果与当前路径点相连的各路径线段的夹角信息的值的差距比较大时，会导致各路径段的启发信息数量差距增大，从而蚂蚁选择路径的概率差距31会有很大悬殊，再加上信息素数量的正反馈效应，蚁群算法将迅速地收敛到局部极值。为了有效地解决这个问题，算法在式(