第五章-粒子群算法

1、第五章 粒子群算法 1. 粒子群算法发展历史简介粒子群算法发展历史简介粒子群算法粒子群算法 由由Kennedy和和Eberhart于于1995年提出年提出该算法是模拟鸟群飞行觅食过程中，通过个体之间的协作，最终达到群体最优目的的行为 已成为现代优化方法领域研究的热点已成为现代优化方法领域研究的热点 其天然的实数编码特点其天然的实数编码特点, 使其尤其适合于处理使其尤其适合于处理 设置参数少设置参数少 简单易行简单易行 收敛速度快收敛速度快 实优化问题实优化问题 2. 粒子群粒子群算法的基本思想算法的基本思想 马良教授在他的著作马良教授在他的著作蚁群优化算法蚁群优化算法一书的一书的 粒子群算法的

2、思想源于对鸟群捕食行为的研究粒子群算法的思想源于对鸟群捕食行为的研究 前言中写到：前言中写到： “自然界的蚁群、鸟群、鱼群、羊群、自然界的蚁群、鸟群、鱼群、羊群、牛群、蜂群等，其实时时刻刻都在给予我们牛群、蜂群等，其实时时刻刻都在给予我们以某种启示，只不过我们常常忽略了大自然以某种启示，只不过我们常常忽略了大自然对我们的最大恩赐！对我们的最大恩赐！ ” 2. 粒子群粒子群算法的基本思想算法的基本思想 粒子群算法的思想源于对鸟群捕食行为的研究粒子群算法的思想源于对鸟群捕食行为的研究 PSO的基础的基础: 一群鸟在某区域随机搜寻食物。该区域只有一片食物，一群鸟在某区域随机搜寻食物。该区域只有一片食

3、物，所有的鸟都不知道食物的具体位置，但它们知道自己和所有的鸟都不知道食物的具体位置，但它们知道自己和其它鸟相比谁距离食物更近。其它鸟相比谁距离食物更近。 那么每只鸟想要以最快的速度找到这片食物的话，那么每只鸟想要以最快的速度找到这片食物的话，就是要找寻比自己离食物更近的鸟，并且依照它的位置就是要找寻比自己离食物更近的鸟，并且依照它的位置更新自己的位置，然后根据自己飞行的经验判断食物的更新自己的位置，然后根据自己飞行的经验判断食物的所在。所在。 最终，群体中每一只鸟都找到这片食物。最终，群体中每一只鸟都找到这片食物。 一群鸟在寻找食物的过程中，飞行习惯默认遵循以下规则： 1）避免与相邻的鸟发生碰

4、撞冲突； 2）尽量与自己周围的鸟在速度上保持协调和一致； 3）尽量试图向自己所认为的最优群体靠近。 即粒子寻找目标解的过程中保持三条准则; 1）保持自身惯性Vi； 2）按自身的最优位置(pbest-区域最优解)来改变状态； 3）按群体的最优位置(gbest-全局最优解)来改变状态。 依照这三条准则更改自己的位置，不久就可以找到食物了PSO正是从这种模型中得到了启发正是从这种模型中得到了启发 信息的社会共享信息的社会共享 搜索空间的鸟所在的位置搜索空间的鸟所在的位置 位置位置 粒子的参数粒子的参数 目标函数值目标函数值 Kennedy和和Eberhart在上述关于动物的群体行为在上述关于动物的群

5、体行为研究的基础上，给出了粒子群优化算法研究的基础上，给出了粒子群优化算法 在在PSO中，中，优化问题的解优化问题的解 “粒子粒子” 粒子的适应值粒子的适应值 速度速度 一个是粒子个体本身所找到的历史最优解一个是粒子个体本身所找到的历史最优解 另一个是群体内其他粒子的历史最优解另一个是群体内其他粒子的历史最优解 粒子通过跟踪两个粒子通过跟踪两个“极值极值”来进行位置的变化来进行位置的变化. 优优化化问问题题的的解解 12(,)iiiinvvvv12(,)iiiinxxxx位置位置 粒子的参数粒子的参数 速度速度 粒子个体本身历史最优解粒子个体本身历史最优解 群体历史最优解群体历史最优解 粒子通

