混合粒子群优化算法

混合粒子群优化算法

朱冰，齐名军

ZHUBing,QIMingjun

鹤壁职业技术学院，河南鹤壁458030

HebiCollegeofVocationandTechnology,Hebi,Henan458030,China

ZHUBing,QIMingjun.Hybridparticleswarmoptimizationalgorithm.ComputerEngineeringandApplications,2012,48（9）：47-50.

Abstract：UsingParticleSwarmOptimization（PSO）tohandlecomplexfunctionswithhigh-dimensionhastheproblemsoflowcon-vergencespeedandprematureconvergence.Thispaperproposesahybridparticleswarmoptimization.Itadoptsprematurityjudgemechanismbythevarianceofthepopulation’sfitnessandputsgeneconversionandmutationoperatorintoalgorithm.Itconstructsanewindividualandindividualgenefitnessfunction,andwilladapttotheworstgenemutationvalue.Toreducethecomputationoftheproposedalgorithm,itusesquantumdissipativeparticleswarmalgorithmstructure.Experimentalresultsshowthatcomparedwithparti-cleswarmalgorithmwhichhasonlyonefitnessvalue,ithasfasterconvergencerate.Especiallythehybridparticleswarmoptimizationisofstrongabilitytoavoidbeingtrappedinlocalminima,andperformancesarefairlysuperiortosinglemethod.Keywords：ParticleSwarmOptimization;multi-strategymechanism;prematuritymachanism摘

要：针对粒子群优化算法在处理高维复杂函数时存在收敛速度慢、易陷入早熟收敛等缺点，提出了混合粒子群优化算法。它借鉴群体位置方差的早熟判断机制，把基因换位和变异算子引入到算法中，构造出新的个体和个体基因的适应值函数，将适应值最差的基因进行变异。为减少算法计算量，采用耗散的粒子群算法结构。实验表明，该算法比只有一个适应值的粒子群算法具有更快的收敛速度。且具有很强的避免局部极小能力，其性能远远优于单一优化方法。关键词：粒子群优化算法；多策略机制；早熟机制DOI：10.3778/j.issn.1002-8331.2012.09.014

文章编号：1002-8331（2012）09-0047-04

文献标识码：A

中图分类号：TP301

1引言

粒子群优化算法是一种智能全局优化算法，最初由Kennedy

间中的位置表示为一个n维向量，每个粒子的位置代表一个潜在的解。设xi=(xi1xi2xin)为粒子i的当前位置；vi=(vi1vi2vin)为粒子i当前飞行的速度；pi=(pi1pi2pin)

等人于1995年提出并成功地应用于函数优化，在处理比较复杂的高维多峰函数时，存在“早熟收敛”现象和搜索能力不强的问题。目前解决该问题的主要方法是增加粒子群的规模，虽然对算法性能有一定改善，但同样存在缺陷：一是不能从根本上克服早熟收敛问题；二是会大大增加算法的运算量。为了解决以上两个问题，本文首先在算法中引入了基因换位算子和变异算子的概念，即在基因换位两个个体中随机选择多个基因位置进行换位，换位的目的是为了产生适应值更高的个体，从而使各代个体都向前进化。其次采用单个个体组成初始群体，在个体评估的基础上，增加了一种基因评估函数，除了对个体进行评估以外，还对个体的每个基因进行评估。在粒子群算法的变异中，根据基因评估函数选择出最差的基因进行变异，这样，变异后的基因将以较大的概率优于原基因，所产生的后代将以较大的概率优于母体，从而避免了演化的盲目性，加快了求解速度。最后把耗散结构引入粒子群算法中，让个体间的基因换位和变异达到一种能量相互平衡过程，即个体间的基因换位成功数目越多，后代变异的次数越少，这样可以大大减少算法的计算量，加快求解速度。

为粒子i所经历的最好位置，也就是粒子i所经历过的具有最好适应值的位置，称为个体最优位置；pg=(pg1pg2pgn)为整个粒子群迄今为止搜索到的最优位置，称为全局最优位置。将xi带入目标函数就可以计算出其适应值，根据适应值的大小衡量xi的优劣。每个粒子的位置和速度按下述两个公式进行迭代。

