基于代理模型的双层粒子群优化算法

龚德志++孙美建++李泽江

摘 要：为了克服粒子群优化算法计算量大和传统代理模型优化方法易陷入局部最优的缺点，本文提出一种在父级量子粒子群中引入繁殖筛选与嵌入子级优化策略的双层粒子群优化算法，实现了子代粒子基于Kriging代理模型的精准更新。对多种基准函数测试以及翼型优化算例表明，该算法可大幅度降低计算量，并有效地保持多样性提高优化精度，大大提高了优化算法的工程实用性。

关键词：粒子群优化算法；量子行为；Kriging代理模型；繁殖；多样性

DOI：10.16640/j.cnki.37-1222/t.2017.15.211

1 引言

粒子群优化算法（Particle Swarm Optimization，PSO）[1]是由Kennedy和Eberhart于1995年提出的一种模拟鸟群觅食行为的群体智能优化算法，该算法实现简单，操作方便，收敛速度快，能有效解决复杂优化问题，在函数优化、神经网络训练、模糊系统控制、模式识别等领域得到了广泛应用[2]。但是与其他随机优化算法一样，标准粒子群算法（Standard PSO，SPSO）也存在早熟收敛现象。对此，研究人员发展了很多增加种群多样性或加强局部搜索的改进算法以提高优化精度，例如根据群体适应度方差自适应变异的PSO算法[3]，引入克隆选择思想的免疫PSO算法[4]，组织进化PSO算法[5]，协同PSO算法[6]等。另外，采用动态惯性权重因子[7]或用优良粒子替换差的粒子[8]等方法可以加速收敛。

然而各种随机优化算法在解决实际工程问题时仍然面临着计算量太大的局限性。以航空工程中翼型优化为例，现有优化算法一般需要对数千个翼型进行计算才能得到满意的优化结果[9-10]，而通常对每个翼型数值计算需耗时数分钟，当进行变量更多、计算要求更高的三维气动外形优化时总计算量变得更难以接受。对此，研究人员发展了基于代理模型的优化方法，用优化算法寻找代理模型的最优解，可大幅度降低计算次数，但是该方法严重依赖于代理模型的精度，容易陷入局部最优。因此，本文的研究重点是在保证优化精度的前提下，将总计算次数大幅降低到可接受的范围以内。

2 标准粒子群与量子粒子群算法

2.1 标准粒子群算法

粒子群优化算法模拟鸟群飞行觅食行为，在每个粒子发现的最优解和整个粒子群最优解的引导下迭代搜索到全局最优解。首先随机初始化粒子种群位置和初速度，然后计算出每个粒子的适应值，每个粒子记住自身所找到的个体最优粒子pbest以及迄今为止找到的全局最优粒子gbest，用粒子当前速度、pbest和gbest的位置来更新粒子速度，从而在下一个时刻粒子能飞行到新的位置进行搜寻。

粒子群算法具有认知、社会及平衡功能，简单高效具有较强的全局搜索能力，但容易陷入局部最优。惯性权重因子对算法收敛性能有很大的影响，较大的值有利于跳出局部最优，较小的值有利于算法收敛，因此Shi Y采用随迭代进行惯性权重因子减小的方法，在算法初期增强全局搜索能力，而后期加快收敛速度。

粒子群算法还应限制粒子最大速度以防止粒子运动发散，一般做法是当速度超过规定最大速度时将粒子速度调整为最大速度，本文用粒子当前速度对最大速度求余。有学者对粒子飞出变量边界的情况采用在边界上反弹的方式将粒子重新归到变量区域内。本文编制了线性减小惯性权重因子的标准粒子群算法（SPSO），并采用反弹方式约束边界以及求余方法约束最大速度。

2.2 改进的量子粒子群算法

QPSO与标准PSO一样也存在早熟的趋势，Kong等人的研究表明每个粒子通过学习自身的pbest和其他粒子的pbest以及gbest进行下一步搜索，可以保持种群多样性，提高算法性能。

本文在此基础上提出进一步改进的量子粒子群算法（MQPSO）：每个粒子计算完成后立即更新pbest、gbest、mbest，并根据pbest进行排序，每个粒子仅向优于自身pbest的粒子学习，而且排名越靠后的粒子向其他粒子学习的程度越高。由此通过提高算法对信息的利用率，加快收敛速度。

3 基于代理模型的优化框架

3.1 Kriging代理模型与传统代理模型优化框架

实际的工程优化问题往往需要付出巨大的计算代价，因此出现了二次响应面、Kriging模型、径向基函数模型、人工神经网络模型等近似模型预测真实解的代理模型方法。