6、过跟踪两个粒子通过跟踪两个“极值极值”来进行位置的变化来进行位置的变化. 12(,)iiiinvvvv12(,)iiiinpppP粒子的速度和位置更新公式：粒子的速度和位置更新公式： 12(,)ggggnpppP1012()()kkkkgkcccvvpxpx11kkkxxv 惯性因子惯性因子 学习因子学习因子 随机数随机数 0c12,c c, 12(,)iiiinxxxx3. 粒子群粒子群算法算法流程流程 3. 粒子群粒子群算法算法流程流程 第第2步步 计算每个粒子的适应值计算每个粒子的适应值 11kkkxxv1012()(),kkkkgkcccvvpxpx第第1步步 在初始化范围内，对粒子群

7、进行随机初始化在初始化范围内，对粒子群进行随机初始化，第第5步步 更新粒子的速度和位置，公式如下更新粒子的速度和位置，公式如下 第第3步步 更新粒子个体的历史最优位置更新粒子个体的历史最优位置 第第6步步 若未达到终止条件，则转第若未达到终止条件，则转第2步步 包括随机位置和速度包括随机位置和速度 第第4步步 更新粒子群体的历史最优位置更新粒子群体的历史最优位置 4. 粒子群粒子群算法的算法的构成要素构成要素 (1) 群体大小群体大小 m mV(3) 最大速度最大速度 (4) 邻域的拓扑结构邻域的拓扑结构 (5) 停止准则停止准则 (6) 粒子空间的初始化粒子空间的初始化 (2) 权重因子：惯

8、性因子权重因子：惯性因子 、学习因子、学习因子 和和 0c1c2c4. 粒子群算法的构成要素粒子群算法的构成要素 (1) 群体大小群体大小 m m 是一个整型参数是一个整型参数 m 很小很小: m 很大很大: 当群体数目增长至一定水平时，再增长将当群体数目增长至一定水平时，再增长将不再有显不再有显 但收敛速度慢但收敛速度慢著的作用著的作用陷入局优的可能性很大陷入局优的可能性很大 PSO的优化能力很好，的优化能力很好，4. 粒子群粒子群算法的算法的构成要素构成要素 (2) 权重因子：惯性因子权重因子：惯性因子 、学习因子、学习因子 和和 0c1c2c失去对粒子本身失去对粒子本身的的速度的记忆速度

9、的记忆 01c 社会经验部分社会经验部分 前次迭代中自身的速度前次迭代中自身的速度 自我认知部分自我认知部分 1012()(),kkkkgkcccvvpxpx基本粒子群算法基本粒子群算法 001c粒子的速度更新主要由三部分组成：粒子的速度更新主要由三部分组成： 惯性因子惯性因子 0c00c 取值范围取值范围 0kc v1()kkcpx2()gkcpx5. 粒子群粒子群算法的算法的构成要素构成要素 (2) 权重因子：惯性因子权重因子：惯性因子 、学习因子、学习因子 和和 0c1c2c社会经验部分社会经验部分 前次迭代中自身的速度前次迭代中自身的速度 自我认知部分自我认知部分 1012()(),k

10、kkkgkcccvvpxpx“只有社会，没有自我只有社会，没有自我” 学习因子学习因子 1c粒子的速度更新主要由三部分组成：粒子的速度更新主要由三部分组成： 10c 无私型粒子群算法无私型粒子群算法 104c取值范围取值范围 迅速丧失群体多样性，迅速丧失群体多样性，易陷入局优而无法跳出易陷入局优而无法跳出0kc v1()kkcpx2()gkcpx5. 粒子群粒子群算法的算法的构成要素构成要素 (2) 权重因子：惯性因子权重因子：惯性因子 、学习因子、学习因子 和和 0c1c2c社会经验部分社会经验部分 前次迭代中自身的速度前次迭代中自身的速度 自我认知部分自我认知部分 1012()(),kkk

