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