蚁群算法的改进研究与应用硕士学位论文.doc

《蚁群算法的改进研究与应用硕士学位论文.doc》由会员分享，可在线阅读，更多相关《蚁群算法的改进研究与应用硕士学位论文.doc（44页珍藏版）》请在三一办公上搜索。

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

2、visor:Xu 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关键词：蚁群

6、算法；模拟退火算法；梯度；夹角优化分类号：O224AbstractAnt 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 prob

7、lems. It fully demonstrated 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 sol

8、ution, convergence is slow, 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

9、 algorithm combines. It takes 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

10、 algorithm and the results 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

11、 algorithm not only possesses 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 backg

12、round and significance of 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. Firs

13、t introduces the basic principle 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 a

14、lgorithm for solving problems 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 pa

15、th planning. Figure 13 table 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

16、.2 蚁群算法的算法流程62.3 蚁群算法的优缺点93基于目标函数梯度的模拟退火蚁群算法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 illus

17、trations and scheduleIntroduction1 Exordium11.1 Background and significance of ant colony algorithm.11.2 Research 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

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

19、 algorithms of simulated annealing algorithm11 3.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 ap

20、plication184.1 Path planning problem184.2 Ant colony algorithm in the angle optimization184.2.1 Orientation angle194.2.2 Fundamental principle214.2.3 The improved algorithm flow224.3 Cases and Analysis25Summarization27References28Acknowledgements30Brief introduction of author31插图或附表清单相关图：图1：蚂蚁路径寻优过程

21、图2：蚁群算法的流程图图3：模拟退火算法的流程图图4：基于目标函数梯度的模拟退火蚁群算法流程图图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，随后出现了多种其他常用的改进方法：改进信息素设定机制以及将与遗传算法、模拟退火算法相结合等。随着社会的进步，特别是智能理论和应用算法研究和发展，学者们已经取得了很大进展，试图将其应用于现实实践中，并取得了意想不到的成果。目

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

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

28、找，便可求出最短路径。如今，蚁群算法作为群智能算法的一种新型进化算法，已经在智能领域13表现出了极为强大的生命力，对于解决各种复杂优化问题都显示了它的卓越之处，由于它本身也存在许多缺陷14，因此蚁群算法改进方面的研究对解决这些实际优化问题具有重要意义，并能更好地推动智能算法的不断发展和完善，本文对蚁群算法的改进方面进行了严格的理论分析和完整的数值实验，对整个群智能理论体系起到了巨大的推动作用，其本身也具有重要的理论研究价值和实践意义。1.3.2 论文的主要内容本论文主要包含以下几方面：1. 首先简要介绍了蚁群算法的意义产生的背景和研究的现状的研究，总结了研究的意义和论文的主要内容。2. 分析了

29、蚁群算法的结构，包括蚁群算法的基本原理、参数设置和算法分析，算法的过程和优缺点等。3. 阐述了模拟退火算法的基本原理和算法流程，然后介绍基于目标函数梯度的模拟退火蚁群混合算法的基本原理和算法流程，并给出新算法对TSP问题优化的实验结果。4. 概要介绍了路径规划问题，然后论述夹角优化的蚁群算法的基本原理和算法流程，最后给出改进后的算法对路径规划问题的优化结果。2 蚁群算法的原理及过程2.1 蚁群算法的基本原理蚁群算法中的虚拟蚂蚁吸收了大自然中真实蚂蚁的行为特征。众所周知，蚂蚁的个体行为显得简单而又无序，再加上蚂蚁的视觉发育不完整甚至有些蚂蚁没有视觉，然而集体组织活动时却能快速有效地找到食物源15

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

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

32、所以蚂蚁最初选择路径的概率是一样的。当时，如图1(b) 所示，只蚂蚁从出发，以相同的概率选择和，因此，各方向有只蚂蚁行走。当时，如图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) 容易

38、出现停滞，搜索到一定程度，所有个体的解决方案完全相同，没有进一步搜索解空间，不利于找到更好的解决方案。3基于目标函数梯度的模拟退火蚁群算法3.1 模拟退火算法的基本原理和算法流程模拟退火算法是基于迭代算法的一种启发式随机搜索算法19，最早的思想由等人于1953年提出20。它源于物理中对固体退火过程的模拟，分为升温、平衡、冷却三个阶段，先将固体加温至充分高，再让其渐渐冷却，升温时粒子变为无序状内能增大，冷却时粒子变得有序，内能逐渐减小。由此过程，可将模拟退火算法应用于求解组合优化问题，此时，将内能模拟为目标函数，温度对应于控制参数，并用冷却控制表控制算法进程。该算法的基本思想是从一给定解开始的，

