基于竞争机制策略的多目标粒子群优化算法

王进成，顾银鲁，宋桢桢

(银川能源学院 基础部，宁夏 银川 750021)

在求解多目标优化问题时[1]，要求尽可能地接近真正的Pareto有效前端；尽可能地保持良好的多样性；尽可能地使粒子分散均匀.目前，出现了许多经典的多目标优化算法.如Dbe[2]等人利用non-dominated sorting提出了NSGA-Ⅱ算法，Corne[3]等人利用强度Pareto支配的思想提出了SPEA2算法，Coello[4]等人利用外部粒子群来指导该群体外其他粒子的飞行的思想提出了MOPSO算法.

粒子群优化算法[5](Particle Swarm Optimization Algorithm，PSO)是由Kennedy博士于1995年提出来的一种群智能优化算法，由于该算法简单收敛速度快且易于实现，近年来就得到了飞速发展并成为群智能优化算法研究领域的热点之一.用于解决多目标优化问题的粒子群优化算法称为多目标粒子群优化算法(Multi-objective particle swarm algorithm，MOPSO).为了提高MOPSO粒子的多样性，本文提出了一种基于竞争机制策略的多目标粒子群优化算法.有效地平衡了种群的全局寻优能力和局部搜索能力，并且使算法能够更快的搜索到最优位置和收敛于Pareto最优边界.最后，通过对多目标测试函数进行仿真试验，以及与经典多目标算法NSGA-Ⅱ、SPEA2、MOPSO相比，结果表明，本文算法在收敛性和分布性方面都有所改善.

1 粒子群优化算法

粒子群算法(PSO)是一种模仿鸟类和鱼群中个体社会行为的一种启发式群体智能算法.该算法稳定且高效，是近年来发展的一种智能全局寻优算法.种群中每一只鸟相当于粒子群算法中的一个粒子，每个粒子类似于寻找食物的鸟，都有其自身的速度和位置，通过自身学习和社会学习两种方式，粒子在搜索空间中运动，从而得到全局最优解.假设种群规模为N的粒子在D维空间内进行搜索，粒子的速度和位置更新公式为

(1)

(2)

ω=ωmax-t*(ωmax-ωmin)/Tmax，

(3)

上式中，ωmax,ωmin分别为惯性权重的最大和最小值，一般取0.9和0.4,t表示当前迭代次数,Tmax表示最大迭代次数.

2 基于竞争机制策略的多目标粒子群优化算法

2.1 竞争机制策略

本文提出的竞争机制策略主要是基于支配的方法，在多目标粒子群算法中可以快速搜索非支配解集以及构建外部档案集.首先，从群体s中任选一个粒子x，一般情况下选取群体中的第一个粒子.然后，令s=s-{x}，将群体中的每个粒子依次与粒子x依据目标函数值的Pareto支配关系进行比较.若x

在求解多目标粒子群优化算法时，每一次迭代都会产生一组非劣解.因此，需要利用外部存档来储存每一次迭代所产生的非支配解，而这些解集构成了Pareto前端[6].从而每迭代一次，Pareto前端也随之更新一次.但是，随着迭代次数的增加，外部档案规模将会增加，算法的复杂度也将会大大增加.此时需要对外部档案规模进行控制，从而可以降低算法的复杂度.本文采用拥挤距离降序排列来限制外部档案集的规模.

2.2 个体最优解和全局最优解的选取

在粒子群算法中，粒子群大小固定，粒子不会被替代，只是调整它们的个体最优解(xbest)和全局最优解(gbest)．在多目标情况下，全局最优解通常存在于一组非劣解中，而不是单个的全局最优位置，而且当两者互不支配时，每个粒子可能不止一个个体最优解．因此，个体最优解和全局最优解的选取比单目标优化更加困难和重要．

(4)

对于多目标粒子群优化算法的全局最优解更新策略，本文从外部档案集排在前20%的非支配解中随机选取全局最优解.

2.3 参数改进策略

对于粒子群算法中的惯性权重ω和学习因子c1和c2这两类参数，它们对种群在目标区域内搜索能力有很大的影响，为此本文对其进行了动态调整.

惯性权重ω取决于粒子之前速度对当前速度影响程度的大小，能够有效地平衡算法全局搜索和局部搜索能力.如果ω=0，则粒子速度由当前位置所确定，速度本身并不存在记忆，因此很容易陷入局部最优.而ω≠0时，ω较大的惯性权重可以加强全局寻优能力，反之可以加强局部搜索能力，为了提高算法的搜索性能，本文采用一种新的惯性权重，其更新公式如下

