融合Rosenbrock搜索法的混合粒子群算法

来源:用户上传      作者:

　　摘 要：为克服粒子群算法在处理复杂高维问题时易陷入局部最优及寻优精度低等缺陷，提出一种融合Rosenbrock搜索法的混合粒子群算法。首先，利用Tent混沌序列进行种群初始化;其次，采用去速度项的简化粒子群公式提高收敛速度并对个体极值加入扰动，增强粒子种群多样性;最后，当全局最优个体更新停滞时，利用Rosenbrock搜索法对全局最优个体进行局部搜索，提高解的精度。利用8个常用基准测试函数分别对30维和50维问题进行实验，证实该算法可寻到病态函数Rosenbrock全局最优值，且比其它7个函数的寻优精度提高[10-2]数量级。实验证明该算法收敛速度快，解的精度高，全局搜索能力强，寻优能力明显提高。
　　关键词：粒子群算法;Tent混沌;极值扰动;Rosenbrock搜索法
　　DOI：10. 11907/rjdk. 192513 开放科学（资源服务）标识码（OSID）：
　　中图分类号：TP312 文献标识码：A 文章编号：1672-7800（2020）007-0060-06
　　Hybrid Particle Swarm Optimization Algorithm Combining
　　Rosenbrock Search Method
　　HUANG Zhuo-chao， ZHANG Wei， WANG Ya-gang
　　（School of Optical-Electrical and Computer Engineering， University of Shanghai for Science and Technology，
　　Shanghai 200093， China）
　　Abstract：For the particle swarm algorithm， it is easy to fall into local optimum and low precision in processing when dealing with complex and high-dimensional problems. A hybrid particle swarm optimization algorithm combining Rosenbrock search is proposed. Firstly， the improved algorithm uses the Tent chaotic sequence to initialize the population， so that the initial particles are well distributed in the solution space. Secondly， the simplified particle swarm optimization algorithm with the velocity term removed is used and the disturbance is added to the individual extremum to enhance the particle population diversity， so that the algorithm is not easy to premature. Finally， the global optimal individual’s stagnation update times is used to judge whether the algorithm falls into local optimum， and the Rosenbrock search method is used to locally search the global optimal individual to improve the solution quality. Experiments were performed on 30-D and 50-D problems using eight common benchmark functions. Compared with some improved particle swarm optimization algorithms proposed in other literatures， the proposed algorithm can find the global optimal value of the ill-conditioned function Rosenbrock， and the optimization accuracy of the other seven functions has an improve of magnitude of [10-2]. The proposed algorithm has fast convergence speed， high precision of the solution， strong global search ability and obvious improvement ability.
　　0 引言
　　粒子群優化（Particle Swarm Optimization，PSO）算法是1995年Eberhart &Kenney[1]受飞鸟集群活动规律性启发提出的一种随机智能群优化算法。由于算法需调整的参数少、运行速度快及实现简单等特点，已在多个科学和工程领域得到广泛应用[2-4]。但该算法在处理高维多峰问题时存在早熟收敛、容易陷入局部最优等不足。
　　针对这些问题，许多学者对经典粒子群算法提出了不同的优化策略。如文献[5]中，shi等以算法复杂度为代价，利用模糊规则确定惯性权重;文献[6]提出一种新的惯性参数自适应策略，主要利用贝叶斯技术更新粒子速度和位置，并利用柯西变异防止算法陷入局部最优;文献[7]引入Sigmoid函数，并根据粒子当前适应度优劣自适应地调整惯性参数，让适应度好的粒子进行小范围局部搜索，适应度差的粒子进行大范围全局搜索，增强了算法寻优能力;文献[8]研究了PID控制与粒子群算法相似性，并利用闭环反馈控制的思想改进粒子群算法;文献[9]采用去掉速度项的简化粒子群算法，并证明了改进算法的收敛性;文献[10]也采用除去速度项的简化公式进行迭代更新，并利用个体最优均值和群体最优值对加速因子进行动态更新，使算法具有较好的性能，但在一些病态测试函数中未能取得较好的效果;文献[11]在位置更新公式中引入了正弦函数因子，利用正弦函数振荡特性，保持算法在迭代过程中种群多样性。一些学者还采用算法结合策略，如文献[12]结合粒子群算法与模拟退火算法，模拟退火算法防止粒子群算法早熟，帮助粒子概率跳出局部最优解;文献[13]结合PSO算法与人工鱼群算法，利用人工鱼群公告板、群聚和随行策略的模式改进PSO更新公式，提高了算法性能;文献[14]将序贯二次规划（SQP）法作为局部搜索算法，通过与PSO结合，提高了收敛速度，但对一些高维多极点问题难以获得全局最优解。 　　對于复杂多峰问题，现有算法很难实现算法全局收敛和收敛速度的平衡。因此本文提出一种融合Rosenbrock搜索的混合粒子群算法（Hybrid Particle Swarm Optimization Algorithm Combining Rosenbrock Search，RHPSO）， 改进算法利用Tent混沌序列确定粒子种群初始位置，采用除去速度项的位置更新公式，有效提高算法收敛速度，并在迭代公式中的个体最优位置加入扰动，增加种群多样性，可有效避免算法早熟，在全局最优个体更新陷入停滞时，采用Rosenbrock搜索法进行有效的局部搜索，提高解的质量。实验结果表明，本文算法在收敛速度和全局收敛性上均优于已有的粒子群改进算法。
　　1 标准粒子群算法原理
　　粒子群算法在解决最优化问题时，一般假定问题的解为搜索空间中的一个粒子。粒子在迭代过程中只根据粒子个体当前发现的历史最优解pbest及粒子群体当前全局最优解gbest更新自己的位置，持续更新直到满足迭代终止条件，最后得出最优解。
　　标准粒子群算法数学描述为：在D维问题可行域搜索空间中，有N个粒子组成的一个粒子群体，每一粒子均有位置和速度两个属性。例如，第i个粒子的位置和速度分别为[xi=（xi1，xi2，？，xiD）]：[xi=（xi1，xi2，？，xiD）]和[vi=（vi1，vi2，][？，viD）]，均为D维向量[vi=（vi1，vi2，？，viD）];第i个粒子的个体历史最优值为pbest，位置为：[pi=（pi1，pi2，？，piD）];种群全局最优值为gbest，位置为[pg=（pg1，pg2，？，pgD）]。
　　在寻优过程中，第i个粒子通过式（1）、式（2）更新位置和速度。
　　其中，[i=1，2，？，M];[d=1，2，？，D]。[ω]为惯性权重因子，可调节算法全局和局部搜索能力，一般取值在[0.1～0.9]之间。t为当前迭代次数;[c1]是粒子向自我历史最优位置学习的权重系数，[c2]是粒子向全局最优位置学习的权重参数;[r1]和[r2]是服从[U（0，1）]分布的随机数;[v（t+1）id]和[x（t+1）id]表示第i个粒子更新后的速度与位置;为防止粒子在迭代过程中跑出搜索空间，一般通过设定位置范围[[xmin，xmax]]和速度范围[[vmin，vmax]]限制粒子移动。
　　2 算法描述
　　本文按照文献[9]中除去速度项的位置更新公式，具体如下：
　　迭代公式由原来的二阶变为一阶，算法更简单高效，避免了速度项引起的粒子发散，使粒子在搜索过程中收敛速度更快[9]。
　　2.1 混沌序列初始化种群
　　混沌序列具有随机性、遍历性和规律性，利用这些性质进行优化搜索，可有效保持种群多样性，尽可能降低算法陷入局部最优的可能性。已有很多学者将混沌的思想引入启发式算法，较多文献使用的是Logistic混沌映射，文献[15]表明Tent映射比Logistic映射有更好的遍历均匀性，并针对Tent混沌序列在迭代过程中存在小周期点和不稳定周期点的不足，提出一种改进的Tent混沌映射表达式，具体为：
　　变换后表达式为：
　　其中[N]为序列长度，[rand0，1]是[[0，1]]内的随机数，加入随机量[rand0，1*1N]不仅可以保持Tent映射的随机性、遍历性和规律性，还可避免迭代过程中陷入小周期点和不稳定周期点内。鉴于上述优点，本文采用改进的Tent映射表达式在可行域内产生一组优秀的初始种群，步骤如下：
　　Step1：利用随机数发生器产生一个（0，1）之间的随机数，并利用式（5）对该随机数产生长度为L（L>N）的序列。
　　Step2：对序列中L个元素分别进行D次Tent变换，产生L个长度为D的向量。
　　Step3：对L个向量进行函数适应度评估，选择N个适应度最优的向量作为初始种群。
　　利用改进Tent混沌方法产生一组较大的点库，该点库中的点均匀分布在问题解空间中，本文从中选取适应度最优的前N个粒子作为初始种群，按照该选取方式使部分初始解分布在全局最优点附近的概率较大，可有效帮助算法找到最优解，并减少发现最优解所需的迭代次数。
　　2.2 个体极值扰动
　　粒子群算法中粒子由个体最优和全局最优引导飞行，当个体最优位置和全局最优位置长时间停止更新时，粒子群算法陷入局部最优，粒子会被聚集在一个很小的区域，由于速度很小，粒子难以找到更优位置，此时需要扩大粒子搜索范围，有利于让粒子跳出局部最优解，探索新区域。所以，个体最优位置引入极值扰动以扩大粒子搜索范围，避免粒子陷入局部最优，常见方法为添加一个高斯扰动[18]。本文选择添加一个简单随机扰动，亦能到达较好效果，将位置更新公式改为：
　　其中，[r3]是服从[U（0，1）]分布的随机数，个体最优值会随着[r3]取值不同而发生范围扰动，速度大小和方向也会发生改变。这种改进策略主要作用在迭代前期，种群搜索范围扩大，粒子会飞向更多新位置，粒子容易发现更优值，通过粒子间的相互学习，粒子会向更优位置移动，减少粒子陷入局部最优的可能。
　　2.3 Rosenbrock搜索法
　　Rosenbrock方法又称为转轴法，于1960年由Rosenbrock[16]提出，后由Bazaraa等改进，是一种解决无约束最优化问题时无需函数导数信息的直接方法，该算法每次迭代包含探测阶段和构造搜索方向两部分，具体步骤[17]如下：
　　（1）探测阶段。
　　Step1：给定一个初始可行解[x（1）∈Rn]，单位正交的n个方向[d（1），d（2），？，d（n）]，一般为坐标轴方向，搜索步长[δ（0）1，δ（0）2，？，δ（0）n，]放大因子[α>1]，缩小因子[β∈（-1，0）]和允许误差[ε>0]。置[y（1）=x（1）]，[δi=δ（0）i，i=1，2，？，n]，置k=1，j=1。 　　Step2：如果[fy（j）+δjd（j）<fy（j）]，则令[y（j+1）=][y（j）+δjd（j）]，[δj=αδj];如果[fy（j）+δjd（j）fy（j）]，则令[y（j+1）=y（j），δj=βδj]。
　　Step3：如果[j<n，]则置[j=j+1]，转Step2;否则，转Step4。
　　Step4：[fy（n+1）<fy（1）]，则令[y（1）=y（n+1）]，置[j=1]，转Step2; 若[fy（n+1）=fy（1）]，则进行Step5。
　　Step5：[fy（n+1）<fx（k）]，则进行Step6; 否则，如果对每个[j]，成立[δj<ε]，则停止计算，[x（k）]作为最优解的估计，如果不满足终止条件，则令[y（1）=y（n+1）]，置[j=1]，转Step2。
　　Step6：令[x（k+1）=y（n+1）]。如果[x（k+1）-x（k）<ε]，则取[x（k+1）]作为极小点的估计，停止计算;否则，进入构造新的搜索方向阶段。
　　（2）构造新的搜索方向。
　　Step7： 根据上一阶段探测结果，有[x（k+1）=x（k）+][i=1nλid（i）]，其中[λi]是探测阶段中所有沿[d（i）]方向的步长代数和，向量[p=x（k+1）-x（k）]可能是有利于函数值下降的方向，为此定义一组向量[p（1），p（2），？，p（n）]为：
　　再利用施密特正交化，把向量组[p（j）]正交化，得：
　　再单位化，令：
　　由此得到n个新单位正交的搜索方向。
　　当粒子陷入局部最优后，常利用高斯变异或混沌变异[19-20]帮助粒子跳出局部最优，但由于缺乏一定的引导性，很多变异是无效的，并没有让粒子跳出局部最优。Rosenbrock搜索算法增强了PSO算法局部搜索能力，可有效提高最优解精度。另一方面，当粒子陷入局部最优难以跳出时，一般情况下是粒子部分维度处于极差状态。在合理选择搜索步长[δ]及放大因子[α]和縮小因子[β]的情况下，Rosenbrock搜索可有效改善单个维度或几个维度陷入较差值的情况，即增强粒子跳出局部最优的能力。与极值扰动相比，该方法主要作用在粒子迭代后期，因为此时粒子速度较低，种群多样性降低，跳出局部最优的能力变差。
　　综上所述，改进算法具体步骤如下：
　　Step1：设定混合粒子群算法及Rosenbrock搜索法的各项参数，并利用tent混沌映射初始化粒子的位置。
　　Step2：评价所有粒子的适应度，将个体粒子当前最优位置设为[pi]，种群最优位置设为[pg]。
　　Step3：按（6）式更新所有粒子的位置，评价所有粒子的适应度，并更新[pi]和[pg]。
　　Step4：若全局最优粒子在T次迭代中未得到改变，则全局最优粒子执行Rosenbrock搜索，直到RosenBrock算法收敛或者Rosenbrock搜索次数达到设定值，更新[pg];否则，转Step3。
　　Step5：若算法到达终止条件，则输出全局最优粒子的位置及其适应值，并停止迭代;否则，转Step3。
　　3 仿真实验及结果分析
　　3.1 基准测试函数
　　本文选取3个改进PSO算法与本文提出的改进算法共4个算法，分别对8个基准测试函数在30维和50维问题上进行性能比较。3个改进算法分别为：惯性权重线性递减粒子群算法（PSO-W）、自适应扩展简化粒子群算法（AESPSO）[6]和带正弦函数因子的粒子群算法（TFPSO）[7]。
　　对不同的改进PSO算法设置相同的群体数量N=20，最大迭代次数T=1 000， PSO-w中[c1=c2=1.496 18]，[ωmax=0.9，ωmin=0.4]，AESPSO和TFPSO算法参数与对应文献中的设置相同。
　　在本文RHPSO算法中，c1=c2=1.496 18，[ω=0.729 84]，混沌序列长度L=10 000，全局最优值停滞更新的最大容忍次数M = 5，在Rosenbrock搜索中，初始搜索步长[δ]为半搜索区间的10%（如一维搜索区间为[-10，10，]则初始[δ=1]），放大因子[α=1.7]，缩小因子[β=-0.65]， 允许误差[ε=10-6]，最大搜索次数[kmax=50]，即到达最大搜索次数，即使步长未达到允许误差也会跳出搜索。
　　8个基准测试函数信息如表1所示。其中[f7x]中[ωi=1+xi4，i=1，？]。实验测试函数主要分为两类，第一类是[f1]～[f3]类的单峰函数，[f1]曲面规则一般用来测试算法寻优精度的能力，[f3]是一个典型的病态函数，在高维时表现出多模态性质，由于其存在一条极细的沟壑，算法跳出局部最优的机会很小，很难寻到全局最优值点;第二类属于非线性多模态函数，函数[f4]～[f8]属于该类函数，由于三角函项的引入，使该类函数存在大量波峰波谷，在寻优过程中极易陷入局部最优，且当问题维数增大时，寻优难度也随之增加。
　　3.2 仿真实验结果及分析
　　为检验改进算法性能，实验分为两组进行，问题维度分别为30和50，4种算法独立运行30次以消除随机性，并将30次结果求取的平均值、标准差和最优值作为评估标准，4种算法中的最佳实验结果加粗表示，实验结果如表2、表3所示。
　　从表2可以看出本文提出的RHPSO算法在解决高维单峰和多峰问题上均有优秀表现。与PSO-w算法相比，在8个函数中寻优能力和稳定性更好;TFPSO算法除在函数[f5]上可到达最优值外，在其它7个函数上优化结果均不如本文改进算法;与ASEPSO算法相比，本文改进算法主要在[f3]，[f7]，[f8]表现出明显优势。[f3]是一个病态函数，在低维时表现出单峰特性，在高维时表现出多峰特性，在搜索过程中极易陷入局部最优且难以跳出局部最优。 　　由表2可看出PSO-w、TFPSO和ASEPSO算法在该函数上陷入局部最优，从最优值指标也可看出，这两种改进算法在30次实验中全部陷入局部最优，本文算法在[f3]的寻优过程中表现优异，寻优精度达到了[10-4]，在处理该函数时本文算法基本不会陷入局部最优。对于[f7]和[f8]两个多峰函数，3种已有的改进算法基本陷入了局部最优，本文算法在处理[f7]函数时能寻得全局最优点，在处理[f8]函数时偶有陷入局部最优，但多数情况下能寻得全局最优点，且寻优精度达到[10-4]。
　　表3为4种算法在问题为50维下的测试结果，可以看出，随着问题维度的提高，3种已有算法在8个测试函数上的性能不同程度降低，PSO-w算法精度上降低了一个数量级，TFPSO算法在函数[f1]和[f2]上精度降低了两个数量级，50维实验时RHPSO算法性能与30维实验保持一致，说明问题维度增大时，本文算法仍能表现出十分良好的性能，具有较强的鲁棒性。
　　3.3 最优粒子进化曲线分析
　　为更直观地比较4种算法收敛性能，本文绘制了全局最优粒子收敛曲线图。图1（a）-图1（f）是两个单模态与4个多模态函数在30维时的进化曲线，横轴为迭代次数，纵轴为适应值对数。
　　由图1（a）和（b）进化曲线看出，RHPSO算法处理单模态问题和多模态问题时收敛速度明显优于其它3个改进算法。由图1（c）、（e）和（f）可看出，RHPSO算法在搜索前期能较快地向最优值靠近，当最优粒子陷入局部最优时，RHPSO算法能快速跳出局部最优，并有较高的搜索精度。
　　显然，与3种已有的改进方法相比，RHPSO算法收敛速度明显提高，跳出局部最优的能力明显增强。
　　4 结语
　　本文针对PSO算法在解决高维多峰问题上易陷入局部最优、收敛速度慢以及收敛精度低等不足，提出了一种融合Rosenbrock搜索的混合粒子群算法（RHPSO）。该算法以简化粒子群的更新公式为基础，引进3种优化策略，分别是Tent混沌初始化种群、对个体极值加入扰动以及利用Rosenbrock搜索提高解的质量。表2、表3实验中的8个测试函数寻优结果表明，本文算法在高维单峰和多峰问题上均有良好的性能，求解精度高于已有改进算法，且在大部分函数上均能寻得最优解，在解决一些容易陷入局部最优的问题时也表现出良好性能。由图1可看出，相比于其它改进算法，本文算法收敛速度明显提高。
　　但本文算法对函数[f8]测试结果仍不太理想，尚有部分实验结果陷入局部最优，稳定性有待提高。此外，面对不同问题时，Rosenbrock搜索参数的设定会影响算法搜索性能，找出一套自适应选择参数的方案，可增强算法對问题的普适性，这些问题是下一步研究内容。
　　参考文献：
　　[1] KENNEDY J，EBERHART R. Particle swarm optimization[C]. IEEE International Conference on Neural Networks，1995：1942-1948.
　　[2] 田峰，林荣文，吴雅琳. 基于CMPSO算法的永磁同步电机转动惯量识别研究[J]. 电机与控制应用，2019，46（10）：14-18，65.
　　[3] 李辉，王军. 基于粒子群算法与循环神经网络的短期电力负荷预测[J]. 软件导刊，2017，16（11）：125-128.
　　[4] 裴佳佳，刘媛华. 基于多因素灰色模型的上海市基层医疗机构诊疗量预测[J]. 软件导刊，2019，18（6）：130-134.
　　[5] SHI Y H， EBERHART R C. Fuzzy adaptive particle swarm optimization[C]. 2001 Congress on Evolutionary Computation[C]. 2001： 101-106.
　　[6] ZHANG L，TANG Y，HUA C， et al. A new particle swarm optimization algorithm with adaptive inertia weight based on Bayesian techniques[J].  Applied Soft Computing， 2015（28）：138-149.
　　[7] 杨智，陈颖. 改进粒子群算法及其在PID整定中的应用[J]. 控制工程，2016，23（2）：161-166.
　　[8] 杨晓，王国柱. 基于PID控制理论的改进粒子群优化算法[J]. 控制工程，2019，26（8）：1497-1502.
　　[9] 胡旺，李志蜀. 一种更简化而高效的粒子群优化算法[J]. 软件学报，2007（4）：861-868.
　　[10] 赵志刚，张振文，张福刚. 自适应扩展的简化粒子群优化算法[J]. 计算机工程与应用，2011，47（18）：45-47.
　　[11] 邵鹏，吴志健. 一种带正弦函数因子的粒子群优化算法[J]. 小型微型计算机系统，2015，36（1）：156-161.
　　[12] SHIEH H L，KUO C C，CHIANG C M.  Modified particle swarm optimization algorithm with simulated annealing behavior and its numerical verification[J]. Applied Mathematics & Computation， 2011， 218（8）：4365-4383.
　　[13] 袁光辉，樊重俊，张惠珍，等. 一种新的粒子群算法与人工鱼群算法的混合算法[J]. 上海理工大学学报，2014，36（3）：223-226，238.
　　[14] CHANG Y P. Integration of SQP and PSO for optimal planning of harmonic filters[J].  Expert Systems with Applications， 2010， 37（3）：2522-2530.
　　[15] 张娜，赵泽丹，包晓安，等. 基于改进的Tent混沌万有引力搜索算法[J/OL]. 控制与决策：1-8.https：//doi.org/10.13195/j.kzyjc.2018. 0795.
　　[16] ROSENBROCK H H. An automatic method for finding the greatest or least value of a function[J]. Computer Journal，1960，3（3）： 175-184.
　　[17] 陈宝林.  最优化理论与算法[M]. 北京：清华大学出版社，2005.
　　[18] 艾兵，董明刚. 基于高斯扰动和自然选择的改进粒子群优化算法[J]. 计算机应用，2016，36（3）：687-691.
　　[19] 韩敏，何泳. 基于高斯混沌变异和精英学习的自适应多目标粒子群算法[J]. 控制与决策，2016，31（8）：1372-1378.
　　[20] 吴定海，张培林，李胜，等. 基于混沌变异的自适应双粒子群优化[J]. 控制与决策，2011，26（7）：1083-1086，1095.
　　（责任编辑：江 艳）
转载注明来源:https://www.xzbu.com/8/view-15285666.htm