39、从邻域中随机生成另一个解，接受准则允许的目标函数恶化在有效范围内，它由一控制参数决定，算法由初始解和控制参数初值开始反复进行“生成新解计算目标函数值的差接受或拒绝”这一迭代过程，它对应着固体在某恒定高温下趋于热平衡的过程，减少了控制参数，系统越来越趋于平衡状态，最终的系统状态对应于优化问题的整体最优解，需要指出的是，由于固体退火缓慢冷却可以使固体在所有温度下达到热平衡，因此，控制参数必须缓缓衰减才能保证优化问题趋于整体最优解。在判断新解是否被接受，我们通常使用准则来判断是否为新解：若目标函数值的差，则接受作为当前解；否则，若，则接受作为新解，否则舍弃。模拟退火算法的基本流程如下：(1) 参数初

40、始化。给定初始温度（足够大）和退火速度，初始解及目标函数；(2) 随机扰动产生新解，计算；(3) 若，作为当前解；否则，若，为新解，否则舍弃，仍为当前解；(4) 对进行缓慢降温，重复步骤2至3，直至满足迭代条件。模拟退火算法的流程图如下：图3 模拟退火算法流程图Fig3 The flowchart of simulated annealing algorithm3.2 基于目标函数梯度的模拟退火蚁群算法3.2.1 混合算法的基本原理通过以上对蚁群算法和模拟退火算法基本原理的研究可知，蚁群算法的优点是正反馈、自组织、分布式，缺点是易限于局部最优解，收敛速度慢。模拟退火算法的优点是算法简单、鲁棒性

41、强、具有全局搜索能力，特别适用于复杂的非线性问题，缺点是对初始解有很强的依赖性，当系统不使用反馈信息，在一定程度上的解是大量的冗余迭代造成的，精确率低。因此根据各自的优缺点可以将两种智能优化算法根据某种法则相融合或在某种优化算法中引入其它优化思想，形成混合优化算法，可以充分发挥智能算法各自的优点，扬长避短，以便取得时间性能和优化性能的双赢，提高算法各方面的性能。模拟退火算法和蚁群算法混合的基本思路是：第一，利用模拟退火算法得到一些更好的解，在其路径上留下信息素，其它东西不变；第二，根据蚁群算法让蚂蚁进行一次周游；第三，采用模拟退火算法在邻域内寻找另外一个解，找到的这个解有可能变坏，为了简化计算

42、可限定一个目标函数变坏的范围，若路径长度差，接受新解，否则舍弃。3.2.2 算法流程考虑到模拟退火算法和蚁群算法各自的特点，许多学者先后提出了基于模拟退火算法和蚁群算法的混合智能优化算法16。许智宏提出一种模拟退火蚁群并行算法17。刘波提出了一种基于模拟退火机制的蚁群算法，该算法在高温阶段以高概率加入更新集，在低温阶段采用回火策略18。常规的模拟退火蚁群算法不考虑目标函数的变化率，只是采用固定的更新信息素的方法和降温的方法，这就有可能产生冗余迭代，并且在一定程度上影响了解的质量。本文提出了一种基于目标函数梯度的模拟退火蚁群混合算法，在优化过程中，根据目标函数的梯度动态地控制信息素浓度和回火过程

43、，并根据数值实验结果对新算法的全局收敛性和解的质量进行了评测。该混合算法充分考虑了目标函数的梯度，当目标函数的梯度较小时，加强当前最优解对应的信息素，这相当于在“平坦”之处加快搜索速度，使算法加快收敛；当目标函数的梯度过大时，引入回火策略19，即在“陡峭”之处放缓搜索速度，以提高解的质量。并用改进的算法求解旅行商问题，结果表明，与常规的模拟退火蚁群算法相比，新算法的收敛速度和解的质量均得到很大的改善。在本文中，设退火函数为（），在完成一轮搜索与信息素更新后，进行退火即降温，降温过程中，当系统温度较高时，较差的解将以较高的概率进入更新集，导致路径上的信息素分布更加广泛，避免出现早熟；随着的降低，

44、接受较差解的概率将逐渐减小，导致路径上的信息素分布集中，算法将快速收敛，我们鼓励过早收敛，采用较小的，这样可以缩短找到更好解的时间以提高效率，但是，这样会增大落入局部极值点的风险。因此，为了解决这个问题，我们在算法中引入回火机制，回火是指将温度略微升高后再降温的策略。回火的温度范围设为，若，将温度升高至，重新进行算法迭代，当再次时，这一过程称为回火过程，重复此过程，可以根据设定进行多次回火，回火次数设为，最大回火次数。考虑目标函数梯度的具体方法是：定义 (7)其中 (8) (9)表示向量的第个分量。对于离散优化问题，不存在梯度，则 (10) (11) (12)其中，分别表示父代和子代个体。当小

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