粒子群优化算法详细解读

1、粒子群优化算法（粒子群优化算法（PS0） Particle Swarm Optimization 粒子群优化算法详细解读 智能算法智能算法 向大自然学习 n遗传算法遗传算法(GA)(GA) n物竞天择，设计染色体编码，物竞天择，设计染色体编码， 根据适应值函数进行染色体根据适应值函数进行染色体 选择、交叉和变异操作，优选择、交叉和变异操作，优 化求解化求解 n人工神经网络算法人工神经网络算法(ANN)(ANN) n模仿生物神经元，透过神经模仿生物神经元，透过神经 元的信息传递、训练学习、元的信息传递、训练学习、 联想，优化求解联想，优化求解 n模拟退火算法模拟退火算法(SA)(SA) n模模模

2、仿金属物质退火过程模仿金属物质退火过程 粒子群优化算法详细解读 解决最优化问题解决最优化问题的方法的方法 n传统搜索方法传统搜索方法 n保证能找到最优解保证能找到最优解 nHeuristic SearchHeuristic Search n不能保证找到最优解不能保证找到最优解 粒子群优化算法详细解读 由由KennedyKennedy和和EberhartEberhart于于19951995年提出年提出 群体迭代，粒子在解空间追随最优的粒子进行搜索群体迭代，粒子在解空间追随最优的粒子进行搜索. . 简单易行简单易行 粒子群算法粒子群算法: 收敛速度快收敛速度快 设置参数少设置参数少 已成为现代优化

3、方法领域研究的热点已成为现代优化方法领域研究的热点 粒子群算法发展历史简介粒子群算法发展历史简介 粒子群优化算法详细解读 粒子群粒子群算法的基本思想算法的基本思想 粒子群算法的思想源于对鸟群捕食行为的粒子群算法的思想源于对鸟群捕食行为的 研究研究 模拟鸟集群飞行觅食的行为，鸟之间通过模拟鸟集群飞行觅食的行为，鸟之间通过 集体的协作使群体达到最优目的，是一种集体的协作使群体达到最优目的，是一种 基于基于Swarm IntelligenceSwarm Intelligence的优化方法的优化方法。 马良教授在他的著作马良教授在他的著作蚁群优化算法一蚁群优化算法一 书的前言中写到书的前言中写到： 大

4、自然对我们的最大恩赐！大自然对我们的最大恩赐！ “自然界的蚁群、鸟群、鱼群、自然界的蚁群、鸟群、鱼群、 羊群、牛群、蜂群等，其实时时刻刻都在给予羊群、牛群、蜂群等，其实时时刻刻都在给予 我们以某种启示，只不过我们常常忽略了我们以某种启示，只不过我们常常忽略了 大自然对我们的最大恩赐！大自然对我们的最大恩赐！.” 粒子群优化算法详细解读 粒子群优化算法详细解读 粒子群粒子群算法的基本思想算法的基本思想 设想这样一个场景：设想这样一个场景：一群鸟在随机搜索食物一群鸟在随机搜索食物 在这块区域里只有一块食物在这块区域里只有一块食物; 所有的鸟都不知道食物在哪里所有的鸟都不知道食物在哪里; 但它们能感

5、受到当前的位置离食物还有多远但它们能感受到当前的位置离食物还有多远. 已知已知 那么那么:找到食物的最优策略是什么呢？找到食物的最优策略是什么呢？ 搜寻目前离食物最近的鸟的周围区域搜寻目前离食物最近的鸟的周围区域 根据自己飞行的经验判断食物的所在。根据自己飞行的经验判断食物的所在。 PSO正是从这种模型中得到了启发正是从这种模型中得到了启发 PSO的基础的基础: 信息的社会共享 信息的社会共享 粒子群优化算法详细解读 n生物学家对鸟生物学家对鸟(鱼鱼)群捕食的行为研究群捕食的行为研究 n社会行为社会行为 (Social-Only Model) n个体认知个体认知 (Cognition-Only

6、 Model) 粒子群优化算法详细解读 粒子群优化算法详细解读 算法介绍 每个寻优的问题解都被想像成一只鸟，称为“粒 子”。所有粒子都在一个D维空间进行搜索。 所有的粒子都由一个fitness function 确定适应值 以判断目前的位置好坏。 每一个粒子必须赋予记忆功能，能记住所搜寻到 的最佳位置。 每一个粒子还有一个速度以决定飞行的距离和方 向。这个速度根据它本身的飞行经验以及同伴的 飞行经验进行动态调整。 粒子群优化算法详细解读 粒子群优化算法求最优解粒子群优化算法求最优解 D维空间中，有N个粒子； 粒子i位置：x xi i=(xi1,xi2,xiD)，将xi代入适应函数f(xi)求适

