改进混沌粒子群算法

改进混沌粒子群算法（共8篇）

改进混沌粒子群算法 篇1

频谱激电法(SIP)是根据复电阻率频谱所提供的丰富的激电信息,找到并评价电性异常体,以达到研究地下地质目的的一种新的激电分支方法。常见解释剖面线上复电阻率的方法是对数据进行反演。早期受计算机的计算速度、内存等条件的限制,反演多为一维,二维(张桂青[1],阮百尧[2],佐佐木[3])。随着计算机硬件的快速发展,更高维度反演的实现成为可能 (Rijo L.[4],Park S K[5],Kim[6,7],Karaoulis[8])。如今,二维反演技术已经趋于成熟并广泛用于对物探资料的处理。三维和四维反演尚在发展,很多只局限于理论研究,且反演时间过长,工作效率低,所以需要研究人员的进一步探究改进。

反演的实质是不适定的寻优,许多实际问题均具有非线性、约束性、多极小等特点。传统的局部搜索方法如共轭梯度法、最小二乘法的搜索空间很小,且依赖初始模型,容易陷于局部极值,因此基于全局搜索的智能算法的研究越来越受到人们的关注。Ranjit S[9]将粒子群算法(PSO)运用到地球物理数据反演,取得了很好的结果,但是搜索过程慢,后期难收敛。师学明[10]提出一种阻尼振荡的惯性权重 ,且证明了这种混沌振荡的能加快收敛速度,跳出局部极值。本文参考了混沌振荡的思 想 , 提出一种 充分混沌 振荡PSO算法(FCO-PSO),在各影响粒子群速度更新的参数中引入混沌搜索,并用于频谱激电复电阻率的三维反演。文中介绍了PSO算法的基本原理和混沌振荡用于改进算法各参数的方案,然后在一复电阻率模型上进行模型反演,并将其性能与标准PSO和阻尼PSO算法进行对比,模型实验表明,该方法不容易陷于局部最优,稳定有效,具有较高的性能。

1 方法原理

1.1 PSO 算法的基本原理

粒子群优化算法(PSO)是在1995年由Kennedy等[11]提出的基于群体智能的全局随机搜索算法。采用速度- 位置搜索模型,每个粒子代表解空间的一个候选解,解的优劣程度由适应度函数决定,而适应度函数的选取根据具体的优化目标定义。PSO随机把一群粒子随机初始化,其中第i(i=1,2,…,N)个粒子在d维解空间的位置是xi=(xi1,xi2,…,xid)。速度vi=(vi1,vi2,…vid)决定在搜索空间单位迭代中位移。每次迭代中,每个粒子都是通过动态跟踪个体极值和全局极值来更新其速度和位置。其中个体极值是粒子从初始到当前迭代次数搜索找到的最优解Pi=(Pi1,Pi2,…Pid)。全局极值是粒子种群目前的最优解g=(g1,g2,…gd)。迭代过程中,个体极值和全局极值不断更新,最后得到的全局极值就是算法得到的最优解粒子群中的每个粒子根据式(1)和(2)来更新其速度和位置:

其中ω为惯性权重,r1、r2是分布的在(0,1)区间的随机数,c1和c2是学习因子,t为迭代次数,r是约束因子,一般设为1。

1.2 改进的充分混沌振荡 PSO(FCO-PSO)算法

PSO算法中,r1、r2、c1、c2和ω都是影响其收敛速度的重要因素。标准的PSO收敛速度很快,但后期表现为趋同性,易陷于局部极小。因此本文在标准PSO的各个参数中各自引入混沌搜素,让其充分混沌振荡,提高PSO算法的收敛速度,同时避免算法后期振荡。

(1)混沌惯性权重、学习因子以及随机数。

合适的惯性权重ω有助于PSO均衡探索能力与开发能力。对较大的ω,粒子利于全局寻优。对较小的ω,算法容易收敛。Y.Shi等[12]提出线性递减惯性权重策略(LDW),Eberhart[13]提出针对动态优化问题的随机惯性权值,师学明[10]证明了一种呈阻尼振荡递减的下降形态有助于PSO跳出局部极值,加快收敛速度。本文结合Logistic方程将混沌引入的优化,实现如下。式(3) 中,是控制参数,t为迭代次数,ωmax和ωmin分别为0.9、0.4。当y(0)∈(0,1)、μ=4时,方程是完全混沌的。已有数值试验证明,y(0)的选择对最终适应度影响不大,算法终能收敛到最优解附近,本文设为y(0)=0.234。

学习因子c1和c2代表粒子本身经验信息和其他粒子经验信息对粒子运行轨迹的影响,反映了群体间的信息交流。Shi和Eberhart平衡随机因素的作用,取c1=c2=2。本文为了有效提高算法收敛度,将混沌因子引入到c1和c2中。式中,i=1,2,cmax和cmin是c的取值范围,分别为1.5、2.05。

除了在ω、c1和c2中引入混沌搜索外,为克服随机数取数取值带来的效率不高,将混沌引入随机数r1和r2中。

式中,ri(t)∈(0,1),i=1,2

(2)混沌粒子初始值和混沌最优解。

PSO随机初始化粒子时,本文也将混沌序列引入到初始值中用以产生初始粒子的位置和速度,提高种群的多样性和搜索便利性。另外,在所有粒子群至今搜到的最优解中引入混沌,并将此混沌序列中最优解作为粒子更新的位置,能防止粒子的趋同性并使惰性粒子快速跳出局部最优解。

1.3 混沌 PSO 算法的优化步骤

本文在SPSO算法基础下,分别在r1、r2、c1、c2和ω中引入混沌搜素,其实现步骤如下:

步骤1初始化算法参数:群体规模N,最大迭代次数Iter,ω的取值[ωmin,ωmax],学习因子范围[cmin,cmax]。根据式(3)至式(7)产生r1、r2、c1、c2和ω的混沌序列;

步骤2利用混沌序列产生初始粒子的位置和速度。随机产生的在(0,1)之间d维向量Zdi(t)代入式(3)logistic映射中,得到N个不同轨迹的混沌序列作为初始群。然后将Zdi(t)各个分量通过Pdi(t)=Pdmin+(Pdmax-Pdmin)×Zdi(t)逆映射到对应变量的取值范围内。计算粒子适应度,从N个初始化种群选取性能好的M个位置作为初始值,随机产生M个初始速度;

步骤3比较粒子的当前适应度值F(xdi)和个体极值适应度F(Pdi),若优于后者,更新Pdi。比较更新后的F(Pdi)和全局极值适应度F(gd),若优于后者,更新gd;

步骤4根据式(1)和(2)更新粒子的速度和位置。其中的ω、r1、r2、c1和c2依次取步骤1中产生的混沌序列;

步骤5混沌优化全局极值gd。将gd映射到(0,1)即Zdi(t)=(gd-xdmin)/(xdmax-xdmin),其中[xmin,xmax]为粒子位置的取值范围。将Zdi(t)代入式(3)logistic映射中进行迭代产生混沌变量。通过gd(t)=xdmin+(xdmax-xdmin)Zdi(t)逆映射将混沌变量载波至原解空间。计算在原解空间的混沌变量经历过每一个可行解gd的适应度值,获取性能最好的最优解gbest,最后用gbest替代当前种群任一粒子的位置;

步骤6判断是否满足精度需求或已达到最大迭代次数,满足输出全局极值,否则返回步骤3。

2 三维频谱激发极化复电阻率模型反演

本文针对SIP复电阻率进行了三维FCO-PSO非线性反演。具体的反演实验方案如下。

2.1 反演过程

反演问题可表示为求最佳模型使目标函数极小:

X是模型,d为测点上的观测数据,G代表正演操作,λ是正则化参数,C是n×n的模型二阶导数矩阵方阵(n是网格单元)。S的第一项(数据失配项)意味着我们要找到满足噪声标准的数据模型,用正演得到的所有测点的视电阻率。本文的正演采用的是有限单元法(FEM),其离散化是基于非结构化三角元素,自动生成三角形网格用以剖分视电阻率数据反演所用的三维地电断面。第二项是为了加入先验信息,引入稳定的反演算法,创建平滑模型。在求解正则化权衡参数λ时,我们采用了递减的方式,开始是一个相对比较大的值(默认为0.15),且随着迭代次数而减少。

一般地下介质的电导率变化范围很大,对数化处理电阻率和视电阻率lg(ρ),缩小变化范围,提高偏导数矩阵稳定性, 确保反演中不会出现视电阻率值和电阻率为负值的情况,有利于反演的稳定性。每次迭代计算后,计算数据的均方根误差RMS,如公式(9)示。其中dai是实测数据,dci是模拟数据,i=1,2,…,n。

2.2 模型反演输出

在上述的反演理论基础上,建立一个复电阻率模型来验证反演的结果,对反演的结果进行分析。观测数据由正演得到,为了说明观测误差对反演结果的影响,我们对模型正演的数据分别添加3%的随机噪声。本文用FCO-PSO进行复电阻率的三维非线性反演,最大迭代次数为2000次,反演中粒子个数取20个。

用于验证的模型为两个相邻地电体,如图1所示。两个地电体直接的距离为11个电极距。模型基本参数如下:采用dipole-dipole装置,每排含25个电极,14层电阻率数据,电极距为1.0m。围岩2的复电阻率幅度为50Ω·m,相位为90mard。模块1异常体大小为3m×2m,复电阻率幅度为100Ω·m,相位为90mard;模块3异常体大小为3m×2m,复电阻率幅度为50Ω·m,相位为100mard,其顶深均为2m.用该模型的正演视电阻率作为混沌PSO网络的输入,对网络进行反演测试。为了评价FCO-PSO算法的效率和反演质量的好坏,本文同时采用Levenberg—Marquardt法对模型的正演数据进行了反演计算。

Levenberg—Marquardt法作为局部搜索寻优法和FCO-PSO算法均能较为准确的反映复电阻率异常体幅度和相位的大小,范围和形态,但FCO-PSO反演算法的结果更加精确,细节方面也更加清晰,反演精度优于局部搜索算法的反演精度。如图2、图3所示。

FCO-PSO算法、标准PSO算法和阻尼PSO的性能对比见表1,其衡量指标为均方根误差RMS。从表中的数据可以看出:FCO-PSO较标准PSO算法和阻尼PSO算法有更低的均方根误差,由于FCO-PSO算法在各影响寻优参数中引入混沌振荡,能够根据结果进行自适应调整,类似于模拟退火的退火过程,提高了全局寻优能力,同时有效避免早熟收敛和提高搜索遍历性。

3 结束语

