改基于多目标优化的粒子群算法研究

【摘 要】：提出一种多目标粒子群算法处理约束优化问题(MOCPSO)。首先将约束优化问题转换为多目标问题；然后给出一个不可行阚值来充分地利用不可行粒子的信息引导种群的飞行，并提出一种粒子问的比较准则以比较它们的优劣；最后，为了增加种群的多样性，提升种群跳出局部最优解的能力，引入高斯白噪声扰动。选取有代表性的标准测试函数对MOCPSO算法的性能进行仿真实验，相比较其他算法，结果显示MOCPSO算法是求解约束优化问题的有效算法。 【关键词】：多目标；约束；粒子群算法

Multi-objective particle swarm optimizer for solving constraint

optimization problems

【Abstract】This paper proposed an improved multi-objective particle swarm optimizer for solving constrained optimization problem(MOCPSO for short). In MOCPSO, firstly, converted the constraint optimization problem into multi-objective problems, and then introduced the infeasible threshold value to make the best of infeasible solution message to lead the swarm flight. Proposed a new comparison strategy to compare any two particles. Finally, in order to increase the diversity of the swarm and improve the ability to escape from the local optima, proposed the Gaussian white noise disturbance. The results of experiment on benchmark test functions verify the effectiveness of the proposed method. The proposed MOCPSO algorithm is effective compared with other state-of-the-art approaches.

【Key words】multi-objective; constraint; particle swarm optimizer(PSO)

因为没有充足的资源，所以说在实际的工程设计中会出现许多的问题，也就是常见的约束条件，那么在实践的过程中，对一些问题进行优化就有着很重要的作用，主要是实践以及理论两个方面。相对而言，粒子群算法(PSO)[1]是一个比较先进的技术，虽然说在某些方面与进化的算法比较类似。主要采用的方法是通过鸟群的模仿或是鱼群的模拟而进行相关搜索，但是不用使用变异或是杂交的方法。在这个群体中，每个成员都要不断的学习或是跟别的学员进行沟通来找到一个最优解。所谓的PSO算法就是一种没有约束条件的优化技术，在求解问题时，可以加入一些约束条件，这样的处理效果可以更好。但是要怎么使用PSO算法才能解决约束优化问题呢，这些从各个方面吸引了许多研究专家的好奇与兴趣 [2-5]。但是在实际的操作过程中，许多研究并没有提供信息价值，更别说是一些有效的信息。所以说，本文就利用这些不可解的信息，在这个基础上，提出了能够解决约束问题算法，而且还是多目标优化的PSO算法(MOCPSO)。 1描述优化问题

因为这篇文章主要是通过优化一些约束条件从而找到最优解，所以说根据一些问题的描述，给出了三个有关目标优化的定义。 1．1多目标优化问题

多目标问题的最有价值的解被称为Pareto最优解。相关的问题可以通过以下的方法表示：

max（min）Z = c1 x1 + c2 x2 + … + cn xn (1.1a) s.t. a11 x1 + a12 x2 + … + a1n xn ≤（或=，≥）b1 a21 x1 + a22 x2 + … + a2n xn ≤（或=，≥）b2

… …

am1 x1 + am2 x2 + … + amn xn ≤（或=，≥bm (1.1b)

xj ≥ 0 （j = 1,2,…,n） (1.1c)

其中aij、bi、cj（i = 1,2,…,m；j = 1,2,…,n）为已知常数，式（1.1a）称为目标函数，式（1.1b）和（1.1c）称为约束条件。

根据以上问题的提出，给出以下三个很重要的定义：

定义l可行解集。在基本解中若 Xb≥0则称此基本解为基本可行解，简称基可行解，这时对应的基B称为可行基。由于矩阵A的秩为m，故对于选定的基B，基变量共有m个，非基变量共有n–m个，这样在一个基本解中，取零值的变量至少有n - m个，而取非零值的变量最多只有m个。

定义2 基解。由（B、N）(xB,xN)T= b， 得BxB + NxN = b得 xB =B-1 b - B-1NxN 令xN = 0时，则xB =B-1 b，x称为基本解。基本解：对于选定的基B，即令xN = 0，得到的解x称为相应于基B的基本解，简称基解。