11、kgkcccvvpxpx粒子的速度更新主要由三部分组成：粒子的速度更新主要由三部分组成： “只有自我，没有社会只有自我，没有社会” 学习因子学习因子 2c20c 自我认知型粒子群算法自我认知型粒子群算法 2104cc取值范围取值范围 完全没有信息的社会共享，完全没有信息的社会共享，导致算法收敛速度缓慢导致算法收敛速度缓慢 0kc v1()kkcpx2()gkcpx5. 粒子群粒子群算法的算法的构成要素构成要素 (2) 权重因子：惯性因子权重因子：惯性因子 、学习因子、学习因子 和和 0c1c2c 完全型粒子群算法更容易保持收敛速度和搜索效完全型粒子群算法更容易保持收敛速度和搜索效果的均衡，是较

12、好的选择果的均衡，是较好的选择 社会经验部分社会经验部分 前次迭代中自身的速度前次迭代中自身的速度 自我认知部分自我认知部分 1012()(),kkkkgkcccvvpxpx称为完全型粒子群算法称为完全型粒子群算法 都不为都不为0 0，这时，这时 12,c c粒子的速度更新主要由三部分组成：粒子的速度更新主要由三部分组成： 0kc v1()kkcpx2()gkcpx4. 粒子群粒子群算法的算法的构成要素构成要素 mV(3) 最大速度最大速度 但但 在于维护算法的探索能力与开发能力的平衡在于维护算法的探索能力与开发能力的平衡 较大时，探索能力增强，较大时，探索能力增强， mV作用作用: 较小时，

13、开发能力增强，较小时，开发能力增强， mVmV一般设为每维变量变化范围的一般设为每维变量变化范围的1020. 但但 粒子容易飞过最优解粒子容易飞过最优解 容易陷入局部最优容易陷入局部最优 4. 粒子群粒子群算法的算法的构成要素构成要素 (4) 邻域的拓扑结构邻域的拓扑结构 全局粒子群算法和局部粒子群算法全局粒子群算法和局部粒子群算法 gp粒子群算法的邻域拓扑结构包括两种，粒子群算法的邻域拓扑结构包括两种，一种是将群体内所有个体都作为粒子的邻域一种是将群体内所有个体都作为粒子的邻域，另一种是只将群体中的部分个体作为粒子的邻域另一种是只将群体中的部分个体作为粒子的邻域 群体历史最优位置群体历史最优

14、位置 邻域拓扑结构邻域拓扑结构决定决定 由此，将粒子群算法分为由此，将粒子群算法分为4. 粒子群粒子群算法的算法的构成要素构成要素 (5) 停止准则停止准则 停止准则一般有如下两种：停止准则一般有如下两种： 最大迭代步数最大迭代步数 可接受的满意解可接受的满意解 (6) 粒子空间的初始化粒子空间的初始化 4. 粒子群粒子群算法的算法的构成要素构成要素 较好地选择粒子的初始化空间，将大大缩短收较好地选择粒子的初始化空间，将大大缩短收敛时间初始化空间根据具体问题的不同而不同，敛时间初始化空间根据具体问题的不同而不同，也就是说，这是问题依赖的也就是说，这是问题依赖的 从上面的介绍可以看到，粒子群算法

15、与其他现代从上面的介绍可以看到，粒子群算法与其他现代优化方法相比的一个明显特色就是所需调整的优化方法相比的一个明显特色就是所需调整的参数很参数很少少相对来说，相对来说，惯性因子惯性因子和和邻域定义邻域定义较为重要这些较为重要这些为数不多的关键参数的设置却对算法的精度和效率有为数不多的关键参数的设置却对算法的精度和效率有着显著影响着显著影响5. 粒子群粒子群算法示例算法示例 例例 求解如下四维求解如下四维Rosenbrock函数的优化问题函数的优化问题 322211min( )100()(1) iiiifxxxx种群大小：种群大小： 30,30 (1,2,3,4)ixi 解解 算法的相关设计分析