(5)

上式中，ω(t)随着迭代次数而变化.在本文中，p1为最大迭代次数的三分之一；p2取值为10；ωmax取值为0.5；ωmin取值为0.4；t为当前迭代次数.

学习因子决定的是粒子搜索过程中本身学习能力和群体学习能力对粒子运动的影响，反映的是粒子间的信息交流.近年来，许多学者对其进行了修正，有学者提出了异步学习因子，当算法在初始阶段搜索时，会使粒子具有较大的自我学习能力和较小的社会学习能力；并且在搜索后期，能够加强粒子向全局最优位置移动的能力以及获得高质量的粒子，有利于算法收敛到最优解.对于学习因子，本文采用上述的新惯性权重的非线性函数[7]，其更新公式如下

c1(t)=1.167×ω(t)2-0.1167×ω(t)+0.66，

(6)

c2(t)=3-c1(t)，

(7)

由上述公式可以得出，学习因子也随着惯性权重的调整而动态调整.

2.4 时变高斯变异

在解决多目标优化问题时，粒子群算法的快速收敛性未必是优势，反而可能使得种群过早地聚集在某一些粒子周围或某一块区域而丧失多样性，容易使算法出现早熟现象.因此，为了增强群体多样性，避免算法陷入局部最优.本文根据文献[8]的思想，设计一种时变变异算子对外部档案中的粒子进行变异，以产生新的非劣解，其扰动公式如下

(8)

(9)

mut_range=(ub(j)-lb(j))*Pm，

(10)

其中，Pm为变异概率；rg服从均值为0，方差为1的高斯分布；mut_range表示变异的作用范围；ub(j)和lb(j)分别为第j维决策变量的上界和下界；Mr为变异参数，本文取值为0.5.

2.5 CMSMOPSO算法的具体步骤

Step1 初始化群体的位置和速度；设定迭代次数，种群规模，算法参数；

Step2 计算各粒子的适应度值；按照支配关系产生非支配解集；

Step3 更新外部档案集；

Step4 按照拥挤距离对外部档案集每个粒子间进行降序排列，判断是否超出设定的规模数，若超出，则清除规模以外的非支配解；

Step5 更新个体最优位置；如果第一代是，则直接将每个粒子初始位置选取为个体最优值；否则，根据Pareto支配关系更新；

Step6 从排在前20%非支配解的外部档案集中任意选取全局最优位置；

Step7 更新速度公式；如果粒子的速度vi>vmax，则令vi=vmax；如果粒子的速度vi

Step8 更新各粒子下一代的位置，并按照发生概率Pm对各外部档案中的粒子进行时变高斯变异，避免算法陷入早熟；

Step9 判断是否满足条件(最大迭代次数)，如满足则结束循环；否则，返回Step2继续迭代.

3 实验结果与分析

3.1 性能度量

世代距离(GD)是描述算法运算求解得到的非劣解与目标问题的真实Pareto前端之间距离的参数，其数学表达式为[9]

(11)

其中，di表达式如下

(12)

分布均匀度量(SP)是评价算法求解得到的Pareto最优解集中分布性能好坏的一个参数,其数学表达式为[10]

(13)

(14)

上式中，k表示目标函数的个数.SP的值越小，表明算法得到的解的分布性越好.SP的理想值为0,即算法得到的Pareto最优解在目标空间中是均匀分布的.

3.2 测试函数

为了测试CMSMOPSO算法的性能，本文选取经典多目标测试函数进行仿真试验[11].其测试函数表示如下.

(i)测试函数1：ZDT1

搜索空间:x∈[0,1]，维数:n=10.

(ii)测试函数2：ZDT2

搜索空间:x∈[0,1]，维数:n=10.

(iii)测试函数3：ZDT3

搜索空间:x∈[0,1]，维数:n=10.

(iv)测试函数4：DTLZ2

搜索空间:x∈[0,1]，维数:n=10.

(v)测试函数5：DTLZ4

搜索空间:x∈[0,1]，维数:n=10.

3.3 实验分析和比较

通过实验，将本文算法与NSGA-Ⅱ、SPEA2以及MOPSO算法的实验结果进行对比.设置种群规模为100，最大迭代次数为200，外部档案集规模为100，其他每个算法的具体参数设置如表1.其中，pc为交叉概率，pm为变异概率，mu为变异比例，sep为变异步长，ng为网格支配最大粒子个数，cg为交叉比例，aph为膨胀比率.分别将算法NSGA-Ⅱ、SPEA2、MOPSO以及CMSMOPSO在每个测试函数上独立运行10次.各个算法对函数的收敛性(GD)和分布性(SP)比较结果如表2和表3所示.实验都是在win7系统matlab 2012a中完成的.

