中国科学技术大学 硕士学位论文 生物启发式算法及其改进研究 姓名：贾亚军 申请学位级别：硕士 专业：系统工程 指导教师：丛爽 20100420 摘 要 I 摘摘 要要 自然界一直是人类创造力的丰富源泉，人类认识事物的能力大部分都来源 于与自然界的相互作用之中。 自然界中的许多自适应优化现象不断给人以启示: 生物体和自然生态系统可以通过自身的演化就使许多在人类看起来极其复杂的 优化问题得到完美的解决。近些年来，一些与经典的数学规划原理截然不同的、 试图通过模拟自然生态系统机制以求解复杂优化问题的生物启发式算法相继出 现(如进化算法、粒子群优化算法、人工免疫算法、蚁群优化算法等)，大大丰 富了现代优化技术，也为那些传统最优化技术难以处理的 NP 难问题提供了切 实可行的解决方案。因其高效的优化性能，无需问题特殊信息等优点，已广泛 应用于工程优化设计、计算机科学、组合优化、优化调度等领域。因此生物启 发式算法也越来越受到众多学者们的关注。本文主要研究了其中的进化算法、 蚁群算法、粒子群算法和人工免疫算法。 全文共分六章，第一章为绪论，主要介绍了生物启发式算法的发展历史， 以及目前的一些发展现状，并分别介绍了进化算法、蚁群算法、粒子群算法和 免疫算法的产生背景和发展现状。并对本论文研究的主要内容和研究方法进行 了简单的介绍。 第二章在介绍了进化算法的基本原理的基础上，分别对遗传算法、进化规 划、进化策略、遗传编程的不同方面的特点进行了研究，然后从编码策略，选 择方式，遗传算子等在不同算法的操作过程中所具有的不同点与侧重点，以及 对性能可能带来的影响进行了对比分析；最后讨论了进化算法中两种最主要的 操作算子：变异操作算子和交叉操作算子各自的优缺点。 第三章首先介绍了蚁群算法的基本原理，并介绍了旅行商问题这一典 型的组合优化问题的特点。针对进化策略收敛速度快但容易陷入早熟收敛以及 最大最小蚂蚁系统求解能力强但收敛速度较慢的特点，将进化策略与最大最小 蚂蚁系统融合，利用最大最小蚂蚁系统求出每一步迭代的最优解，再对迭代出 最优解进行进化策略中的变异操作来加快解的收敛速度。最后将所提出的改进 算法应用到中国旅行商问题(CTSP)的实际应用中，来验证算法的优越性。 第四章介绍了粒子群算法的基本原理以及解决旅行商问题的基本步骤，并 针对基本粒子群算法易陷入局部极小值的缺点，分别将进化算法中的变异因子 和模拟退火算法引入粒子群算法中，结合粒子群算法全局搜索能力强和模拟退 火算法局部搜索能力强的优点，提出了一种混合算法。最后将混合算法应用于 解决中国旅行商问题中，并将实验结果与基本的模拟退火算法、基本的粒子群 算法以及带有变异因子的粒子群算法进行了对比研究。 第五章首先对人工免疫算法的起源，基本原理，以及解决实际优化问题的 摘 要 II 基本步骤进行了介绍，并着重介绍了基于信息熵和基于欧式距离的免疫算法。 针对上述两种免疫算法存在的不足，提出了一种基于新的浓度计算方法的改进 人工免疫算法，最后将该算法应用在中国旅行商问题的求解中，并针对旅行商 问题的实际特点提出了一种新的免疫疫苗的提取和注射的方法，通过对比实验 验证了改进算法有着更高的求解效率。 第六章对本论文的一些研究成果进行了归纳总结，并指出了目前生物启发 式算法的研究中还存在一些问题， 最后对下一步研究的内容和方向进行了展望。 关键词：关键词： 生物启发式算法 进化算法 蚁群算法 粒子群算法 人工免疫算法 中国 旅行商问题 Abstract III ABSTRACT Nature has always been a rich source of human creativity, humans ability to understand things come from the interactions of human and natural. Many phenomena in nature give people inspirations：Organisms and natural ecosystems can solve many complex optimization problems by their evolutions. In recent years, some biological heuristic algorithms which different from some classical mathematical programming principles have emerged, such as evolutionary algorithm, particle swarm optimization, ant colony algorithm and artificial immune algorithm, etc. They have greatly enriched the modern optimization techniques and provided a practical solution for the NP-hard problem in which those of traditional optimization techniques are difficult to solve. With the advantage of efficient optimization performance and no need of problems specific information, they have been widely used in engineering optimal design, computer science, combinatorial optimization, optimal scheduling and other fields. This thesis mainly studies the evolutionary algorithm, ant colony optimization, particle swarm algorithm and artificial immune algorithm. This thesis is divided into six chapters. Chapter 1 is an introduction, which introduces the historical development of biological heuristic algorithm and the current development status, especially presents the background and development status of the evolutionary algorithm, ant colony optimization, particle swarm algorithm and immune algorithm. Finally, gives a brief introduction of the research contents and methods of the thesis. Chapter 2 studies the different aspects of genetic algorithm, evolutionary programming, evolution strategies and genetic programming after introducing the basic principles of evolutionary algorithm, then makes a compare study from the coding strategy, selection method and genetic operators. The two main operators in evolutionary algorithm: mutation and crossover are discussed. Chapter 3 introduces the basic principles of ant colony algorithm and the travelling salesman problem which is a typical combinatorial optimization problem. Evolution strategies converge fast but it has the problem of premature convergence. The max-min ant system has better solving ability but it converges slowly. To this problem, we combine max-min ant system with evolution strategies. Using max-min ant system to calculate the optimal solution of every iteration and make a mutate Abstract IV operation on the iterative optimal solution to speed up the convergence rate of solutions. The combination algorithm is applied into the Chinese Traveling Salesman Problem (CTSP) to verify the superiority of the algorithm proposed. Chapter 4 introduces the basic principles of particle swarm optimization and the steps of solving traveling salesman problem. For the shortcomings of particle swarm optimization (PSO) algorithm easily trapping into the local minimum value, we propose a hybrid algorithm which introduces the mutation factors of evolutionary algorithm and simulated annealing algorithm into the PSO. Finally, the hybrid algorithm is applied to solve the Chinese traveling salesman problem. Experimental results of basic simulated annealing algorithm, basic particle swarm algorithm and the particle swarm algorithm with mutation factor are compared. The origin of artificial immune algorithm, basic principles and steps of solving practical optimization problems are introduced in chapter 5