16、如下算法的相关设计分析如下 编码：因为问题的维数是编码：因为问题的维数是4，所以每个粒子的位置和，所以每个粒子的位置和 max60V即算法中粒子的数量，取即算法中粒子的数量，取 5m 速度均速度均4 维的实数向量维的实数向量设定粒子的最大速度设定粒子的最大速度： 初始位置：初始位置： 0ix设各粒子的初始位置设各粒子的初始位置 和初始速度和初始速度 为：为： 0iv对粒子群进行随机初始化对粒子群进行随机初始化 包括随机初始化各粒子的包括随机初始化各粒子的位置位置和和速度速度 (0)121.721, 9.13677, 6.62244, 3.84079x(0)329.6563, 0.871811,

17、 27.8912, 17.7425 x(0)2 13.5001, 23.6131, 17.4462, 29.0515 x(0)528.0992, 22.6482, 0.675616, 8.43752 x(0)423.6218, 16.4885, 22.7019, 25.4033x初始速度：初始速度： 0ix设各粒子的初始位置设各粒子的初始位置 和初始速度和初始速度 为：为： 0iv对粒子群进行随机初始化对粒子群进行随机初始化 包括随机初始化各粒子的位置和速度包括随机初始化各粒子的位置和速度 (0)1 19.9048, 29.562, 22.104, 5.45346 v(0)37.83576,

18、55.7173, 40.9177, 28.255 v(0)220.5922, 28.6944, 26.3216, 19.0615 v(0)517.561, 13.5365, 51.2722, 56.098v(0)4 11.6373, 41.0138, 17.7311, 14.87 v初始速度：初始速度： (0)(0)(0)(0)(0)12345,vvvvv初始位置：初始位置： (0)(0)(0)(0)(0)12345,xxxxx(0)71()2.38817 10fx计算每个粒子的适应值计算每个粒子的适应值 (0)72()4.45306 10fx322211( )100()(1) iiiifxx

19、xx按照按照 计算适应值计算适应值 (0)1gpx(0)75()8.50674 10fx(0)74()6.56888 10fx(0)83()1.35376 10fx历史最优解历史最优解0, (1,2,3,4,5)iiipx更新粒子的速度和位置：更新粒子的速度和位置： 122cc01c 取取 ， , 得到速度和位置的更新函数为得到速度和位置的更新函数为 初始速度：初始速度： (0)(0)(0)(0)(0)12345,vvvvv初始位置：初始位置： (0)(0)(0)(0)(0)12345,xxxxx群体历史最优解：群体历史最优解： (0)1gpx0, (1,2,3,4,5)iiipx个体历史最优

20、解：个体历史最优解： 12 ()2 (),kkkkgkvvpxpx11kkkxxv(1)1 19.9048, 29.562, 22.104, 5.45346 v(1)240.0498, 3.76972, 44.9573, 75.6939v更新速度，得：更新速度，得：(1)314.8665, 59.3694, 25.667, 22.1122v初始速度：初始速度： (0)(0)(0)(0)(0)12345,vvvvv初始位置：初始位置： (0)(0)(0)(0)(0)12345,xxxxx群体历史最优解：群体历史最优解： (0)1gpx0, (1,2,3,4,5)iiipx个体历史最优解：个体历史

21、最优解： (1)4 13.843, 32.4824, 51.7604, 39.892 v(1)595.9018, 63.5174, 60.6234, 36.7907v6060606012 ()2 (),kkkkgkvvpxpx(1)11.81621, 20.4252, 15.4816, 1.61267x(1)226.5497, 27.3829, 27.5112, 30.9485x更新位置，得：更新位置，得：(1)3 14.7898, 60.2412, 53.5582, 39.8547 x初始速度：初始速度： (0)(0)(0)(0)(0)12345,vvvvv初始位置：初始位置： (0)(0)(0)(0)(0)12345,xxxxx群体历史最优解：群体历史最优解： (0)1gpx0, (1,2,3,4,5)iiipx个体历