基于混沌振荡的FCO-PSO算法通过各粒子协同合作寻找极值,基本能准确的反映频谱激发极化复电阻率非线性反演的的输入输出特性,取得较好的反演结果。且算法避免了对初始模型的依靠和计算偏导数矩阵的问题,具有较强的适应性,优于局部搜索技术。在各参数 中引入混 沌搜索做 自适应调 整 , 使得FCO-PSO算法能更精准的逼近全局最优解,易跳出局部极值,优于标准PSO和阻尼PSO算法。

摘要：文章针对常规粒子群优化算法易于陷于局部极值,后期收敛速度慢,反演精度不高等缺点,提出了一种改进的充分混沌振荡粒子群优化算法,并用此算法在matlab2012b编程环境中对频谱激电复电阻率进行了三维数值试验,结果表明,此种算法反演时不依赖初始模型,增大搜索空间,在全局搜索,在准确性上优于标准PSO反演和阻尼PSO反演,成像质量优于Levenberg—Marquardt法反演。

关键词：频谱激发极化,复电阻率,三维反演,粒子群优化,混沌序列

改进混沌粒子群算法 篇2

基于改进粒子群优化算法的新安江模型参数优选

新安江模型是一种实用有效的水文模型,在洪水预报以及水资源评估和管理中得到了广泛的应用.为此,结合新安江模型参数的`特点,提出了基于改进粒子群优化算法的新安江模型参数优选方法,并将该模型应用到日径流预报中.实例表明,该方法能快速地完成参数寻优,并能较好地寻找出参数的全局最优解.

作 者：刘力 周建中 杨俊杰 刘芳 安学利 Liu Li Zhou JianZhong Yang JunJie Liu Fang An XueLi 作者单位：华中科技大学水电与数字化工程学院,湖北,武汉,430074刊 名：水力发电 ISTIC PKU英文刊名：WATER POWER年，卷(期)：200733(7)分类号：O224 TV125关键词：参数优选 新安江模型 粒子群优化算法 径流预测

改进混沌粒子群算法 篇3

粒子群优化算法[1,2,3,4]是基于大自然中鱼群、鸟群等群体生物的觅食活动的启发由美国心理学博士Kennedy和电气工程师Eberhart首次提出来的一种群体智能算法。由于它涉及的理论知识少、实现方式简单方便、执行效率高, 自问世以来已经受到了诸多研究者和研究机构的广泛关注。现今, 不同版本的改进粒子群算法已经被成功地应用到了自然科学和工程领域等问题中[5,6,7,8]。但粒子群算法和其它的元启发式算法类似, 存在粒子早熟收敛、全局搜索能力差等缺点。为此, 研究者们已经对标准粒子群算法进行了不同方式的改进。文献[9]将差分进化的基本思想引入标准粒子群算法中, 对算法的所有局部最优位置进行了选择、杂交、变异等操作, 高效地解决了算法搜索能力和开发能力之间的矛盾。文献[10]使得算法自适应地选择适合粒子的速度更新方式, 使得每一代的粒子可以根据需要适应不同的进化环境, 有助于算法解决不同性质的实际问题。

本文基于对标准粒子群算法的研究分析, 给出了两个粒子之间相似度值的概念, 根据种群中每个粒子与群体最优位置的相似度值, 动态非线性地调整每个粒子的惯性权重值, 使得算法更适应当前粒子的更新状态。并将混沌算子引入粒子群算法中, 改善了算法的全局寻优能力, 提出了一种基于惯性权重动态调整的混沌粒子群算法。

1 惯性权重动态调整的混沌粒子群算法

1.1 标准粒子群算法

在标准粒子群算法中, 群体中的所有粒子根据下面的二阶迭代方程来更新它们的速度和位置

1.2 基于相似度值动态非线性调整的惯性权重

在标准粒子群算法中, 当算法执行到后期时, 群体中粒子位置与群体最优位置之间的差异会越来越不明显, 如此下去, 种群中粒子的多样性会逐渐降低, 从而使得算法的全局搜索能力也逐步下降, 算法不能有效地寻找其它区域。为了改善算法的全局搜索和局部搜索能力, 这里给出了粒子与粒子之间相似度的定义, 并根据粒子之间的相似度值动态非线性地更新算法的惯性权重值。

定义:微粒群中粒子i与粒子j的相似度可以表述如下:

1.3 混沌算子

1.4 算法步骤

惯性权重动态调整的混沌粒子群优化算法具体描述如下:

Step 1 给定算法中种群的微粒个数ps 、最大迭代次数tmax等参数;

Step 2 随机初始化, 产生粒子的速度和位置, 并评价每个粒子的适应度值;

Step 3 确定每个粒子找到的个体最优位置和群体粒子找到的群体最优位置;

Step 4 按照式 (3) 计算每个粒子与群体最优粒子之间的相似度值, 并更新粒子的速度和位置;

Step 5 对粒子进行混沌搜索;

Step 6 判断算法给定的终止条件是否满足。若满足, 则输出全局最优解和全局最优值, 算法结束;否则返回Step4 继续迭代。

2 仿真实验

本文采用了如下4 个经典测试函数对算法性能进行测试:

为了验证本文提出算法的可行性和有效性, 我们在相同的实验条件下, 将本文算法 (DPSO) 与标准粒子群算法的寻优结果进行了比较, 实验结果如表1 所示。

从表中可以看出, 在四个测试函数上, DPSO算法在迭代次数为30 时就已经找到了全局最优点。而从最优值、最差值、均值和方差四个评价指标来说, 它都远远优于标准粒子群算法, 故该算法的鲁棒性较好。

为了更好的比较两种算法的性能, 测试了两种算法的平均收敛率和平均收敛代数, 实验结果表明, DPSO算法比PSO算法有明显的提高。

3 结论

本文鉴于标准粒子群算法的一些缺点, 提出了一种惯性权重动态调整的混沌粒子群算法。算法中根据粒子与群体最优粒子的相似度的大小对惯性权重进行了动态非线性调整, 并引入了混沌映射算子, 提高了算法的全局搜索能力。通过在4 个典型测试函数的实验分析可知, 提出的惯性权重动态调整的混沌粒子群算法, 无论在寻优速度上还是在全局寻优能力上都比标准粒子群算法有显著提高。它是一种可行且高效的粒子群算法的改进算法。

摘要：鉴于标准粒子群算法 (PSO) 有易陷入局部最优位置和全局搜索能力差等缺点, 给出了相似度的定义, 并根据群体中每个粒子与全局最优粒子的相似度值的大小, 动态非线性地更新每个粒子的惯性权重值。为了改善算法的全局搜索性能, 将混沌算子引入粒子群算法中。新算法在4个测试函数上与标准粒子群算法进行了比较, 结果表明新算法的性能更好。

关键词：粒子群算法,相似度值,混沌搜索

参考文献

[1]Zhang Yingnan, Teng Hongfei.Detecting particle swarm optimization[J].Concurrency and Computation Pratice and Experience, 2009, 21 (4) :449-473.

[2]曾建潮, 介倩, 崔志华.微粒群算法[M].北京:科学出版社, 2004.

[3]黄文秀.粒子群优化算法的发展研究[J].软件, 2014, 35 (4) :73-77.

[4]洪蕾.粒子群及人工鱼群算法优化研究[J].软件, 2014, 35 (8) :83-86.

[5]Qi H, Niu C Y, Gong S, et al.Application of the hybrid particle swarm optimization algorithms for simultaneous estimation of multi-parameters in a transient conductionradiation problem[J].International Journal of Heat and Mass Transfer, 2015, 83:428-440.

[6]Vempati S R, Khan H, Pamula V K, et al.Multiuser Detection for DS-CDMA Systems over Generalized-K Fading Channels using Particle Swarm Optimization[J].Proceedings of ICETET, 2014, 29:30th.

[7]徐甜丽.基于粒子群算法的轨道电路补偿电容故障诊断方法[J].软件, 2014, 35 (1) :49-52.

[8]陈骁睿.基于改进粒子群算法的机位分配问题研究[J].软件, 2015, 36 (1) :72-76.

[9]段玉红, 高岳林.基于差分演化的粒子群算法[J].计算机仿真, 2009, 26 (6) :212-245.

[10]Li C, Yang S, Nguyen T T.A self-learning particle swarm optimizer for global optimization problems[J].Systems, Man, and Cybernetics, Part B:Cybernetics, IEEE Transactions on, 2012, 42 (3) :627-646.

改进混沌粒子群算法 篇4

关键词：云遗传算法,混沌,粒子群算法,混合算法

Kennedy和Eberhart受到鸟群觅食行为的启发,提出一种模仿鸟群觅食行为的多元搜索优化算法,即粒子群(particle swarm optimization,PSO)算法[1,2,3,4]。PSO算法因其自身良好的局部收敛效果、快速的收敛速度、易于实现以及控制参数少等优点[5,6],在提出后得到了广泛应用。但是PSO算法种群随机初始化遍历性差、易陷入早熟收敛和不具备全局收敛性的缺点[7,8],极大地限制了PSO算法的性能。为了提高PSO算法的性能,文献[9]通过自适应策略,动态地调整PSO算法的惯性权重参数,来提高PSO算法的全局收敛性能;文献[10]提出一种遗传算法和PSO算法相结合的混合路径规划方法,避免了PSO算法陷入早熟收敛;文献[11]通过在PSO算法初始化阶段引入Logistics混沌映射,利用Logistics混沌映射的遍历性和随机性,提高了初始粒子的质量。

为了解决PSO算法存在的不足,本文提出一种基于云遗传的混合混沌粒子群算法(cloud genetic hybrid PSO,CGHP),使用均匀性更优的无限折叠混沌映射实现粒子的初始化,通过自适应云算子、改进的Metropolis接受准则以及动态调整粒子集规模等策略,实现了云遗传算法和PSO算法的协同,并进行了全局收敛性证明、时间复杂度分析和实验分析。

1 算法介绍

1.1 PSO算法

在一个涉及到h维解空间的问题中,假设粒子群的规模为m,第i个粒子为Zi=(zi1,zi2,…,zih),粒子i的速度为Vi=(vi1,vi2,…,vih)。依据不同粒子的适应度值来判定不同粒子的优劣,粒子i适应度最佳的个体最优解为Pi=(pi1,pi2,…,pih),而种群中具有最佳适应度值的种群全局最优解为Pg=(pg1,pg2,…,pgh)。粒子群算法在运算过程中,根据速度更新公式和位置更新公式来实现粒子的进化,速度更新和位置更新的公式[6]如下

其中,i表示粒子数,t为迭代次数,T为最大迭代次数。c1与c2为加速常数,r1和r2是两个随机数,ω为惯性权重[11]。图1为二维空间内粒子位移示意图。粒子群根据更新公式不断向最优粒子靠拢,但当最优粒子为局部最优时,算法将会陷入早熟收敛[7]。

1.2 云遗传算法

1995年李德毅教授在概率论、数理统计和模糊数学基础上首次提出云模型理论[12]。云模型是一种用自然语言描述定性概念与定量概念的双向认知转换模型[13]。云模型具有三个典型数字特征,即Ex,En和He。其中,Ex是云的期望,集中体现云的定性概念,最能代表样本空间中最优个体的特征;熵En用来表征不确定性的带宽,亦代表随机性和模糊性的范围;He是熵的熵,衡量熵的不确定性和模糊性,通常,采用这三个数字特征共同反映一朵云的定性概念。

云模型发生器是指被软件模块化或硬件固化了的云模型生成算法[14],现采用Y条件云发生器进行交叉操作,由正态云发生器进行变异操作,如图2。

云遗传算法在传统的遗传算法思想中集合了云模型理论[15],借助云模型的随机性和稳定倾向性的特点,采用云模型更新个体,保证了给个体的多样性和全局最佳定位,从而有效克服了传统遗传算法的早熟收敛和易陷入局部最优等缺点。

2 CGHP算法

2.1 初始化

标准的PSO算法初始化过程是随机的,往往使初始粒子分布不均匀,出现大量粒子远离最优解的现象[6]。为了克服这一缺陷,文献[16]和文献[17]利用混沌模型来对PSO算法进行初始化。混沌(Chaos)是确定性系统在长期演进中表现出来的一种从有序到无序的伪随机自组织过程,具有规律性、遍历性等特点[18]。Logistic映射是一种常用的一维迭代混沌模型,其函数映射式为

当μ=2时,映射处于满射混沌状态,其在(0,1)上概率密度函数为:

Logistic映射在(0,1)区间上的概率密度曲线如下

从图3中可以看出,Logistics映射存在着边缘骤变,中间平缓,区间两端处概率大于区间中部概率的特点[19],映射的均匀分布特性较差。文献[20]提出一类无限折叠混沌映射,并通过实验证明了在区间(0,1)内较Logistics映射具有更佳的均匀分布特性,其函数映射式为

为避免搜索的盲目性,提高搜索效率及遍历程度,采用均匀性更优的无限折叠混沌映射产生随机数序列randi对初始种群进行赋值,种群中粒子不同维度取值范围为[zmin,zmax],则采用下式对种群粒子的各个维度进行初始化:

2.2 自适应云算子

在云模型的三个数字特征中,He与En成正比,En一方面反映云模型中元素在论域空间中的范围,即云模型的水平宽度,另一方面其又是随机性的度量,反映了云滴的离散程度[18]。在执行云遗传算法时,对于适应度低的粒子,需要产生方差较大、离散程度髙的云滴,以增强搜索能力,提高产生更高适应度后代的概率;对于适应度髙的粒子,则产生方差小、离散度低的云滴,以保证算法的收敛效果。因此,本文提出一种自适应于粒子适应度的云交叉算子和云变异算子,对云遗传算法进行改进。

自适应En定义如下:

式(7)中Fmax为父代最大适应度,Fmin为父代最小适应度,m=t(D1),t(D1)为区间(0,5)上服从t分布的随机数,D1的表达式如下

在自适应条件下,适应度低的粒子,D1较小,t分布产生较大随机数的概率髙,易产生较大En值,可以产生离散程度高的云滴,提高产生更高适应度后代的概率;适应度髙的粒子,D1较大,t分布产生较小随机数的概率较髙,易产生较小的En值,可以产生离散程度低的云滴,可以保证算法的收敛性。

定义云交叉算子如下

式(9)中Ex为两个父代个体的适应度均值,He=n1En,E'n是以En为期望值,以He为标准差生成的一个正态随机数。

定义云变异算子如下

式(10)中Ex为单个父代个体的适应度值,He=n2Ee,E'n是以En为期望值,以He为标准差生成的一个正态随机数。

2.3 基于云遗传的混合粒子群算法

在传统的PSO算法中,随着算法的进行和迭代次数的增加,粒子群种群多样性不断损失,直到算法陷入早熟收敛[7]。因此,定义种群密度(population density,PD)来衡量粒子群种群多样性水平,作为判断是否进入早熟收敛的依据,其表达式为:

式(11)中zij为第i个粒子的当前第j维值,pgj为群体当前最优粒子的第j维值。当种群密度小于预设值时,表示粒子群算法陷入早熟收敛。

为了解决PSO算法的早熟收敛问题,提出改进Metropolis接受准则更新全局最优解和动态减少PSO算法粒子数两种策略,实现PSO算法和云遗传算法的协同。

改进的Metropolis接受准则:若云遗传算法种群最优粒子Pgc的适应度fc大于PSO算法的种群最优粒子Pgp的适应度fp,则将Pgc作为共同的全局最优粒子Pgt存储于全局最优数据库中,并令Pgp=Pgt;否则,若Er=exp[-(fc-fp)/A]大于随机数R,则仍接受Pgc为全局最优粒子存储于全局最优数据库中,若Er小于R,则接受Pgp为全局最优粒子存储于全局最优数据库中,并令Pgc=Pgt。其中A=a/lg(t+T),a为一个趋近于1的常数,T为协同算法最大迭代次数,t为算法当前迭代次数,R=t(D2)/5,t(D2)为区间[0,5]上由t分布产生的随机数,D2公式如下:

当种群密度小于预设值,PSO算法陷入局部收敛时,依据式(11),保留PSO算法当前粒子数mt中前mt+1个粒子,将其他粒子加入云遗传算法中。

CGHP算法流程如下。

Step1:利用无限折叠映射对种群进行初始化,产生两个规模为m的粒子集A、B。

Step2:判断是否达到结束条件,若达到,终止运算,并输出全局最优数据库中适应度值最大的粒子;否则执行Step3。

Step3:根据种群密度,判断PSO算法是否进入早熟收敛,若进入早熟收敛,动态增减数据集A、B的粒子数,然后执行Step4;否则,直接执行Step4。

Step4:对数据集A、B分别进行PSO算法和云遗传算法,将PSO算法和云遗传算法产生的各自的全局最优解Pgp和Pgc利用改进的Metropolis接受准则进行筛选,将接受的最优解赋值给协同算法全局最优解Pgt存入全局最优数据库中,并令Pgp=Pgt、Pgc=Pgt,然后执行Step2。

CGHP算法流程图如图4。

其中执行云遗传算法的流程图5所示。

3 收敛性和时间复杂度

3.1 收敛性分析

对于云遗传算法,虽然相较于传统的遗传算法,其采用云模型进行选择、交叉和变异操作,但是由于“交叉-变异-选择”操作和进化代数无关,云遗传算法构成了一个有限状态齐次马尔科夫链[15],且CGHP算法中的云遗传部分采用保留最优个体的精英选择方法。文献[21]应用齐次有限马尔科夫链分析并证明了保留最优个体的遗传算法以概率1全局收敛,云遗传算法构成有限齐次马尔科夫链并保留最优个体,虽然在遗传算法的基础上引入了云模型,但仍然具有全局收敛性。

Solis和Wets[22]给出的一般随机搜索算法收敛性判定准则及相关定理,文献[5]利用收敛判定准则证明了协同算法的收敛性。根据收敛性判定准则及相关定理,并参考文献[5],给出CGHP算法全局收敛性的证明。

一般最优化问题可记为<A,f>,对于随机搜索算法D,其第k次寻优结果为Xk,下一次迭代寻优结果为Xk+1=D(Xk,ζk)。其中,A为Rn上某个子集的σ-域,f为适应度函数,ζk为算法D寻优过程中找到的解。

判定准则1:算法D满足f(D(x,ζ))≤f(x),若ζ∈A,则f(D(x,ζ))≤f(ζ)。

准则1要求随机搜索算法D是广义单调非递增的,从而保证适应度值f(x)是非递增的。

判定准则2:对于A的任意Borel子集P,若满足v(P)>0,则有

式(15)中,μk(P)为算法D在第k次迭代中搜索到的解在集合P上的概率测度。准则2说明,只要是可行解空间A中概率测度大于零的子集P,算法D连续无穷次搜索不到集合P中解的概率为0。

引理(随机算法全局收敛的充要条件):若函数f可测,可测空间A是Rn上可测子集,且算法D满足条件1和条件2,{xk}∞k=1是算法D产生的解序列,则

式(16)中,P(xk∈Rε,M)是算法D第k步搜索到的解xk在最优区域Rε,M中的概率测度。

文献[8]指出PSO算法不能以概率1收敛于最优解,文献[23]证明种群初始分布不会直接影响算法收敛性,因此证明CGHP算法的全局收敛性,仅需证明PSO算法和云遗传算法的协同过程的全局收敛性。

定理设CGHP算法优化的目标函数f是一个可测函数,其解空间S为Rn上可测子集,并且CGHP算法满足随机搜索算法全局收敛的准则1和准则2,设{xk}k∞=0是CGHP算法所产生的解序列,则

式(17)中,P(xk∈Rε,M)是CGHP算法第k步搜索到的解xk在最优区域Rε,M中的概率测度。

证明:

依据CGHP算法协同部分的流程,迭代函数F可定义为

因为CGHP算法利用全局最优数据库保留种群最优解,即采用适应度值非递增的精英保留策略,可知算法满足准则1。

如果CGHP算法满足准则件2,则规模为n的混合种群样本采样空间的并集一定包含目标函数f的解向量空间S,即

式(19)中,Mi,k为第k次迭代种群中粒子i的样本空间支撑,即概率测度为1的最小闭子集。

令Yk为云遗传算法在第k次迭代时搜索到的解。因为单独执行云遗传算法算法得到的解序列{Yk}以概率l全局收敛于最优区域Rε,M。因此,在CGHP算法中,对于有限个满足f(Yk)>f(Pg,k)的解Yk,可令其下一状态为Pg,k,并将其存储于全局最优数据库中,而且该机制对云遗传算法全局收敛性没有影响,即在CGHP算法中恒有公式(20)成立,也就是说,当f(Yk)<f(Pg,k)时,存在一个粒子i0,其支撑集Mi0,k=S。

而对于其他粒子i,

式(20)中,0≤φ1≤c1,0≤φ2≤c2,可知Mi,k为一个顶点为(φ1,φ2)=(0,0),另一个顶点为(φ1,φ2)=(c1,c2)的超矩形。

当max{c1|Pi-X(t-1)|,c2|Pg-X(t-1)|}<0.5diameterj(S)时,有:v(Mi,k∩S)<v(S),其中,diameterj(S)表示解向量空间S在第j维分量的长度。因xi收敛到平衡点(φ1Pi+φ2Pg)/(φ1+φ2),所以Mi,k长度趋于0。随着迭代次数k增加,v((Mi,k∩S))和v(∪i≠i0(Mi,k∩S))逐渐减少,从而存在整数k1,当k>k1时,v(∪i≠i0(Mi,k∩S))<v(S)),但是因为有支撑集Mi0,k=S,所以∪ni=1Mi,k=S。令S的Borel子集A=Mi,k,则v(A)>0,且(22)式成立,从而CGHP算法满足准则2。

综上所述,CGHP算法的PSO算法和云遗传算法的协同部分,满足随机搜索算法全局收敛的判定准则1和判定准则2。因此CGHP算法的搜索序列以概率1收敛于全局最优解,即CGHP算法具有全局收敛性。

3.2 时间复杂度分析

算法时间复杂度[24]是衡量算法性能优劣的标准之一,CGHP算法的时间复杂度主要由四部分构成:无限折叠混沌映射初始化、PSO算法和云遗传算法并行协作全局搜索、种群密度判定和改进Metropolis接受准则进行最优解筛选。

设种群规模为2m,粒子维数为h,T为最大迭代次数。初始化的时间复杂度为O(h·m)。设PSO算法和云遗传算法的粒子数分别为mtp和mtc,t为迭代次数,则在PSO算法中,初始化粒子群的速度、适应度值的复杂度均为O(h·mtp),个体最优和种群全局最优选取也均为O(h·mtp);在一次迭代寻优过程中,所有粒子速度、位置更新及适应度评价的复杂度均为O(h·mtp);对于云遗传算法在一次交叉、变异和计算适应度的复杂度均为O(h·mtc),选择和评价优劣等操作复杂度均为常数O(C)。因此协同部分的时间复杂度为O[h·(mtp+mtc)·T],又因为mtp+mtc=2m,PSO算法和云遗传算法协同部分的复杂度为O(h·m·T)。种群密度判定和改进Metropolis接受准则进行最优解筛选的时间复杂度均为O(T)。综上,CGHP算法的时间复杂度为O(h·m·T),且与PSO算法的复杂度[[25,26]]在同一数量级上。

4 实验分析

4.1 测试函数

为测试CGHP算法性能,选取4个典型benchmark测试函数[[27,28]]对算法性能进行验证,并对测试结果进行分析,测试函数如表1所示。

测试函数的三维视图如图6所示。

其中,Quadric noise具有一个广阔的平坦区域;Rosenbrock是一个非凸且变量间具有高度相关性的函数,其全局最优位置在狭长的抛物面状谷底内,搜索方向极难辨别;Griewanks是一个变量间相互独立的多峰值函数;Rastrigin是一个具有大量正弦波动特性局部最优位置的多峰值函数,其变量间相互独立。本文采用的多峰函数均为非线性复杂函数,大量局部极值点的存在特别适合测试改进算法全局寻优特性和避免过早收敛等方面的性能。

4.2 实验结果和分析

所有算法实现的编译环境均为MATLAB R2014a。实验参数设置如下:初始种群规模为40,两个子种群规模各为20,为进一步优化CGHP算法在进化过程中的开发和开采性能,惯性权重ω从0.9线性递减至0.4,学习因子c1、c2均为1.494,最大迭代次数为1 000,种群密度阈值为0.05。同于对比的PSO算法[29]和CSPSO算法[30]的参数设置与原始文献中设置保持一致。

实验对维数为30的测试函数(f1~f4)分别进行30次独立实验,算法性能测试的最终结果如表2所示。

为便于验证分析,表2中实验结果均以“寻优平均值+标准差”形式表示每个解,同时,在表2中的0.05显著水平下双侧t-检验结果符号标记及相应释义如表3所示。

从表3中的实验结果可以看出,对于单峰函数f1和f2而言,CGHP算法与标准PSO算法、CSPSO算法相比,在提高寻优精度的同时,解的标准差为0,解的稳定性显著提高;三种算法都可以找到全局最优解,CGHP算法的全局最优解质量最高,标准PSO算法和CSPSO算法均可收敛到相应容忍度下限,且CSPSO算法优于标准PSO算法。多峰函数f3和f4具有众多的局部极值点,CGHP算法相较于其他两种算法,同样可以显著提高解的质量,并且获得了测试函数f3的全局最优解;对于测试函数f4而言,CGHP算法虽未获得全局最优解,但是子PSO算法和云遗传算法的协同以及全局最优数据库保存全局最优的策略仍然能够使CGHP算法得到精度更高的解。在0.05显著水平下的双侧t-检验结果也验证了CGHP算法在寻优精度和稳定性方面的优势。

为进一步说明CGHP算法的收敛性能,图7(a)~图7(d)展示了三种算法在迭代1 000次过程中对于四种测试函数的收敛情况。

从图7可以看出,CGHP算法的收敛性明显优于PSO算法和CSPSO算法,在算法迭代前期,CGHP算法的适应度值迅速减小,收敛速度快于PSO算法和CSPSO算法;在迭代后期,CGHP算法的适应度值维持在极小的水平,算法寻优精度较好。

图7(a)显示30维f1函数的实验结果,CGHP算法在迭代初期适应度值迅速减小,表明算法定位到最优解区域,CGHP算法具有优于其他两种算法的全局搜索性能;在迭代中后期,CGHP算法的适应度值维持在极小的水平,表明算法具有良好的寻优精度,优于PSO算法和CSPSO算法的全局搜索能力和寻优精度,体现PSO算法和云遗传算法协同策略的优势。对于f2函数的优化问题,如图7(b)所示,当传统PSO算法获得的最优粒子为局部最优时,算法将会陷入早熟收敛而难以迅速寻找到全局最优解,而CGHP算法采用并行协同机制,借助动态调整粒子集规模和改进的Metropolis接受准则策略,使算法能够有效地跳出早熟收敛,实现最优解区域的准确定位,在短时间内实现算法的快速收敛。f3和f4函数是典型的用来测试算法全局搜索性能的函数,如图7(c)和图7(d)所示,CGHP算法在开始阶段即能找到全局最优解所在的区域,并且可以有效跳出早熟收敛并找到全局最优解,虽然迭代后期收敛速度放缓,但相对于PSO算法和CSPSO算法仍然具有良好的寻优精度,表明CGHP算法的搜索能力要优于其他两种算法。

5 结论

改进混沌粒子群算法 篇5

Kennedy博士和 Eberhart教授于1995 年提出了粒子群优化(Particle Swarm Optimization,PSO)算法[1]。粒子群优化方法自提出后,由于其收敛速度快、算法简单等优点,目前已成功应用到组合优化[2]、连续问题参数优化[3]、神经网络训练[4]、数据挖掘[5]、故障识别[6]等领域。但是在实际应用中发现PSO易“早熟”且精度不高。因此许多学者对算法提出了很多改进方法和策略。量子进化算法(QEA)[7]是新近发展起来的一种以量子计算的一些理论为基础的概率进化算法,同传统进化算法相比具有更好的群体多样性和全局寻优能力,群体规模较小但不影响算法的性能等优点。基于量子进化算法的优点,文献[8]提出了一种量子粒子群优化算法(Quantum Particle Swarm Optimization,QPSO)。该算法采用量子位的概率幅表示粒子,但惯性因子、自身因子及全局因子的设置仍沿用标准粒子群的设置方法,因此无法有效避免种群在搜索空间中多样性的丢失。因此,本文提出一种基于混沌优化的双种群量子粒子群(Dual Population Quantum Particle Swarm Optimization Based on Chaotic Optimization,BCQPSO)改进算法。首先,利用混沌序列产生两个种群规模相等的种群,以避免早熟收敛、保持种群的多样性;其二,对于其中一个种群采用线性递减的更改权重,对另一个种群利用本文建立的基于混沌序列的自适应惯性权重策略来更新;最后,对两个种群执行融合变异操作。用典型函数的极值优化问题进行仿真实验,结果表明改进算法在搜索能力和优化效率两方面均优于原粒子群优化算法。

1 量子粒子群算法

粒子采用文献[8]的编码方式:

undefined

,每个粒子代表解空间的两个解,分别对应量子态的|0>和[1]>的概率幅:

Pic=(cos(θi1),cos(θi2),…cos(θin)),

Pis=(sin(θi1),sin(θi2),…sin(θin))

由粒子编码方式可知其遍历空间每维均为[-1,1],则要比较粒子优劣需进行解空间变换。设待优化问题第j维变量的取值区间为undefined,粒子Pj上第i个量子位为[αundefined,βundefined]T,则按下式对粒子Pj的两组解进行变换:

undefined

粒子Pi上量子位幅角增量的更新:

Δθij(t+1)=ωΔθij(t)+c1r1(Δθl)+c2r2(Δθg)

粒子上量子位概率幅的更新:

undefined

故粒子Pi更新后的两个位置分别为:

Pic=(cos(θi1(t)+Δθi1(t+1)),cos(θi2(t)+Δθi2(t+1)),…cos(θin(t)+Δθin(t+1)))

Pis=(sin(θi1(t)+Δθi1(t+1)),sin(θi2(t)+Δθi2(t+1)),…sin(θin(t)+Δθin(t+1)))

粒子量子位幅角增量的更新由三个部分组成:惯性部分ω、自身部分c1和社会部分c2。如何选择和调整这三个参数关系到算法是否能避免早熟而又能快速地收敛。因此本文从如何保持粒子多样性,以及如何平衡算法全局搜索和局部搜索之间的矛盾为出发点,提出以下改进策略。

2 基于混沌优化的双种群量子粒子群算法

目前,大多数PSO粒子的初始位置都是采用随机方式初始化,这种方式有可能造成初始搜索解空间的分布程度不均衡。由于混沌序列具有混沌运动的遍历性、随机性、规律性等特点,利用混沌序列的随机性、遍历性来寻找问题的最优解,其随机性保证了大范围的搜索能力,遍历性使搜索过程能在一定范围内不重复地遍历所有状态[9] ,因此可以有效加强种群多样性,为进行全局搜索打下良好基础。本文引入Logistic混沌序列, Zt+1=μZt(1-Zt),t=0,1,2,…,其中,μ为控制参量,当μ=4时,z0≠0.5,产生的混沌序列可以遍历[ 0, 1] 区间。

2.1 基于混沌序列的双种群粒子位置初始化

在进化算法中,种群规模是一个十分重要的参数,种群规模的大小及多样性直接影响着算法的收敛率、收敛速度、可靠性等方面问题,本文提出以下基于混沌序列的双种群粒子位置初始化方法:

步骤1:用Logistic混沌序列代替原有随机数的方式来初始化各粒子。

步骤2:由于混沌序列产生的值在[0,1]区间,而解空间在[-1,1]区间,故对上面产生的初始解取反,产生[-1,0]区间的值,这样便产生两个种群。

步骤3:将上面两个种群合并,再通过随机分组方式分成种群数相等的两组种群。

步骤4:分别用这两组种群的粒子进行进化寻寻优。

由于混沌序列能在一定范围内不重复地遍历所有状态,因此大大增强了种群的多样性。

2.2 基于混沌序列的自适应惯性权重

惯性权重的引入是为平衡算法全局搜索和局部搜索之间的矛盾,惯性权重取值较大时,全局寻优能力强,局部寻优能力弱;反之,则局部寻优能力增强,而全局寻优能力减弱。文献[10]提出一种惯性权重线性改变方式:

undefined

其中,ωmax、ωmin分别是ω的最大值和最小值;t、tmax分别是当前迭代次数和最大迭代次数。这种递减策略虽然可以调节全局与局部的寻优能力,且运算速度快,但在运算的过程中,线性减小惯性系数ω,使得搜索步长逐渐减小,迭代慢慢地收敛到极值点[11]。故本文提出一种基于混沌序列的自适应改变惯性权重的方法,公式如下:

其中,undefined将权重与进化代数联系起来作自适应调整, 使算法在进化初期以较大的权重进行搜索;随着进化代数的增加, 惯性权重逐渐变小, 有利于进化后期的精细搜索;Zt是Logistic混沌序列值, 能让惯性权重在解空间内进行遍历, 有利于提高搜索效率;ωmax、ωmin分别是ω的最大值和最小值。对于两个种群的量子粒子分别用线性递减权重和自适应权重对ω进行更改,线性递减权重用于快速进化,获取最优解,自适应权重用于精细搜索,扩大解空间遍历性。

2.3 基于混沌序列的双种群融合变异

由2.1节产生的种群,在很大程度上增加了种群的多样性,并且通过2.2节的方式各自改变惯性权重,当两子种群独立进化若干代,需执行融合操作,这样可实现两个种群之间的信息交流,既能提高算法的收敛速度,又能在一定程度上保持种群的多样性,再按以下规则重新划分子种群和变异粒子。

(1)随机产生两个0-1之间的随机数α、β,α用于指导分组操作,β用于指导变异操作。

(2) 产生一个混沌序列值Zt,用Zt与α比较,如果大于则将该粒子从刚合并的种群中删除掉,并加入新种群中,该操作直到合并种群的粒子数与新生成的粒子数相等时停止,这样就又生成两个种群用于以后的进化。

(3)利用步骤(2)产生的混沌序列值Zt与β比较,如果大于则用量子Hadamard门对粒子群种群进行变异,公式如下:

undefined

,由上式可以看出,这种变异是一种旋转,对于第j个量子位,转角大小为undefined。

2.4 算法流程

(1)用2.1节的方法产生两个粒子个数相等的种群。

(2)对粒子进行解空间变换,计算适应度。

(3)根据公式进行调整粒子位置,对于种群1使用线性递减惯性权重策略,对于种群2使用自适应递减权重策略。

(4)根据2.3节合并两个种群,并记录最优粒子,如果满足终止条件则退出,否则转到步骤(2)继续进化。

3 对比试验

为验证提出本文算法的有效性,实验中采用如下2个典型函数作为仿真对象,对算法进行对比。

①Ackley:

undefined

②Rosenbrock :

undefined

对于函数(1)和(2),分别用BCQPSO、 QPSO和PSO各优化50次,然后统计平均结果、收敛次数、平均步数作为对比评价指标。三种算法的种群规模均取100,最大优化步数均取500,性能对比结果如表1所示。

从表1的对比结果可以看出,BCQPSO的优化效果最好。这是由于基于混沌序列生成的种群多样性好,并且通过两种惯性权重改变策略,既加速了寻优速度,又能扩大解空间的遍历性,最后又基于Hadamard门进行变异操作,从而提高了寻优能力。

4 结束语

提出了一种基于混沌优化的双种群量子粒子群优化算法。该算法通过引入混沌理论,采用双种群结构并行运行,每个子种群的惯性权重选用不同的更新策略,同时采用Hadamard门进行变异,这使算法在维持种群多样性的同时加快了收敛速度,扩展了解空间的遍历性,能使算法具有较好的全局搜索和跳出局部最优的能力。实验结果表明,BCQPSO算法的优化性能明显优于PSO算法。

参考文献

[1] Kennedy J,Eberhart R C.Particle swarms optimization[C]//Proceedings of IEEE International Conference on Neural Networks,USA,1995:1942-1948.

[2] Ammar W,Nirod C,Tan K.Solving shortest path problem using particle swarm optimization[J].Applied Soft Computing,2008,8(4):1643-1653.

[3] Marcio S,Evaristo C.Nonlinear parameter estimation through particle swarm optimization[J].Chemical Engineering Science,2008,63(6):1542-1552.

[4] Lin C J, Hong S J. The Design of Neuro-fuzzy Networks Using Particle Swarm Optimization and Recursive Singular Value Decomposition[J].Neurocomputing. 2007, 71(1-3):297-310.

[5] Souda T, Silva A, Neves A. Particle Swarm based Data Mining Algorithms for classification task[J]. Parallel Computing. 2004(30):767-783.

[6] Sahin F, Yavuz M &#x00C7;, Arnavut Z,et al. Fault Diagnosis for Airplane Engines Using Bayesian Networks and Distributed Particle Swarm Optimization. Parallel Computing, 2007,33(2):124-143.

[7] Hyun K,Kim J H.Quantum-inspired evolutionary algorithm fora class of combinational optimization[J].IEEE Transactions on Evolutionary Computing,2002,6(6):580-593.

[8] 李士勇,李盼池.求解连续空间优化问题的量子粒子群算法[J].量子电子学报,2007,24(5):569-574.

[9] 李广文, 贾秋玲, 刘小雄,等. 基于反馈和混沌变异的自适应进化策略[J] . 计算机应用研究, 2009, 26(6):2056-2058.

[10] Shi Yuhui, Eberhart R. A Modified Particle Swarm Optimizer[C]//Proc. of IEEE International Conference on Evolutionary Computation.Anchorage, Alaska, USA: [s. n.], 1998.

改进混沌粒子群算法 篇6

面对日益壮大的电梯市场,其逐年增加的巨大能耗已引起社会各界的普遍关注[1]。为了节能减排,减少电梯对电网依赖,国内外的主要电梯制造企业和一些节能技术研究机构已陆续开展混合能源电梯的相关研究工作。在满足电梯运行的基本需求下,对超级电容、蓄电池、太阳能等多种不同的供能设备进行系统优化控制,减少电梯对电网的耗电量,已成为越来越多专家研究的目标。Teleke[2]针对光伏发电能量输出间歇性问题,通过优化控制电池能量存储系统进行弥补。Baumann[3]对安装了储能设备的可再生能源系统能量管理问题进行了研究,提出基于规则对储能设备充放电以及系统与电网电力的混合能源进行控制管理。针对由超级电容器存储的电能、太阳能光伏发电存储在蓄电池的电能以及电网电能等混合能源组成的基于混合能源的电梯集成控制节能装置进行能量优化管理。

在电梯的混合能源模型中,其变量有离散的变量如电梯的运行时间和类似0-1的变量如超级电容与变频器的DC/DC控制变量开关α以及超级电容与蓄电池的DC/DC控制变量开关β等非连续的变量,其混合能源管理优化过程是非线性变参数优化问题,难以用普通的解析方法进行计算。非线性变参数优化问题,混沌粒子群算法保持了群体多样性,增强了PSO算法(粒子群算法)的全局寻优能力,提高了算法的计算精度,改善了收敛性和鲁棒性,很大程度上避免了算法停滞现象的发生。针对电梯混合能源管理的优化是非线性变参数优化问题的特点[4],本文采用基于混沌粒子群算法对电梯混合能源管理进行了优化,并通过对某电梯的测试,验证了模型和算法的有效性。

1 目标优化函数

根据电梯的运行特点,在满足电梯所需能量的前提下,使得电网所需的耗电量最小:

式中:EW(t)为电网消耗的各个时间段内消耗的能量;EL(t)为各时间段内大楼内的势能;EG(t)为各时间段内收集的太阳能;EX(t)为蓄电池的各时间段内提供的能量;EC(t)为超级电容的各时间段内的能量。ED(t)为电梯在各时间段内所需消耗的能量。

α表示蓄电池和超级电容间的DC/DC开关变量,其值如下:

β表示超级电容和电梯变频器的DC/DC开关变量,其值如下:

2 粒子编码与解码

在优化过程中,种群的一个粒子对应工程问题的一个解。具体到所要解决的混合能源的管理优化,一个粒子对应的是选择一种蓄电池和超级电容的变量开关的选择。采用一个n维的向量表示一个粒子。即:

其中,xi(i=1,2...,n)只能够取-1,0,1三个整数。此时x可解码为:p1x1=1,p1x2=-1,........,pixi=0,pixn=1,表示第i个时刻,蓄电池和超级的电容的开关选择,即一个粒子表示了混合能源一个时刻内的能源管理策略。例如,在第1个时刻,蓄电池的开关选择为1,表明由蓄电池的能量提供给电梯所需,而超级电容此时的开关变量选择为-1,表明此时需要给超级电容充电。在文中由于只有2个变量,n取2。因此x=[αβ]。

3 约束处理

在粒子群中的混合能源优化算法中,其根据速度更新位置的粒子出现不满足约束条件的分量,需进行调整。

a)电池充放电功率即蓄电池的开关变量α的调整

由于蓄电池的充放电过程中会损耗电池的寿命,为了延长电池的使用寿命,电池需要进行连续充放电,即电池需充电到θCxQB,U上后才能够进行放电,放电到θDxQB,U后再进行充电。同时,电池充放电功率以及储能容量也存在上限。粒子中α的编码部分,对不满足连续充放电,最大充放电功率以及电池储能上下界约束的位置αPB(T),可按照充电和放电2种情况进行调整,其调整策略如下:

1)在蓄电池的提供功率的前一段时间电池处于充电状态且储能未达到能够进行放电阈值,即:

此时,αPB(T)的调整策略为:

2)如果前一时刻电池处于放电状态且储能未达到能够进行充电阈值,即:

此时αPB(k)的调整策略为:

b)超级电容的开关变量β的调整

考虑到超级电容的容量限制,当超级电容中的存储电量大于其所允许的最大充电量时,即其电量超过其上限值EC(T)>Q时,采用下列调整方法,将k时段前超级电容的开关变量β调整为0,即停止向超级电容充电直到EC(k)≤Q。

4 优化迭代过程

由于在PSO中,存在求解质量不稳定、算法收敛速度受粒子初始化的影响,容易陷入局部最优等缺点[5,6],在对PSO算法的不足之处进行分析的基础上,需要对PSO算法做了进一步改进,本文采用一种混沌粒子群算法[7,8]。

a)PSO算法的改进思路

本文的改进思路主要是在PSO算法的基础上加入了表征PSO算法是否陷入局部最优的测量变量PJ以及优秀粒子保留策略和混沌思想。

1)测量变量PJ

设目标搜索空间为D维空间,首先随机初始化N个粒子的位置和速度,记第i(i=1,2,…,n)个粒子的位置表示为xi=(xi1,xi2,…,xi D),相应的飞行速度表示为vi=(vi1,vi2,…,vi D)。然后通过求得待优化问题的目标函数适应值寻找最优位置,最优位置有2个,一个是个体极值最优位置pi,另一个是全局最优位置pg。最后,种群中每个粒子第t(t≥2)次位置更新都按照下述公式进行:

式中:i=1,2,…,N;

w—惯性权重系数,随着迭代次数线性减小;

c1,c2—学习因子,一般c1=c2=2;

wmax—最大惯性权重系数;

wmax—最小惯性权重系数;

t—实际循环次数;

M—最大迭代次数;

r1,r2—取值在c(7183)=[0.8,0.9]之间的随机数。

测量变量,表示种群中全部粒子的平均适应度和目前搜寻到的全局最优值之差的绝对值。因为当标准PSO算法陷入局部最优时,种群中的粒子会趋向于目前搜索到的全局最优位置pg,粒子群位置的更新也局限于pg附近。那么此时粒子xi的适应度值与全局最优位置pg的适应度值相差也很小,当PJ小于一个足够小的正实数δ时,可以认为这一代种群进化过程已经进入了停滞阶段,此时的种群便失去了多样性。因此,算法中引入PJ就相当于算法具有了自我监控能力,当标准PSO算法陷入局部最优时,可以及时采取相应措施增加种群粒子的多样性,进而增强粒子在解空间中的全局搜索能力。

2)优秀粒子保留策略

所谓优秀粒子保留策略就是在确定算法找到的局部最优值和全局最优值之前,首先计算该代种群中全部粒子适应度值的平均值favg,保留适应度值优于favg的粒子,非优秀粒子用随机生成的新粒子替换。其优点是能够保留每一代种群中的精英粒子,有利于群体向更优位置方向靠近。

3)混沌思想

混沌是一种无规则的运动形式,它是由确定性非线性系统产生的并且对初始条件有敏感依赖性的往复稳态非周期运动。确定性系统中呈现混沌状态的变量称为混沌变量。Logistic方程是一种典型的可产生混沌变量的发生器,在优化算法中普遍被采用。其迭代方程为:

其中,μ为控制参数,一般取μ=4,xk为变量。则上述混沌序列发生器可表示成:

其中,cxj为第j个混沌变量,k为迭代步数。

4)PSO具体操作步骤

在工程实践中,人们往往利用混沌现象的遍历性增强粒子在解空间的全局搜寻能力,从而获得最优解或符合误差要求的解。因此,本文把这种混沌思想引入到标准PSO算法。在标准PSO算法中嵌入混沌局部搜索策略的具体操作步骤如下:

首先,在利用式(2)-式(4)对粒子进行位置更新之前,首先计算PJ,检查种群进化是否进入停滞阶段。如果种群已经进入停滞阶段,则对于满足f(xi)-f(pg)<δ(i=1,2,…,N)的粒子,首先令x=xjk,然后用式(7)决策变量映射成混沌变量。

其次,设置混沌局部搜索迭代次数k,利用式(6)对混沌变量cxjk(j=1,2,…,n)进行混沌迭代,得到k个迭代序列。若优化问题每一维变量的取值范围是[xmin,jxmax,j],把上述k个迭代序列的混沌变量按式(8)转化为决策变量。

最后计算搜索到的所有新粒子的适应度,找出最优秀的粒子,并用该粒子代替当前粒子,实现粒子更新。

b)实现混沌粒子群算法的步骤(图1)

在电梯运行过程中的T0决策时刻,对未来T∈[T0,T0+t]的时域中采用混沌粒子群算法进行能量管理决策优化。设计的混沌粒子群算法的步骤如下:

1)初始化:设定粒子种群规模为N,在本优化过程中取10,每个粒子中包含超级电容和蓄电池中2个重要开关变量,所以其维数D=2,并在2个开关变量所能取得的范围内随机选取一组粒子,并将每个粒子的初始位置作为当前个体最优位置pi,计算全部粒子的适应度值,把所有粒子中具有最优适应度值的粒子位置标为全局最优位置pg。

2)令t=1,考虑到超级电容的容量及蓄电池因使用寿命对充放电的特殊需求,可确定约束位置向量和速度向量中各个决策变量的取值范围。并计算各个粒子适应度值f(xi)和这一代种群的平均适应度值favg。

3)以favg为阈值,将种群中每个粒子的适应度值与favg进行比较,如果f(xi)<favg,剔除该不良粒子并且及时补充一颗新的随机粒子,然后再计算新粒子的适应度值。

4)将每个粒子xi的适应度值f(xi)与pi的适应度值f(pi)进行比较,如果f(xi)>f(pi),则令pi=xi,然后再把xi的适应度值f(xi)与pg的适应度值f(pg)进行比较,如果当前xi的适应度值较优,则令pg=xi。

5)计算PJ。若PJ≤δ(δ为一足够小正数),则说明该粒子的进化过程进入了停滞阶段。此时,设置混沌迭代次数k的取值,然后按照混沌局部搜索策略的具体操作步骤执行。否则,仍然按照式(2)-式(4)更新该粒子位置。

6)令t←t+1,如果t达到最大迭代次数,则停止计算,输出最优解pg。否则,转向执行Step 2继续进行计算。这里的最优解表示在时刻下,经优化后的蓄电池与超级电容间的DC/DC开关变量α和最优解和超级电容和电梯变频器的DC/DC开关变量β能够使得T∈[T0,T0+t],电梯运行对电网的耗电量最小。

各个T0的决策时刻,混合能源的管理模型以消耗最少电网的电量为目标,采用混沌粒子群算法求解出在各个时域中蓄电池与超级电容间的DC/DC开关变量α和最优解和超级电容和电梯变频器的DC/DC开关变量β的值,通过这种控制策略,在满足电梯运行能量需求的同时,能够减少电梯对电网能量的需求。

5 优化结果

采用Matlab优化工具箱编写程序,对在电梯运行的各个时域中分别采用混沌粒子群算法进行能量管理决策进行优化。图2为经优化后蓄电池与超级电容间的DC/DC开关变量α的最优解,图3为超级电容和电梯变频器的DC/DC开关变量β的优化结果。图中表示各个时刻,蓄电池、超级电容、电网以及电梯之间的能量交互过程。从图2和图3中可知,在当电梯处于充电状态时如空载上行,图2和图3的纵坐标此时α和β开关状态变值为-1时,蓄电池和超级电容把多余的能量存储起来,为储能状态,等到电梯处于放电状态时如满载下行时,图2和图3的纵坐标α和β开关状态值为1时,电梯优先使用超级电容的能量,再使用蓄电池的能量,为释放能量,此时超级电容与蓄电池的电量就提供给电梯使用,达到节能的目的。

为了验证基于混沌粒子群优化算法的混合能源优化策略的节能效果,分2种情况进行对比:直接采用蓄电池和超级电容直接对电梯进行供电;采用本优化算法的控制策略对蓄电池和超级电容的变量开关进行优化后电网的耗电量进行对比,其图如4和图5所示,其横坐标表示时刻,纵坐标表示该时刻下的电网耗电量。

通过图4和图5很明显可以看出,经优化后不同时刻下所需电网的耗电量得到了明显减少,纵坐标的数量级少了一级,通过计算可知使用该优化结果可节约80%的电能。

6 结语

提出了基于混沌粒子群算法求解电梯混合能源管理模型,将电梯混合能源管理中的非线性变量进行粒子编码,对超级电容及蓄电池的约束处理问题进行了处理。通过验证分析可知,采用了混沌粒子群算法对蓄电池与超级电容间的DC/DC开关变量α和最优解和超级电容和电梯变频器的DC/DC开关变量β的能量管理决策进行优化,在满足电梯运行的能量的前提下,能够较大程度的较少电网的能量,节约了电能,也验证了粒子群算法求解电梯混合能源管理模型的有效性。

摘要：电梯混合能源控制优化是对电梯、太阳能、蓄电池、超级电容等设备间的能量交换进行控制优化。根据电梯系统的特点,在满足电梯所需能量的前提下,以电网所需的耗电量最小为优化指标,建立电梯的混合能源优化目标函数。其中目标优化函数中的变量如0-1等非连续的开关变量,其混合能源管理优化过程是非线性变参数优化问题,难以用普通的解析方法进行计算。采用混沌粒子群算法的智能求解策略,通过对某电梯的仿真,验证了模型和算法的有效性。

关键词：电梯,优化函数,能源管理,混沌粒子群算法

参考文献

[1]刘文,刘艳斌,张星.基于虚拟样机技术的电梯动态设计与优化[J].图学学报,2012,33(6):82-88.

[2]Teleke S,Baran M E,Bhattacharya S,et al.Rule-Based Control of Battery Energy Storage for Dispatching Intermittent Renewable Sources[J].Sustainable Energy,2010,1(3):117-124.

[3]Baumann L,Boggasch E,Rylatt M,et al.Energy flow management of a hybrid renewable energy system with hydrogen[C]//Proc IEEE Conference on Innovative Technologies for an Efficient and Reliable Electricity Supply(CITRES 2010).Waltham,MA,UK:IEEE Press,2010:78-85.

[4]段晓东,王村睿,刘向东.粒子群算法及调度算法[M].沈阳:辽宁大学出版社,2007.

[5]van den Bergh F,Engelbrecht A P.A Cooperative approach to particle swarm optimization[J].Evolutionary Computation,2004,8(3):225-239.

[6]Kennedy J,Eberhart R.A discrete binary version of the particle swarm algorithm[C]//Proc IEEE International Conference on Systems,Man and Cybernetics.Washington,DC,USA:IEEE Press,1997:4104-4108.

[7]高鹰,谢胜利.混沌粒子群优化算法[J].计算机科学,2004,31(8):13-15.

改进混沌粒子群算法 篇7

微粒群优化算法PSO属于群体智能方法的一个分类,是1995年首次由Kennedy与Eberhart等首次提出的[1],是一种新的进化算法。但当面临复杂的优化问题,由于目标存在很多的局部极值,也不可避免地存在早熟、收敛速度慢等一些缺陷。

本文针对这一问题,提出以全局性更好的小生境策略,小生境中各个子种群互相排斥,动态形成自己独立的搜索空间,各自追逐自己搜索范围内的极值点,使小种群在搜索空间有效地分布,避免了协同中的种群汇聚;进一步引入淘汰更新机制,迭代一定次数后更新最劣子种群,以保证整个种群不断向前进化,直至搜索到全局最优点;引入变尺度混沌变异,进一步提高了本文算法的搜索精度。

2004年Sun等在研究了Clerc等人关于粒子收敛行为的研究成果后,从量子力学的角度提出了一种新的PSO算法模型。认为粒子具有量子行为,并根据这种模型提出了量子粒子群算法(QPSO)[2],并且得到了很好的实验效果。

1 粒子群和量子粒子群算法

1.1 粒子群算法(PSO)

由Kennedy和Eberhart提出的PSO算法[3],是将寻优的参数组合成群体,通过对环境的适应度来将群体中的个体向好的区域移动。与其他进化算法不同,个体没有体积的微粒(点),结合微粒的历史最佳位置和群体历史最佳位置信息,以一定的速度向目标值逼近。

1.2 量子粒子群算法(QPSO)

从量子力学的角度提出了一种新的PSO算法模型[4,5]。认为粒子具有量子行为,并根据这种模型提出了量子粒子群算法(QPSO),在量子空间中粒子的满足聚集态的性质完全不同,它可以在整个可行解空间中进行搜索,因此QPSO算法的全局搜索的性能远远优于标准PSO算法。在量子空间中,粒子的速度和位置是不能同时确定的。通过波函数来描述粒子的状态,并通过求解薛定谔方程得到粒子在空间某一点出现的概率密度函数,又通过蒙特卡罗随机模拟方式得到粒子的位置方程。在具有量子行为的粒子群优化算法中,粒子的主要迭代公式:

undefined

Pid=ϕ*Pid+(1-ϕ)*Pgd ϕ=rand (2)

xid=Pid±β*|mbest-xidundefined

这里mbest是粒子群pbest的中间位置,Pid为Pid和Pgd之间的随机点,ϕ和μ都是[0,1]的随机数,β为QPSO的收缩扩张系数。

QPSO的算法流程可以这样描述:

(1) 初始化粒子群;

(2) 根据公式(1)计算mbest的值;

(3) 求每一个粒子的适应度值,比较求出Pid;

(4) 对于每一个粒子比较Pid,求得Pgd;

(5) 更新Pgd;

(6) 对于粒子的每一维,根据公式(2),在Pid和Pgd之间取得一个随机点;

(7) 根据公式(3)获得一个新的位置;

(8) 重(2)～(7)直到条件不满足,则迭代过程结束。

2基于混沌变异算子的小生境量子粒子群算法

2.1 RCS小生境进化策略

小生境策略以其能有效解决多峰函数优化问题而广泛应用于进化算法[6]。本文采用文献[7]提出的RCS(Real time Control System)策略作为构造小生境的基础。通过控制子种群之间的排挤和竞争,使各个子种群在进化中动态形成各自独立的搜索空间,从而实现对多个局部极值进行同步搜索,避免了算法的早熟收敛。

算法中的小生境半径定义了各个子种群独立的搜索空间,一旦某个小生境最优个体进入了其他小生境的搜索空间,则重置该个体,并在其所在的小生境内重新选择最优个体。从而使每个小生境子种群自然形成,减少了标准PSO算法和QPSO算法的所有个体作为整体种群陷入局部最优的概率。

2.2 变尺度混沌变异

混沌是自然界广泛存在的一种非线性现象,具有随机性、遍历性、初始条件敏感性等特点,已被广泛应用于随机优化[8],在局部寻优领域具有优越的性能。本文使用的混沌映射Logistic迭代方程为:

βundefined=μβundefined(1-βundefined) k=1,2,… (4)

β∈(0,1) β≠0.25,0.5,0.75

其中βundefined是对应于粒子Xundefined的第j个混沌向量,当μ=4时,logistic方程完全进入混沌状态。经过多次试验可以证明,利用混沌的遍历性,可以很好地实现局部搜索。

在寻优的过程中,对每个小生境的种群最优个体进行混沌迭代变异,变异空间随着代数的增加而逐渐减小。对第i个种群的最优个体Pibest=[x1,x2,…,xj,…,xn]进行混沌变异最优粒子Pnbest变量的搜索空间随着代数的增加而围绕小生境的极点逐渐缩小。这样,在进化初期变异尺度大,有利于算法在广阔的空间搜索全局最优解;在进化后期变异尺度小,在小空间内紧紧围绕局部极点精细搜索,有利于提高解的精度。

2.3 基于混沌变异算子的小生境量子粒子群算法

结合小生境策略全局优化与变尺度混沌变异精细搜索各自的优点,本文提出一种全新的粒子群算法,并在算法中引入了种群淘汰策略,结合小生境的子种群竞争策略一起使用。运行中首先利用RCS竞争策略,使各个小生境子种群形成独立的搜索空间,追逐不同的极值点;然后每隔一定代数,对陷入局部最优的最劣子种群进行随机初始化。这样可使种群在不断的竞争和更新中向前进化,从而避免了算法早熟收敛,保证了收敛到全局最优。而没有更新的小生境种群继续向前进化,又保证了搜索精度的连续提高。NCQPSO(Niche Chaotic mutation Quantum-Behaved Particle Swarm Optimization )算法具体流程如下:

(1) 初始化小生境粒子种群;

(2) 计算粒子适应度,找出每个小生境种群中的最优粒子;

(3) 实施RCS小生境淘汰选择进化策略,确定每个小生境独立搜索空间的最优个体;

(4) 如果迭代次数到达一定代数,则对最劣的小生境子种群进行更新初始化;

(5) 对所有小生境子种群的最优个体实行变尺度的混沌变异,进一步提高搜索的精度;

(6) 对每一个小生境子种群独立进行QPSO优化;

(7) 如果满足条件,则停止迭代,输出最优解,否则转向(2)。

3 实验结果和分析

为了测试基于混沌变异小生境的量子粒子群算法(NCQPSO)的性能,本文使用了3个典型测试函数来进行实验,并且将实验的结果和标准的PSO和原始的QPSO算法进行比较。所用函数如图1所示,Rosenbrock函数是一个经典复杂优化问题,其全局最优点位于一个平滑、狭长的抛物线形山谷内,由于函数仅仅为优化算法提供了少量信息,使算法很难辨别搜索方向,找到全局最小点的机会微乎其微,因此,Rosenbrock函数通常用来评价优化算法的执行效率。Rastrigrin和Griewank函数是典型的非线性多模态函数,它们具有广泛的搜索空间、大量的局部极小点和高大的障碍物,通常被认为是遗传算法很难处理的复杂多模态问题。表1给出的是3个测试函数的初始空间,以及理论值,维位置的上限。

本文比较了NCQPSO算法和标准的PSO算法,原始的QPSO 算法对于基准函数测试的结果。算法的粒子种群为25,分为5个子种群,每个子种群的粒子数是5。标准PSO的参数的设置如下:

c1=c2=2 wmax=0.9 wmin=0.1

算法统一的迭代的次数定为2000次,2000次以后认为算法停滞。各个算法分别运行50次,取平均结果来表示算法对函数测试的结果。与此同时,将各个种群的空间维数固定为20,以便于各个算法进行比较,同时设小生境的半径Rnich为10-4。另外还将在50次运算当中成功找到最优解的次数作为解的稳定性的衡量。

从表2可以看出NCQPSO与另外两种算法相比较具有更加优秀的搜索最优解的能力,即拥有更高的稳定性和更加精确的搜索精度。为了进一步说明NCQPSO的优越性,本文给出几种算法对于Rosenbrock函数的测试曲线,如图1所示。

4 结 论

本文算法利用广泛应用于多目标函数优化的小生境策略掌控粒子群的全局搜索方向,其竞争策略使子种群在搜索过程中自动追寻不同的极值点,形成不同的搜索空间;淘汰策略则使子种群不断更新。两种策略的有机结合,成功地避免了算法的早熟收敛,提高了全局寻优能力;变尺度混沌变异的引入,则显著提高了算法的搜索精度。实验结果表明,与传统的PSO算法和QPSO算法相比,本文算法寻优能力强、搜索精度高、稳定性好,适用于处理高维多极连续函数的优化问题。

摘要：针对粒子群算法早熟收敛和搜索精度低的问题,提出了基于混沌变异的小生境量子粒子群算法(NCQPSO)。该算法结合小生境技术并加入了淘汰机制。使算法具有良好的全局寻优能力。变尺度混沌变异具有精细的局部遍历搜索性能。使算法具有较高的搜索精度,实验结果表明,NCQPSO算法可有效避免标准PSO(Particle Swarm Optimization)算法的早熟收敛,具有寻优能力强、搜索精度高、稳定性好等优点。也优于原始的量子粒子群算法QPSO(Quantum-behaved Particle Swarm Optimization)。

关键词：混沌变异,小生境,粒子群优化算法,量子粒子群优化算法

参考文献

[1]Kennedy J,Eberhart RC.Particle Swarm Optimization[A].Proceed-ings of the IEEE Service Center,1995:1942-1948.

[2]Sun J,Feng B,Xu WB.Particle SwarmOptimization with Particles Hav-ing Quantum-Behavior[A].Proceedings of 2004 Congress on Evolu-tionary Computation,2004:325-331.

[3]Eberhart R,Kennedy J.A new optimizer using particle swarm theory[C].Proc of Int’1 Symp on Micro Machine and Human Science.Pis-cataway,IEEE Service Center,1995:39-43.

[4]Sun J,Xu WB.A Global Search Strategy of Quantum-behaved ParticleSwarm Optimization[A].Proceedings of the IEEE Congress on Cyber-netics and Intelligent System,2004:111-116.

[5]Maurice Clerc,James Kennedy.The Particle Swarm:Explosion,Stabili-ty,and Convergence in a Multi-Dimensional Complex Space.IEEETransactions on Evolutionary Computation,2002:58-73.

[6]陈辉,张家树,张超.实数编码混沌量子遗传算法[J].控制与决策.2005,20(11):1300-1303.

[7]Lee C G,Cho D H,Jung H K.Niche genetic algorithm with restrictedcompetition selection for multimodal function optimization[J].IEEETrans on Magnetics,1999,35(3):1122-l125.

改进混沌粒子群算法 篇8

旅行商问题(TSP)是一类著名的组合优化问题,要求找到经过所有城市、且每个城市仅经过一次的路径最短的Hamilton回路。由于原理简单,在很多领域都有广泛的应用。例如VLSI芯片设计[1],网络路由[2],车辆路径[3]等。

对一个n城市的TSP问题,一共存在(n-1)!/2条可能路径,因此,TSP是一个NP-C问题。传统的解决手段[4]有动态规划法(DM)、分枝定界法(LC)等。但DM是一个递归算法,时间复杂度为O(n22n),空间复杂度为O(n2n)。随着问题规模的增长,所需空间会急剧增长。LC的算法时间复杂度也是O(n22n),而且为了计算智能化的判断函数,必须为每个节点附带一个归约矩阵。所以,在实际中很少将DM与LC用于大规模求解问题。

Hopfield和Tank[5]首先提出利用Hopfield神经网络(HNN)求解TSP问题,该方法简单明了,且能够采用硬件实现。但是,该方法也存在多种不稳定性,经常出现局部最优解。因此,不少学者对该网络进行分析和改进。例如,Peng[6]提出一种局部最小逃逸(LME算法,通过参数扰动,使网络能从局部极小点跳出。Papageorgious[7]发展了LME算法,提出用SA来调整参数。李萍等[8]也提出采用SA来指导Hopfield网络的参数设置。

但是上述改进方法皆不能有效解决HNN的不稳定性问题,主要是因为LME算法虽然能够逃逸出局部最小点,但是缺乏对全局最优搜索的指导;SA算法尽管可以使得参数模拟自然界的退火过程逐步下降到指定值,但是面临相同的问题。

考虑到粒子群优化(PSO)是一类性能优异的全局优化算法,效率高,结构简单,代码短。同时为了使其性能更好,引入混沌算子,构成混沌粒子群算法(CPSO)。将CPSO算法嵌入到HNN中,就得到本文的CPSO-HNN算法。这是第一次有人将CPSO与HNN相结合。

文章结构如下:第1节介绍用HNN求解TSP的原理;第2节是基本的PSO算法;第3节给出所提出的CPSO-HNN的原理与步骤;第4节通过仿真将本文算法与文献[5]的基本HNN算法、文献[8]的SA-HNN算法以及“PSO+HNN”策略相比较,从获得全局最优解的概率与算法运行时间两方面,展现本文算法的有效性与快速性。

2 HNN求解TSP原理

Hopfield神经网络能够优化的函数形式必须如(1)式:

如何将TSP问题转化为式(1)形式的待优化函数,目前较好的方法是将自变量从城市序号的排列P,变为有效路线换位阵v(ER-TA)[9]。为解释ERTA的含义,以一个5-TSP为例,如图1所示。

图1(a)是一个5-TSP问题的路线,可记作P={01234}。对应地,采用ER-TA,则如图1(b)所示。这里矩阵v第i行第j列的元素vij表示在旅行路线的第i个位置是城市j。

采用ERTA后,可以构造一个如下式所示的能量函数,

式中,第1项保证v中每行的1不多于1个,即对每个城市访问次数不超过1次;第2项保证v中每列的1不多于1个,即每次访问的城市数不超过1个;第3项保证v中1的数目等于城市数目N;第4项才是旅行路线长度。这里A、B、C、D均是正常数。

最后,式(2)可以与式(1)等价,即令

2 粒子群算法

粒子群优化(PSO)是模仿自然界鸟群,蜂群,鱼群的行为规律的一类随机优化算法。图2给出了PSO的流程图。

PSO将每个可行解视作一个粒子(particle),每个粒子有两个属性,位置x与速度v。假设第i个粒子的位置与速度如下:

其中N表示问题的维数。每次迭代过程中,计算每个粒子的适应度函数(fitness function),然后将粒子群不断跟踪两个最好的粒子:一个是当前粒子经历的最好位置,称为“pBest”;另一个是当前粒子的邻域内最好的粒子,称为“nBest”;如果邻域为整个粒子群,那么n Best变为全局最好的粒子,称为“g Best”。综上,某粒子的速度与位置按照下式更新:

其中ω表示惯性权重(inertia weight),控制过去的速度对现在速度的影响。c1与c2是正常数,表示加速度系数(acceleration coefficients)。r1与r2是两个在区间[0,1]上满足均匀分布的随机数。Δt表示时间间隔。必须注意的是,粒子速度存在一个上限vmax,以保证粒子的搜索不会太快。

3 混沌粒子群算法

传统的PSO算法中,参数(ω,r1,r2)是影响收敛的关键参数[10]。然而,由于这些参数或在理论上是绝对随机(absolute random)的,或在实际中的计算机上运行时是伪随机(pseudo random)的,会造成以下两点问题:1)绝对随机性不能保证粒子在解空间中的遍历性(ergodicity);2)伪随机性不能保证粒子在不同时刻的独立性(independency)。

因此,将式(7)中的r1与r2改用下式计算:

其中ri(0)∈(0,1)且ri(0)埸{0.25,0.5,0.75}.通过式(9)得到的ri(t)会表现出遍历性与混沌性,如图3(a)所示。如果ri(0)在{0.25,0.5,0.75}中取值,则ri(t)收敛到一个固定常数,如图3(b)所示。

ri(t)的遍历性保证了粒子在解空间中的遍历性,混沌性保证了粒子之间的彼此不相关性,这就很好地解决了上述两个问题。这也说明了为什么本文不直接采用“PSO+HNN”的策略。

4 基于CPSO的HNN

传统HNN的基本思想是沿着梯度下降的最优路径到达离初始点最近的极小点,所以整个学习过程是一个非线性优化过程,有可能产生局部最小值与震荡,使结果变差,即得不到全局最优解。而改进后的CP-SO-HNN算法充分利用了CPSO的全局搜索性能,能够保证HNN跳出局部极小,其算法过程可以用下述伪码表示:

Step1初始化参数,构建基于HNN的能量函数,随机选取一个初始解x0,令k=1;

Step2按照HNN的搜索过程,寻找到一个局部极小点xk;

Step3将局部极小点设置为CPSO的初始化位置,继续搜索能量函数更小的粒子,覆盖xk;

Step4若满足终止条件,则跳到Step5;否则令k=k+1,返回Step2;

Step5输出最优解。

5 实验与讨论

5.1 验证算法有效性

为了验证CPSO-HNN算法的优越性,以10城市TSP问题为例,坐标如表1所示。

本文算法得到的最优结果如图4所示,其中最优路径为{9,10,2,3,1,4,5,6,7,8,9},路径总长仅为2.6907。

5.2 算法收敛性能比较

对比算法采用文献[5],文献[8]与“PSO+HNN”策略。每种算法各运行100次,结果列于表2。

由表2,本文算法有92%的概率得到全局最优解,另外所有解都在相对误差5%的范围内。反观其他算法,文献[5]是原始的HNN,其最好纪录为2.89,一次也没有得到最优解;文献[8]采用SA指导HNN的参数设置,有83%的概率得到全局最优解,有98%的概率得到相对误差小于5%的次优解;采用“PSO+HNN”的策略,也能得到不错的结果,有89%的概率得到全局最优解,其所有解也在相对误差为5%的范围之内。

综上,本文算法在收敛性能上最优。

5.3 算法运行时间比较

一个好的算法,不仅必须有较高的命中率,而且耗时必须在可接受范围之内。因此运行各个算法多次,剔除那些收敛到局部极小解的迭代过程,计算每种算法的平均收敛时间,结果见表3。考虑到文献[5]收敛到最优解的概率为0,故在表3中不予考虑。

由表3可见,文献[8]耗时最长,为5.81s.这是因其采用了SA,模拟退火过程一般较慢。而“PSO+HNN”策略由于采用了PSO算法,速度明显改善;而本文算法耗时最短,仅为2.16s.显然在运行时间上,本文算法亦最优。

6 结论

本文提出一种CPSO-HNN算法,用于求解TSP问题。通过实验与文献[5][8]提出的方法以及“PSO+HNN”策略相比较,证实了本文算法的有效性、收敛性与快速性。

更进一步的研究方向在于,如何将其向更大规模的TSP问题拓展。

摘要：针对Hopfield网络求解TSP问题经常出现局部最优解,该文将混沌粒子群算法(PSO)与之结合,提出一种基于混沌粒子群的Hopfield神经网络方法。通过实验将其与文献[5,8]以及“PSO+HNN”策略比较,验证了该文算法不仅能够以更大概率收敛到全局最优,而且耗时更少。

关键词：旅行商问题,混沌粒子群算法,Hopfield网络

参考文献

[1]Dorigo M,Gambardella L M.Ant colony system:A cooperative learning appraoch to the traveling salesman problem[J].IEEE Transac-tions on Evolutionary Computation,1997,1(1):53-66

[2]Ascheuer N,Junger M,Reinelt G.A branch and cut algorithm for the asymmetric traveling salesman problem with precedence con-straints[J].Computational Optimization and Applications,2000,17(1):61-84

[3]Laporte G.The vehicle routing problem:An overview of exact and approximate algorithms[J].European Journal of Operational Re-search.1992,(59):345-358

[4]王剑文,戴光明,谢柏桥,等.求解TSP问题算法综述[J].计算机工程与科学,2008,30(2):72-75.

[5]Hopfield J J,Tank D W.Neural computation of decisions in optimization problems[J].Biological Cybernetics.1985,52(3):141-152

[6]Peng M,Narendra K,Gupta Alistair F.An investigation into the improvement of local minima of the Hopfield network[J].Neural Net-works.1996,9(7):1241-1253

[7]Papageorgiou G,Likas A,Stafylopatis A.Improved exploration in Hopfield network state-space through parameter perturbation driven by simulated annealing[J].European Journal of Operations Research,1998,(108):283-292.

[8]李萍,高雷阜,刘旭旺.一种基于模拟退火和Hopfield神经网络求解TSP算法[J].科学技术与工程,2008,8(14):3937-3939.

[9]Siqueira P H,Steiner M T A,Scheer S.A new approach to solve the traveling salesman problem[J].Neurocomputing,2007,70(4-6):1013-1021.