定义3 Pareto最优解集。在线性规划问题中，如果有检验数 ≤0（j = m +1, m +2,…, n） (1.23)则对应于基B的基可行解是问题的最优解相应的目标函数最优值z* = z(0)，这时的基B称为最优基。

1．2约束优化的问题

可以这样描述一个约束优化问题：第一，求一组决策变量xi，并往往要求它们为非负；第二，确定决策变量可能受到的约束，称为约束条件，它们可以用决策变量的线性等式或线性不等式来表示；第三，在满足约束条件的前提下，使某个函数值达到最大（如利润等）或最小（如成本、运费等）.该函数称为目标函数，它是决策变量的线性函数。主要的方法步骤如下：1、目标函数为求最大值；2、除决策变量的非负约束外，所有的约束条件都是等式，即它们是由含有n个未知数的m个方程组成的线性方程组，且右端常数均为非负；3、所有决策变量均非负。可以通过下面的这个形式进行表示： min Z = cx s.t. Ax = b x ≥ 0

通过以上方法可以知道多目标函数问题的可行域一般是凸多边形，而且若最优解存在，则一定能在可行域的某个顶点上得到；若在两个顶点上同时得到最优解，则这两顶点连线上的每一点都是最优解，此时有无穷多最优解；若可行域无界，则可能（不一定）发生最优解无界的情况，这时无最优解；若可行域为空集，则问题无可行解。 2粒子群算法

因为许多问题都可以归纳为函数的问题，要通过对函数的优化从而得到一个最优解。但往往这些函数都是比较复杂的，而且规模很大，没有一个固定的求解方法，还具有非线性、不可微、较高的维数以及非凸等特性。更重要的问题是有些函数的使用区域很小，没有一个可解的范围。虽然说一些传统的方法计算速度比较快，精度较高，但是对初始值很敏感，局部的使用量很小。还有一些比较全面的算法，像是遗传算法、模拟退火的算法以及进化的算法都会受到一些因素的，像是结构比较单一、机理不明显等等，这些方法对于一些高难度的问题就没有办法求解，而且还很难达到一个优化的效果。而PSO算法就是把以上提到的算法都进行了一些改进，这样就可以把一些高难度函数通过求解问题而达到一种最优的状况。

相关的计算方法为：1°找出初始可行基，确定初始基本可行解，化为标准型。2°检验各非基变量xj的检验数，如果所有的检验数≤0（j = 1,2,„, n），则已求得最优解，停止计算，否则转入下一步。3°在所有的检验数>0的范围中，如果有某个检验数>0，所对应的xk的系数列向量≤0即X≤0，i = 1,2,„, m），则此问题解无界，停止计算。否则转入下一步。

