毕业设计（论文）-群智能算法用于优化计算问题研究.doc

全套设计加 153893706 SHANDONG 毕 业 论 文 群智能算法用于优化计算问题研究 学 院： 理学院 专 业： 信息与计算科学 学生姓名： 学 号： 指导教师： 2012 年 6 月 全套设计加 153893706 I 摘 要 优化算法是一门以数学为基础、用来求解各种工程问题最优解的计算机应 用技术。随着技术进步，组合优化问题变得越来越复杂，传统的计算方法在求 解这类问题时面临着诸多问题，如计算复杂度高、计算时间长等，特别是对于 一些 NP 难和 NP 完全问题。为了在求解时间和计算精度上取得平衡，研究学者 提出了各种启发式特征的计算方法。常见的启发式特征算法有禁忌搜索、模拟 退火算法、 进化算法 和群智能等。 本课题主要研究了群智能算法在组合优化计算问题方面的应用。群智能算 法是一种基于群体搜索的随机优化算法，主要有蚁群算法和粒子群优化算法两 种。文章中详细地介绍了蚁群算法和粒子群优化算法的原理、发展及基本流程， 我的工作主要是利用群智能算法在 VC+平台下实现其在连续空间及离散领域 的常见应用，如连续多峰函数极值求解、0-1 背包和典型的旅行商问题(TSP)。 关键词：群智能，蚁群算法，粒子群优化算法，0-1 背包，TSP 全套设计加 153893706 II 全套设计加 153893706 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 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 calculation 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 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 common 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, Particle Swarm Optimization, 0-1 Knapsack, TSP 全套设计加 153893706 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 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 全套设计加 153893706 IV 3.5 参数设置.21 结 论.22 参考文献.23 致 谢.24 附录.25 全套设计加 153893706 1 第一章 引 言 1.1 课题的背景和意义课题的背景和意义 伴随着科学技术的进步，实践生活中遇到的问题越来越复杂，传统的计算 方法在解决这些问题时面临着越来越多的困难，如计算复杂度高、计算时间长 等，尤其是对一些 NP（Nondeterministic Polynomial）难问题，传统算法根本不 能在可以承受的时间内计算出精确的解。 鉴于此种原因，计算机科学家们提出了很多具有启发式特征的计算智能方 法，以期能够平衡求解时间和求解精度。这些方法大多是研究者们受到大自然 的启发而被提出，它们有的是模仿生物界的进化过程，有的是模仿生物的生理 构造和身体机能，也有的是模仿动物的群体行为、或者模仿人类的思维、语言 和记忆过程的特性，更有的是模仿自然界的物理现象，但它们有一个共同点， 都是希望通过模拟大自然和人类的智慧实现对问题的优化求解，以期在可承受 的时间内计算出可接受的解。这些算法共同组成了计算智能优化算法，计算智 能算法具有智能性、并行性、健壮性和很好的自适应性以及很强的全局搜索能 力，因此得到了众多研究者的广泛关注，并且在算法理论和性能方面取得了很 多突破性的进展，被广泛应用于各种领域，在科学研究和生产实践中发挥着中 重要的作用。 人们从生物进化的机理中受到启发， 在 20 世纪 50 年代中期创立了仿 生学，提出了许多用以解决复杂优化问题的新方法，如遗传算法、进化规划、 计划策略等。群智能作为一种新兴的 智能演变 计算技术在 20 世纪 90 年代 被提出，已经成为越来越多 研究者的关注焦点，它与人工生命，特别是进 化策略以及遗传算法有着极为特殊的联系。群智能是指“无智能的 主体通 过合作表现出智能行为的特性 ”，它在没有集中控制且不提供全局模式的 前提下，为复杂的分布式问题求解方案 奠定了基础。目前，群智能领域主 要有两种算法：蚁群算法（ Ant Colony Optimization，ACO）和粒子群优 化算法（ Particle Swarm Optimization，PSO）。前者是对蚂蚁群落 采集食 物过程的模拟，已成功应用于许多离散优化问题。粒子群优化算法也是起源 于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一 种很好的优化工具。 到目前为止 ，群智能方法能够被用于解决大多数优化 问题或者能够转化为优化求解的问题。 全套设计加 153893706 2 1.2 组合优化（组合优化（CO）问题模型）问题模型 ACO 算法是随机搜索程序。它们的主要组件是信息素模型（在后续文章中 会有介绍），这种模型常常被用在概率采样搜索空间。这种模型从一个解决的 组合优化（CO）问题模型派生而出，CO 问题模型定义如下： 一个 CO 问题的模型包含：),(fSP 搜索空间（或解空间）定义在一组离散决策变量的有限集合上，是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 * 果全局最优解决方案就会表示成。这样解决 COSssfsf),()( * S)( * SS 问题是只需要找到一个方案。 * Ss 1.3 群智能算法的特点群智能算法的特点 与大多数基于梯度应用优化方法算法不同，群智能依靠的是概率搜索算法。 虽然概率搜索算法通常要采用较多评价函数，但与梯度算法及传统的演化算法 相比，其优点还是显著的：无集中控制约束，不会因个别个体的故障影响整个 问题的求解，确保了系统具备更强的鲁棒性；以非直接的信息交流方式确保了 系统的扩展性，由于系统中个体的增加而增加的通信开销也较少；并行分布式 算法模型，可充分利用多处理器，这样的分布模式更适合于网络环境下的工作 状态；对问题定义的连续性无特殊要求；系统中每个个体的能力十分简单，每 个个体的执行时间也比较短，并且算法实现简单。 群智能方法易于实现，算法中仅涉及各种基本数学操作，其数据处理过程 对 CPU 和内存的要求也不高。且这种方法只需要目标函数的输出值，而无需其 梯度信息。已完成的群智能理论和应用方法研究证明群智能方法是一种能够有 全套设计加 153893706 3 效解决全局优化问题的新方法。更重要的是，群智能潜在的并行性和分布特点 为处理大连的以数据库方式存在的数据提供了技术保证。无论是从理论研究还 是应用研究的角度分析，群智能理论及应用研究都是具有重要学术意义和现实 价值的。 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 领域渗透到了多个应用领域,由 解决一维静态优化问题发展到解决多维动态组合优化问题,由离散域范围内研究 逐渐拓展到了连续域范围内研究,而且在蚁群算法的硬件实现上取得了突破性进 展。 我国在蚁群算法领域的研究起步较晚，国内最先研究蚁群算法的是东北大 学控制仿真研究中心的张纪会博士与徐心和教授，随后几年里，越来越多的学 者进入了这个领域，并在蚁群算法的改进和应用方面作了大量的工作 1.4.2 粒子群算法研究现状 粒子群算法是由 James Kenney 和 Russell Eberhart 于 1995 年提出。之后， Kennedy 和 Eberhart 在基本粒子群算法的基础上提出了一种离散二进制模型。 到至今的几年时间里，研究者们的大部分精力主要集中于对其算法结构和性能 的改善方面。在应用方面，粒子群算法已被迅速地应用于函数优化、神经网络 训练、模糊系统控制、数据聚类以及原有的一些遗传算法应用领域。并且随着 对其研究的深入，其应用领域正在逐渐扩大。 全套设计加 153893706 4 第二章 蚁群算法（ACO） 4 第二章 蚁群算法（ACO） 2.1 蚁群算法简介蚁群算法简介 2.1.1 基本原理 蚂蚁是大自然中一种常见的群居生物，虽然没有视觉，却能找到由蚁穴到 食物源的最短路径。而且在运动路线上突然出现障碍是，蚂蚁也能够很快的重 新找到新的最优路径。人们经过大量的研究发现，蚂蚁个体间通过一种称之为 信息素（pheromone）的物质进行信息传递，从而能相互协作，完成复杂的任务。 蚂蚁之所以表现出复杂有序的行为，个体之间的信息交流和相互协作起着重要 的作用。 蚂蚁在运动过程中，能够在它所经过的路径上留下信息素，并以此为指导 寻找自己的运动方向。蚂蚁倾向于朝着信息素强度高的方向移动。于是，随着 蚂蚁群体的不断选择，蚁群的集体行为便表现出一种信息正反馈现象：某一路 径上走过的蚂蚁越多，则后者选择该路径的概率越大。蚂蚁个体之间就是通过 这种信息的交流达到搜索食物的目的。 如下图所示： 路径二 路径一 蚁穴 图 2-1 蚂蚁通过不等长双支桥的实验 实验最初，两条路径上都没有信息素，蚂蚁选择两条路径的概率相等。但 由于路径二较短，耗费时间也较少，随着蚂蚁在食物源和蚁穴之间的不断移动， 食物 第二章 蚁群算法（ACO） 5 路径二上的信息素量越来越大，两条路径上的信息素量差距越来越大，导致蚁 穴中越来越多的同伴选择路径二。正式由于路径二比路径一短，因此，在相同 的时间区间内，短的路线会有更多的机会被选择。 蚁群算法是一种随机概率搜索算法，与其他模型进化算法一样，通过候选 解组成的群体的进化过程来寻求最优解。该过程包含两个阶段，适应阶段和协 作阶段。在适应阶段，各候选解根据积累的信息不断调整自身机构；在协作阶 段，候选解之间通过信息交流，以期产生性能更好的解。 作为与遗传算法同属一类的通用型随机优化算法，蚁群算法不需要任何先 验知识，最初只是随机地选择搜索路径，随着对解空间的“了解”，搜索变得 有规律，并逐渐逼近直至最终达到全局最优解。蚁群算法对搜索空间的“了解” 机制主要包括三个方面： （1）蚂蚁的记忆。一只蚂蚁搜索过的路径在下次搜索时就不会再被选择， 由此在蚁群算法中建立禁忌列表来进行模拟。 （2）蚂蚁利用信息素进行相互通信。当同伴进行路径选择是，会根据路径 上的信息素进行选择，这样信息素就会成为蚂蚁之间进行通信的媒介。 （3）蚂蚁的集群行动。通过一只蚂蚁的运动很难到达食物源，但整个蚁群 进行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，在路径上留下的 信息素数量就会越来越多，导致信息素强度增大，蚂蚁选择该路径的概率就会 随之增加，从而进一步增加该路径的信息素强度，而某些路径上通过的蚂蚁较 少时，路径上的信息素就会随时间的推移而蒸发。一次，模拟这种现象即可利 用群体智能建立路径选择机制，使蚁群算法的搜索向最优解推进。 2.2 蚁群算法模型蚁群算法模型 2.2.1 蚁群算法基本流程 以旅行商问题（TSP）为例，说明算法的基本流程。 旅行商问题是指一位商人从一个城市出发，周游 N 个城市最后返回远程是 问题。图论描述为：给定图，其中是顶点集，为各顶点相互连接),(AVG VA 组成的边集，已知各顶点之间的距离（或坐标），要求确定一条长度最短的哈 密顿回路。 第二章 蚁群算法（ACO） 6 这个 NP 难 CO 问题能够如下建立模型：我们为每一个城市用决策变Vi 量表示，域值包含每个传出边的域值。一个变量实例化意味着 j i X j i a j i v j i j i vX 边是对应解决方案的一部分。为了保证在图中只有对应哈密顿回路的候选 j i aG 解决方案是有效的解决方案，还必须要定义约束集。解决方案组件包含了一 个合并了变量及域值的组件和包含关联到信息素线索参数及其值 j i X j i v j i c j i c j i T 的信息素模型。 j i T 简单的蚁群算法的流程如图 2-2 所示： （1）初始化（Initialization）。初始化蚁群及相关参数 （2）构建解（ConstructSolution）。每只蚂蚁通过对解空间的不断搜索， 构建出一条可行解； （3）判断是否达到终止条件，满足，则退出，否则进行信息素更新，然后 回到步骤（2） 图 2-2 蚁群算法流程图 2.2.2 一个基本 ACO 算法框架 蚁群算法的框架如下。在每一次迭代中，个蚂蚁按照一个给定的信息素 a n 模型以概率构建要解决的组合优化问题的解决方案。然后，选择一个本地搜索 程序应用于构建解决方案。最后，在下一次迭代开始时，一些解决方案进行信 息素更新。 第二章 蚁群算法（ACO） 7 基本 ACO 算法的框架伪代码如下： Input: An instance of a CO problem model .P),(fSP InitializePheromoneValues() /初始化参数T NULL bs s while termination conditions not met do iter for j = 1, . . . , do a n ConstructSolution() /解的构建sT if is a valid solution thens LocalSearch( ) optional /局部搜索ss if (f ( ) f() or (= NULL) then s bs s bs s bs ss iter s iter end if end for ApplyPheromoneUpdate(, ,) /信息素更新 T iter bs s end while output: The best-so-far solution bs s 初始化信息素值（）。在算法开始时，初始化信息素值为一个大于 0 常T 数 。c 解的构建（）。任何一个 ACO 算法的基本成分是概率构建方案的建设性T 启发式。一个建设性启发式从解决方案的有限集合中选取解决方案组成元素 序列。解决方案以一个空的局部方案为开始。然后在每一步构建中，从 p s 集合选取可行组件扩展当前的局部方案。在每一步构建中，)( pp ss p s 这个集合由满足问题约束条件的解决方案构建机制决定。解决方案的构建过程 可以认为是一个称作构造图的走道（或路线），构造图是一个完全),( C G 连接图，每一条边都是的解决方案组件，每一个顶点都是的元素。中的 C G 可行路线由定义了局部解决方案的集合的解决方案构建机制间接定义。 p s)( p s 在每一步构建中，解决方案组件的选择是按照信息素模型以概率进)( pj i sc 行的。选择的概率与成比例，在这里是分配给每一个有效的 j i c )( j i j i c 解决方案组件的函数（可能依赖于现有的构建步骤），它的启发式值也称作启 发式信息。参数和的值满足，决定了信息素值和启发式信息的0, 0 相对重要性。启发式信息是可选的，但往往能够实现算法的高性能。在大部 第二章 蚁群算法（ACO） 8 分的 ACO 算法中，选择下一个解决方案的概率（也称作转移概率）定义如下： （2-1） )(, )( )( )( )( pj i sc l k l k j i j ipj i sc c c scp pl k 值得注意的是转移概率有不同的选择方式。上面的形式主要有历史的原因， 因为它在论文中被提出使用在第一个 ACO 算法。在本文的以下部分，我们假 定如果并且 不是一个有效的解决方案，解的构建过程就会终止。)( p ss 作为这个方面构建的例子，我们重新考虑 ATSP 问题。用表示当前变量I 的指数集和给定值的决策变量的集合。用表示当前决策变量的下标（例如， c i 在当前构建过程中已经指定值的决策变量）。解决方案的构建开始时设定空的 局部解决方案，随机选取，。并且，将第一个 p s|, 2 , 1Vic c iI 决策变量的下标赋值给（）。然后，在|-1 步解的构建的每一步中， f i cf ii V 将从中选取一个解决方案组件添加到当前局部方案。这就意味着在解)( p s j i c 的构建每一步中，都会选取一个域值赋值给下标为的决策变量。一旦解决方 c i 案组件被添加到中，就将赋给。在 ATSP 问题中，每一步解的构建开 c i c p s c ij 始时使用方程 1 计算转移概率，其中（这种做法对短边会产生偏差） j i j i dc/1)( 。在最后一步解的构建时，将解决方案组件添加到局部方案中，构成哈密 f c i i c p s 顿回路。 局部搜索（ ）一个局部搜索程序可以通过蚂蚁应用在改善解的构建性能s 上。尽管实验已经观察到这个局部程序的使用能够改善算法的整体性能，但这 个程序只是可选的，而非必须的。 信息素更新。信息素更新规则的目的是增加已经选定的高校解决方案组件 的信息素值。大部分 ACO 算法遵循以下的信息素更新规则： （2-2） | )()1 ( scsupd j i j i j iupd sF 其中。更新规则的实例由不同的规格得| , 2 , 1;, 2 , 1 i Djni iter 到。在本文中的所有情况下，是的一个子集，其中是当前 iter bsiter s iter 迭代中构建的解的集合，是目前最好的解决方案。参数称作信息素 bs s 1 , 0( 蒸发率。它具有统一降低信息素值的功能。信息素蒸发的使用是为了避免算法 第二章 蚁群算法（ACO） 9 过快的收敛向次优区域。它实现了一个遗忘的有效形式，有利于在搜索空间中 探索新的区域。 2.3 蚁群算法应用举例蚁群算法应用举例 2.3.1 离散领域 旅行商问题（TSP）是蚁群算法首先应用于实际解决的组合优化问题，是 一个典型的 NP 问题。 首先研究给定 4 个城市坐标点的旅行商问题，城市坐标点为（37,52）， （49,49），（52，64），（20, 26），找出最短路径。 建模过程： 由坐标点可知城市距离矩阵为 503731 501519 371512 311912 （1）初始化相关参数 令城市数量，蚂蚁数量，信息素蒸发率，最大4NCity20NAnt5 . 0 迭代次数，信息素权重，启发式权重：2000NcMax 5 . 1 ，构建城市之间距离矩阵，信息素矩阵，为一个0 . 2 ij d1 ij d 0 ij0 正数，一般设为 1.0。迭代次数0k （2）解的构建 a.将蚂蚁的记忆清空，即对所有蚂蚁来说所有的城市都设置为未访问，禁 忌表为空。 b.随机分配每只蚂蚁到一个初始城市。 c.每只蚂蚁构建一条路径，每只蚂蚁的城市选择规则为 （2-3） 否则 为可以选择的城市编号 0 j P k alloweds isis ijij k ij 第二章 蚁群算法（ACO） 10 每只蚂蚁按照轮盘赌算法选择下一个访问的城市。最后蚂蚁返回初始城市， 并计算蚂蚁构建的路径长度。 d.信息素更新 每次迭代后的都要进行信息素更新，更新规则如下： ， （2-4） ij k ij k ij 1 )1 ( NAnt n n ijij 1 （2-5） 否则 过路径只蚂蚁在本次循环中经若第 0 j)(i,nLQ nn ij （3）程序终止判定 令。若达到最大迭代次数，则退出程序，输出最后解；反之，则1 kk 返回步骤（2）。 算法运算结果为 23142，整个路径长度为 102 本文重点研究了模拟 20 个城市坐标点的 TSP，城市坐标点为：（37,52）， （49,49），（52，64），（20, 26），（40, 30），（21, 47），（17, 63）， （31,62），（52,33），（51,21），（42,41），（31,32），（5,25）， （12,42），（36,16），（52,41），（27,23），（17,33），（13,13）， （57,58） （1）初始化相关参数 令城市数量，蚂蚁数量，信息素蒸发率，最大20NCity50NAnt5 . 0 迭代次数，信息素权重，启发式权重：2000NcMax 5 . 1 ，构建城市之间距离矩阵，信息素矩阵，为一个0 . 2 ij d1 ij d 0 ij0 正数，一般设为 1.0。迭代次数0k （2）解的构建 a.将蚂蚁的记忆清空，即对所有蚂蚁来说所有的城市都设置为未访问，禁 忌表为空。 b.随机分配每只蚂蚁到一个初始城市。 c.每只蚂蚁构建一条路径，每只蚂蚁按公式（2-3）的规则选择城市，每只 蚂蚁按照轮盘赌算法选择下一个访问的城市。最后蚂蚁返回初始城市，并计算 蚂蚁构建的路径长度。 第二章 蚁群算法（ACO） 11 d.信息素更新 每次迭代后的都要进行信息素更新， 更新规则同公式（ 2-4）、（2- 5）。 （3）程序终止判定 令。若达到最大迭代次数，则退出程序，输出最后解；反之，则1 kk 返回步骤（2）。 程序运行结果如下： 图 2-2 旅行商问题运算结果 从图中可以看到算法在不断地迭代更新中，路径长度不断在变，并且多次 的运算结果最优值为 243。 24 其他应用其他应用 蚁群优化算法（ACO）自 1991 年 Dorigo 提出并应用于 TSP 问题以来，已 经发展了 20 余年。由于其鲁棒性强、全局搜索、并行分布式计算、易与其他方 法结合等优点，近年来 ACO 的应用领域不断扩张，如车间调度问题（Job-Shop Scheduling Problem，JSP）、车辆路径问题（Vehicle Routing Problem ，VRP）、 第二章 蚁群算法（ACO） 12 分配问题（Assignment Problem，AP）、子集问题（Sub-Set Problem，SSP）、 网络路由问题（Network Routing Problem，NRP）等。 25 参数设置参数设置 以下参数为基本的 AS 算法的主要常用参数，其他改进型蚁群算法涉及到 的其他参数设置本文不做讨论。 蚁群规模（蚂蚁数量）：一般根据问题规模设定，在 TSP 问题中可设定为 同城市数目相同为宜，也可以稍微多一些。在 ACS 算法中，一般设为 10.。 信息数权重：值越小，最邻近城市被选中概率越大，一般可设为。1 启发式信息权重：值越小，蚂蚁越倾向于根据信息素浓度确定路径，算 法收敛越快，但过小时会导致最短路径与实际目标差距较大，一般设置为 为宜。52 信息素蒸发率：关系到算法的全局搜索能力和收敛速度。值较大时从未 被选择过的便上的信息素浓度快速减少接近于 0，降低算法的全局搜索能力； 值越小时，算法具有较好的全局搜索能力，但各路径上信息素差距拉大慢，算 法收敛慢。一般在 AS 中，设置为；在 ACS 中，设置为5 . 01 . 0 初始化信息素：值太小时，未被选择的边上信息素太少，蚂蚁会很快集 0 中到一条局部最优路径上，与最优值有较大差异；值太大时，算法收敛过慢， 一般可设为。1 0 终止条件：一般设定为迭代次数，如 200,1000,2000,5000 等。 第二章 蚁群算法（ACO） 13 第三章 粒子群优化算法（PSO） 13 第三章 粒子群优化算法（PSO） 3.1 粒子群优化算法简介粒子群优化算法简介 3.1.1 基本原理 在自然界鸟群捕食的过程中，捕食的鸟群都是通过各自的探索与群体的合 作最终发现食物所在的位置。每个个体的行为不但会受到自己过去的经验和认 识影响，同时也受到整体社会行为的影响。一群分散的鸟随机地飞行觅食，各 个小鸟在飞行的过程中不断的记录和更新它曾经到达的距离食物的最近位置， 同时，它们通过信息交流的方式比较大家所找到的最好的位置，得到一个当前 群体已经找到的最佳位置。这样，每个小鸟在飞行的时候有了一个指导的方向， 它们会结合自身的经验和整个群体聚集到食物位置。 PSO 算法就是从这种模型中得到启示而产生的，并用于求解组合优化问题。 在 PSO 算法中，每一个粒子在搜索空间中各自有其方向和速度，并且根据自身 过去的经验与群体行为进行概率搜索策略的调整。整体求解思想为：让一群成 为粒子（particle）的鸟在问题的搜索空间中飞翔，最优解被理解为食物所在的 位置，每个粒子都有各自的速度和位置，由问题定义的适应函数确定粒子的适 应值，然后不断迭代，由粒子本身的历史最优解和群体的全局最优解来影响粒 子的速度和位置，让粒子在搜索空间中探索，最后找到全局最优解。 3.2 粒子群优化算法基本流程粒子群优化算法基本流程 粒子群优化算法（PSO）要求每个个体（粒子）在更行的过程中维护两个 变量：速度变量和位置向量，其中, 21n iiii vvvv, 21n iiii xxxx 表示粒子编号，表示粒子数量，表示求解问题的维数。粒子的Ni, 2 , 1Nn 速度决定了其运动的方向和速率，而位置则体现了粒子所代表的解在解空间中 的位置，是评估该解质量的基础。算法同时还要求每个粒子各自维护一个自身 的历史最优位置变量 。在迭代过程中，如果粒子到达了某个使得适应值 i pBest 更好的位置，则将该位置向量替代原来的历史最优向量，如果粒子能够不断找 到更优的位置，历史最有变量将会不断进行更新。另外，粒子群体还要维护一 个全局最优位置向量，代表所有粒子的中最优的位置向量，这个全gBest i pBest 局最优向量起到引导粒子向该全局最优区域收敛的作用。 第三章 粒子群优化算法（PSO） 14 PSO 算法步骤如下： （1）初始化所有粒子。初始化所有粒子的位置变量和速度变量，并将 i x i v 当前位置作为历史最优变量，群体中最有个体位置作为全局最优位置变 i pBest 量。gBest （2）在每一代的进化中，计算每个粒子的适应度函数值。 （3）如果粒子当前的适应度函数值比历史最优值好，那么历史最有位置将 会被当前位置替代。 （4）如果粒子的历史最优位置比全局最优位置好，那么全局最优将会被粒 子的历史最优替代。 （5）对每个粒子 的第维的速度和位置分别按照公式（3.1）和（3.2）进ik 行更新。粒子的速度和位置更新如图 3-1 图 3-1 粒子速度和位置更新示意图 （3.1）)()( 2211 1k i kkk i k i kk i k i xgBestrandcxpBestrandcvv （3.2） k i k i k i vxx 1 其中,，为惯量权重；和是加速系数；和Ni, 2 , 1nk, 2 , 1 1 c 2 c 1 rand 是两个区间上的随机数，每次更新时均会使用新的随机数。需要注意 2 rand 1 , 0 的是，在更新过程中，PSO 要求采用一个由用户设定的最大速度和最小速 max V 度来限制速度的范围，在位置更行时还要注意更新后的位置要保证处在问 min V 题空间中，否则必须进行修正，一般可以是重新随机设定或限定在边界上。 （6）如果还没有达到结束条件，转到（2），否则输出结束。gBest PSO 的流程图如下： 第三章 粒子群优化算法（PSO） 15 图 3-2 PSO 的流程图 PSO 的伪代码为： procedure PSO for each particle i Initialize velocity and position for particle ViXi i Evaluate particle and set =ipBestXi end for =min 或 =maxgBestpBestgBestpBest while not stop for =1 to Ni Update the velocity and position of particle i Evaluate particle i if fit(Xi)fit()pBest =Xi;pBest if fit()fit()pBestgBest =；gBestpBest 第三章 粒子群优化算法（PSO） 16 end for end while print gBest end procedure 3.3 粒子群优化算法应用实例粒子群优化算法应用实例 3.3.1 连续多峰函数极值应用 实例一：利用基本粒子群算法求解函数在区间上的 x exy 3cos140 ， 最大值。 建模过程如下： （1）确定参数值 确定粒子群数目，学习因子和，惯量权重，最大进化代数，令N 1 c 2 cG 进化代数。令，0k2N0 . 2 21 cc5 . 030G （2）初始化变量。初始化粒子的初始位置和速度，可以利用随机数取点， 也可以认为设定点。 （3）计算粒子的适应值，并获取历史最优和全局最优位置。适应度函数即 为目标函数 x exy 3cos1 （4）更新粒子群位置和速度。 )()( 2211 1k i kkk i k i kk i k i xgBestrandcxpBestrandcvv k i k i k i vxx 1 令，转向步骤（3）。1 kk 粒子更新示意图如下： 第三章 粒子群优化算法（PSO） 17 图 3-3 一维函数中第 30 次迭代粒子群更新 从图中可以看出，每一次迭代过程，粒子都会更多的想最优值点不断靠近， 直到无限接近最优值点。 运算结果为： 图 3-4 算法运行结果 实例二，求解函数的最小值。10,10,10,10,),( 22 yxyxyxf （1）确定参数值 确定粒子群数目，学习因子和，惯量权重，最大进化代数，令N 1 c 2 cG 进化代数。令，0k2N0 . 2 21 cc5 . 030G （2）初始化变量。初始化粒子的初始位置和速度，可以利用随机数取点， 也可以认为设定点。 （3）计算粒子的适应值，并获取历史最优和全局最优位置。适应度函数即 第三章 粒子群优化算法（PSO） 18 为目标函数 ,),( 22 yxyxf （4）更新粒子群位置和速度。 )()( 2211 1k i kkk i k i kk i k i xgBestrandcxpBestrandcvv k i k i k i vxx 1 令，转向步骤（3） 。1 kk 运算结果如下： 图 3-5 函数运行结果 这与实际点（0,0）的结果相