发布网友
共1个回答
热心网友
粒子群优化算法(PSO)是一种模拟鸟类觅食行为的算法,由Eberhart 和Kennedy 于1995年提出。这种算法因其操作简单、速度快等特点,在处理多目标优化问题时被广泛采用。多目标粒子群优化算法(MOPSO)由Carlos A. CoelloCoello 等人提出,旨在将传统的粒子群算法(PSO)扩展到多目标优化问题中。
MOPSO算法通过外部存档和Pareto支配基本原理来处理多个目标,具有适用范围广、设置参数少、优化结构简单的特点,在多个领域得到了广泛应用。相比于单目标算法,多目标算法考虑的内容更多,更容易受到审稿人的青睐。因此,本文将介绍该算法的原理与代码。本期代码免费赠送,需要代码的小伙伴可直接拉到最后!
作为群体智能演化算法,PSO模拟自然界中鸟类的觅食行为,将食物的位置类比为优化问题的最优解集,将鸟类的飞行方向与位置类比为粒子的速度和位置。根据全局最优(gBest)和个体历史最优(pBest)的信息交互,不断更新粒子的位置和速度,提高搜索效率、有效引导种群往PF方向收敛,但这也导致其可能陷入局部最优,其具体更新过程可以表示如下:
式中:Xi(t)为位置向量,Xi(t)=[xi1(t),xi2(t),…,xid(t)],Vi(t)为速度向量,Vi(t)=[vi1(t),vi2(t),…,vid(t)],Xi(t)和Vi(t)分别表示粒子i第t时刻的位置和速度,Xi(t+1)和Vi(t+1)分别为更新后的位置和速度;pBesti(t)和gBesti(t)分别表示粒子i在t时刻的历史最优位置和全局最优位置;w为惯性权重因子;c1和c2为大于零的加速因子;γ1, γ2∈[0,1]。
相比于刚刚的单目标粒子群算法,多目标粒子群算法MOPSO主要体现在两个方面的区别,一是外部档案,二是突变算子。
一、外部档案
外部档案即利用网格划分法对算法中的精英个体进行更新。首先,将目标空间划分为若干网格,任意一个网格都为考察对象,并计算外部存档内种群个体的适应度值;其次,计算每个网格内粒子个数,并将其作为分布密度,分布密度的倒数即为网格被选择概率,通过轮盘赌方式选择网格。最后,被选中的网格中随机确定精英个体位置。具体分为以下几个步骤:
1)目标空间划分
对目标空间进行划分时,需确定目标空间中每个维度的最大、最小边界(minFi ,maxFi)。通过边界计算网格的模,公式如下:
式中:Fi 为第 i 个维度的目标函数值, i =1,2, ……, n;M为第 i 个维度要划分的网格数。
2)计算网格内粒子数
遍历外部存档中的粒子,计算粒子所在网格编号。对于第i个粒子,通过公式(5)计算网格位置。
通过粒子编号可以确定粒子所处的网格位置,以此来确定,每个网格被选择的概率为
式中:Numk 为第 k 个网络的粒子数。
3)基于轮盘赌确定网格和猎物位置
通过轮盘赌方式确定网格。首先,需要将每个网格被选中的概率归一化处理,如下:
其次,计算各网格累积概率,如下:
最后,通过生成随机数选择网格内的粒子。通过网格划分法确定猎物位置避免算法陷入局部最优的同时,为提升算法收敛速度,当种群超出边界时,算法不对个体直接赋边界值,而是超出界限的相应值赋予猎物位置,避免算法重复搜索边界位置。公式如下:
网格划分法基于划分网格内粒子数对网格进行选取,为算法提供了更优猎物位置使算法的Pareto前沿分布更加均匀。而且对超出搜索边界的个体位置选取返回猎物位置的更新方法而不是采取返回边界位置的更新方法,更加有效的提升了算法收敛速度。
二、突变算子
突变算子通过引入随机扰动,有效避免了粒子群陷入局部最优,提升了算法的全局搜索能力。均匀突变保证了随机性,而非均匀突变则随着迭代次数的增加逐渐减少突变程度,平衡了探索和开发的关系。
将粒子群分成三部分,分别是不进行突变、进行均匀突变和进行非均匀突变。
第一部分粒子不进行突变。
第二部分粒子,按照比例进行均匀突变,即随机改变一部分粒子的位置。均匀突变的粒子位置重新在搜索空间内生成。
第三部分粒子,进行非均匀突变,其突变程度随代数的增加而逐渐减小。
突变算子通过增加搜索空间的多样性以及不同类型的突变策略,保证算法在初期进行充分的探索,而在后期则逐渐收敛至最优解附近。
为了更清晰的展示PSO与MOPSO的流程,这边给出两个算法的流程图,非常清晰~
为这边以三个多目标函数“ZDT1”、“ZDT3”、“Viennet2”为例,检测一下MOPSO的性能。图中有帕累托真实前沿,越靠近前沿面则代表效果越好。
ZDT1:
ZDT3:
Viennet2:
可以看到,绝大多数粒子都能够接近前沿面,但仍然有改进的空间~
MOPSO完整代码如下:
其中有部分函数封装为了子函数,因篇幅原因文章中无法全部放下。
因此,需要免费完整代码(能够运行出结果展示中的图片)的小伙伴只需查看链接:
多目标粒子群算法(MOPSO):原理讲解与代码实现 Matlab代码免费获取