第6章 粒子群优化算法
Contents
1 算法简介 2 基本流程 3 改进研究 4 相关应用 5 参数设置
2
6.1 粒子群优化算法简介
粒子群优化算法是什么？
粒子群优化算法的思想来源是怎样的？ 它由谁提出的？
粒子群优化算法 （Particle Swarm Optimization，PSO）
是进化计算的一个分支， 是一种模拟自然界的P生S物O模活拟动了的自随然机界搜鸟索群算捕法食。和鱼群捕食的过程。
14
步骤1：初始化。 假设种群大小是N=3；在搜索空间中随机 初始化每个解的速度和位置，计算适应函 数值，并且得到粒子的历史最优位置和群 体的全局最优位置。
p1

vx11

(3,2) (8,5)

f1

82

(5)2

64
25

89
pBest1 x1 (8,5)
p2
6.1
1.8
(6.1,1.8)
x1 x1 v1 (5,9) (6.1,1.8) (1.1,10.8) (1.1,10)
注意！ 对于越界的位置，需要进行合法性调整
v3 v3 c1 r1 ( pBest3 x3 ) c2 r2 (gBest x3 )
粒子群优化算法
Байду номын сангаас鸟群觅食现象
6
6.2 粒子群优化算法的基本流程
基本流程
速度与位置更新公式 速度与位置更新示意图 算法流程图和伪代码
应用举例
函数最小化问题 算法的执行步骤示意图
7
粒子的个体速度与位置更新公式
vid vid c1 r1d ( pBestid xid ) c2 r2d (gBestd xid )
2006
2006
Kadirkamanathan 等人2006年在动态 环境中对PSO的行 为进行研究，由静
态分析深入到了动
态分析
F. van den Bergh 等人2006年对 PSO的飞行轨迹 进行了跟踪，深 入到了动态的系 统分析和收敛性 研究
19
6.3.2 拓扑结构改进
静态拓扑结构
全局版本：
end procedure
12
6.2.2 应用举例
例6.1 已知函数 y f (x1, x2) x12 x22 ， 其中 10 x1, x2 10 ，用粒子群优化算法求解y的 最小值。
13
运行步骤
步步骤骤步根31骤据：：2自：评身初粒的估子始历的粒史化速最子度。优和的位位置适置和更应全新局度。的函最优数值。 更假新设位粒种置子，群更的新大每历小个史粒是子最N的优=速3度位；和置在位置和搜。全索局空的间最中优随位机置。
群理论
4
6.1.2 基本原理
鸟群觅食现象
鸟群觅食现象
•鸟群 •觅食空间 •飞行速度 •所在位置 •个体认知与群体协作 •找到食物
类比关系
粒子群优化算法
•搜索空间的一组有效解 •问题的搜索空间 •解的速度向量 •解的位置向量 •速度与位置的更新 •找到全局最优解
粒子群优化算法
5
6.1.2 基本原理
Conference (GECCO) International Conference on Ant Colony
Optimization and Swarm Intelligence (ANTS) International Conference on Simulated Evolution
评估每个粒子并得到全局最优 是 满足结束条件
否 更新每个粒子的速度和位置 评估每个粒子的函数适应值 更新每个粒子历史最优位置
更新群体的全局最优位置
结束
procedure PSO for each particle i Initialize velocity Vi and position Xi for particle i Evaluate particle i and set pBesti = Xi end for gBest = min {pBesti} while not stop for i=1 to N Update the velocity and position of particle i Evaluate particle i if fit (Xi) < fit (pBesti) pBesti = Xi; if fit(pBesti) < fit (gBest) gBest = pBesti; end for end while print gBest
星型结构
局部版本：

f2

f2*
101.21
pBest2 X2 (1.1,10)
f3* (3.5)2 (1.7)2 12.252.8915.14113 f3

f3

f3*
15.14
pBest3 x3 (3.5,1.7)
gBest pBest3 (3.5, 1.7)
1.5 1

(1.5,1)
x1 x1 v1 (8,5) (1.5,1) (9.5,4)
v2 v2 c1 r1 ( pBest2 x2 ) c2 r2 (gBest x2 )
p2

v2

0.5 (3) 0 2 0.3 (8 (5)) 0.5 (2) 0 2 0.1 ((5) 9)

v2

x
2

(3,2)
f2

(5)2
92

2581106
(5,9) pBest2 x2 (5,9)
p3

v3

x3

(5,3)

f3

(7)2
(8)2

4964
113
(7,8)pBest3 x3 (7,8)
gBest pBest1 (8, 5)
通过群体中的协作寻找到问题的全局最优解。 它是1995年由美国学者Eberhart和Kennedy提出的， 现在已经广泛应用于各种工程领域的优化问题之中。
3
6.1.1 思想来源
生物界现象
群体行为 群体迁徙 生物觅食
……
粒子群 优化算法
社会心理学
群体智慧 个体认知 社会影响
……
人工生命
鸟群觅食
鱼群学习
步骤3：评估粒子的适应度函数值。 更新粒子的历史最优位置和全局的最优位置。
f1* 9.52 (4)2 90.2516 106.25 f1 89

f1 89 pBest1＝(8,
5)
f2* 1.12 102 1.21100 101.21106 f2
拓扑结构 研究
混合算法 研究
算法应用 研究
16
与PSO相关的重要学术期刊与国际会议
重要学术期刊
IEEE Transactions on Evolutionary Computation IEEE Transactions on Systems, Man and Cybernetics IEEE Transactions on …… Machine Learning Evolutionary Computation ……
xid xid vid
自身速度
个体认知
更新速度
社会引导
8
速度与位置更新示意图
x2 P2
gBest x1
P1 P3
9
速度与位置更新示意图
x2 PB 2
P1
P2
x1 P3
10
速度与位置更新示意图
x2
经过若干次迭代之后
P2
P1
x1 P3
11
PSO算法流程图和伪代码
开始 随机初始化每个粒子
//功能：粒子群优化算法伪代码 //说明：本例以求问题最小值为目标 //参数：N为群体规模
p3

v3

0.5 5 0 2 0.05 (8 (7)) 3.5 0.5 3 0 2 0.8 ((5) (8)) 6.3

(3.5,6.3)
x1 x1 v1 (7,8) (3.5,6.3) (3.5,1.7)
17
与PSO相关的重要学术期刊与国际会议
重要国际会议
IEEE Congress on Evolutionary Computation (CEC) IEEE International Conference on Systems, Man, and
Cybernetics (SMC) ACM Genetic and Evolutionary Computation
步 如骤 果4满：足结束条件，则输出 ff1初数体2p*p*f11B始值的pp9e112s.8.，化全51t9122vx＝vvx11112并每局vv(1(128x且个最01,((4238v)v00得解优00v1,2,52..12..55551))c5到的位.c1(3229((1)8,01粒速置23r0r1.0)5)12)51。子度(pf0000(1p0(Bp1B0B.的和1ee21251es,.s861s5tt1t)20历位0121..310(1x(19x史置1(1.0)x25.((5.(8),6112,5)，最.c51)24c2)(2)52(计优58r9)12,r))620算位4f5(6116g()..gB81适置Be28se5fts(9应和26t.1x,1函群8x1)2.98)) ppf22B全 否esft局 则22注*vxx2意21 1X， 最！0x211((.转 优2v(31511,,.对91向 结(,于)215)0越,9步 果))界pf2B的(骤 并6e.位1s,(1t置.2结285)，继)2需x束(12要.续19,1进2程0(.行8执)5合2序,59(法1行).1性，,81调01。)整106