代理模型方法可以根据已有的点预测未知点的函数值分布情况，当代理模型达到一定精度时，可代替真实求解用于工程优化。优化与代理模型相结合也成为研究热点，传统的代理模型优化框架如下：首先用一定数量的样本点构造代理模型，优化找到代理模型的最优解并与真实值对比，若不满足收敛要求则用新计算的真实值更新代理模型，直到优化结束。该方法严重依赖于代理模型预测的精度，对于复杂的高维度优化问题极容易陷入局部最优。只有当代理模型的样本点数量达到一定级别，并且合理地分布在解空间中才能获得较高的精度，对样本点数量的需求将随着维数和问题复杂程度增加而急剧上升，与优化问题一样，代理模型方法的计算量也将变得难以接受。

3.2 基于Kriging代理模型的双层量子粒子群优化算法

虽然代理模型预测精度有限，但是往往能较好地反映出真实解的大体情况。为了将代理模型获得的信息充分用于优化，本文设计了如下基于Kriging代理模型的双层量子粒子群优化算法（KMQPSO），该算法由两层MQPSO算法构成，并以Kriging代理模型为联系媒介。

首先在变量空间均匀产生具有Q个粒子的粒子池，通过真实计算获取适应值，然后从中选取适应值最好的M个粒子作为父级MQPSO的初始种群，对种群中每个粒子按照MQPSO更新位置的方法繁殖X个个体（公式1中为（0，1）的随机数，所以该X个个体位于不同的进化位置），此时用已计算的粒子构造Kriging代理模型预测繁殖的粒子，选出适应值最优的粒子，计算该粒子与父级粒子种群中最近的粒子的“欧氏距离”，据此确定一个合适的阀值半徑R，以为中心R为半径产生一个变量区域，在该区域中嵌入种群规模为m迭代代数为n的子级MQPSO进行优化寻找代理模型的最优解，将该解作为正式进化的个体进行真实的适应值计算，完成后立即更新pbest、gbest、mbest和代理模型，直到N代父级MQPSO优化结束。KMQPO算法流程如图1所示。endprint

阀值半径R由公式1确定：

（2）

其中，Dim为变量维数，为控制半径的系数，一般可取0.5到0.8，以各粒子的子级区域能覆盖父级的进化区域，而相互之间又不产生过多的重叠为宜。

KMQPSO算法中具有Q个粒子的粒子池用于获得初始代理模型样本点，可以通过实验设计方法或约束由“欧氏距离”表述的相似度在解空间产生初始样本点。根据适应值排序原则选择M个粒子的方法可获得优良的初始种群而且这些粒子较均匀地分布在解空间，有利于避免陷入局部最优。粒子的繁殖策略可以为子级MQPSO筛选优良的局部区域，嵌套的子级优化则有助于找到代理模型的局部最优。通过粒子的繁殖筛选和局部优化，将要进行真实计算的粒子精准地定位于代理模型的局部最优，通过迭代更新不断提高代理模型在最优解附近的预测精度，从而收敛速度更快，而又能保持多样性保证优化精度。

3.3 KMQPSO算法参数设置

KMQPSO算法中引入了较多的设置参数，以下讨论各参数对优化搜索的影响。该算法从本质上可以理解为对代理模型所描述的各个局部最优点进行搜索，并且优秀的局部得到的搜索更多。代理模型能描述多少个局部最优和采用多大的种群规模M进行搜索需要合理地配置，当优化对象比较复杂时设置较大的M。粒子的繁殖数量X增加以及子级MQPSO优化算法的种群规模m和代数n增加都会带来多样性的降低，合理地做法是在优化的初期进行少量的繁殖和较低精度的子级优化以保持多样性，后期则增加繁殖数量提高子级优化的精度以加快搜索。当优化对象相对容易时可采用更大的X、m和n来进行快速搜索。

4 仿真实验与分析

4.1 测试函数

为了比较KMQPSO与SPSO、QPSO、MQPSO的搜索效果，选取以下6种常用基准函数进行测试。

（1）Alpine二维多峰值函数。

（3）

x在（0，12）上最小值为-1.271

（2）Sphere单峰值函数。

（4）

其中n=15，x在（-10，10）上最小值为0

（3）Griewank函数。

（5）

其中n=15，x在（-50，100）上最小值为0

（4）Rastrigrin函数。

（6）

其中n=30，x在（-2.5，5）上最小值为0

（5）Rosenbrock函数。

（7）

其中n=10，x在（-5，10）上最小值为0

（6）Ackley函数。

（8）

其中n=10，x在（-5，10）上最小值为0

4.2 仿真结果与分析

SPSO惯性权重因子随迭代进行由0.8线性减小到0.3，学习因子。量子粒子群收缩扩张系数随迭代进行由1.0线性减小到0.5，向其他粒子学习的程度根据适应度优劣排名由0.2增加到0.9。KMQPSO中总共计算次数Number=初始粒子数Q+种群规模M×代数N，其它算法中Number=种群规模M×代数N。

