《毕业论文：群智能算法用于优化计算问题研究》由会员分享，可在线阅读，更多相关《毕业论文：群智能算法用于优化计算问题研究（47页珍藏版）》请在金锄头文库上搜索。
1、III 目 录 摘 要I ABSTRACT .II 目 录III 第一章 引 言.1 1.1 课题的背景和意义1 1.2 组合优化（CO）问题模型.2 1.3 群智能算法的特点2 1.4 国内外研究现状3 1.4.1 蚁群算法研究现状 .3 1.4.2 粒子群算法研究现状 .3 第二章 蚁群算法（ACO）.4 2.1 蚁群算法简介4 2.1.1 基本原理 .4 2.2 蚁群算法模型5 2.2.1 蚁群算法基本流程 5 2.2.2 一个基本 ACO 算法框架 6 2.3 蚁群算法应用举例9 2.3.1 离散领域 9 24 其他应用.11 25 参数设置.12 第三章 粒子群优化算法（PSO）13
2、 3.1 粒子群优化算法简介13 3.1.1 基本原理 .13 3.2 粒子群优化算法基本流程13 3.3 粒子群优化算法应用实例16 3.3.1 连续多峰函数极值应用 16 3.3.2 0-1 背包问题 18 3.4 其他应用21 IV 3.5 参数设置21 结 论22 参考文献23 致 谢24 附录.25 群智能算法用于优化计算问题研究 I 摘 要 优化算法是一门以数学为基础、用来求解各种工程问题最优解的计算机应 用技术。随着技术进步，组合优化问题变得越来越复杂，传统的计算方法在求 解这类问题时面临着诸多问题，如计算复杂度高、计算时间长等，特别是对于 一些 NP 难和 NP 完全问题。为了
3、在求解时间和计算精度上取得平衡，研究学者 提出了各种启发式特征的计算方法。常见的启发式特征算法有禁忌搜索、模拟 退火算法、进化算法 和群智能等。 本课题主要研究了群智能算法在组合优化计算问题方面的应用。群智能算 法是一种基于群体搜索的随机优化算法，主要有蚁群算法和粒子群优化算法两 种。文章中详细地介绍了蚁群算法和粒子群优化算法的原理、发展及基本流程， 我的工作主要是利用群智能算法在 VC+平台下实现其在连续空间及离散领域 的常见应用，如连续多峰函数极值求解、0-1 背包和典型的旅行商问题(TSP)。 关键词：群智能，蚁群算法，粒子群优化算法，0-1 背包，TSP 群智能算法用于优化计算问题研究
4、 II Abstract The optimization algorithm is a computer application technology which based on the mathematics and used to solve various engineering problems for optimal solution. With the progress of technology, combinatorial optimization problems become more and more complex. The traditional methods
5、in solving such problems are faced of much trouble, such as high computational complexity and long computing time and so on, especially for some NP-hard and NP-complete problems. The researchers introduce several of heuristic algorithms in order to strike a balance in the computing time and calculat
6、ion accuracy. The ordinary heuristic algorithms are tabu search, simulated annealing, evolutionary computation and swarm intelligence and so on. In this paper, I mainly research the application of swarm intelligence algorithm in combinatorial optimization problem. Swarm intelligence algorithm which
7、mainly includes ant colony optimization and particle swarm optimization is a stochastic optimization algorithm based on colony search. The article describes the theory, development and the basic process of ant colony optimization and particle swarm optimization in detail. My main work is achieving c
8、ommon applications of continuous space and discrete area in the platform of VC+ by use of swarm intelligence algorithm. Common applications are continuous peak function solving, 0-1 knapsack problem and typical traveling salesman problem (TSP). Key words: Swarm Intelligence, Ant Colony Algorithm, Pa
9、rticle Swarm Optimization, 0-1 Knapsack, TSP 1 第一章 引 言 1.1 课题的背景和意义课题的背景和意义 伴随着科学技术的进步，实践生活中遇到的问题越来越复杂，传统的计算 方法在解决这些问题时面临着越来越多的困难，如计算复杂度高、计算时间长 等，尤其是对一些 NP（Nondeterministic Polynomial）难问题，传统算法根本不 能在可以承受的时间内计算出精确的解。 鉴于此种原因，计算机科学家们提出了很多具有启发式特征的计算智能方 法，以期能够平衡求解时间和求解精度。这些方法大多是研究者们受到大自然 的启发而被提出，它们有的是模仿生物
10、界的进化过程，有的是模仿生物的生理 构造和身体机能，也有的是模仿动物的群体行为、或者模仿人类的思维、语言 和记忆过程的特性，更有的是模仿自然界的物理现象，但它们有一个共同点， 都是希望通过模拟大自然和人类的智慧实现对问题的优化求解，以期在可承受 的时间内计算出可接受的解。这些算法共同组成了计算智能优化算法，计算智 能算法具有智能性、并行性、健壮性和很好的自适应性以及很强的全局搜索能 力，因此得到了众多研究者的广泛关注，并且在算法理论和性能方面取得了很 多突破性的进展，被广泛应用于各种领域，在科学研究和生产实践中发挥着中 重要的作用。 人们从生物进化的机理中受到启发，在20 世纪 50 年代中期
11、创立了仿 生学，提出了许多用以解决复杂优化问题的新方法，如遗传算法、进化规划、 计划策略等。群智能作为一种新兴的智能演变计算技术在20 世纪 90 年代 被提出，已经成为越来越多研究者的关注焦点，它与人工生命，特别是进化 策略以及遗传算法有着极为特殊的联系。群智能是指“无智能的主体通过 合作表现出智能行为的特性 ”，它在没有集中控制且不提供全局模式的前 提下，为复杂的分布式问题求解方案奠定了基础。目前，群智能领域主要有 两种算法：蚁群算法（ Ant Colony Optimization，ACO）和粒子群优化算 法（Particle Swarm Optimization，PSO）。前者是对蚂蚁
12、群落采集食物过 程的模拟，已成功应用于许多离散优化问题。粒子群优化算法也是起源于对 简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很 好的优化工具。到目前为止，群智能方法能够被用于解决大多数优化问题或 者能够转化为优化求解的问题。 2 1.2 组合优化（组合优化（CO）问题模型）问题模型 ACO 算法是随机搜索程序。它们的主要组件是信息素模型（在后续文章中 会有介绍），这种模型常常被用在概率采样搜索空间。这种模型从一个解决的 组合优化（CO）问题模型派生而出，CO 问题模型定义如下： 一个 CO 问题的模型包含：),(fSP 搜索空间（或解空间）定义在一组离散决策变量的有限集
13、合上，是S 一组约束变量； 目标函数：，求其最小值。 RSf : 搜索空间定义如下：给定一个维离散变量，值S n i X ，。一个变量的实例就是为一个变量分 i D iii j i vvDv, 1 ni, 2 , 1 i X 配一个值，记为，一个可行的解决方案就是满足限制条件的一 j i v j ii vX Ss 个完整分配（例如，在一个分配方案中每一个决策变量有一个分配的域值）。 如果约束变量集合是空的，那么每一个决策变量可以不依靠其他决策变量而 从它的域值中任取一个值。这时我们称是非约束问题模型，否则称作约束问P 题模型。一个可行的解决方案称作是全局最优方案（或全局最优）。如Ss * 果全
14、局最优解决方案就会表示成。这样解决 COSssfsf),()( * S)( * SS 问题是只需要找到一个方案。 * Ss 1.3 群智能算法的特点群智能算法的特点 与大多数基于梯度应用优化方法算法不同，群智能依靠的是概率搜索算法。 虽然概率搜索算法通常要采用较多评价函数，但与梯度算法及传统的演化算法 相比，其优点还是显著的：无集中控制约束，不会因个别个体的故障影响整个 问题的求解，确保了系统具备更强的鲁棒性；以非直接的信息交流方式确保了 系统的扩展性，由于系统中个体的增加而增加的通信开销也较少；并行分布式 算法模型，可充分利用多处理器，这样的分布模式更适合于网络环境下的工作 状态；对问题定义
15、的连续性无特殊要求；系统中每个个体的能力十分简单，每 个个体的执行时间也比较短，并且算法实现简单。 群智能方法易于实现，算法中仅涉及各种基本数学操作，其数据处理过程 对 CPU 和内存的要求也不高。且这种方法只需要目标函数的输出值，而无需其 梯度信息。已完成的群智能理论和应用方法研究证明群智能方法是一种能够有 3 效解决全局优化问题的新方法。更重要的是，群智能潜在的并行性和分布特点 为处理大连的以数据库方式存在的数据提供了技术保证。无论是从理论研究还 是应用研究的角度分析，群智能理论及应用研究都是具有重要学术意义和现实 价值的。 1.4 国内外研究现状国内外研究现状 1.4.1 蚁群算法研究现
16、状 蚁群系统 (Ant System，简称 AS)是意大利学者 M.Dorigo 和 Maniezzo 于 20 世纪 90 年代初受自然界中真实蚁群的觅食行为启发提出的一种新型的智能算法。 此后，经 Dorigo、Colorni、Holgerhoos、Bilchev、Gambardella、Gutjahr 等多位 学者的发展，从蚂蚁系统(Ant System，AS)开始，先后出现了 Ant-Q、蚁群系统 (Ant Colony System ACS)、最大最小蚂蚁系统(Max- Min AS，MMAS)等。在对 蚁群算法的应用方面，已经由当初单一的 TSP 领域渗透到了多个应用领域,由 解决一维静态优化问题发展到解决多维动态组合优化问题,由离散域范围内研究 逐渐拓展到了连续域范围内研究,而且在蚁群算法的硬件实现上取得了突破性进 展。 我国在蚁群算法领域的研究起步较晚，国内最先研究蚁群算法的是东北大 学控制仿真研究中心的张纪会博士与徐心和教授，随后几年里，越来越多的学 者进入了这个领域，并在蚁群算法的改进和