7、应值； 粒子i速度：v vi i=(vi1,vi2,viD) 粒子i个体经历过的最好位置：pbestpbesti i=(pi1,pi2,piD) 种群所经历过的最好位置：gbestgbest=(g1,g2,gD) 通常，在第d（1dD）维的位置变化范围限定在 内， 速度变化范围限定在 内（即在迭代中若 超出了边界值，则该维的速度或位置被限制为该维最大速度或边界 位置） min,max, X, dd X ,max, -V, max dd V id v id 、x 粒子群优化算法详细解读 粒子i的第d维速度更新公式： 粒子i的第d维位置更新公式： 第k次迭代粒子i飞行速度矢量的第d维 分量 第k次

8、迭代粒子i位置矢量的第d维分量 c1,c2加速度常数，调节学习最大步长 r1,r2两个随机函数，取值范围0，1，以 增加搜索随机性 w 惯性权重，非负数，调节对解空间的搜 索范围 kk-111 idid1 12 2 v =wv()() kk ididdid c r pbestxc r gbestx 11kkk ididid xxv k id v k id x 粒子群优化算法详细解读 粒子速度更新公式包含三部分： 第一部分为粒子先前的速度 第二部分为“认知”部分，表示粒子本身的 思考，可理解为粒子i当前位置与自己最好位 置之间的距离。 第三部分为“社会”部分，表示粒子间的信 息共享与合作，可理解

9、为粒子i当前位置与群 体最好位置之间的距离。 kk-111 idid1 12 2 v =wv()() kk ididdid c r pbestxc r gbestx 粒子群优化算法详细解读 區域區域 最佳解最佳解 全域全域 最佳解最佳解 運動向量運動向量 慣性向量慣性向量 12 X = X ,X ,.,X iiiid 12 V = V ,V ,.,V iiiid 12 (1)( )( )( )() ()() () ididididgdid ttttvw vc randpxcrandpx (1)( )( ) iii tttxxv pg 粒子群优化算法详细解读 111 1122 V = V+C *

10、r*(Pbest -X)+C *r *(gbest -X) kkkk iiiii 11 X =X+V kkk iii 12N X = X ,X ,.,X iiii 12N V = V ,V ,.,V iiii 粒子群优化算法详细解读 算法流程 Initial： 初始化粒子群体（群体规模为n），包括随机位置和速度。 Evaluation： 根据fitness function ，评价每个粒子的适应度。 Find the Pbest： 对每个粒子，将其当前适应值与其个体历史最佳位置（pbest）对应 的适应值做比较，如果当前的适应值更高，则将用当前位置更新历 史最佳位置pbest。 Find th

11、e Gbest： 对每个粒子，将其当前适应值与全局最佳位置（gbest）对应的适 应值做比较，如果当前的适应值更高，则将用当前粒子的位置更新 全局最佳位置gbest。 Update the Velocity： 根据公式更新每个粒子的速度与位置。 如未满足结束条件，则返回步骤2 通常算法达到最大迭代次数 或者最佳适应度值的增量小于 某个给定的阈值时算法停止。 max G 粒子群优化算法详细解读 粒子群优化算法流程图粒子群优化算法流程图 开始 初始化粒子群 计算每个粒子的适应度 根据适应度更新pbest、gbest，更新粒子位置速度 结束 no yes 达到最大迭代次数或 全局最优位置满足最小界限

12、？ 粒子群优化算法详细解读 粒子群优化算法详细解读 粒子群粒子群算法的算法的构成要素构成要素 - -群体大小群体大小 m m m 是一个整型参数是一个整型参数 m 很小很小: m 很大很大: 当群体数目增长至一定水平时，再增长将当群体数目增长至一定水平时，再增长将不再有显不再有显 但收敛速度慢但收敛速度慢 著的作用著的作用 陷入局优的可能性很大陷入局优的可能性很大 PSO的优化能力很好，的优化能力很好， 粒子群优化算法详细解读 粒子群粒子群算法的算法的构成要素构成要素 -权重因子权重因子 权重因子：惯性因子权重因子：惯性因子 、学习因子、学习因子 1 c 2 c 失去对粒子本身失去对粒子本身