二维Alpine函数在（0，12）区域有8个极小值8个极大值，最小的极值点坐标为（11.0001，11.0001），大小为-1.271。用该函数对MQPSO、KMQPSO以及传统代理模型优化框架各进行100次测试，每次优化共计算150个粒子。对MQPSO算法而言，150个粒子的计算量还不足以进行有效的搜索，所以找到全局极小值点的概率仅为9%。传统代理模型优化方法以很快的速度找到某个极小值，之后适应值几乎不再变化，找到全局极小值的概率为33%。KMQPSO算法找到全局最优的概率为71%。

用SPSO、QPSO、MQPSO算法对公式4-8五种基准函数各进行2000次优化，用KMQPSO各进行50次。表1给出四种优化算法所获得的统计平均适应值。统计结果表明QPSO对多数函数的优化性能要优于SPSO，MQPSO则有进一步的提高。KMQPSO算法表现出了更为优秀的性能，在收敛到相同精度的前提下，对Sphere、Griewank、Rastrigrin函数优化的计算次数还不到其它算法的7%，对Rosenbrock和Ackley函数也分别降低到27%和60%。

为了比较不同计算次数对搜索精度的影响，统计四种算法优化10维Rosenbrock多峰值函数采用不同算次数所获得的平均适应值，粒子群基本设置.

4.3 翼型优化算例

翼型对飞行器的气动性能具有重要的影响，采用高精度的数值计算方法进行翼型优化已经成为研究热点。本文采用10个设計变量的Hicks-Henne函数参数化翼型，采用k-ω雷诺平均N-S方程求解绕翼型流场，在笔者的双核PC机上每个翼型数值计算需要244秒，以RAE2822为初始翼型，保持翼型最大相对厚度不变，设计状态为巡航马赫数0.73，雷诺数2.1E7，设计升力系数Cl=0.70，采用适应值加权组合方法以降低阻力系数Cd和力矩系数Cm的绝对值为优化目标。KMQPSO算法作180次数值计算的优化结果要优于MQPSO作210与540次计算的优化结果，设计翼型与初始翼型压力分布对比，设计翼型具有理想的无激波的压力分布，说明本文算法是有效的。在整个优化过程中KMQPSO算法大约用了5分钟时间来构造代理模型和子级量子粒子群优化，在优化精度相同的情况下，总的优化耗时只有MQPSO算法的1/3。

5 结论

本文提出基于代理模型的双层粒子群算法KMQPSO，在父级改进的量子粒子群MQPSO中引入繁殖筛选与嵌入子级MQPSO策略，对子代粒子进行基于Kriging代理模型的精准更新，从而实现快速有效的搜索。对多种基准函数仿真测试表明，该算法避免了传统的代理模型优化方法易陷入局部最优的缺点，与SPSO、QPSO和MQPSO等相比可大幅度降低优化的计算次数。翼型优化算例表明KMQPSO可大大提高优化算法的工程实用性。endprint

参考文献：

[1]Kennedy J， Eberhart R C. Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks Perth， WA， Australia，1995：1942-1948.

[2]蘇守宝，汪继文，方杰.粒子群优化技术的研究与应用进展[J]. 计算机技术与发展，2007，17（05）：249-253.

[3]吕振肃，侯志荣.自适应变异的粒子群优化算法[J].电子学报， 2004，32（03）：416-420.

[4]李莉，李洪奇，谢绍龙等.基于克隆选择的免疫粒子群优化算法[J].计算机科学，2008，35（10）：253-255.

[5]丛琳，沙宇恒，焦李成. 组织进化粒子群数值优化算法[J].模式识别与人工智能，2007，20（02）：145-153.

[6]Van den Bergh，F.Engelbrecht A P. Effects of swarm size on cooperative particle swarm optimisers[C].In Proceedingd of

（下转第276页）

（上接第231页）

the Genetic and Evolutionary Computiaion Coonference，San Francisco，USA，2001.

[7]虞斌能，连志刚，焦斌.动态惯性权重粒子群优化算法[J].上海机电学院学报，2008，11（03）：169-172.

[8]Angeline P J.Using seleetion to improve partiele swarm optimization[C].In Proceedings of the IEEE InternationalConference on Evolutionary Computation，1998， 84-89.

[9]王晓鹏，高正红.跨音速翼型和机翼的气动优化设计[J].应用力学学报，2001，11（02）：90-93.

[10]夏露，高正红.一种单亲DNA 算法在翼型设计中的应用[J].空气动力学学报，2009，27（03）：335-339.endprint