《1 前言》
1 前言
从20世纪90年代初, 就产生了模拟自然生物群体 (swarm) 行为的优化技术。Dorigo等从生物进化的机理中受到启发, 通过模拟蚂蚁的寻径行为, 提出了蚁群优化方法;Eberhart和 Kennedy于1995年提出的粒子群优化算法是基于对鸟群、鱼群的模拟。这些研究可以称为群体智能 (swarm intelligence) 。通常单个自然生物并不是智能的, 但是整个生物群体却表现出处理复杂问题的能力, 群体智能就是这些团体行为在人工智能问题中的应用。粒子群优化 (PSO) 最初是处理连续优化问题的, 目前其应用已扩展到组合优化问题
《2 PSO基本原理》
2 PSO基本原理
《2.1基本PSO原理》
2.1基本PSO原理
粒子群优化算法是基于群体的演化算法, 其思想来源于人工生命和演化计算理论。Reynolds对鸟群飞行的研究发现, 鸟仅仅是追踪它有限数量的邻居, 但最终的整体结果是整个鸟群好像在一个中心的控制之下, 即复杂的全局行为是由简单规则的相互作用引起的。PSO即源于对鸟群捕食行为的研究, 一群鸟在随机搜寻食物, 如果这个区域里只有一块食物, 那么找到食物的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。PSO算法就是从这种模型中得到启示而产生的, 并用于解决优化问题。另外, 人们通常是以他们自己及他人的经验来作为决策的依据, 这就构成了PSO的一个基本概念。
PSO求解优化问题时, 问题的解对应于搜索空间中一只鸟的位置, 称这些鸟为“粒子” (particle) 或“主体” (agent) 。每个粒子都有自己的位置和速度 (决定飞行的方向和距离) , 还有一个由被优化函数决定的适应值。各个粒子记忆、追随当前的最优粒子, 在解空间中搜索。每次迭代的过程不是完全随机的, 如果找到较好解, 将会以此为依据来寻找下一个解。
令PSO初始化为一群随机粒子 (随机解) , 在每一次迭代中, 粒子通过跟踪两个“极值”来更新自己:第一个就是粒子本身所找到的最好解, 叫做个体极值点 (用pbest表示其位置) , 全局版PSO中的另一个极值点是整个种群目前找到的最好解, 称为全局极值点 (用gbest表示其位置) , 而局部版PSO不用整个种群而是用其中一部分作为粒子的邻居, 所有邻居中的最好解就是局部极值点 (用lbest表示其位置) 。在找到这两个最好解后, 粒子根据如下的式 (1) 和式 (2) 来更新自己的速度和位置。粒子i的信息可以用D维向量表示, 位置表示为 Xi= (xi1, xi2, ..., xiD) T, 速度为Vi= (vi1, vi2, ..., viD) T, 其他向量类似。则速度和位置更新方程为
v
Step 1 初始化 初始搜索点的位置X
Step 2 评价每一个粒子 计算粒子的适应度值, 如果好于该粒子当前的个体极值, 则将pbest设置为该粒子的位置, 且更新个体极值。如果所有粒子的个体极值中最好的好于当前的全局极值, 则将gbest设置为该粒子的位置, 记录该粒子的序号, 且更新全局极值。
Step 3 粒子的更新 用式 (1) 和式 (2) 对每一个粒子的速度和位置进行更新。
Step 4 检验是否符合结束条件 如果当前的迭代次数达到了预先设定的最大次数 (或达到最小错误要求) , 则停止迭代, 输出最优解, 否则转到Step 2。
PSO的一些特点:
1) 基本PSO算法最初是处理连续优化问题的。
2) 类似于遗传算法 (GA) PSO也是多点搜索。
3) 式 (1) 的第一项对应多样化 (diversification) 的特点, 第二项、第三项对应于搜索过程的集中化 (intensification) 特点, 因此这个方法在多样化和集中化之间建立均衡
PSO有全局版和局部版两种, 全局版收敛快, 但有时会陷入局部最优。局部版PSO通过保持多个吸引子来避免早熟, 假设每一个粒子在大小l的邻域内定义为一个集合
从Ni中选出最好的, 将其位置作为lbest代替公式中的gbest, 其他与全局版PSO相同。实验表明, 局部版比全局版收敛慢, 但不容易陷入局部最优
《2.2二进制PSO》
2.2二进制PSO
最初的PSO是从解决连续优化问题发展起来的, Eberhart等又提出了PSO的离散二进制版, 用来解决工程实际中的组合优化问题
二进制版本PSO的公式为
向量ρ
《2.3解决混和整数非线性规划 (MINLP) 问题的PSO》
2.3解决混和整数非线性规划 (MINLP) 问题的PSO
如果用离散数字来表达当前的位置和速度, 或者在速度更新完成后对整数变量进行取整运算, 则可以在算法中同时处理连续和离散变量。这就为解决MINLP等问题提供了广阔天地, 文献
《3 PSO的变化和改进》
3 PSO的变化和改进
PSO与GA有很多共同之处, 两者都随机初始化种群, 使用适应值来评价系统和进行一定的随机搜索。但PSO是根据自己的速度来决定搜索, 没有GA的明显的交叉和变异。如果将pbest也看作是种群的成员, 那么PSO也有一种很弱形式的选择
PSO收敛快, 特别是在算法的早期, 但也存在着精度较低, 易发散等缺点。若加速系数、最大速度等参数太大, 粒子群可能错过最优解, 算法不收敛;而在收敛的情况下, 由于所有的粒子都向最优解的方向飞去, 所以粒子趋向同一化 (失去了多样性) , 使得后期收敛速度明显变慢, 同时算法收敛到一定精度时, 无法继续优化, 所能达到的精度也比GA低
《3.1收敛速度的改进》
3.1收敛速度的改进
《3.1.1 惯性权重 (inertia weight) 法 》
3.1.1 惯性权重 (inertia weight) 法
Shi等提出了惯性权重的方法
用惯性权重来控制前面的速度对当前速度的影响, 较大的w可以加强PSO的全局搜索能力, 而较小的w能加强局部搜索能力
《3.1.2 模糊惯性权重 (fuzzy inertia weight) 法 》
3.1.2 模糊惯性权重 (fuzzy inertia weight) 法
Shi等提出用模糊控制器来动态自适应地改变惯性权重的技术
NCBPE是规范化后的评价值, CBPEmin和CBPEmax依问题而定, 且需事先得知或者可估计。
模糊w法与线性下降w方法的比较结果显示, 后者不知道应该降低w的合适时机, 而自适应模糊控制器能预测使用什么样的w更合适, 可以动态地平衡全局和局部搜索能力。但是由于需知道CBPEmin和CBPEmax等, 使得模糊权重法的实现较为困难, 因而无法广泛使用
《3.1.3 压缩因子 (constriction factor) 法 》
3.1.3 压缩因子 (constriction factor) 法
Clerc得出结论:压缩因子有助于确保PSO算法收敛
其中χ=2/|2-φ- (φ2-4φ) 1/2|为压缩因子, φ=c1+c2, 且φ>4。
约束因子法控制系统行为最终收敛, 且可以有效搜索不同的区域, 该法能得到高质量的解, 如果与此同时将每维vd max设置为一维搜索空间的大小xd max, 则可以得到更好的效果。
《3.1.4 选择 (selection) 法 》
3.1.4 选择 (selection) 法
Angeline提出的混和PSO主要应用PSO的基本机制以及演化计算所采用的自然选择机制
《3.1.5 繁殖 (Breeding) 法 》
3.1.5 繁殖 (Breeding) 法
LØvbjerg等人将遗传算法中的复制和重组这些称为繁殖的操作加入到全局版PSO中, 该方法是对按概率Pi选出的粒子进行如下式
的代数杂交操作, 产生子代的粒子取代父代。选择父代没有基于适应值, 防止了基于适应值的选择对那些多局部极值的函数带来潜在问题
《3.2增加多样性的改进》
3.2增加多样性的改进
《3.2.1 空间邻域 (spatial neighborhoods) 法 》
3.2.1 空间邻域 (spatial neighborhoods) 法
基本的局部版PSO中 (见式 (3) ) 粒子的邻域是基于粒子序号划分的。Suganthan提出了基于粒子的空间位置划分的方案
计算一个比值, 其中‖Xa-Xb‖是当前粒子a到粒子b的距离。而选择阈值frac根据迭代次数而变化。当另一粒子b满足‖Xa-Xb‖/dmax<frac时, 则b成为当前粒子的邻域。所有满足该条件的粒子组成N′i, 其他同原局部版PSO。应用改进的邻域规则, 且采用时变w的PSO在绝大多数测试中都取得了比全局版PSO更优良的性能。
《3.2.2 邻域拓扑 (neighborhood topologies) 法 》
3.2.2 邻域拓扑 (neighborhood topologies) 法
基本局部版PSO (见式 (3) ) 每个粒子左右两边的粒子都是它的邻居, 实际上这是应用了环形拓扑。Kennedy测试了如图2所示的几种邻域拓扑结构
《图1》
Fig.1 A diagrammatic representation of two possible neighbourhood topologies, before and after edges have been randomly exchanged
结果表明, 拓扑非常影响算法的性能, 且最佳的拓扑形式因问题而定。如对有很多局部最优的函数, 轮形拓扑邻域算法能得到最好的结果, Kennedy推测, 这是由于较慢的信息流动;而对于单峰函数, 星形拓扑邻域算法可以产生较好的结果, 因为它有较快的信息流动 (这里的拓扑都是在粒子序号空间下的拓扑) 。
《3.2.3 社会趋同 (social stereotyping) 法 》
3.2.3 社会趋同 (social stereotyping) 法
Kenney提出了混和空间邻域和环形拓扑方法的另一个局部PSO版本, 称为社会趋同法
《3.3全局方法》
3.3全局方法
《3.3.1 序列生境技术 (SNT, sequential niche technique) 法 》
3.3.1 序列生境技术 (SNT, sequential niche technique) 法
Beasley等提出的最初使用在遗传算法中的序列生境技术可以系统地访问每一个全局极值
《3.3.2 函数延伸 (function stretching) 法 》
3.3.2 函数延伸 (function stretching) 法
为了减小定位所有全局极值的花费, Parsopoulos等将自适应改变目标函数方法应用到了PSO中
《3.4动态目标函数》
3.4动态目标函数
很多现实优化问题的目标函数是随时间变化的, 因此已经有很多学者开始致力于这方面的研究。Parsopoulos等的试验表明, 基本PSO就可以有效而稳定地在噪声环境中工作, 且在很多情况下, 噪声的存在还可以帮助PSO避免陷入局部最优
《3.5其他改进》
3.5其他改进
《3.5.1 保收敛PSO (guaranteed convergence PSO) 》
3.5.1 保收敛PSO (guaranteed convergence PSO)
若粒子的当前位置恰是全局最好位置, 那么速度更新方程式 (6) 就只剩下v
《3.5.2 协同PSO (cooperative PSO) 》
3.5.2 协同PSO (cooperative PSO)
文献
《4 PSO的应用》
4 PSO的应用
PSO的优势在于算法的简洁性, 易于实现, 没有很多参数需要调整, 且不需要梯度信息。PSO是非线性连续优化问题、组合优化问题和混合整数非线性优化问题的有效优化工具
一般说来, PSO比较有潜力的应用包括系统设计、多目标优化、分类、模式识别、调度、信号处理、决策、机器人应用等。其中具体应用实例有:模糊控制器设计、车间作业调度、机器人实时路径规划、自动目标检测、时频分析等
《5 仿真》
5 仿真
为了检验算法的性能, 笔者按照图2的流程框图编写了仿真程序, 对两例优化问题进行求解。
例1 混合整数优化问题
表1是各种算法对例1的仿真计算结果。采用线性下降惯性权重从0.9到0.4的PSO和压缩因子c1=c2=2.05的PSO两种方法, 得到了同样好的结果, 惯性权重法得到该解的概率更高。
Table 1 Comparison among the results of various algorithms in example 1
《表1》
项 | IDCNLP | SA | MVEP | MIHDE | 空间收缩 | PSO |
x1 | 48.380 7 | 58.290 0 | 51.195 8 | 48.576 5 | 42.006 0 | 42.098 44 |
x2 | 111.744 9 | 43.693 0 | 90.782 1 | 110.055 9 | 183.047 3 | 176.636 66 |
y1 | 18 | 18 | 16 | 15 | 13 | 13 |
y2 | 10 | 10 | 10 | 8 | 7 | 7 |
g1 | -0.191 3 | -0.025 0 | -0.011 9 | 0.000 0 | -0.001 8 | -6.790×10-8 |
g2 | -0.163 4 | -0.068 9 | -0.136 6 | -0.036 6 | -0.036 8 | -0.035 88 |
g3 | -75.8750 | 6.5496 | -13584.5631 | 0.0000 | -29169.0801 | -0.07965 |
g4 | -128.255 1 | -196.307 0 | -147.217 9 | -129.944 1 | -56.952 7 | -63.363 34 |
f | 8048.6190 | 7197.7 | 7108.6160 | 6370.7035 | 6193.7788 | 6059.71533 |
例2 Schaffe提出的实例
已知全局最优点是 (0, 0) , f (x) 为 -0.5。由于其强烈的振荡性以及全局最优点被无限个局部最优点包围的特性, 一般优化算法很难找到它的全局最优值。PSO算法的运行结果如表2。两种方法都只需要迭代200次, 即可找到以上最优值, 且耗时只有十几毫秒。
Table 2 Results of the PSO simulated procedure in example 2
《表2》
项 | 惯性权重0.9~0.4线性下降的PSO | 使用约束因子的PSO |
x1 | -3.416 583×10-5 | -5.412 430×10-5 |
x2 | -2.828 398×10-6 | -2.138 258×10-7 |
f (x) | -0.5 | -0.5 |
2个实例的仿真表明, 用基本PSO很难得到满意的结果, 而这里采用的两种改进方案都十分简单、有效。
《5 结语》
5 结语
粒子群优化算法是一种新兴的有潜力的演化算法, 但还存在一些问题, 在这一点上它与遗传算法很类似。
2) 利用不同问题的特点设计出相应有效的算法, 是非常有意义的工作。因此当前针对具体应用问题深化研究PSO算法是值得提倡的工作。
3) 应该致力于补充和扩展PSO与其他算法或技术的结合, 解决PSO易陷入局部最优的问题。