李艳丽，黄天民,刘雅雅

(西南交通大学, 数学学院，四川 成都 610031)



一种新型的带有小生境技术和精英集策略的多目标粒子群算法

李艳丽，黄天民,刘雅雅

(西南交通大学, 数学学院，四川 成都 610031)

摘要：为提高多目标粒子群算法的有效性和运行效率，利用小生境技术求解适应度，采取轮盘赌的方法根据精英集中各个粒子的适应度选取全局最佳位置，提出一种新型的带有小生境技术和精英集策略的多目标粒子群算法。论文对算法运行的过程作了调整，加入小概率变异方法，采用测试函数验证算法的有效性。结果表明，在相同的实验环境中本文算法的运行时间为2.113 s，比基于粒子群的多目标优化算法(4.157s)缩短近一半，即本算法的运算效率大大提高了。仿真结果还表明本文中的算法不仅有很好的收敛性，所得的解还有较好的均匀性。

关键词：多目标优化;小生境技术;小概率变异;粒子群;精英集

多目标优化问题中各目标之间通常相互制约，对其中一个目标优化必须以其他目标的损失为代价，多目标优化问题的解并非唯一，而且很难评价多目标问题解的优劣性。随着多目标问题研究的深入,对解的精度要求也越来越高，粒子群算法作为一种新而有效的算法因其概念简单, 控制参数少, 寻优结果与初值无关,具有一定的并行性，一直备受关注。

粒子群优化算法(particle swarm optimization ,PSO)是由Eberhar等于1995年提出的一种进化计算技术,其源于鸟群群体运动行为的研究[1]。当前，已经有一些学者提出了基于PSO的多目标粒子群算法，例如:2005年李宁等提出了基于粒子群的多目标优化算法[2];同年，Coello 等又提出了多目标粒子群算法(简称CMOPSO)[3];2012年，凌海风等提出了改进的约束多目标粒子群算法[4];邢小红等[5]设计了一种基于邻域最大拥挤距离的全局极值选择算子和基于差分进化的精英种群自学习算子对多目标粒子群算法进行了改进 。但是传统的粒子群算法在多目标求解方面还有待于进一步的研究，比如粒子群算法本身在全局搜索和收敛方面也还有一定的不足，运算复杂度还比较高，运算时间还比较长。文献[2]虽然提高了解的均匀性，但也增加了运算的复杂性、延长了运算时间；文献[6]中增强了解的全局性，但是优化的策略仍有待于改善。 本文在文献[2，6]的研究的基础上，旨在降低粒子群算法运算的复杂性、减少运算时间，提高算法的效率，在原有的算法中加入了边界限制和拥挤距离策略。

1多目标优化问题及其相关概念

一般的多目标问题可以描述如下：

minf(x)=min{f1(x),f2(x),f3(x),…,fn(x)}，

(1)

s.t. x∈S={x|g1(x)≤0,1=1,2,…,p}。

其中：x=[x1,x2,x3,…,xm]T为m维决策变量，fk(x)(k=1,2,…,n)表示第i个目标函数；g1(x)≤0,(1=1,2,…,p)表示第j个不等式约束条件，(由于等式约束在求解的过程中通常转化为不等式约束，故此省略)S为决策变量的可行域。

占优：对于决策变量x、y,若有fk(x)≤fk(y)，(k=1,2,…,n),且至少有一个k使得fk(x)

Pareto最优解(非劣解)：如果在决策空间里没有其他解比x*占优，则称x*为多目标优化问题 Pareto最优解(或Pareto非劣解)。

2改进的多目标粒子群算法

文献[1]提出的粒子群算法是基于鸟群迁徙行为的思想。假设现有一个由N个粒子组成的群落，每个粒子i的位置都是决策空间的一个m维的向量，记为xi=[xi1,xi2,xi3,…,xim]T(i=1,2,…,N)，各个粒子的适应值可由xi代入目标函数或适应度函数求得，由适应值的大小判断粒子的优劣。把每个粒子的当前最优位置(与最优值对应)与历次选代中的最优位置进行比较，得出个体历史最优位置。第i个粒子在算法搜索过程中的历史最优位置记为Xipb=[xi1pb,xi2pb,xi3pb,…,ximpb]T，全体粒子的历史最优位置记为Xigb=[xi1gb,xi2gb,xi3gb,…,ximgb]T，每个粒子i也有各自相对应的速度，记为Vi=[vi1,vi2,vi3,…,vim]T(i=1,2,…,N)。