表1 参数设置

表2 各个算法对每个测试函数的收敛性比较结果

测试函数GD算法NSGA-ⅡSPEA2MOPSOCMSMOPSOAverage1.93E-022.88E-022.21E-026.72E-04ZDT3Worst2.50E-025.05E-022.58E-027.54E-04Std.Dev.3.57E-039.13E-036.40E-034.20E-05Best8.82E-022.24E-028.05E-024.23E-02Average8.97E-022.53E-029.03E-026.55E-02DTLZ2Worst8.89E-022.40E-028.64E-029.05E-02Std.Dev.6.26E-031.32E-033.74E-031.61E-02Best8.38E-021.61E-021.03E-013.15E-01Average9.55E-022.63E-021.07E-013.83E-01DTLZ4Worst1.10E-012.15E-021.05E-014.74E-01Std.Dev.1.25E-025.02E-031.23E-032.57E-02

表3 各个算法对每个测试函数的分布性比较结果

从表2和表3可以看出，在测试函数ZDT1-ZDT3上，CMSMOPSO算法所得的Pareto前端无论是收敛性指标还是分布性指标都要比其他算法好；相比NSGA-Ⅱ和SPEA2算法，CMSMOPSO和MOPSO算法所得结果有很大提升，并且CMSMOPSO算法所得结果明显优于MOPSO算法.在测试函数DTLZ2和DTLZ4上，CMSMOPSO算法在收敛性指标和分布性指标上所得结果相对较差，有待提高.综上所述，CMSMOPSO算法可以有效地解决多目标优化问题.

图1 NSGA-Ⅱ对ZDT-1的测试图 图2 SPEA2对ZDT-1的测试图

图3 MOPSO对ZDT-1的测试图 图4 CMSMOPSO对ZDT-1的测试图

图5 NSGA-Ⅱ对ZDT-2的测试图 图6 SPEA2对ZDT-2的测试图

图7 MOPSO对ZDT-2的测试图 图8 CMSMOPSO对ZDT-2的测试图

图9 NSGA-Ⅱ对ZDT-3的测试图 图10 SPEA2对ZDT-3的测试图

图11 MOPSO对ZDT-3的测试图 图12 CMSMOPSO对ZDT-3的测试图

DTLZ-21.41.210.80.60.40.20000.511.51.510.51stObjective2ndObjectiveTrueParetoCMSMOPSO3rdObjective1.41.210.80.60.40.200.511.51.510.51stObjective2ndObjective3rdObjectiveTrueParetoCMSMOPSODTLZ-4图13 CMSMOPSO算法在DTLZ2所得Pareto前端图14 CMSMOPSO算法在DTLZ4上所得Pareto前端

图1～图12是4种算法各自在ZDT1-ZDT3测试函数上所得到的Pareto解，从图1～图12中可以明显看出，CMSMOPSO算法所得到的Pareto解集都要比NSGA-Ⅱ、SPEA2和MOPSO算法好；NSGA-Ⅱ、SPEA2和MOPSO算法有部分解明显偏离真实Pareto前端；在多样性方面，对ZDT3测试函数，可以观察到MOPSO算法的均匀性较差，而NSGA-Ⅱ、SPEA2和CMSMOPSO算法的均匀程度较好.图13～图14是CMSMOPSO算法在DTLZ2和DTLZ4上所得Pareto解，从图可以明显看出，CMSMOPSO算法所得Pareto解的均匀程度较差，需要进一步提高.综上所述，CMSMOPSO算法在部分函数上所得到的Pareto解显著优于其他三种算法.

4 结论与展望

为了解决多目标粒子群优化过程中各个解之间存在的资源争夺和冲突，算法由于趋同性而带来的早熟无法收敛等缺点，提出了一种基于竞争机制策略的多目标粒子群优化算法.通过引入竞争机制策略和动态调整粒子参数，避免算法陷入局部最优解.在算法后期引入时变高斯变异，提高了算法的多样性.实验结果表明，对两个目标测试函数，CMSMOPSO算法在两个指标上的性能显著优于其他经典多目标算法，但对三个目标测试函数，CMSMOPSO算法所得结果并不理想，需要进一步改进CMSMOPSO算法的性能，使其解决更多的多目标优化问题.