蚁群算法改进及应用研究VIP

1国内图书分类号：TP181国际图书分类号：621.3工学博士学位论文蚁群算法改进及应用研究博士研究生导师申请学位级别学科、专业所在单位授予学位单位：刘波吴惕华教授李惠光教授工学博士控制理论与控制工程电气工程学院燕山大学 Classified Index:TP181U.D.C.:621.3Dissertation for Doctoral Degree in EngineeringIMPROVEMENT OF INTELLIGENT ANTCOLONY ALGORITHM AND ITSAPPLICATIONCandidate：Liu BoSupervisor：Prof.Wu TihuaProf.Li HuiguangAcademic Degree Applied for： Doctor of EngineeringSpeciality：Control Theory and Control EngineeringUniversity：Yanshan University 燕山大学博士学位论文原创性声明本人郑重声明：此处所提交的博士学位论文蚁群算法改进及应用研究 ，是本人在导师指导下，在燕山大学攻读博士学位期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。作者签字：日期：年月日燕山大学博士学位论文使用授权书蚁群算法改进及应用研究系本人在燕山大学攻读博士学位期间在导师指导下完成的博士学位论文。本论文的研究成果归燕山大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解燕山大学关于保存、使用学位论文的规定，2同意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山大学，可以采用影印、缩印或其它复制手段保存论文，可以公布论文的全部或部分内容。保密，在年解密后适用本授权书。本学位论文属于不保密。(请在以上相应方框内打“” )作者签名：日期：年月日导师签名：日期：年月日摘要蚁群算法(ACO)是由意大利学者 M.Dorigo，V.Maniezzo 等人于 20 世纪 90 年代初期通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启发式仿生进化算法。他们通过对蚂蚁觅食行为的研究，发现整个蚁群是通过一种叫做信息素的化学物质进行相互协作，形成正反馈，使多个路径上的蚂蚁逐渐聚集到最短的那条路径上来。蚁群算法的出现引起了学者们的巨大关注，在过去的短短不到二十年时间内，蚁群算法已经在组合优化、函数优化、系统辨识、网络路由、机器人路径规划、数据挖掘以及大规模集成电路的综合布线设计等领域获得了广泛的应用，并取得了较好的效果。但是，随着解决问题复杂程度的不断增加，传统的蚁群算法越来越显现出其解决问题的局限性，于是，越来越多的学者展开了蚁群算法的改进研究，从目前来看，蚁群算法的改进主要从两个方面展开，一是对蚁群算法本身的改进，诸如针对信息素释放修改进行改进、针对概率选择方式进行改进等；二是与其它其他智能优化算法进行融合改进。本文通过对基本蚁群算法原理的研究与分析，从蚁群算法本身的改进，与其他智能优化算法的融合改进和改进蚁群算法的应用等方面进行了比较系统的研究论述。(1)在二进制蚁群算法的基础上，提出了两种二进制蚁群算法的改进方案，一是将解空间变量直接进行二进制离散化，根据区间大小确定二进制转化位数 n，即精度，然后将整个变量组成的这个 n 位二进制数列看成一个 n 个城市的 TSP 问题求解。完全区别于传统蚁群算法和已有二进制蚁群算法中将解空间划分成若干子域，在每个区间内将每个种群独立并行地遍历求解的方法。经测试函数进行测试，算法的收敛速度和寻优迭代次数方面都有了很大程度的改善；二是将加权策略成功应用于二进制蚁群算法的信息素更新方面，使得算法的全局收敛性能大大提高，通过经典测试函数测试，效果明显。(2)将蚁群算法与 PBIL 分布估计算法相融合，提出了一种新的分布估计蚁群算法。该算法以蚁群算法为主，引入分布估计算法中的 PBIL 算法的概率分布模型来指导启发蚂蚁的路径选择，从而可以大大的改善蚁群算法由于信息素的正反馈机制而造成容易陷入局部最优的缺陷。(3)从 Qos 属性最优的角度将蚁群算法成功应用于 Web 服务组和优化问题。Web服务组合本身就是一种解决复杂问题的方法，其应用也越来越广泛，采用蚁群算法解决 Web 服务组合优化，并最终给出了最优服务组合对应的 Qos 属性值，实际上是解决了与之相关的一类问题，具有非常的现实意义。(4)将蚁群算法成功应用于白洋淀景区旅游线路规划问题，从而在第一时间为白洋淀旅游开发总体规划规划研究人员提供轮廓性资料，让研究人员节省更多的时间进行细节规划，从而大大提高规划效率。3关键词蚁群算法；二进制蚁群算法；加权策略；分布估计算法；Web 服务组和优化；旅游规划 AbstractDuring the 1990s,the Italian scholar M.Dorigo,V.Maniezzo proposed a heuristicevolutionary bionic algorithm based on population by simulation the collective behaviorof ant routing,and found the whole ant colony make use of pheromone to collaboratewith each other to form a positive feedback that each ant follow the shortest path.In last two decades,Ant colony algorithm got extensive application in combinatorialoptimization,function optimization,system identification,network route,robot pathplanning,data mining and cabling design of large scale integrated circuit.But manyscholars realized the limitation of traditional ant colony algorithm to improve.Theimprovement of ant colony algorithm have two handles,one aspect is the improvement ofitself,such as improvement mode of pheromone release,probability of selection method,and the other is fusion improvement on ant colony algorithm and other intelligentoptimization algorithms.This paper is a detailed study of the principle,analysis,fusion improvement and theapplied of ant colony algorithm.Firstly,we propose two improvement of binary ant colony algorithm.One improve-ment is binary discrete with solution space variable.We determine binary digitconversion n according to the size range,then we will convert it into the solving TSPproblems on n cities.Each population interval are computed by forward and backward inevery interval,which was completely different from the method of solution space isdivided into many subdomains in traditional ant colony algorithm and binary ant colonyalgorithm.The tests show that improvement algorithm has make a lot of progress withtraditional ant colony algorithm and binary ant colony algorithm in convergence rate anditerations of optimization.The other improvement is apply weighted strategy to renewalof pheromone.The test results show that improve the global convergence performancealgorithm greatly,heighten the accuracy of the solution.Secondly,we propose a novel estimation of distribution algorithm by fusionimprovement on ant colony algorithm and PBIL estimation of distribution algorithm.Thealgorithm introduce probability distribution model of PBIL algorithm to guide routechoice,which greatly improve the faults that positive feedback mechanism of pheromonecan easily fall into local optimum.Thirdly,we apply ant colony algorithm to the problem of web services section andoptimization form Qos property optimal.Web services section is a way of solvingcomplex problems and widely used.In last,we obtain the attribute values Qos foroptimal service composition.This way has a very practical significance.Fourthly,wo apply ant colony algorithm to line planning of Baiyang Lake,whichcome up with the new idea for the planning staff in Master Plan of Baiyang LakeTourism Area Development and improve the efficiency greatly.Keywords Ant colony algorithm;Binary ant colony algorithm;Weighted strategy;Estimation of Distribution Algorithms;Web services section and optimization;Tourism planning 目录摘要.IABSTRACT.III4第 1 章绪论.11.1 课题的背景及意义.11.2 蚁群算法原理及算法描述.11.2.1 蚁群算法的生物基础.11.2.2 蚁群算法的基本原理.31.2.3 蚁群算法基本实现.51.3 蚁群算法的特点.81.3.1 人工蚂蚁系统与真实蚂蚁系统的比较.81.3.2 蚁群算法的特点.101.4 蚁群算法的改进.111.4.1 基于网格划分策略的蚁群算法.111.4.2 基于信息量分布函数的蚁群算法.111.4.3 基于交叉变异操作的蚁群算法.121.4.4 嵌入确定性搜索的蚁群算法.131.4.5 多目标优化问题的蚁群算法.131.4.6 与其它仿生优化算法的融合.141.5 蚁群算法的应用.141.6 论文研究内容及成果.16第 2 章连续域二进制蚁群算法的实现及其改进.192.1 引言.192.2 二进制蚁群算法模型表述.192.3 二进制蚁群算法中有关参数的选择及对算法性能的影响.212.3.1 启发式因子 、 的选择.212.3.2 信息素残留因子 的选择.232.3.3 蚂蚁数量 m 的选择.242.3.4 总信息量 Q 的选择.252.4 二进制蚁群算法改进与实现.262.4.1 编码方式.262.4.2 解码方式.272.4.3 初始解.272.4.4 路径选择.272.4.5 信息素更新.272.4.6 转移概率的计算.282.4.7 算法基本步骤.282.4.8 试验结果.282.5 二进制蚁群算法的加权策略.322.5.1 适于加权改进的算法表述.322.5.2 加权策略的实现.332.5.3 加权二进制蚁群算法的测试及分析.352.6 本章小结.40第 3 章 PBIL 分布估计蚁群算法 .413.1 引言.413.2 二进制蚁群算法.413.3 PBIL 分布估计算法.4353.3.1 PBIL 算法原理.433.3.2 PBIL 算法流程.443.4 算法的混合改进策略.443.5 算法参数的确定.453.5.1 学习速率 的确定.473.5.2 分布模型样本百分比 的测试.493.5.3 信息素蒸发率 的测试.503.5.4 蚂蚁个数 m 的测试.523.5.5 学习指导因子 的测试.533.6 仿真实验及分析.553.7 本章小结.60 第 4 章蚁群算法在 WEB 服务组和优化中的应用.614.1 引言.614.2 基于 QOS 的 WEB 服务组合 .614.2.1 Web 服务架构.614.2.2 Web 服务 QoS 模型.624.2.3 Web 服务动态组合.624.3 QOS 驱动下 WEB 服务优化算法 .634.3.1 基于 Qos 的 Web 服务选择问题 .634.3.2 QoS 驱动下 Web 服务选择的蚁群算法模型.634.3.3 算法流程.654.3.4 初始蚁群的生成与分布.654.3.5 参数选择.664.3.6 算法终止条件.674.3.7 实验数据及运行平台.674.3.8 实验结果.694.4 WEB 服务组合的应用.694.5 本章小结.70第 5 章蚁群算法在白洋淀旅游规划中的应用.715.1 白洋淀旅游开发现状.715.2 白洋淀旅游规划要点.725.3 基于改进蚁群算法的景区线路规划.755.3.1 白洋淀景区规划坐标图.755.3.2 基于加权蚁群算法的 TSP 问题.785.3.3 基于加权蚁群算法的景点线路规划.825.4 本章小结.84结论.85参考文献.87攻读博士学位期间承担的科研任务与主要成果.97致谢.99作者简介.100ContentsAbstract(in Chinese).IAbstract(in English).IIIChapter 1 Introduction.161.1 Background and significance of the task.11.2 Principle of ant colony algorithm and its description.11.2.1 Biological basis of ant colony algorithm.11.2.2 Basic principles of ant colony algorithm.31.2.3 Basic realization method of ant colony algorithm.51.3 Characteristic of ant colony algorithm.81.3.1 Comparison of artificial ant system and natural ant system.81.3.2 Characteristic of ant colony algorithm.101.4 Characteristic of ant colony algorithm.111.4.1 Ant colony algorithm for based mesh generation strategy.111.4.2 Ant colony algorithm for based distribution function of information.111.4.3 Ant colony algorithm for based crossover mutation.121.4.4 Ant colony algorithm with embedded deterministic search.131.4.5 Multi-objective optimization ant colony algorithm.131.4.6 The integration of bionic optimization algorithm and ant colony algorithm.141.5 The application of ant colony algorithm.141.6 The main research content and results.16Chapter 2 The realization method and improvement of binary ant colonyalgorithm in continuous domain.192.1 Introduction.192.2 The expression of binary ant colony algorithm.192.3 The choice of relevant parameters and its performance with binary ant colonyalgorithm