基于精英学习的量子行为粒子群算法
第28卷第9期V ol. 28No. 9
文章编号:1001-0920(2013)09-1341-08
控制与
and
决策
Control Decision
2013年9月Sep. 2013
基于精英学习的量子行为粒子群算法
章国勇, 伍永刚, 顾巍
(华中科技大学水电与数字化工程学院，武汉430074)
摘
要:在分析量子行为粒子群算法中吸引子指导作用的基础上, 引入两种精英学习策略, 提出了基于精英学习的
量子粒子群算法(QPSO-EL).采用动态逼近学习策略对精英个体进行局部更新, 协助其跳出自身局部极值点, 引导种群进行有效搜索; 借鉴群体早熟判断机制对停滞状态下的精英个体空间进行变尺度混沌扰动, 增大种群全局搜索空间, 有效平衡了算法的局部和全局搜索能力. 典型函数的仿真结果表明, 该算法具有收敛速度快、求解精度高的特点. 关键词:量子行为粒子群；精英学习；动态逼近搜索；变尺度混沌扰动中图分类号:TP301.6
文献标志码:A
Quantum-behaved particle swarm optimization algorithm based on elitist learning
ZHANG Guo-yong , WU Yong-gang , GU Wei
(Collegeof Hydropower and Information Engineering ，Huazhong University of Science and Technology ，Wuhan 430074，China ．Correspondent ：WU Yong-gang ，E-mail ：[email protected])
Abstract:The local attractor point in the quantum-behaved particle swarm optimization algorithm plays an important role in determining the convergence process of population. Therefore, a quantum-behaved particle swarm optimization algorithm based on two elitist learning strategys(QPSO-EL)is presented. In this method, the dynamic-approximation search strategy is exerted on the elitist particles to avoid them running into local optima and provides a good guidance for the population. While the algorithm is found to be in a dead state according to the premature judgment mechanism, the mutative-scale chaotic perturbation is used to exhibit a wide range exploration and keep the balance of exploration and exploitation. The experiment results on classic functions demonstrate the global convergence ability and the search accuracy of the proposed method. Key words:quantum-behaved particle swarm optimization ；elitist learning ；dynamic-approximation research ；mutative-scale chaotic perturbation
0引言
优于标准PSO 算法.
与PSO 算法一样, QPSO 算法在搜索过程中也容易因迭代后期粒子多样性减小而早熟收敛[4-17]. 对此, 国内外已有许多针对QPSO 算法的改进工作. 文献[5-6]通过对参数进行自适应控制来提高算法优化性能; 文献[7-10]提出采用多种变异操作方法来增强QPSO 跳出局部最优点的能力; 文献[11-13]通过引入多种其他优化机制来改善QPSO 的寻优能力. 基于QPSO 中吸引子的指导作用[4], 文献[14]引入遗传算法中的选择操作来产生吸引子坐标, 增加了种群多样性; 文献[15]引入微分进化算子来增加粒子随机性; 文献[16]提出基于高斯分布的方法来产生局部吸引点; 文献[17]采用基于动态随机变量和自身最优粒
粒子群优化(PSO)算法是一种全局优化进化算法[1], 由于其具有流程简单、可调参数少、收敛速度快等优点, 已成功应用于数值优化、图像处理等领域. 但标准PSO 算法已被证明在求解复杂优化问题时并不能收敛于全局最优解[2], 这极大地限制了PSO 的应用前景. 受量子力学的启发, Sun 等[3]提出一种具有量子行为的粒子群优化算法(QPSO).相比传统的PSO 算法, QPSO 算法利用种群中所有粒子的位置建立分布概率模型, 通过随机采样操作完成了对群体的更新, 使得粒子能够以某一概率出现在整个可行搜索空间的任意位置[4], 因而, QPSO 算法的全局搜索性能远远
收稿日期:2012-05-03；修回日期:2012-07-16. 基金项目:国家科技支撑计划项目(2009BAC56B03).
作者简介:章国勇(1989−), 男, 博生生, 从事智能计算、电力系统优化调度的研究；伍永刚(1963−), 男, 教授, 博士生导
师, 从事电力系统优化调度、自动发电优化控制等研究.
子加权平均的策略更新吸引子坐标.
上述针对吸引子的改进均是基于改变吸引子表达式来改善QPSO 的寻优性能, 一定程度上降低了吸引子位置的随机性. 本文在保持吸引子位置多样性不变的前提下, 通过引入精英学习策略更新吸引子位置, 引导粒子在保持多样性的同时向全局最优值进行有效靠拢; 同时针对进化过程中不同种群状态提出了两种精英学习策略, 并对精英个体的选取和学习策略的参数进行了分析, 以求达到算法在局部搜索和全局空间搜索的平衡.
1QPSO 算法
在一个D维的目标搜索空间中, 由M个粒子组成一个群体, 在第t时刻将第i个粒子的位置表示为一个D维向量(xi1(t) , xi2(t) , ⋅⋅⋅, xiD(t)) . 个体最好的位置为Pi(t) =(Pi1(t) , Pi2(t) , ⋅⋅⋅, PiD(t)) , 群体全局最好的位置为Pg(t) =(Pg1(t) , Pg2(t) , ⋅⋅⋅, PgD(t)) , 其中g为全局最优位置下标. 根据Clerc 等[18]
对PSO
算法中粒子收敛分析, 必然存在以点Pd为中心的某
种形式的吸引势, 且满足以下条件:
Pd=φ1dPid+φ2dPgd/(φ1d+φ2d) , (1)φij(t) =c1r1ij(t) /(c1r1ij(t) +c2r2ij(t)) .
(2)
将粒子移至量子力学空间中, 采用波函数∣ψ(r,
t) ∣来描述粒子的位置, 由薛定谔方程决定粒子的状态
变化过程. 假设每个粒子都在一个以各自吸引子为中心的δ势阱中移动, 通过求解薛定谔方程得出粒子在各自δ势阱中的概率密度函数为
Q(y) =∣ψ(y) ∣2=∣ψ(x−p) ∣2=
1e −2∣x−p∣/L, (3)其中L为Delta 势阱的特征长度, 它决定了粒子的搜索范围. 在势场中, 粒子的运动位置服从上述概率密度函数, 其位置是不确定的, 但在实际应用中, 任意确定时刻粒子必须具有确定的位置, 故采用蒙特卡罗进行随机模拟得到运动方程, 即粒子的进化方程如下:
x=Pd±L
ln(1/u) , u∈U(0, 1) , (4)
L=2β⋅∣mbest −xij(t) ∣. (5)其中:mbest 为所有个体最好位置平均, 即
m(∑M∑
M∑Mbest =
Pi1/M,Pi2/M,⋅⋅⋅, P) iD/M; i=1
i=1
i=1
(6)
参数β为收缩-扩张系数. 为保证算法收敛, β必须满足β
β=(β1−β2) ×(Gmax −t) max
+β2. (7)
其中:β1和β2分别为β的开始值和结束值, Gmax 为最大进化代数.
2基于精英学习的量子行为粒子群算法
2.1
算法机理描述
通过分析QPSO 进化方程(4)可知, 在QPSO 算法中, 粒子个体的每一维变量xij服从一个以吸引子
Pd为中心、L为范围的概率分布[4]. 将式(1)代入(4),
得到粒子进化方程为
xid=φid(Pid−Pgd) +Pgd±
L
⋅ln(1/u) . (8)分析式(8)可以看出, 由于粒子对Pgd的收敛性, 当Pid和Pgd非常接近时粒子将集中在全局最优解附近, 出现群体聚集现象. 若此时Pgd在全局最优解的领域内, 则粒子向Pgd的收敛可增强对该领域的局部搜索, 从而提高最优解的精度[14]; 但如果Pgd位于局部最优解领域内, 并且距离全局最优解较远时, 粒子以较大的概率出现在局部最优解附近, 很容易导致算法早熟. 由此可以看出, 吸引子Pd的坐标直接决定了该粒子分布区域的中心位置.
为克服上述早熟收敛的现象, 本文充分利用吸引子的引导作用, 针对不同种群状态引入两种精英学习策略来更新种群中吸引子位置, 形成基于精英学习的量子行为粒子群(QPSO-TL)算法, 算法结构如图1所示. 通过精英选择策略选取个体进入精英个体空间, 将动态逼近学习策略施加于精英个体空间, 提高算法局部搜索能力, 改善个体进化中心位置, 指引种群有效搜索; 当种群出现聚集现象时, 通过变尺度混沌扰动使得Pid和Pgd保持一定距离, 扩大种群的搜索范围, 降低算法早熟收敛概率, 最终寻求算法在全局和局部搜索的有效平衡.
图1QPSO-TL 算法结构图
2.2混沌初始化种群
混沌是自然界中广泛存在的一种非线性现象,
利用混沌序列具有的遍历性、随机性和规律性特点[19]进行种群的初始化分布, 既不改变QPSO 算法初始化时具有的随机性本质又可大大加强算法搜索的多样性. 本文采用的帐篷映射表达式如下:
⎨Zi+1=2Zi, 0⩽Zi⩽0. 5; ⎩Zi+1=2(1−Zi) , 0. 5⩽Zi⩽1.
(9)
设种群规模为n, 变量的维数为D维. 首先随机
给出D个初始参数序列rk=[rk1, rk2, ⋅⋅⋅, rk
D], 将其代
入式(9),经过n次迭代运算产生D条运动轨迹, 每条运动轨迹有n个序列, 构成了n×D的初始种群. 2.3精英学习策略
精英学习策略的第1步是精英个体的选择. 由QPSO 进化方程知, 个体的迭代过程取决于自身概率密度函数中心吸引子的位置和种群分布范围L. 为改善分布中心吸引子坐标, 将个体按适应度值进行排序, 选取当前种群最优前m个粒子和全局最优向量一起进入精英个体空间进行动态逼近学习更新. 当种群出现聚集时, 已有研究表明, 利用混沌特有的特性进行小空间扰动具有较好的效果[10,15], 但当搜索空间较大时其效果却不能令人满意. 为此, 本文利用基于帐篷映射的变尺度混沌扰动机制对精英个体空间进行扰动, 扩大个体搜索空间, 增加种群多样性. 2.3.1动态逼近学习策略
引入动态逼近搜索机制对当前进化过程中精英个体进行局部寻优, 将更新后的最优解向量作为量子粒子群算法的全局最优解, 种群在新的最优位置的引导下进行有效搜索, 动态逼近学习策略表达式如下:
xkj
+1
=xkj±A⋅U⋅rxj, (10)U=e
−m⋅Gen /Gmax
,
(11)rxj=(xjmax −xjmin ) ⋅N(0, 1) .
(12)
其中:A为动态逼近系数, 用于控制精英个体在自身更新过程中不断缩小搜索步长, 初始值取1; U为自适应系数, 用于确定主循环迭代过程中每次调用动态逼近学习策略时精英个体搜索的初始步长值; m为进化系数; rxj为搜索步长; xjmax 和xjmin 为变量搜索区间最大值和最小值.
为提高精英个体的局部搜索能力, 改善种群进化方程中吸引子的位置, 选取了局部搜索能力较强的高斯分布函数来控制个体搜索步长. 考虑到算法的计算效率, 在进化初期, 由于算法的收敛速度较快, 以小概率对精英个体进行局部搜索; 而在进化后期, 以接近1的概率调用动态逼近搜索, 调用精英学习策略的概率y如下:
y=1−e −m⋅Gen /Gmax .
(13)
综上所述, 动态逼近学习策略实现流程如下:Step 1:按式(11),(12)计算当前逼近搜索步长值. Step 2:
对精英个体中变量xkj
按式(10)进行局部
更新, 其余的D−1个变量保持不变.
Step 3:评价xk+1=[xk1, xk2, ⋅⋅⋅, xk
D]的适应度,
若优于xk, 则将xk替换为xk+1, 并保存该搜索步长转Step 2继续运行, 直到最大逼近次数, 否则转Step 4.
Step 4:j=j+1, 若j=D, 则结束本次局部搜索转Step 5, 否则转Step 2继续对下一变量进行搜索.
Step 5:k=k+1, 若k大于指定的搜索次数则退出程序, 否则按下式:
A=α⋅A
(14)
缩小搜索步长(α为动态逼近因子), 并按新的搜索步长转Step 1继续执行.
由上述分析可以发现, 随迭代次数的增加, 搜索也越来越精细. 当α取值较小时, 算法搜索精度较高但不能保证跳出局部最优解; 而当α取值较大时, 搜索步长变幅较小, 局部搜索步长较大, 算法易跳过最好解所在区域. 本文采用自适应线性减小的方式确定α的值, 表达式如下:
α=(α1−α2) ×(Gmax −t) max
+α2.
(15)
2.3.2种群停滞判断与变尺度混沌学习策略
进化停滞判断是早熟处理的基础, 通常采用平均适应度方差或平均粒距来判断, 相应表达式如下:
δ2
=
1∑n
(fi−favg ) , (16)i=1
D(t) =1∑n ⋅
⎷∑D(pij−j) 2. (17)i=1
j=1
其中:n为种群规模; l为搜索空间最大对角长度; fi为个体i的适应度值; favg 为平均适应度值; f为归一化因子, 且有f=max[1, max ∣fi−favg ∣]; pij为个体
i第j维变量的值; i表示所有个体第j维变量的平均
值.
由式(16)和(17)可以看出, 种群平均适应度方差是从函数值方面反映粒子分布情况, 而平均粒距是从空间角度反映各个个体相互之间的分布离散程度[19]. 当粒子群陷入早熟收敛或者达到全局收敛, 粒子将聚集在搜索空间的一个或几个特定的位置, 当这几个极小点相差不大时种群的适应度方差将很小而平均粒距却很大, 因此, 采用平均粒距来描述种群多样性是不够完善的. 本文采用平均适应度方差δ2对种群聚集现象进行判断, 采用变尺度混沌策略对精英个体空间进行扰动变异操作, 具体流程如下:
Step 1:利用混沌对初值敏感的特点, 取D个有
微小变异的初值zk
j∈[0, 1]. 其中D为个体中的变量
维数, k为第k次混沌搜索次数.
Step 2:
将zk
j映射到xj的取值区间[xkjmin ,
xkjmax ], 初始取值x0jmin =xjmin , x0
jmax =xjmax , 得
到混沌搜索变量值
kkkk
xkj=xjmin +zj(xjmax −xjmin ) .
沌扰动通过动态改变混沌扰动步长可以有效地扩大
(18)
个体进化空间范围, 使得pid和pgd保持一定距离, 减少因多样性下降而出现早熟收敛的可能性.
kk
Step 3:评价xk=[xk1, x2, ⋅⋅⋅, xD]的适应度值,
若优于x, 则将xk替代x, 否则继续.
Step 4:k=k+1, 采用式(9)更新混沌变量. Step 5:若k大于最大混沌搜索迭代次数, 则终止迭代, 否则重复Step 2∼Step 4, 直到一定次数内(本文取10次) 最优解保持不变为止, 执行Step 6.
Step 6:通过下式:
+1∗kk
xkjmin =xj−γ⋅(xjmax −xjmin ) , +1xkjmax
3仿真实验结果与分析
3.1
仿真设计
仿真中引入6个标准函数(见表1) 来测试QPSO -EL 的总体性能, 其理论最小值均为0. 为了测试和比较算法的性能, 本文设计了7组算法对比测试实验, 包括标准QPSO [14]和现有的相关改进QPSO 算法, 如:
(19)(20)
CMQPSO [20]、RQPSO [8]、IGSO [12]、CQPSO-DE [15]和QPSO-RS [14]. 各算法中的参数参考相应文献, 本文QPSO-EL 算法的参数设置如下:扩张-收缩因子β从1.0到0.5线性减小, 动态逼近因子α从0.3到0.1线性减小, 变尺度因子γ取0.1, 多样性度量值阈值Δδ取0.015, 自适应进化系数取3.0, 精英个体数取1, 变尺度混沌扰动100次, 动态逼近迭代搜索8次. 参照文献[14]的实验设置, 分别测试10, 20, 30维的情况, 对应算法的最大迭代次数为1000, 1500, 2000, 粒子个体为20, 40, 80. 对于Schaffer 函数, 维数固定为2, 最大迭代次数为2000. 每个实例运行30次所得到的平均最优值如表2∼表7所示.
=
x∗j
+γ⋅
(xkjmax
−
xkjmin ) ,
动态缩小各变量的搜索范围, 转Step 2继续执行. 其中:x∗j为变量xj的当前最优位置, γ为变尺度系数. 为使新搜索范围不致越界, 需做以下处理:
+1k当xkjmin >xjmin 时,
+1
xkjmin
=
xkjmin ;
+1k
当xkjmax
+1k
xkjmax =xjmax .
相比传统的混沌量子行为粒子群, 上述变尺度混
表1
测试函数Sphere Tablet
函数表达式
f1(x) =f2(x) =10
n−1∑i=1
6
n∑i=1
标准测试函数
搜索范围
初始化范围[50,100][50,100][15,30][2.56,5.12]
函数类型单峰单峰单峰多峰
xi
2
[−100,100]
(xi)
22
x21
+
n∑i=2
[−100,100]
2
Rosenbrock Rastrigrin
f3(x) =(100(xi+1−xi) +(xi−1) ) (xi−10cos(2πxi) +10)
i=1
2
n∑i=1
2
22
[−30,30][−5.12,5.12]
f4(x) =
n∑i=1
− ⎷xi
Ackley Schaffer
f5(x) =20+e−20e −e
−cos(2πxi)
[−32,32][−100,100]
[16,32][30,100]
多峰多峰
sin 2() −0. 5
f6(x) =0. 5+
√
表2
m
Sphere 函数测试结果
CQPSO-DE [15]
---3.4758e-1131.5331e-75
-1.1041e-129
--CMQPSO [20]5.542e-282.255e-243.459e-157.483e-191.970e-183.459e-154.565e-173.763e-164.903e-12
QPSO-RS [14]4.9478e-441.8155e-244.1725e-159.9049e-763.0673e-444.1725e-152.3896e-1031.5558e-684.1574e-50
IQPSO [12]4.68e-301.57e-121.53e-103.48e-36.37e-21.65e-207.33e-413.17e-242.16e?21
QPSO-EL 1.6662e-2082.3278e-281.0371e-229.6785e-1911.4742e-2131.2241e-2382.5966e-1774.9401e-2023.3502e-227
Dim 10
Gmax
QPSO [14]3.1979e-0431.9197e-0247.3736e-0152.7600e-0763.1979e-0437.3736e-0152.5607e-1031.4113e-0686.5764e-050
RQPSO [8]1.7412e-71.8517e-66.0118e-61.5035e-71.3454e-66.0118e-61.0779e-71.3454e-64.1723e-6
[***********][***********]
20
203010
40
203010
80
2030
表3
m
Tablet 函数测试结果
CMQPSO [20]7.665e-439.820e-293.045e-144.672e-475.831e-359.873e-275.643e-661.064e-527.886e-41
QPSO-RS [14]1.9635e-531.4842e-295.8467e-191.0025e-971.1802e-569.0171e-388.7100e-1326.9240e-902.5827e-64
IQPSO [12]
---------QPSO-EL 5.8385e-566.6901e-432.2259e-434.3562e-2701.0090e-551.2111e-523.9543e-2665.4423e-754.3569e-59
Dim 10
Gmax
QPSO [14]2.3998e-213.0603e-102.3953e-082.7783e-276.8015e-171.3263e-112.5895e-283.9996e-177.6177e-12
RQPSO [8]
---------
CQPSO-DE [15]
---------
[***********][***********]
20203010
40203010
802030
表4
m
Rosenbrock 函数测试结果
CQPSO-DE [15]
---5.581215.6854-5.2616--CMQPSO [20]
9.55230.982113.3668.03119.55331.9825.67317.03625.775
QPSO-RS [14]
6.912035.504872.91505.193619.482136.73735.099017.096827.1737
IQPSO [12]15.0438.9525.974.173.7911.070.762.8910.46
QPSO-EL 7.39921.49992.34320.03939.4846e-31.0248e-45.4177e-37.2748e-54.0243e-6
Dim 10
Gmax
QPSO [14]9.565782.429498.79488.998340.744943.55826.831233.528744.5946
RQPSO [8]47.690470.7450103.732220.187246.827078.555113.428829.825754.1137
[***********][***********]
20203010
40203010
802030
表5
m
Rastrigrin 函数测试结果
CQPSO-DE [15]
---00-0--CMQPSO [20]
4.99511.52123.9943.01715.68021.0251.3968.09614.271
QPSO-RS [14]
3.736514.963123.76222.015411.927115.44281.46927.747614.6705
IQPSO [12]
3.559.2712.471.386.083.470.674.778.79
QPSO-EL
006.9388e-19
000000
Dim 10
Gmax
QPSO [14]4.003215.064828.30272.645211.310918.92792.26178.412114.8574
RQPSO [8]4.448915.971527.64143.208110.581720.97482.09228.479416.4016
[***********][***********]
20203010
40203010
802030
表6
m
Ackley 函数测试结果
CMQPSO [20]
4.90710.09215.6635.9868.02312.8901.0531.9955.257
QPSO-RS [14]
1.60113.66783.98763.1283e-125.3905e-93.5112e-73.0287e-137.2111e-61.1425e-7
IQPSO [12]
---------QPSO-EL 7.9936e-155.2238e-152.2706e-143.5526e-166.0121e-162.2285e-162.6645e-162.7921e-156.0297e-15
Dim 10
Gmax
QPSO [14]15.203318.608320.148714.82429.52320.528112.375317.408318.6159
RQPSO [8]
---------
CQPSO-DE [15]
---4.2633e-151.4211e-15
-1.4211e-15
--
[***********][***********]
20203010
40203010
802030
表7
m
Schaffer 函数测试结果
CQPSO-DE [15]
---CMQPSO [20]2.207e-41.620e-79.433e-9
QPSO-RS [14]3.6421e-62.0970e-86.9487e-9
IQPSO [12]
---QPSO-EL 1.7756e-133.0937e-184.3221e-19
Dim 102030
Gmax
QPSO [14]0.00165.8308e-47.5695e-9
RQPSO [8]0.0014332.1303e-83.5979e-9
204080
[1**********]0
3.2仿真结果分析
从上述测试结果可以看出, 除了Tablet 函数测试中部分结果不如QPSO-RS 外, 在大多数实例中QPSO-TL 的结果都优于其他算法. 针对函数f1, f2, 由于函数形式比较简单, 函数最优值所在的区域比较平坦, 大多数算法能获得较好的收敛效果, 但随着测试函数维数的增加, 部分算法出现寻优精度不高的问题. 对于函数f3而言, 虽然也是单峰问题, 但由于函数最优值附近有陡峭的区域, 使得算法极易陷入局部最优. 随着维数的增加, 大多算法出现早熟收敛的情况, QPSO-EL 算法的测试结果表现出了较好的全局寻优性能. 对于多峰函数f4∼f6而言, 标准的QPSO 算法表现出较差的全局寻优能力, 本文改进算法与文献[15]中CQPSO-DE 相当, 且随着函数维数的增加仍能表现出较好的收敛精度, 充分说明了QPSO-EL 算法求解复杂多峰问题的优越性.
为进一步分析两种精英学习策略的必要性, 本文选取了3个标准函数:Tablet 、Rosenbrock 、Rastrigrin 对标准的量子行为粒子群(QPSO)、单独基于动态逼近学习的QPSO-DA 和包含两种精英学习策略的QPSO-EL 算法的性能进行测试. 图2给出了在粒子数为40、变量维数为30、迭代1000次的情况下3种不同学习策略下最优值的进化曲线.
1.0e+041.0e -081.0e -20QPSO QPSO-DA 1.0e -32QPSO-EL
1.0e -44
200
600
1000
(a)Table
1.0e+09QPSO
1.0e +05QPSO-DA QPSO-EL 1.0e +011.0e -03
200600
1000
(b) Rosenbrock
1.0e+01QPSO
QPSO-DA 1.0e -05QPSO-EL
1.0e -111.0e -17
200
600
1000
(c) Rastrigrin
图2不同学习策略下算法最优解收敛过程
从图2可以看出, 动态逼近学习策略的加入有效提高了算法搜索效率, 相比标准QPSO 函数最优适应度值得到较大的改善. 但随着迭代过程的推进, 种群的多样性不断减少, 出现聚集现象. 对于较简单的Tablet 函数, QPSO-DA 的最优适应度值依然得到改善, 但对于存在较多局部收敛点的Rosenbrock 函数而言, QPSO-DA 进化后期开始出现早熟收敛的情况, 种群最优适应度值衰减缓慢. 此时, 变尺度混沌扰动策略的作用被充分凸显出来. 从图2中可以看出, QPSO-EL 种群仍然能够保持较大的搜索空间, 个体进化过程中搜索范围得以保持, 函数最优适应度值较QPSO-DA 有较大的改进. 总的看来, QPSO-EL 在提高QPSO 局部搜索能力的同时保持了种群较强的全局搜索能力. 3.3
参数分析
QPSO-EL 中重要的参数包括动态逼近因子α、扩张-收缩因子β、多样性度量阈值Δδ等. β在相关文献中已有讨论[5-6], 本文仅讨论Δδ和α对算法性能的影响. 3.3.1
多样性度量阈值Δδ的影响
Δδ的取值直接影响了QPSO-TL 调用变尺度混
沌变异的时机. 取初始种群规模40, 保持其他参数不变, 停滞阈值分别取0.005, 0.01, 0.015, 0.02. 对测试函数f2、f3和f4分别进行20次优化. 函数的维度均为30, 迭代1000次优化结果的最优值、最差值和平均值如表8所示. 可以发现, Δδ较小时算法容易陷入早熟收敛; 而Δδ较大时, 则使得粒子失去较优的局部搜索精度. 仿真结果表明, 对于单模函数由于函数较简单, 借助QPSO 自身较强的全局寻优能力, Δδ越小最优解精度越高; 而对于多模函数, 由于迭代过程中存在较多的早熟收敛点, 当停滞阈值Δδ较小时, 算法易陷入局部最优出现较差解, 但Δδ较大也会因此降低搜索精度. 通常取0.015左右时优化结果较理想. 3.3.2
动态逼近因子α的影响
保持其他参数不变, 动态逼近因子分别取0.1,
0.3, 0.5和自适应变化. 函数设置同上, 优化结果的最优值、最差值和平均值如表9所示. 可以看出, 当α较小时, 动态步长衰减较快, 搜索精度高, 但不能保证算法跳出局部最优. 对于单模函数, 当α=0. 1时可以保证较高的收敛精度, 但对于多模函数却容易因此陷入早熟收敛. 当α=0. 5时由于步长变幅较小, 局部搜索步长较大, 算法易跳过最优解区域. 本文采用自适应变化方式, 算法初期保持较大的全局搜索步长, 在算
法后期自适应减小步长, 增强局部搜索精度. 实例验证了该方法相比单一的系数法具有更高的全局寻优能力和收敛精度.
表8
Δδ对测试函数结果影响
Δδ=0. 015
Δδ=0. 02
函数
Δδ=0. 005Δδ=0. 01
[最优解, 最差解, 平均解]
f2f3f4
[最优解, 最差解, 平均解][1.127e-50,1.077e-39, 1.579e-40]
[8.173e-03, 0.883, 0.312]
[0,0.994, 0.099]
[最优解, 最差解, 平均解][1.723e-47,1.411e-37, 1.473e-38]
[6.319e-03, 0.419, 0.167][0, 1.734e-18, 4.336e-19]
[最优解, 最差解, 平均解][3.253e-47,6.159e-37, 4.359e-38]
[0.024,1.012, 0.252][0,2.602e-18, 1.041e-18]
[1.102e-51, 2.812e-41, 2.816e-42]
[0.017,1.071, 0.363][0,0.994, 0.198]
表9
函数
α=0. 1
α对测试函数结果影响
α=0. 5
α自适应变化
α=0. 3
[最优解, 最差解, 平均解]
f2f3f4
[最优解, 最差解, 平均解][1.348e-50,1.138e-40, 1.099e-41]
[0.002,2.042, 0.456]
[0,0, 0]
[最优解, 最差解, 平均解][1.705e-35,5.860e-46, 1.721e-36]
[1.363,7.761, 4.297][0,8.673e-19, 2.602e-19]
[最优解, 最差解, 平均解][8.853e-52,5.593e-47, 1.204e-47]
[7.065e-4, 0.699, 0.271]
[0, 0, 0]
[4.265e-217, 8.266e-59, 1.796e-59]
[0.021,10.49, 1.790]
[0,0, 0]
表10
函数
m=1
精英个数m对测试函数结果影响
m=0. 05x
m=0. 1x
[最优解, 最差解, 平均解]
f2f3f4
运行时间1.9313.7972.807
[最优解, 最差解, 平均解][4.990e-48,5.353e-44, 9.549e-45][9.506e-7,1.481e-4, 5.681e-5]
[0,0, 0]
运行时间2.8285.7044.375
[最优解, 最差解, 平均解][6.634e-51, 4.612e-46, 3.485e-48][1.831e-7, 6.275e-6, 1.728e-6]
[0, 0, 0]
运行时间4.0669.8138.086
[7.891e-47,2.206e-42, 1.82e-44]
[2.795e-5,0.739, 0.140][0,8.673e-19, 8.673e-20]
3.3.3精英个体数量的影响
针对不同的精英数保持其他控制参数不变, 考虑到运行时间的影响, 本文讨论了3种不同精英数量下函数的运行结果, 如表10所示. 可以看出, 增加精英学习个体数可以改善个体自身最优位置坐标, 但同时平均运行时间也大幅度增加. 对于多峰复杂问题的求解可通过增加精英个体数来增强个体的全局寻优能力, 提高算法收敛精度; 而对于求解过程较简单的函数而言, 已有的学习机制已经能够达到要求. 因此, 实际工程问题可根据具体情况调整精英个体数量获取最优解.
[4][3][2]
1995:1942-1948.
Van den Bergh F. A new locally convergent particle swarm optimizer[C].Proc of the IEEE Int Conf on Systems, Man and Cybernetics. Tunisia:IEEE, 2002:94-99.
Sun J, Feng B, Xu W B. Particle swarm optimization with particles having quantum behavior[C].Proc of 2004Congress on Evolutionary Computation. Portland:IEEE, 2004:325-331.
周頔, 孙俊, 须文波. 具有量子行为的协同粒子群优化算法[J].控制与决策, 2011, 26(04):582-586.
(ZhouD, Sun J, Xu W B. Quantum-behaved particle swarm optimization algorithm with cooperative approach[J].Control and Decision, 2011, 26(4):582-586.) [5]
黄泽霞, 俞攸红, 黄德才. 惯性权自适应调整的量子粒子群优化算法[J].上海交通大学学报, 2012, 46(2):228-232.
(HuangZ X, Yu Y H, Huang D C. Quantum-behaved particle swarm algorithm with self adapting adjustment of inertia weight[J].J of Shanghai Jiaotong University, 2012, 46(2):228-232.) [6]
方伟, 孙俊, 谢振平, 等. 量子粒子群优化算法的收敛性分析及控制参数研究[J].物理学报, 2010, 59(6):3686-3694.
(FangW, Sun J, Xie Z P, et al. Convergence analysis of quantum-behaved particle swarm optimization algorithm and study on its control parameter[J].Acta Physica Sinica, 2010, 59(6):3686-3694.) [7]
Coelho L S. Gaussian quantum-behaved particle swarm optimization approaches for constrained engineering
4结论
基于对QPSO 算法易陷入局部最优的原因分析, 考虑到算法中局部吸引子的指导作用, 论文通过精英个体选择策略对不同进化状态下的种群引入两种精英学习策略, 提出了基于精英学习的量子行为粒子群(QPSO-EL),并分析了动态逼近因子、多样性度量阈值和精英个体数量对算法性能的影响. 在该算法中, 动态逼近局部更新策略提高了算法的局部搜索能力, 改善了个体概率进化中心点位置; 变尺度混沌扰动的引入, 拓宽了种群聚集时个体的寻优空间, 提高了算法全局寻优几率. 通过多个测试函数的仿真结果对比分析, QPSO-EL 较其他算法具有更高的全局寻优能力和收敛精度, 适用于对多峰函数的优化求解. 参考文献(References )
[1]
Kennedy J, Eberhart R. Particle swarm optimization[C].Proc of IEEE Int Conf on Neural Networks. Perth:IEEE,
design problems[J].Expert Systems with Applications, 2010, 37(2):1676-1683. [8]
Sun J, Lai C H, Xu W B, et al. A modifiedquantum-behaved particle swarm optimization [C].Proc of IEEE Conf on Computational Science. Beijing:IEEE, 2007:294-301. [9]
龙海侠, 马生全. 基于多样性变异的量子行为粒子群优化算法[J].计算机应用研究, 2011, 28(6):2064-2066. (LongH X, Ma S Q. Quantum-behaved particle swarm optimization with diversity guided mutation[J].Application Research of Computers, 2011, 28(6):2064-2066.)
[10]林星, 冯斌, 孙俊. 混沌量子粒子群优化算法[J].计算机
工程与设计, 2008, 29(10):2610-2612.
(LinX, Feng B, Sun J. Chaos quantum-behaved particle swarm optimization algorithm[J].Computer Engineering and Design, 2008, 29(10):2610-2612.)
[11]Liu J, Sun J, Xu W B. Improving quantum-behaved
particle swarm optimization by simulated annealing[J].Computational Intelligence and Bioinformatics, 2006, 4115:130-136.
[12]Chen D B, Wang J T. An improved group search
optimizer with operation of quantum-behaved swarm and its application[J].Applied Soft Computing, 2012, 12(2):712-725.
[13]朱颢东, 李红婵. 新的自适应免疫量子粒子群优化算
法[J].微电子学与计算机, 2011, 28(3):123-125. (ZhuH D, Li H C. New adaptive immune quantum-behaved particle swarm optimization algorithm[J].Micro electronics and Computer, 2011, 28(03):123-125.) [14]龙海侠, 须文波, 王小根, 等. 基于选择操作的量子粒子
群算法[J].控制与决策, 2010, 25(10):1499-1506. (LongH X, Xu W B, Wang X G, et al. Using selection to improve quantum-behaved particle swarm optimization[J].Control and Decision, 2010, 25(10):1499-1506.)
[15]田雨波, 彭涛, 沙莎. 基于微分进化算子和混沌扰动的
量子粒子群算法[J].江苏科技大学学报:自然科学版, 2011, 25(2):158-162.
(TianY B, Peng T, Sha S. Improved quantum-behaved particle swarm optimization algorithm based on differential evolution operator and chaos disturbance[J].J of Jiangsu University of Science and Technology:Natural Science Edition, 2011, 25(2):158-162.)
[16]Sun J, Fang W, Palade V , et al. Quantum-behaved particle
swarm optimization with Gaussian distributed local attractor point[J].Applied Mathematics and Computation, 2011, 218(7):3763-3775.
[17]李盼池, 王海英, 宋考平, 等. 量子势阱粒子群优化算法
的改进研究[J].物理学报, 2012, 61(6):1-10.
(LiP C, Wang H Y , Song K P, et al. Research on the improvement of quantum potential well-based particle swarm optimization algorithm[J].Acta Physica Sinica, 2012, 61(6):1-10.)
[18]Clerc M, Kennedy J. The particle swarm:Explosion,
stability, and convergence in a multi-dimensional complex space[J].IEEE Trans on Evolutionary Computation, 2002, 6(1):58-73.
[19]刘军民, 高岳林. 混沌粒子群优化算法[J].计算机应用,
2008, 28(2):322-325.
(LiuJ M, Gao Y L. Chaos particle swarm optimization algorithm[J].Computer Applications, 2008, 28(2):322-325.)
[20]逄珊, 杨欣毅, 张小峰. 混沌映射的多种群量子粒子群优
化算法[J].计算机工程与应用, 2012, 48(33):56-62. (PangS, Yang X Y , Zhang X F. Chaotic mapping multi population quantum-behaved particle swarm optimization algorithm[J].Computer Engineering and Applications, 2012, 48(33):56-62.)
(上接第1334页)
[17]Lofberg J. Yalmip:
A toolbox for modeling and
[19]Reznick B. Some concrete aspects of Hilbert’s17th
problem[C].Contemporary Mathematics. Providence :American Mathematical Society, 2000:251-272. [20]俞立. 鲁棒控制—–线性矩阵不等式处理方法[M].北
京:清华大学出版社, 2002:21-22.
(YuL. Robust control —Linear matrix inequality approach[M].Beijing:Tsinghua University Press, 2002:21-22.)
optimization in Matlab[C].Proc of 2004IEEE Int Symposium on Computer Aided Control Systems Design. Taipei, 2004:284-289.
[18]Parrilo P A, Sturmfels B. Minimizing polynomial
functions[C].Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science 2001. Providence :Mathematical Society, 2003:83-100.
American