vij(t+1)=wvij(t)+c1r1j(t)(pij(t)-xij(t))+

c2r2j(t)(pgj(t)-xij(t))

xij(t+1)=xij(t)+vij(t+1)

（1）（2）

其中，下标j表示粒子的第j维(j=12n )i表示第i个c1、c2为加速度常数，粒子(i=12m )t表示第t代，通常在c1调节粒子向自身最优位置飞行的步长，c2调节0～2间取值，

r2j~U(01)粒子向全局最优位置飞行的步长。r1j~U(0，1)，

为两个相互独立的随机函数。为了减小在进化过程中粒子离

开搜索空间的可能性，vij通常限定于一定范围内，即vijÎ[-vmaxvmax]。如果问题的搜索空间限定在[-xmaxxmax]内，则

2粒子群优化算法

在粒子群优化算法中，假设在一个n维的目标搜索空间

可设定vmax=k×xmax0.1£k£1。迭代中若粒子的位置和速度超出了对其限定的范围，则取边界值。pij(t)-xij(t)代表第i个粒子目前位置到其迄今为止搜索到的最优位置的距离，pgj(t)-

中，有m个粒子组成一个群落，其中第i个粒子在n维搜索空

基金项目：河南省社科联基金项目（No.SKL20103224）。

作者简介：朱冰（1979—），讲师，主要研究领域为人工神经网络和人工智能；齐名军（1976—），讲师。E-mail：[email protected]收稿日期：2010-12-27；修回日期：2011-03-04；CNKI出版：2011-07-20；http://www.cnki.net/kcms/detail/11.2127.TP.20110720.1512.011.html

xij(t)代表第i个粒子目前位置到整个粒子群迄今为止搜索到

的最优位置的距离。公式（1）用于计算粒子的速度，如当前是t时刻，则粒子在t+1时刻速度是由当前时刻的速度、当前位置与该粒子的局部最优位置的距离、当前位置与全局最优位置的距离共同决定的；公式（2）用于计算粒子速度更新后的位置，它由粒子当前位置和粒子更新后的速度决定。所有粒子的初始位置和速度随机产生，然后根据上述两个公式进行迭代，不断变化它们的速度和位置，直到找到满意解或达到最大的迭代次数为止（粒子的位置即是要寻找的解）。

3混合粒子群优化算法

新算法的核心思想包括四部分：基于早熟判断机制、基因

换位算子机制、多适应值函数机制和粒子群算法的耗散结构。早熟判断机制是根据函数在进化过程中对最优解进行早熟收敛而进行的判断。基因换位算子是为了克服个体早熟而处理的优化方法。多适应值函数机制是为克服算法的盲目变异而提出的。粒子群算法的耗散结构是在算法演化过程中，让个体间的基因换位和变异数量达到一种能量相互平衡过程。

3.1PSO的早熟现象及早熟判断机制

算法在搜索过程中，如果某粒子发现一个当前最优位置，

其他粒子将迅速向其靠拢。如果该最优位置为一局部最优点，粒子群就无法在解空间内重新搜索，这就是所谓的“早熟收敛”现象。为解决这个问题，而引入早熟收敛判断机制。该机制由早熟收敛的预防与处理两部分组成，二者相互联系、有机结合，贯穿于整个算法。早熟收敛预防与处理的统一框架见图1。

图1早熟收敛判断机制图

早熟收敛判断是早熟处理的基础。实验证明，粒子群优化算法无论是早熟收敛还是全局收敛，粒子群中的粒子都会出现“聚集”现象，这里将粒子的最佳位置的状态作为早熟收敛判断的条件。设粒子群的粒子数目为m，fi为第i个粒子的位置，favg为粒子群目前的平均位置，α2为粒子群的群体位置方差[1]，定义为：

α2m=åfi-favg

（3）

i=1其中f是归一化定标因子，其作用是限制α2的大小。f的取