13、的的速度的记忆速度的记忆 1 社会经验部分社会经验部分 前次迭代中自身的速度前次迭代中自身的速度 自我认知部分自我认知部分 基本粒子群算法基本粒子群算法 粒子的速度更新主要由三部分组成：粒子的速度更新主要由三部分组成： 惯性因子惯性因子 k v 0 kk-111 idid1 12 2 v =wv()() kk ididdid c r pbestxc r gbestx 1 1 1( ) k idid c r pbestx 1 2 2( ) k did c r gbestx 粒子群优化算法详细解读 粒子群粒子群算法的算法的构成要素构成要素-权重因子权重因子 权重因子：惯性因子权重因子：惯性因子 、

14、学习因子、学习因子 1 c 2 c 社会经验部分社会经验部分 前次迭代中自身的速度前次迭代中自身的速度 自我认知部分自我认知部分 粒子的速度更新主要由三部分组成：粒子的速度更新主要由三部分组成： k v kk-111 idid1 12 2 v =wv()() kk ididdid c r pbestxc r gbestx 1 1 1( ) k idid c r pbestx 1 2 2( ) k did c r gbestx 学习因子学习因子 1 c 1 0c 无私型粒子群算法无私型粒子群算法 “只有社会，没有自我只有社会，没有自我” 迅速丧失群体多样性，迅速丧失群体多样性， 易陷入局优而无法

15、跳出易陷入局优而无法跳出 粒子群优化算法详细解读 粒子群粒子群算法的算法的构成要素构成要素 -权重因子权重因子 权重因子：惯性因子权重因子：惯性因子 、学习因子、学习因子 1 c 2 c 社会经验部分社会经验部分 前次迭代中自身的速度前次迭代中自身的速度 自我认知部分自我认知部分 粒子的速度更新主要由三部分组成：粒子的速度更新主要由三部分组成： k v kk-111 idid1 12 2 v =wv()() kk ididdid c r pbestxc r gbestx 1 1 1( ) k idid c r pbestx 1 2 2( ) k did c r gbestx 自我认知型粒子群算

16、法自我认知型粒子群算法 “只有自我，没有社会只有自我，没有社会” 完全没有信息的社会共享，完全没有信息的社会共享， 导致算法收敛速度缓慢导致算法收敛速度缓慢 学习因子学习因子 2 c 2 0c 粒子群优化算法详细解读 粒子群粒子群算法的算法的构成要素构成要素-权重因子权重因子 权重因子：惯性因子权重因子：惯性因子 、学习因子、学习因子 1 c 2 c 社会经验部分社会经验部分 前次迭代中自身的速度前次迭代中自身的速度 自我认知部分自我认知部分 粒子的速度更新主要由三部分组成：粒子的速度更新主要由三部分组成： k v kk-111 idid1 12 2 v =wv()() kk ididdid

17、c r pbestxc r gbestx 1 1 1( ) k idid c r pbestx 1 2 2( ) k did c r gbestx c c1 1,c,c2 2都不为都不为0 0，称为，称为 完全型粒子群算法完全型粒子群算法 完全型粒子群算法更容易保持收敛速度和搜索效完全型粒子群算法更容易保持收敛速度和搜索效 果的均衡，是较好的选择果的均衡，是较好的选择 粒子群优化算法详细解读 粒子群粒子群算法的算法的构成要素构成要素-最大速度最大速度 但但 在于维护算法的探索能力与开发能力的平衡在于维护算法的探索能力与开发能力的平衡 Vm较大时，探索能力增强，较大时，探索能力增强， m V 作

18、用作用: Vm较小时，开发能力增强，较小时，开发能力增强， m V m VVm一般设为每维变量变化范围的一般设为每维变量变化范围的1020. 但但 粒子容易飞过最优解粒子容易飞过最优解 容易陷入局部最优容易陷入局部最优 m V 粒子群优化算法详细解读 粒子群粒子群算法的算法的构成要素构成要素- 邻域的拓扑结构邻域的拓扑结构 全局粒子群算法和局部粒子群算法全局粒子群算法和局部粒子群算法 g p 粒子群算法的邻域拓扑结构包括两种，粒子群算法的邻域拓扑结构包括两种， 一种是将群体内所有个体都作为粒子的邻域，一种是将群体内所有个体都作为粒子的邻域， 另一种是只将群体中的部分个体作为粒子的邻域另一种是只