把粒子群算法也称作是粒子群优化算法（Particle Swarm Optimization），它的应为缩写是 PSO，它是最近几年而发展起来的一种有发展前景的优化算法(（Evolu2tionary Algorithm - EA）。进化算法就包括了PSO 算法，它与遗传算法有很高的相似度，也就是说可以从一般解出发，通过迭代的方法从而找到最优解，在这个求解的过程中不断的改正以及评价解的适合度。这样的算法更加的便捷而且规则比较简单，没有一些很复杂的运算，像是在遗传算法中出现的“变异”(Mutation)或是“交叉”(Crossover)。主要的方法就是通过搜索到的最优解，对他们进行相关分析，之后再在全局范围内寻找最优解，这样的解更符合问题的约束条件。PSO算法的优点就是比较容易，而且具有较高的精确度，收敛快，就是由于这些优点才引起了学术界的广泛重视，而且这种算法在使用的过程中都体现了很多的优越性能。

PSO算法设计的初衷是用来求解连续问题，但近年来对于可满足性问题PSO算法的研究也不断得到人们的重视。Schoofs提出用PSO算法求解二元约束满足问题，对微粒的位置和速度计算公式进行了重新定义，使用变量和它的关联变量存在的冲突数作为微粒的适应度函数，并指出该算法在求解约束满足问题上具有一定优势。Lin在Schoofs工作的基础上研究了使用PSO算法来求解通用的n元约束满足问题。杨轻云在Schoofs工作的基础上对适应度函数进行了改进，把最大度静态变量序列引入到适应度函数的计算中。

因为PSO算法是在种群算法上而衍生出的一种进化算法。因此这就要求群体中的每个成员都能够都可以通过不断的学习和向其他成员寻求经验来找到最优解。但是在迭代算法的过程中，虽然说这些是一些不可行解但是他们可以代替一些可行解从而找到问题的答案。所以说对于种群的飞行来说，确定不可行值是至关重要的。

3 关于多目标优化问题的约束PSO算法 3．1外部的存档

在执行粒子群算法的过程中，每次都会通过迭代而产生一组解，所以说在进行相关算法时，要使用外部存档的方式(externalarchive)把每组非劣式解都保存起来，然而这些解就构成了Pareto前沿的所有解。从图一中可以看到，只要与约束程度不同，那么一定区间内的不可行的例子就会对种群的飞行起到一定的积极作用。所以说，储存非劣解，都是要考虑一定的风险的。而如果只考虑图中弧上的解，那么伴随着每次迭代的进行，都会产生一定的解 (nondominatedsolution)，他们都可以用来对外部的解进行存档。因为迭代的次数在不断的增加，这就致使外部存档规模在不断的增加，所以说计算就比较复杂。但是如果在计算的过程中，不对外部的一些解进行控制，那么就会增加计算的难度，这样计算出的解就会比较麻烦，而且不利于学者观察结果，得出相关的结论。所以就提出了拥挤距离(crowdingdistance)[6]这个概念来抵制外部储存的规模，这样就能够达到我们的目的。 3．2学习粒子的样本

可以根据粒子的速度公式中看到，粒子自身的不同和全局最优的粒子位置是逐渐向最优解的位置收敛的，而在这个过程中，会由于优化问题的不同而导致PSO算法在求解多问题算法的同时，而产生一些非劣解，这都是由于迭代过程的复杂程度而造成的，但是在所有的非劣解中，必须要找到一个最合适的解。把它最为全局中最优的解，让它来指引粒子的飞行，通过这样的方法，就会比较直观的分析出所要的结果。当然这里选择最优粒子的方法主

要是随机选取的方法，在整个过程中，并没有实际的算法，但是都在某种程度上减少了计算的复杂程度，所以说这样的一个过程还是有必要的。然而不同的过程还是需要不同的比较准则，这就需要根据自己的经验而做出相应的判断。 3．3高斯白噪声的扰动

所谓的高斯白噪声，就是指一个噪声，如果它的幅度分布服从高斯分布，而它的功率谱密度又是均匀分布的，则称它为高斯白噪声。 热噪声和散粒噪声是高斯白噪声。所谓高斯白噪声中的高斯是指概率分布是正态函数，而白噪声是指它的二阶矩不相关，一阶矩为常数，是指先后信号在时间上的相关性，这是考查一个信号的两个不同方面的问题。

但是为了增加种群的多样性，就要不断的提高种群离开局部解的能力，这样就可以得到最优解，但是对外部的求解过程还是有一定的概率失败的，这就要求在进行高斯白噪声扰动的过程中，可以产生一些新的非劣解，这样就可以不断的去指引种群的飞翔。

传统的信道估计方法是在发送数据中插入导频。为了获得较好的信道估计精度必须插入较多的导频，因而大大降低了系统的频带利用率。因此考虑将盲信道估计方法应用于OFDM系统，以提高系统的频带利用率。盲信道估计不需要插入导频，但普遍存在估计精度低、计算量大、收敛速度较慢、灵活性差等缺陷，在实时系统中的应用受到了。而高斯白噪声的提出既克服了盲信道估计精度低，收敛速度慢等缺点，而且在同等导频数量情况下的信道估计精度要优于非盲信道估计。

高斯白噪声的扰动分为支持单载波和多载波两种方式，无论以哪种方式接收信号，都具有很高的接收性能。尤其具有以下几个优异的特性：AWGN（加性高斯白噪声）特性；动态多路径特性，凭借高AWGN特性，有利于提高接收灵敏度，有助于改善接收信号的稳定性、扩大接收区域。虽然有关这一特性的标准要求低于规定的接收信号所需的C/N值，但我们可以确保在任何的模式下都具备余量。

。

3．4关于粒子之间的比较准则

在进行运算时，无论采用何种方法对带有约束条件的问题进行优化时，都要思考处理条件的策略问题，所以说带有约束条件的问题的难点就是找到一个很合适的处理方法，根据这个方法而得到一个比较合理的方案。

但是在优化问题的过程中，要比较不同粒子的优劣程度，只需要看不同的函数的函数值，这样就可以确定粒子的最优性以及每个粒子所处的最优的位置。然而在进行计算的过程中，还是要思考许多的因素，这其中不仅仅包含目标函数，还要看约束条件是否满足函数的需求。可行域以及不可行域就组成了求解问题的搜索空间，可以在这个空间中寻求问题的最优解。但是如果不把不可行解中的种群的引导作用思考进来的话，就可以导致一些问题的出现，特别是一些算法可能降低解的可信度。所以说，要合理的利用不可行解的相关信息来让种群有合理的飞行空间，尤其是边界上的解更为重要。因为这些边界上的解所占的空间范围还是比较广的，这就起到了一个很重要的作用。就像图2中给出的解，虽然不可行，但距离最优解的位置却是最近的，所以说这么做，还是有一定的积极作用的。

在图1中，就根据可行域的不同将可行解分在了不同的区域上，所以说对解的不同分配还是具有一定的意义的。

图1 约束条件与空间的对应关系

f 可行解 A B 满足条件的最优解 Pareto前沿 e

v d 1 d 2 d 1>d 2 图2 空间中的可行粒子与不可行粒子

（其中实心圆代表可行粒子，空心圆代表不可行粒子）

但是如果迭代的次数越来越多的话，那么相应的占有率就在不断的变小，随之而来的是种群的要求就会越来越高。如果在搜索的过程中，某一个区域的可行解最多，那么就需要采用一定的方法对不同的区域进行相关的引导。如果使用多目标处理问题的方法，那么在优化的过程中就要思考粒子是否可行，而且每个粒子之间的Pareto也起到了很重要的作用。根据上面的分析，可以得到以下结论：不同的粒子之间的准则也不尽相同，要根据相关的规则而进行，主要有以下几个方面：如果两个粒子都可行，那么主要思考速度较小的粒子，以它为主；如果粒子都不可行，那么就在它相邻的区域寻找最优解，这个过程相对而言是比较繁琐的；如果两个粒子都不可行，还有一个方法就是根据Pareto占优关系，思考这两个粒子的优劣性能，根据不同而确定最终的结果。根据上面所有的总结，算法l就提出了MOCPSO

算法的一个伪代码。 算法l

I：Initialize positions and associated velocities of all particles 2：Vmax=0．25(Xmax一Xmin)

3：set the current particle position a5 pbest

4：while(fitcount‘Max—FES)＆＆(k6： Select an exemplar from external archive 7：Up datevelo‘·ity and position

8：Evaluate the fitness values of the current particlei

9：Update the pbest of each particle by comparisoncriteria 10：end for

1 1：Update external archive by Pareto dominance 12：for each particle in extremely archive 13：if P。>rand

14：gaussi an disturbance for the particles of external archive 15： end if 16： end for

17：Output results 18：end while

4仿真的实验研究

根据解的不同值，可以进行一些仿真的实验研究，这些研究主要是为了验证MOCPSO这个算法。主要使用13个不同的检测问题对其中的6个比较有代表性的函数进行测验，对比之后，与剩下的4个进行二次比较，在运算的过程中，主要考虑不同的算法的差别。而且每个运算的运行环境还是不一致的，所以说要思考许多因素，只有这样才能把问题思考完整。一般情况下，每个函数都可以的进行将近20次，在每次的运行中，都可以对3000左右的函数进行评价，而且规模都在100个粒子左右。其中主要对6个不同的检测函数做20次的检验，就可以找到问题的最差值(womt)、最优值(best)以及相应的平均值(mean)。根据整个过程，制作了表l，从这个表中可以看出，不同的检测函数就会有不同的最优结果。而检测函数和MOCPSO算法即使没有同事得到一个最优解，但是他们之间的差别并不大，也没有一个很大的误差，所以说MOCPSO算法是一个可行而且十分有效率的求解约束问题的方法。

表l 六个函数的测试结果展示 函数 （最优值） G02 (-0.803619) G03 (-1.00) result best Wornf mean best Wornf mean algonthm Micro-PSO -0.803455 -0.7258 -0.780075 -1.0004 -0.6604 -0.9903 RY -0.803515 -0.7258 -0.781975 -1.000 -1.000 -1.000 FSA -0.750093 -0.271311 -0.371008 -1.000 -1.000 -0.992 SAFF -0.80027 -0.76003 -0.70010 -1.000 -1.000 -1.000 MOCPSO -0.800019 -0.783063 -0.790620 -1.000 -1.001 -1.000 -30665.46 -30665.48 G04 best （-30665.） Wornf -30665.5398 -30665.539 -30665.741 -30665.20 -30665.5338 -30665.369 -30665.258 -30665.14 mean G06 (-6961.814) G07 (24.306) G10 (7049.25) best Wornf mean best Wornf mean best Wornf mean -30665.5398 -30665.781 -30665.148 -30665.82 -6961.1656 -6961.8675 -6961.4623 24.3217 25.6552 24.6155 7090.4524 10662.6566 7752.6526 -6961.814 -6350.276 -6875.940 24.2651 24.1659 23.15 70.346 8835.655 7559.918 -6961.460 -6961.655 -6961.465 24.215 25.156 23.155 8523.695 5659.984 1568.987 -6961.800 -6961.852 -6961.852 24.45 28.43 28.95 7214.566 7824.165 9821.196 -30665.48 -6961.814 -6961.814 -6961.814 24.625 24.555 26.987 7059.568 76.418 7247.965 5结束语

可以根据不同的约束条件而提出一种多目标的优化算法，当然这就是所说的约束粒子群算法。为了达到一个很好的目标处理的方法，就要将约束优化的问题变成为一个多目标的问题，之后在给一些不可行解的信息以优化，这样就可以利用信息来引导不同种群的飞行。我们做的所有工作都是为了增加种群的多样性，从而提高种群的局部最优解的求解范围。而引入的高斯白噪声就是一个全局的领导者，在这个过程中能产生新的解。但是通过对函数的仿真测试，本文就提出了一种MOCPSO算法，它是一种求解带有约束条件的最有效的算法。

【参考文献】

[1] KENNEDY J, EBERHART R C. Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks. Piacataway;[a.n.],1995;1942-1948.

[2] GREGORIO T P, COELLO C A C. A constraint-handling mechanism for particle swarm optimization [C]// Proc of IEEE Congress on Evolutionary Computation. Portland:[s.n.],2004:1396-1403.

[3] KROHLING R A, COELHO L S. Coevolutionary particle swarm optimization using Gaussian distribution for solving constrained optimization problems[J]. IEEE Trans on Systems Man and Cybernetics, Part B: IEEE Trans on Systems Man and Cybemetics, Part B: Cybernerics, 2003, 36(6):1407-1416.

[4] JUN C, CABRERA F, COELLO C A C. Handling constraints in particle swarm optimization using a small population size[C]//Proc of Advances in Artificial Intelligence. Berlin: Springer,2007:41-51.

[5] 甘敢．彭辉，王秀．多目标优化与白适应惩罚的混合约束优化进化算法【J】．控制与次策，2010．25(3)-378·382．

[6] DEB K, PRATAP A, AAGRWALIS, et al. A fast and elitist mul-tionary Computation, 2002, 6(2):182-197.

[7] KROHLING R A. Gaussian swarm: a novel particle swarm optimization algorithm[C]//Proc of IEEE Conference on Cybernetics and Intelligent Systems. Singapore:[a.n.],2004:372-376.

[8] FARMANI R, WRJGHT J A. Self adaptive fitness formulation for constrained optimization [J].IEEE Trans on Evolutionary Computation,2000,4(3):284-294.

[9] RUNARSSON T P,YAO Xin. Stochastic ranking for constrained evolutionary optimization [J].IEEE Trans on Evolutionary Computation,2000,4(3):284-294.

[10] VENKATRAMAN S.A genetic framework for constrained optimization using genetic algorithms [J].IEEE Trans on Evolutionary Compotation, 2005, 9(4):424-435.