值采用如下公式：

f=ìí1max£i£m|fi-favg|, 

1max£i£m|fi-favg

|>1 î1,其他

式（3）表明，群体位置方差α2反映的是粒子群中所有粒子的“聚集”程度。α2越小，则粒子群的“聚集”程度就越大，若算法不满足结束条件，“聚集”将使群体失去多样性而陷入早熟状态，故当α2

3.2基于基因换位算子改进策略

基因换位算子是随机抽取临时储备器Q1和Q2中的两个

体进行换位，然后在换位个体中随机选择换位位置进行换位，

换位算子在算法中起着关键作用，它是产生新个体的主要方

法。换位的目的是为了产生适应值更高的个体，从而使各代个体都向前进化。在本算法中引入的基因换位算子是按一定的概率交换一条染色体中某些位置上的基因，被交换基因的位置是随机的。由于单亲粒子群算法不引入杂交算子，即使种群中各个个体均相同，也不影响算法迭代的进行，摆脱了对群体多样性的要求，简化了进化操作，有效避免了粒子群算法中常见的“早熟收敛”问题。该算法中引入的基因换位为多点换位，即对预先给定的正整数N，取随机数（i1≤i≤N），然后交换i对位置的基因值。

定义1（多点换位算子）首先在母体对的基因串中随机设置多个换位点，然后以一定的概率在换位点所分隔的基因段中进行段交换[2-3]。

引理1基于数值计算方法的“取大”、“取小”换位算子：这种换位方法跟常规“一点”实数型换位方法相比，在数值计算上显示了优越性。具体实施方法如下：

（1）按轮盘选择规则从临时存储器Q1，Q2中分别选出两个个体xi和xj；（2）由xi和xj按位“取大”运算产生一个字串C1；（3）由xi和xj按位“取小”运算产生一个字串C2；例如，选

择的两个个体为xi：85078652，xj=65140698，则由“取大”、运算产生的两个子串分别为：

C1：85178698，C2：65040652

（4）

易知这种换位方法使子代继承了双亲的同型基因。

3.3多适应值函数机制

根据孟德尔的遗传学原理[3]，如果生物体基因发生变异，

则对应生物体相关部位的性质就会发生相应的改变。如果在生物进化过程中尽量保持好的基因不变，而对不良基因加以改造，使之发生突变，这将有助于提高生物体的适应率。在现有的粒子群优化算法中，大多只有一个适应函数，用于指导算法搜索的方向，而其他算法中的变异算子，则采用随机方式来选取，具有一定的盲目性，而这种盲目性最终导致了算法收敛速度的下降。为此本文采用单个个体组成初始群体，在旧的适应值函数的基础上，构造新的个体评估函数和一种基因评估函数，即除对个体进行新的评估以外，还对个体的每个基因进行评估。在单亲粒子算法的变异中，根据基因评估函数选择出最差的基因进行变异，同时为了保证个体不至于陷入局部全优，还以相对较少的概率接受较差的个体和基因。这样，变异后的基因将以较大的概率优于原基因，所产生的后代将以较大的概率优于母体，从而以较高的概率避免了好的基因向不好的基因发生变化的情况发生，加快了求解速度。

定义2（基因亲和度）两个实数个体对应位的差值称为这两个个体基因亲和度。假定两个实数个体x1（子代个体）和x2

母体）的关系为fi

i(x1x2)=x1-xi其中，

i2，xj表示个体j的第i个基因，则称fi(x1x2)为两个实数个体基因i的亲和度。一般来说，当基因亲和度小于0时，表示后代个体基因优于母体基因，

其基因是优质基因，否则为劣质基因（这相对于最小值函数来说）。

定义3fj(i)=i3´fi(x1x2)，其中，j=x1x2；i从低位到高位依次取1，2，3…，称fj(i)为个体j第i个基因的适应值。适应值越小，表明进化中的该位数越好。在实施粒子群算子的变异操作中，将对适应值比0大的基因进行变异。

“取小”（

定义4f*åm