在粒子群算法的求解过程中粒子的速度和位置更新公式如下：

(2)

xid(t+1)=xid(t)+vid(t+1);

(3)

Vmax=[v1max,v2max,…,vmmax]T。

(4)

式中：Vmax为常数；c1、c2称为学习因子，为非负常数；ri1,t、ri2,t为0和1之间的随机数；w称为惯性权重，当选择较大的惯性权重时，粒子群算法通常因为粒子偏离全局最优位置和自己的历史最优位置而具有较好的全局搜索能力，较小的惯性权重就不利于全局搜索。

本文借鉴文献[2]中适应度求解的思想，在可行解空间中随机初始化粒子群，选取非劣解“粒子”构成精英集P，精英集在粒子更新的过程中可以指导粒子的“飞行”。通过小生境技术求解精英集中粒子的适应度，粒子的聚集程度越高，粒子的适应度就越小。第i个粒子的适应度定义如下：

(5)

其中，j∈P,s(d(ij))为P中第i个粒子和第j个粒子的适应度分享函数：

(6)

式中：σshare为小生境半径，在计算时可预设为常数；α为常数。

本算法采取轮盘赌的方法根据精英集中各个粒子的适应度选取全局最佳位置，在算法迭代过程中，具有全局最佳位置的粒子指导其他粒子按照公式(2)—(4)更新各个粒子的位置和速度；每次迭代之后，选取所得粒子中的非劣解加入到精英集中，这样精英集中的粒子数会因迭代次数的增加而不断增加，从而影响算法的运行速度；因此，当精英集中的粒子数超过精英集的最大容量时，根据适应度公式(5)计算精英集中各粒子的适应度，删除其中适应度较小的个体粒子。当算法满足终止迭代条件时，精英集的粒子即可认为是所求的Pareto最优解。

改进后的算法具体步骤如下：

1)设置粒子群的种群规模N，最大速度Vmax，精英集的容量M，预设M=∅，迭代次数t=0，设定算法终止的条件(迭代次数达到预先设定值)，随机初始化粒子的位置、速度，计算各粒子的目标函数值，得出初始解。

2)选取粒子群中的非劣解加入精英集中，利用式(5)计算精英集中各粒子的适应度。

3)当迭代次数小于最大迭代次数，执行步骤4)至7)，否则跳出循环，算法结束。

4)根据精英集中各个粒子的适应度选取全局最佳位置Xigb，按照公式(2)—(4)更新各个粒子的位置和速度，再次计算种群内每个粒子的目标函数值。

5)选取粒子群中的非劣解加入精英集中，利用式(5)计算精英集中各粒子的适应度，并且删除精英集中适应度小的劣解，保证精英集中的个体数不超过其最大容量。

6)如果当前粒子的位置优于其历史最佳位置的粒子Xipb，则用当前的粒子替换Xipb，如果当前粒子的位置既不优于也不劣于其历史最佳位置的粒子，则按照50%的概率替换或保持Xipb，对于劣于Xipb的粒子，按照5%的几率进行变异操作，即再次初始化该粒子。

7)如果群体中某个粒子当前的位置优于全体粒子的历史最佳位置Xigb，则更新，否则保持全体粒子的历史最佳位置Xigb不变。

8)最后所得的精英集即为所求的Pareto最优解集。

本算法在求解过程中加入限制条件(如步骤中的Vmax，精英集的容量M)，在步骤6)中改善了变异机制。

3实例验证算法的有效性及结果分析

为了验证本文算法的有效性，本文采用了测试函数，在算法运行的过程中群粒子数和迭代次数根据函数的复杂程度选取，对每个函数均做50次试验以消除随机性。

测试函数1(Schaffer函数)：

minf1(x)=x2，-3≤x≤3；

minf2(x)=(x-2)2，-3≤x≤3。

测试函数2(K.Deb函数)：

minf1(x)=x1，

minf2(x)=g(x)×h(x)。

其中：

1(xi2-10·cos(4πxi))；

-5≤xi≤5,x=(x1,…xi,…xn)。

算法选取的参数如下：

w=0.729,c1=c2=1.495,σshare=0.48,α=1.2,P=200。

结果分析：对于测试函数1、2(参数n取2)，当粒子数和最大迭代次数均取50时，所得的解99%均为Pareto最优解，而且解的均匀性也比较好，算法所得结果在解的均匀性、错误率和分散性方面和文献[2]基本一致。由运算结果可知，本算法的收敛速度要比标准的粒子群算法快了许多，而且在相同的实验环境下本文算法的运行时间(2.113 s)比文献[2]运行时间(4.147 s)缩短了近一半，即本算法的运算效率大大提高了。

