【人工智能Ⅰ】5-粒子群算法

【人工智能Ⅰ】5-粒子群算法

5.1 粒子群算法PSO基本思想

特点：简单、收敛速度快、设置参数少

群体迭代，粒子在解空间追随最优的粒子进行搜索

PSO基础：信息的社会共享

粒子群特性：社会行为 + 个体认知

5.2 PSO介绍

1：所有粒子都在一个D维空间搜索

2：所有粒子由适应度函数确定适应值，用于判断目前位置的好坏

3：所有粒子有记忆功能，保存最佳位置

4：所有粒子以一个速度决定飞行距离和方向，且速度根据个体认知和社会行为进行动态调整

5.3 PSO求最优解

D维空间，N个粒子

粒子i位置：（可将x_i带入适应度函数f(x)求解适应值）
$$x_i=(x_{i1},...,x_{iD})$$
粒子i速度：
$$v_i=(v_{i1},...,v_{iD})$$
粒子i的最好位置：
$$pbes{t}_i=(p_{i1},...,p_{iD})$$
种群的最好位置：
$$gbest=(g_1,...,g_D)$$
在第d维的位置变化范围：
$$[X_{min,d},X_{max,d}]$$
在第d维的速度变化范围：
$$[-V_{max,d},V_{max,d}]$$

上述范围保证了位置和速度约束在预设的边界内部

粒子i在第d维的速度更新：
$$v_{id}^k=w{v}_{id}^k+c_1{r}_1(pbes{t}_{id}-x_{id}^{k-1})+c_2{r}_2(gbes{t}_d-x_{id}^{k-1})$$
粒子i在第d维的位置更新：
$$x_{id}^k=x_{id}^{k-1}+v_{id}^{k-1}$$

c1、c2：加速度常数，调节学习最大步长

r1、r2：随机函数，取值范围[0,1]，增加搜索随机性

w：惯性权重，非负，调节搜索范围

粒子的速度更新包括三部分：

1：粒子先前的速度
$$w{v}_k$$
2：认知：粒子当前位置与自己最好位置间的距离
$$c_1{r}_1(pbes{t}_{id}-x_{id}^{k-1})$$
3：社会：粒子当前位置与群体最好位置间的距离
$$c_2{r}_2(gbes{t}_d-x_{id}^{k-1})$$

5.4 算法流程

1：初始化

初始化群体规模未n，以及随机位置和速度

2：评估

根据适应度函数，评价每个粒子的适应度

3：找到个体最优pbest

比较当前适应度值和个体pbest，更新pbest

4：找到群体最优gbest

比较当前适应度值和群体gbest，更新gbest

5：更新粒子情况

根据公式更新每个粒子的速度和位置

6：终止

如果达到最大迭代次数G_max，或最佳适应度值的增量小于阈值

5.5 PSO构成要素

群体大小m

过小：提前局部最优

过大：优化能力好但收敛速度慢，当群体数目增长到一定水平时，再增长不明显

权重因子

1：惯性因子w

若w=1，则是基本粒子群算法

若w=0，则失去对粒子本身速度的记忆

2：学习因子c1、c2

若c1=0，则是无私型粒子，会丧失群体多样性，陷入局部最优解

若c2=0，则是自我认知型粒子，会丧失信息社会共享，收敛速度缓慢

若c1!=0且c2!=0，则是完全型粒子，平衡收敛速度和搜索效率

最大速度Vm

作用：维护探索能力和开发能力的平衡

过大：探索能力增强，但容易飞过全局最优解

过小：开发能力增加，但容易陷入局部最优解

一般变化范围：每个维度变量的10%-20%

停止准则

1：最大迭代步数

2：可接受的满意解

粒子空间的初始化

依赖于问题

特色：参数少，惯性因子和领域定义重要

领域的拓扑结构

1：群体内所有个体都是粒子的领域（对应全局粒子群算法）

2：群体内部分个体是粒子的领域（对应局部粒子群算法）

领域拓扑结构，决定，群体pbest

邻域随迭代次数的增加线性变大，最后邻域扩展到整个粒子群

全局粒子群算法：收敛速度快，容易局部最优

局部粒子群算法：收敛速度慢，不容易局部最优

5.6 PSO应用

1：函数优化问题

2：TSP问题（路径对应位置，交换子/交换序列对应速度）

3：参数优化

4：组合优化

5.7 PSO改进

动态调整惯性权重

前期提高全局搜索能力（w较大），找到合适的种子

后期提高局部搜索能力（w较小），提高收敛精度

解决方法：线性递减权值
$$w=w_{max}-(w_{max}-w_{min})\ast run/ru{n}_{max}$$

$$w_{max}：最大惯性权重，w_{min}：最小惯性权重，run：当前迭代次数，ru{n}_{max}：总迭代次数$$

收缩因子法

作用：保证收敛性

速度更新公式：
$$v_{id}=K[v_{id}+f_1{r}_1(pbes{t}_{id}-x_{id})+f_2{r}_2(gbes{t}_d-x_{id})]$$

$$K：收缩因子（受到f_1和f_2限制的w），f_1和f_2是预先设定的模型参数$$

$$K=2/|2-f-\sqrt{t(f^2-4f)}|$$

$$f=f_1+f_2,f>4$$

5.8 群智能优化的特点和不足

共同特点

基于概率计算的随机搜索进化算法，在结构、研究内容、方法以及步骤上有较大的相似性

存在问题

1：数学理论基础相对薄弱

2：参数设置没有确切的理论依据，对具体问题和应用环境的依赖性大；

3：比较性研究不足，缺乏用于性能评估的标准测试集；

4：不具备绝对的可信性，存在应用风险

进一步研究

1：真实群居动物的行为特征

2：算法收敛性

3：提高收敛速度，从而解决大规模优化问题

4：各种参数设置问题

5：群智能的并行算法

6：各算法的适用范围

7：与其它算法的混合技术

5.9 群智能小结

1：什么是群？什么是群智能？

2：群智能算法的一般框架

3：群智能算法有哪些？

4：PSO的基本思想，粒子、评价函数、粒子学习（跟踪2个极值：个体极值和社会极值）

5：粒子的速度更新公式的含义，各部分对算法性能的作用

6：PSO算法步骤