19、将群体中的部分个体作为粒子的邻域 群体历史最优位置群体历史最优位置 邻域拓扑结构邻域拓扑结构 决定决定 由此，将粒子群算法分为由此，将粒子群算法分为 粒子群优化算法详细解读 粒子群粒子群算法的算法的构成要素构成要素- 邻域的拓扑结构邻域的拓扑结构 全局粒子群算法全局粒子群算法 1. 1. 粒子自己历史最优值粒子自己历史最优值 2. 2. 粒子群体的全局最优值粒子群体的全局最优值 局部粒子群算法局部粒子群算法 1. 1. 粒子自己历史最优值粒子自己历史最优值 2. 2. 粒子邻域内粒子的最优值粒子邻域内粒子的最优值 邻域随迭代次数的增加线性变大，最后邻域扩展到整个粒子群。邻域随迭代次数的增加线性

20、变大，最后邻域扩展到整个粒子群。 经过实践证明：全局版本的粒子群算法收敛速度快，但是容易陷入经过实践证明：全局版本的粒子群算法收敛速度快，但是容易陷入 局部最优。局部版本的粒子群算法收敛速度慢，但是很难陷入局部最局部最优。局部版本的粒子群算法收敛速度慢，但是很难陷入局部最 优。现在的粒子群算法大都在收敛速度与摆脱局部最优这两个方面下优。现在的粒子群算法大都在收敛速度与摆脱局部最优这两个方面下 功夫。其实这两个方面是矛盾的。看如何更好的折中了。功夫。其实这两个方面是矛盾的。看如何更好的折中了。 粒子群优化算法详细解读 粒子群粒子群算法的算法的构成要素构成要素 -停止准则停止准则 停止准则一般有如

21、下两种：停止准则一般有如下两种： 最大迭代步数最大迭代步数 可接受的满意解可接受的满意解 粒子群优化算法详细解读 粒子群粒子群算法的算法的构成要素构成要素 - 粒子空间的初始化粒子空间的初始化 较好地选择粒子的初始化空间，将大大缩短收较好地选择粒子的初始化空间，将大大缩短收 敛时间初始化空间根据具体问题的不同而不同，敛时间初始化空间根据具体问题的不同而不同， 也就是说，这是问题依赖的也就是说，这是问题依赖的 从上面的介绍可以看到，粒子群算法与其他现代从上面的介绍可以看到，粒子群算法与其他现代 优化方法相比的一个明显特色就是所需调整的优化方法相比的一个明显特色就是所需调整的参数很参数很 少相对来

22、说，惯性因子和邻域定义较为重要这些少相对来说，惯性因子和邻域定义较为重要这些 为数不多的关键参数的设置却对算法的精度和效率有为数不多的关键参数的设置却对算法的精度和效率有 着显著影响着显著影响 粒子群优化算法详细解读 3. 粒子群粒子群算法示例算法示例 例例 求解如下四维求解如下四维Rosenbrock函数的优化问题函数的优化问题 3 222 1 1 min( )100()(1) iii i fxxx x 种群大小：种群大小： 30,30 (1,2,3,4) i xi 解解 算法的相关设计分析如下算法的相关设计分析如下 编码：因为问题的维数是编码：因为问题的维数是4，所以每个粒子的位置和，所以

23、每个粒子的位置和 max 60V 即算法中粒子的数量，取即算法中粒子的数量，取 5m 速度均速度均4 维的实数向量维的实数向量 设定粒子的最大速度：设定粒子的最大速度： 粒子群优化算法详细解读 初始位置：初始位置： 0 i x设各粒子的初始位置设各粒子的初始位置 和初始速度和初始速度 为：为： 0 i v 对粒子群进行随机初始化对粒子群进行随机初始化 包括随机初始化各粒子的位置和速度包括随机初始化各粒子的位置和速度 (0) 1 21.721, 9.13677, 6.62244, 3.84079x (0) 3 29.6563, 0.871811, 27.8912, 17.7425 x (0) 2

24、 13.5001, 23.6131, 17.4462, 29.0515 x (0) 5 28.0992, 22.6482, 0.675616, 8.43752 x (0) 4 23.6218, 16.4885, 22.7019, 25.4033x 粒子群优化算法详细解读 初始速度：初始速度： 0 i x设各粒子的初始位置设各粒子的初始位置 和初始速度和初始速度 为：为： 0 i v 对粒子群进行随机初始化对粒子群进行随机初始化 包括随机初始化各粒子的位置和速度包括随机初始化各粒子的位置和速度 (0) 1 19.9048, 29.562, 22.104, 5.45346 v (0) 3 7.83