=fj(i)，称为个体j的适应值函数。即当f*

i=1

比0越大时，说明该个体越差，它比0越小时，说明个体越好。在演化过程中，个体的适应值和基因的适应值都会越来越小。在用单亲粒子群算法求解问题时，个体的适应值用于指导后代的选择，而基因的适应值则用于指导选择个体中对哪些基因进行变异。

定义5（成功基因换位次数）根据基因换位概率和新适应值函Nc

数决定整个种群成功操作的次数。定义ρ=åρ(f*(xinx=1jn)³pr)

n为成功换位次数，其中，ρ(f*(xinxjn)³p1,成功交叉

r)=

{

0,未成功交叉

，

Nc为以基因换位概率确定基因换位的个体数目的一半；pr开

始可取一个稍大一点的值，避免陷入局部最优，随着进化的进行，逐步减小，以便在最优解附近微调。

3.4粒子群算法的耗散结构

耗散结构是指一种非平衡状态下的非线性区域形成的有

序结构，由于不断和外环境交换物质和能量，可能从原来的无序状态变为一种时间、空间或功能有序的状态。在粒子群算法中，粒子向自身历史最佳和邻域或群体历史最佳位置聚集，形成粒子种群的快速趋同效应，容易出现局部极值、早熟收敛或停滞现象，并且随着进化的不断进行，种群的多样性渐趋于零，适应值不能得到改善，无法满足有序的要求。为了避免这种情况和加快求解速度，本文引入基因换位概率，并将变异概率和基因换位成功次数联系起来。基因换位成功次数越多，变异次数减少，变异可以理解为系统与环境进行能量交换的方式，这样便构成了新的耗散结构，使种群的进化能够充分利用基因换位和变异的优点，取得较为理想的效果。

3.5混合粒子群算法的实现

首先运行粒子群初始化操作，运行一定的代数后（N代），

判断粒子是否处于早熟收敛状态，如果是的话，就进行基于耗散机构的粒子群优化算法，即以一定概率随即抽出两个母体进行个体换位，通过个体适应值函数计算得到新的最优个体；然后通过数位适应值函数求出最差数位，让最优个体的最差数位进行变异，最后根据新构造的评估函数进行演化，得出新的粒子个体，如果得到的新个体优于旧个体，则取代旧个体，否则，仍取旧个体；最终看个体是否满足终止条件，如果满足就结束，不满足就再次进行基于耗散结构的PSO优化，以此循环往复（在这里设置一个循环体，让换位和变异设定一定循环次数，换位成功一次，就让变异次数减少一次，以此循环往复）。其算法流程如图2所示。

图2算法流程图

3.6算法的收敛性的分析及时间复杂度分析

文献[4]对粒子群优化算法的收敛性进行了理论上的分析

和数学上的证明，最后得出了粒子群优化算法是收敛的，而本

文的新算法是在不改变粒子群优化算法搜索机制的基础上所进行的改进，所以混合粒子群优化算法也是收敛的。并且新算法对易出现“早熟收敛”现象采取各种策略来避免这种情况的发生，使新算法的收敛率大大提高，提高了算法收敛速度，减少了算法的收敛时间，这在下面的对比仿真实现可以得到证明。算法的时间复杂度是衡量一个算法优劣的重要指标，而在混合粒子群优化算法中，它不仅利用群体位置方差的早熟判断机制，而且还用到基因换位和变异算子，尽管采用耗散的粒子群算法结构并减少算法计算量，但是相对于基本的粒子群算法来说，在新算法中还多出一个循环体，这就稍微增加了算法的复杂度，不管做什么事情，都不可能方方面面兼顾到，但新算法能够很好处理一般粒子群算法遇到“早熟收敛”这个主要问题，因此它仍是个较好的算法。

3.7对比仿真结果

（1）SchafferF5函数[5]

minf(x25

i)=1+å1j=1j+å(x(-65.53665.536))

(x6

iÎi-aij)

i=2(akij

)=

æç-32-16-1601632öè-32+16k-32+16k-32+16k-32+16k-32+16k-32+16k÷

ø

(a01234

ij)=(aij aij aij aij aij)(i=12;j=1225;k=014)

此函数有多个局部极大点，全局极大点为（－32，－32）；

全局极大值为1.002。当优化结果大于１时认为算法收敛。

（2）SchafferF6函数

f(xy)=0.5

12此函数有无限个局部极大点，其中只有一个（0，0）为全局

最大，最大值为1。自变量取值范围均为（－100，100）。此函数最大峰值周围有一个圈脊，取值均为0.9903，因此很容易陷入此局部极大点。当优化结果大于0.9905时认为算法收敛。对上述两个函数，分别用简单遗传算法（SGA）、基本粒子群算法（PSO）、本文混合粒子群算法（HPSO）各优化50次。三种算法种群均取20；限定代数500。HPSO和PSO参数：惯性因子W＝0.5；自身因子C11＝2；全局因子C12＝2；基因换位概率Pr=0.75，变异概率Pm=0.03，循环次数40次。SGA参数：交

叉概率PcÎ(0.60.8)，变异概率PmÎ(0.010.05)优化结果见表1，收敛曲线如图3和图4所示。

表1

基本的粒子群算法、粒子群优化算法和混合粒子群算法的实验结果比较

F5

F6算法最优值平均值收敛率平均时间/s最优值平均值收敛率平均时间/sHPSO1.0021.0000.980.7821.0001.0000.990.672PSO1.0021.0010.960.8311.0000.9990.980.817SGA

1.002

0.976

0.80

0.916

1.000

0.987

0.84

0.908

根据以上结果，对于函数极值优化问题，HPSO在搜索能力和效率两方面均优于普通SGA和PSO。

（3）神经网络权值优化

本实验用HPSO优化神经网络权值，实现如图5所示的九点模式分类问题。该问题是典型的两类模式分类问题，可看作“异或”问题的推广，经常作为检验算法分类能力的尺度。

50

1.00函数最大值

2012，48（9）ComputerEngineeringandApplications计算机工程与应用

1.00函数最大值0.750.500.25

100

HPSO

PSOSGA

200300400进化代数

500

4结论

针对粒子群优化算法的早熟收敛问题，提出了一种混合

0.750.500.25

100

HPSO

PSOSGA

200300400进化代数

500

粒子群优化算法。它借鉴群体位置方差的早熟判断机制，并把基因换位算子和变异算子引入到算法中，同时对个体和个体的基因分别计算其适应值，并将适应值最差的基因进行变异。为减少算法计算量，而采用耗散的粒子群算法结构。实验表明，混合粒子群算法不但具有很强的全局搜索能力和较快的收敛速度，而且能有效避免粒子群优化算法的早熟收敛问题，具有较大的实用价值。

图3三种算法的SchafferF5函数的收敛曲线图

图4三种算法的SchafferF6函数的收敛曲线图

用三层前馈神经网络作为分类器，网络结构为2-5-1型，需要优化的权值和阈值共21个，属高维优化问题。限定优化代数为500。因为模式为两类，所以，误差小于0.5时可认为算法收敛。用HPSO、PSO、SGA各优化50次，算法参数与前述实验相同优化结果见表2，收敛曲线如图6所示。由实验结果可知，对于高维优化问题，HPSO同样表现出优于PSO和SGA的特性。

表2

算法HPSOPSOSGA4

平均误差率

3210

1

2

X

3

4

Y

参考文献：

[1]EberhartRC，HuX.Humantremoranalysisusingparticleswarm

optimization[C]//ProceedingsoftheIEEECongressonEvolution-aryComputation（CEC1999）.WashingtonDC：IEEEPress，1999：1927-1930.

[2]刘亮.一类工作调度问题的回溯解法[J].计算机工程与设计，2006，27（18）：38-43.

[3]张德传.学生分班软件DIY[J].中国西部科技，2005（19）：60-62.[4]刘洪波.粒子群优化算法的收敛性分析及其混沌改进算法[J].控制

与决策，2006，21（6）：636-640.

[5]YoshidaH，KawataK，FuKuyamaY，etal.Aparticleswarmopti-mizationforreactivepowerandvoltagecontrolconsideringvolt-agesecurityassessment[J].IEEETransactionsonPowerSystems，2000，15（4）：1232-1239.

[6]KennedyJ，EberhartRC.Particleswarmoptimization[C]//IEEE

InternationalConferenceonNeuralNetworks.Perth，Piscataway，NJ，Australia：IEEEServiceCenter，1995，IV：1942-1948.

[7]李士勇.求解连续空间优化问题的粒子群算法[J].电子学报，2007，

40（35）：50-52.

HPSO，PSO，SGA神经网络权值优化结果对比

最大误差0.4930.6450.821

平均误差0.13740.34860.4328

1.000.750.500.25

100

200300400

进化代数

500

收敛率（/%）

1008773

平均时间/s1.2671.6871.813HPSO

PSOSGA

最小误差0.022340.082320.10023

图5九点模式分类图图6三种算法收敛误差对比图

（上接17页）

[7]ScaliseS，SchenaV，GuaschJH，etal.Linkperformanceforasat-ellite-basedcommunicationssystemforfasttrains：analysisoftrialsandmeasurements[C]//ProcEMPS2004.Noordwijk，NL：ESA，2004.

[8]GraceD，CapstickMH，MohorcicM，etal.Integratingusersinto

thewiderbroadbandnetworkviahighaltitudeplatforms[J].IEEEWirelessCommunications，2005，12（5）：98-105.

[9]NokiaSiemensNetworks.Thalyshighspeedtrainpassengersen-joybroadbandInternetaccess[EB/OL].（2008-05-18）[2011-09-18].http：//www.nokiasiemensnetworks.com/system/files/document/[1**********].pdf.

[10]邹复民，蒋新华，林漳希，等.一种基于榕树型拓扑的铁路无线

Mesh网络结构[J].铁道学报，2010，32（2）：47-54.

[11]胥桓，方旭明，向征.基于无线Mesh网络技术的列车宽带接入原

型系统设计[J].铁道学报，2010，32（2）：41-46.

[12]宋文，方旭明.无线网状网研究与发展[J].铁道学报，2007，29（2）：

96-103.

[13]GuptaP，KumarPR.Thecapacityofwirelessnetworks[J].IEEE

TransactionsonInformationTheory，2000，46（2）：388-404.

[14]杨盘隆，陈贵海.无线网状网容量分析与优化理论研究[J].软件学

报，2008，19（1）：111-125.

[15]JunJ，SichitiuML.Thenominalcapacityofwirelessmeshnet-works[J].IEEEWirelessCommunications，2003，10（5）：8-14.[16]束永安，洪佩琳，覃振权.无线网状网中基于干扰模型的多信道分

配策略[J].电子学报，2008，36（7）：1256-1260.

[17]张克旺，张德运，杜君.面向多跳无线网络的无冲突MAC协议[J].

软件学报，2009，20（7）：1895-1908.

[18]朱铨，蒋新华，邹复民.基于实验方法的多模Mesh网络多跳传输

性能影响因素研究[J].科学技术与工程，2008，8（21）：5822-5826.[19]LanManStandardsCommittee.IEEEStd802.11nTM-2009[S].2009

ed.NewYork，America，2009.[20]

Open

Mesh.B.A.T.M.A.N.advanced[EB/OL].（2011-09-14）

[2011-09-18].http：//www.open-mesh.org/wiki/batman-adv.[21]GarroppoRG，GiordanoS，TavantiL.Experimentalevaluation

oftwoopensourcesolutionsforwirelessmeshroutingatlay-ertwo[C]//ISWPC’10Procofthe5thIEEEInternationalConfonWirelessPervasiveComputing，Modena，Italy，2010.

[22]李威煌，吕品，陈颖文.多速率无线Mesh网络环境下功率控制与

调度机制——PSMR[J].计算机应用，2011，31（1）：208-211.