蚁群算法及其应用研究

博 士 学 位 论 文论文题目 蚁群算法及其应用研究 作者姓名 杨剑峰 指导教师 蒋静坪 学科(专业) 控制理论与控制工程 所在学院 电气工程学院 提交日期 2007 年 4 月 中文摘要1摘 要社会性动物的群集活动往往能产生惊人的自组织行为，如个体行为显得简单、盲目的蚂蚁组成蚁群以后能够发现从蚁巢到食物源的最短路径。生物学家经过仔细研究发现蚂蚁之间通过一种称之为“外激素”的物质进行间接通讯、相互协作来发现最短路径。受这种现象启发，意大利学者 M.Dorigo，V.Maniezzo 和A.Colorni 通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法蚁群算法。该算法的出现引起了学者们的巨大关注，在过去的短短十余年时间内，蚁群算法已经在组合优化、函数优化、系统辨识、网络路由、机器人路径规划、数据挖掘以及大规模集成电路的综合布线设计等领域获得了广泛的应用，并取得了较好的效果。本论文围绕蚁群算法的原理、理论及其应用，就如何改进基本蚁群算法、蚁群算法的并行实现，蚁群算法在组合优化、函数优化以及电厂主蒸汽温度控制系统等领域的应用进行了较为深入、系统的研究。本文的主要研究成果包括：1.提出了一种回溯蚂蚁系统。该算法使用了一种新的类型的回溯蚂蚁（BA）来发现新的路径，类似于 NP 算法中在周围区域中的抽样。除了对信息素的轨迹量限制一个最大和最小值以防止停滞以外，该算法让蚂蚁随机的选择最好解的那一条边，并且迫使蚂蚁避免这条边，然后用周游的方法更新信息素矩阵，而不是发现的最好解。仿真实验结果证明：该算法在无论是求解对称还是非对称 TSP 问题都可以和 MMAS 算法相媲美，体现了很高的性能。2.提出了一种多重蚁群算法。该算法是受并行遗传算法的概念所启发，在求解 TSP 问题时使用不同种群搜索解空间以避免局部最优从而获得全局最优。对几个 TSP 基准问题的仿真实验结果证实了该算法的有效性和可行性，其性能高于ACS 算法。3.针对大规模的 TSP 问题，提出了一种并行蚁群算法并行蚁群系统。同以往的并行策略不同的是，该算法把并行处理的概念用之于蚁群系统。该算法把人工蚂蚁分成几个群，然后把蚁群系统应用于每一个群体，群体之间可以进行通讯，即按照邻居群所发现的最好路径来更新自己每条路径上的信息素水平。该算法不仅减少了计算时间，而且具有极高的搜索较好解的能力。仿真实验结果表明了该算法的有效性，而且其性能也远远超过了 ACS 算法和 AS 算法。4.提出了求解函数优化问题的 GAAA 算法。该算法是基于遗传算法和蚂蚁算法的混合算法。其基本思路是算法前过程采用遗传算法,充分利用遗传算法的快速性、随机性、全局收敛性,其结果是产生有关问题的初始信息素分布。算法后过程采用蚂蚁算法,在有一定初始信息素分布的情况下,充分利用蚂蚁算法的并行性、正反馈机制以及求解效率高等特性,提高求解效率。实验结果表明，该算法是一种时间效率和求解效率都比较好的求解函数优化问题的有效算法。5.提出了一种求解电厂主蒸汽温度串级 PID 控制系统参数优化的蚁群算法。该算法针对 PID 参数优化的特点，把控制系统的绝对误差的矩的积分作为评价的浙江大学博士学位论文2性能指标来对控制系统进行优化；而后在蚂蚁的搜索过程中，嵌入了邻近搜索机制以搜索更优的解。实验结果证明，蚁群算法应用于主蒸汽温度 PID 控制器参数的优化是可行和有效的，而且比传统的方法和遗传算法具有更高的性能。最后，对全文的研究工作进行了总结，并对蚁群算法的未来研究方向作了展望。关键词：蚁群算法，信息素，协同机制，并行实现，组合优化，函数优化，电厂主蒸汽温度控制系统英文摘要3ABSTRACTA wonderful self-organization behavior will usually be produced from the collective behavior of social animals. Take a colony of ants for example, simple and blind ants can find the shortest routing path from their nest to food source. Biologists had studied the phenomenon carefully and found that ants cooperate to find the shortest routing path by means of indirect communications using a kind of substance call“pheromone”.Inspired by this phenomenon, a population-based simulated evolutionary algorithm called ant colony algorithm (ACA for short) was proposed by Italian researchers M.Dorigo, V.Maniezzo and A.Colorni. Many scholars are attracted to study ACA and in the past ten years than more the algorithm has been widely applied to the fields of combinatorial optimization,function optimization, system identification, network routing, path planning of robot, data mining and premises distribution of large scale integrated circuit etc, and good effects of application are gained.This paper focuses on the principles, theory, and applications of ACA, especially, an in-deep and systemic study on how to improve the basic ACA algorithm, parallel implementation of ACA, solving the problems such as combinatorial optimization, function optimization, and main-steam temperature control system at power plant. The main achievements of this paper include:1. A backtracking ant system (BAS) was proposed. In BAS, a new type of ants that is called backtracking ants（BA） is used to find mew routes, in a manner similar to the sampling of the surrounding subregion in the NP algorithm. In addition to using maximum and minimum values for the pheromone,s trails to avoid stagnation, the BAS algorithm obliged the ants to select new routes by random selecting an edge of the best solution and forcing the ants to avoid this edge and then update the pheromone matrix using a tour different than the best found. Simulated experiments show that the results obtained by the BAS algorithm are comparable to the MMAS in case of the symmetric TSP instances and the asymmetric instances.2. An ant colony optimization with multiple ant clan (ACOMAC) was proposed. Inspired by the concept from parallel genetic algorithm, 浙江大学博士学位论文4this algorithm searches solutions space that using different islands to avoid local minima and so as to obtain global minimum for solving the TSP problem. Simulated experiments for the TSP on several bench show the validity and the feasibility of the proposed algorithm, and that the algorithm performs better than the ant system (AS) and the ant colony system (ACS).3. A parallel ant colony system (PACS) was proposed to solve the large traveling salesman problem. Other than the prevenient parallelization strategy, we apply the concept of parallel processing to the ant colony system. In the algorithm the artificial ants are separated into several groups, and the ant colony system is then applied to each group, and each group may communicate each other, that is to say each group updates their pheromone level for each route according to the best route found by neighboring groups. This algorithm not only reduces the computation time but also obtains a better solution. Experimental results based on the traveling salesman problem confirm the efficiency and effectiveness of the proposed PACS, and it also confirm that the proposed PACS is superior to the existing ant colony system (ACS) and ant system (AS).4. A hybrid algorithm for function optimization called genetic algorithm and ant algorithm (GAAA) was proposed. The algorithm is based on genetic algorithm and ant algorithm. The basic idea is that we adopt genetic algorithm with its properties of speediness, randomicity and global convergence to give information pheromone to distribute firstly, and then we adopt ant algorithm with its properties of parallelization, positive feedback mechanism and high efficiency to enhance the efficiency under the condition of having some initial pheromone distribution. Experimental results show that the proposed GAAA is a effective algorithm for function optimization with good time efficiency and solving efficiency.5. An algorithm for parameter optimization of the cascade PID control system of main-steam at power plant was proposed. The algorithm adopts the moment integral of absolute error as the assessment index to optimized the control system; Then we add neighboring searching mechanism to find better solution during the course of ant searching. Experimental results show that the proposed algorithm for parameter optimization of main-steam control system is effective and feasible, moreover it performs better than the 英文摘要5traditional methods and genetic algorithm.Finally, the work of this paper is summarized and the prospective of future research is discussed.Keywords: Ant Colony Algorithm, Pheromone, Stigmergy, parallel realization, Combinatorial Optimization, Function Optimization, Main-Steam Temperature Control System at Power Plant浙江大学博士学位论文6英文摘要7目 录中文摘要 .1英文摘要 .31 绪论 .11.1 引言 .11.2 蚁群算法的原理分析及算法描述 .21.2.1 蚂蚁的信息系统 .31.2.2 蚁群社会的遗传和进化 .31.2.3 蚂蚁的觅食行为和觅食策略 .31.2.3.1 蚂蚁的觅食行为 .31.2.3.2 蚂蚁的觅食策略 .31.2.4 蚁群算法的原理分析 .61.2.5 人工蚁群算法的算法描述 .81.2.5.1 人工蚁和真实蚂蚁的异同 .81.2.5.2 人工蚁群算法描述 .91.2.5.3 人工蚁群算法的特点 .101.3 蚁群算法与其他搜索算法的比较 .111.3.1 蚁群算法与进化计算的比较 .111.3.2 蚁群算法和模拟退火算法的比较 .121.3.3 蚁群算法与神经网络的比较 .131.4 蚁群算法的研究现状 .131.5 本论文研究内容及成果 .162 蚁群算法的收敛性 .192.1 引言 .192.2 基于图解的蚂蚁系统及其收敛性 .192.2.1 基于图解的蚂蚁系统 .192.2.1.1