图1和图2分别为测试1和测试2的某一次的运行结果，即Pareto边界。

图3为在一次实验时的2种算法的贴近度收敛情况：(虚线为本算法，实线为文献的算法)由图3可以看出本算法的收敛性确实具有一定的优越性。

图1　测试函数1的Pareto最优解

图2　测试函数2的Pareto最优解

图3　实验时的2种算法的贴近度收敛情况

4结论

本文在基本粒子群算法的基础上，结合了小生境技术和精英集策略的优势，采用了轮盘赌的方法，在算法运行的过程中加入了小概率变异策略，使得粒子群算法具有更好的全局搜索能力、收敛性，并且算法所得到的Pareto最优解分布也更均匀，最重要的是，本算法的运算效率大大提高了。但是本文设计的算法在保持解的多样性方面还有待于进一步研究，把算法用于解决实际问题也是下一步将要进行的工作。

参考文献

[1]KENNEDY J,EBERHART R. Particle Swarm Optimization[C]//Proceeding of IEEE International Conference on Neural Networks.Perth:[s.n.],1995:1942.

[2]李宁,雏丹. 基于粒子群的多目标优化算法[J]. 计算机工程与应用, 2005(23): 43.

[3]COELLO C C A, PULIDO G T, LECHUGA M S. Handling Multiple Objectives with Particle Swarm Optimization[J]. IEEE Trans on Evolutionary Computation, 2004, 8(3): 256.

[4]凌海风,周献中. 改进的约束多目标粒子群算法[J]. 计算机应用, 2012, 32(5): 1320.

[5]邢小红,罗军刚. 基于改进多目标粒子群算法的水库防洪调度[J]. 计算机工程与应用, 2012, 48(30): 33.

[6]肖乐,吴相林. 自适应混沌粒子群优化的粮食应急点选址研究[J]. 河南工业大学学报(自然科学版)，2012, 33(4): 77.

[7]崔逊学. 多目标进化算法及其应用[M].北京:国防工业出版社,2006:279.

[8]王维博,林川. 粒子群算法中参数的实验与分析[J].西华大学学报(自然科学版), 2008,27(1):76.

[9]张其亮,陈永生,韩斌,等. 改进的粒子群算法求解置换流水车间调度问题[J].计算机应用,2012,32(4):1022.

[10]刘淳安. 带Levy变异的约束优化PSO算法[J].西华大学学报(自然科学版),2008,27(2):72.

[12]SHI Y, EBERHART R C. AModified Particle Swarm Optimizer[C]// The 1998 IEEE International Conference on Evolutionary Computation Proceedings .IEEE World Congress on Computational Intelligence. Piscataway: IEEE Press, 1998: 69.

(编校：叶超)

A New Multi-objective Particle Swarm Algorithm with a Niche Technology and Elite Set Policies

LI Yanli, HUANG Tianmin, LIU Yaya

(InstituteofMathematics,SouthwestJiaotongUniversity,Chengdu610031China)

Abstract:In order to improve the effectiveness and efficiency of the multi-objective particle swarm optimization (pso) algorithm, by using niche technology to solve the fitness, this paper puts forward a new kind of multi-objective particle swarm optimization (PSO) algorithm with a niche technology and elite set strategy. the fitness was solved with niche technology and the roulette method was utilized to select global best position with the fitness of each particle of elite set .The adjustment in the process of algorithm running was made in this paper and the small probability variation method was also used. Finally, the test function was adopted to verify the effectiveness of the algorithm. The results show that the algorithm running time is 2.113 s, multi-objective optimization ratio on particle swarm algorithm(4.147s) was reduced by neraly half, and that the operation efficiency of the algorithm is greatly improved. The simulation results also show that the algorithm has better convergence and the solution has better uniformity.

Keywords:multi-objective optimization; niche technology; small probability variation; PSO; elite set

doi:10.3969/j.issn.1673-159X.2016.01.015

中图分类号：TP18

文献标志码：A

文章编号：1673-159X(2016)01-0073-04

基金项目：中央高校基本科研业务费专项资金(swjtu11zt29)。

收稿日期：2014-09-09

第一作者：李艳丽(1988—),女,硕士研究生，主要研究方向为优化与决策-多目标优化。

·计算机软件理论、技术与应用·