25、576, 55.7173, 40.9177, 28.255 v (0) 2 20.5922, 28.6944, 26.3216, 19.0615 v (0) 5 17.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)7 1 ()2.38817 10fx 计算每个粒子的适应值计算每个粒子的适应值 (0)7 2 ()

26、4.45306 10fx 3 222 1 1 ( )100()(1) iii i fxxx x按照按照 计算适应值计算适应值 (0) 1g px (0)7 5 ()8.50674 10fx (0)7 4 ()6.56888 10fx (0)8 3 ()1.35376 10fx 历史最优解历史最优解 0 , (1,2,3,4,5) ii ipx 粒子群优化算法详细解读 更新粒子的速度和位置：更新粒子的速度和位置： 1 2 ()2 (), kkkkgk vvpxpx 11kkk xxv 12 2cc 0 1c 取取 ， , 得到速度和位置的更新函数为得到速度和位置的更新函数为 初始速度：初始速度：

27、 (0)(0)(0)(0)(0) 12345 ,vvvvv 初始位置：初始位置： (0)(0)(0)(0)(0) 12345 ,xxxxx 群体历史最优解：群体历史最优解： (0) 1g px 0 , (1,2,3,4,5) ii ipx个体历史最优解：个体历史最优解： 粒子群优化算法详细解读 (1) 1 19.9048, 29.562, 22.104, 5.45346 v (1) 2 40.0498, 3.76972, 44.9573, 75.6939v 更新速度，得：更新速度，得： (1) 3 14.8665, 59.3694, 25.667, 22.1122v 初始速度：初始速度： (0

28、)(0)(0)(0)(0) 12345 ,vvvvv 初始位置：初始位置： (0)(0)(0)(0)(0) 12345 ,xxxxx 群体历史最优解：群体历史最优解： (0) 1g px 0 , (1,2,3,4,5) ii ipx个体历史最优解：个体历史最优解： 1 2 ()2 (), kkkkgk vvpxpx (1) 4 13.843, 32.4824, 51.7604, 39.892 v (1) 5 95.9018, 63.5174, 60.6234, 36.7907v 60 606060 粒子群优化算法详细解读 (1) 1 1.81621, 20.4252, 15.4816, 1.6

29、1267x (1) 2 26.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) 1g px 0 , (1,2,3,4,5) ii ipx个体历史最优解：个体历史最优解： (1) 4 9.77877, 48.971, 29.0584, 14.4887x (1) 5 3

30、1.9008, 37.3518, 60.6756, 45.2282x 11kkk xxv 不强行拉回解空间不强行拉回解空间 粒子群优化算法详细解读 (1) 1 1.81621, 20.4252, 15.4816, 1.61267x (1) 2 26.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 群体历史

31、最优解：群体历史最优解： (0) 1g px 0 , (1,2,3,4,5) ii ipx个体历史最优解：个体历史最优解： (1) 4 9.77877, 48.971, 29.0584, 14.4887x (1) 5 31.9008, 37.3518, 60.6756, 45.2282x 3 222 1 1 ( )100()(1) iii i fxxx x按照按照 计算适应值计算适应值 粒子群优化算法详细解读 重复上述步骤，将迭代进行下去重复上述步骤，将迭代进行下去 3 222 1 1 ( )100()(1) iii i fxxx x按照按照 计算适应值计算适应值 (1)7 1 ()2.457

32、26 10fx (1)9 3 ()2.16403 10fx (1)8 2 ()1.6674 10fx (1)8 4 ()6.37125 10fx (1)9 5 ()1.6783 10fx 历史最优解历史最优解 粒子群优化算法详细解读 从上述结果，可以看出，经过从上述结果，可以看出，经过10000次迭代，次迭代， 粒子群算法得到了比较好的适应值粒子群算法得到了比较好的适应值. 粒子群优化算法详细解读 4. 粒子群粒子群算法算法流程流程 第第2步步 计算每个粒子的适应值计算每个粒子的适应值 11kkk xxv 1012 ()(), kkkkgk ccc vvpxpx 第第1步步 在初始化范围内，对粒子群进行随机初始化，在初始化范围内，对粒子群进行随机初始化， 第第5步步 更新粒子的速度和位置，公式如下更新粒子的速度和位置，公式如下 第第3