数值分析方法 课件 8.5 粒子群算法

数值分析方法主编

李冬果李林高磊首都医科大学生物医学工程学院智能医学工程学学系面向“四新”人才培养普通高等教育系列教材第八章智能优化算法基础第一节最优化问题和随机算法第二节禁忌搜索算法第三节模拟退火方法第四节遗传算法第五节粒子群算法

目录/Contents

8.5粒子群算法在多维连续空间中搜索最优解是一个非常困难的过程，粒子群算法（particleswarmoptimization,PSO）通过模拟一组粒子的初始状态，通过群内粒子彼此间的信息共享，不断迭代的向最优解移动来获取优化问题的最优解。粒子群算法最早在1995年由Eberhart和Kennedy提出，由于其算法简明，易于实现，已经在科学计算和工程领域得到了广泛的研究和应用。5.1算法原理粒子群算法的灵感来自于对鸟类捕食行为的模拟。假设一群鸟要在一片区域中搜索唯一的食物来源，每只鸟都不知道食物所在位置，但却能知道当前位置与食物的距离。如果这些鸟能够彼此通讯，那么最优的搜索策略是，所有的鸟都基于自己搜索的经验，向离食物最近的鸟附近去做进一步搜索。粒子群算法假设，优化问题的全局最优解就是鸟类所追寻的食物所在位置，而每一只鸟（或者称为粒子）的位置都可以代表着搜索空间中的一个潜在最优解。所有粒子位置都对应一个由被优化函数决定的适应值，除此之外，粒子还有一个速度代表着它的飞行方向和速率。在优化过程中，首先通过随机初始化每个粒子的位置和速度，然后通过迭代算法，求得每个粒子的个体极值，和所有粒子的全局极值。随后，每个粒子都根据代表自身经验的个体极值，和代表群体经验的全局极值来调整自己的搜索策略，更新下一步的位置和速度。当这个过程不断迭代进行，粒子群将越来越接近全局最优解。5.2算法设计

5.3算法实现粒子群算法的实现步骤如下：步骤1

确定粒子群规模，适应度函数，随机初始化每个粒子的初始位置和速度；步骤2

为每个粒子计算适应度；步骤3

更新每个微粒的个体最优位置以及粒子群的全局最优位置；步骤4

根据粒子群迭代公式，计算每个粒子的新位置和新速度；步骤5

如果达到停止条件，则输出当前的全局最优位置，否则返回步骤2，开始下一次循环。

（2）邻域拓扑结构。在基本粒子群优化算法迭代公式中，“社会部分”是通过比较粒子位置与全局最优位置来得到的，这里也可以将全局最优位置替换为“局部最优”位置，即通过粒子位置与其邻域内最优位置进行比较来迭代更新粒子的运动速度。因此可以通过定义粒子的“邻域”来修正迭代公式。常见的邻域拓扑结构包括：星型结构，即每个粒子的邻域是整个粒子群，迭代过程受全局最优值的影响；环形结构，即每个粒子只受与其最接近的两个近邻粒子的影响；齿形结构，需要先定义一个中心粒子，在每次迭代中，中心粒子向全局最优方向移动，而其他粒子则通过中心粒子的位置计算迭代公式中的“社会部分”。目前的研究显示，星型结构算法收敛快，但容易陷入局部最优，环形结构收敛慢，但更可能找到全局最优。

（4）收敛性问题。粒子群优化算法的收敛性问题是其理论研究中的热点问题，由于粒子群算法中包含有随机因子，是一个随机系统，其收敛问题的研究困难很大。目前的一些研究显