改进的粒子群算法求解函数极值研究_钱泽钜.pdf

197信息：技术与应用信息记录材料 2022年12月 第23卷第12期 0 引言在求解函数极值的问题中，当函数比较简单时，可以通过直接求解求得极值。但是，大部分函数是无法通过直接求解求得极值。这时就需要用到智能算法，在一个解空间中寻找最优极值解。传统的智能算法包括遗传算法、粒子群、鱼群算法等。其中，粒子群算法有简单易行、收敛速度快、设置参数少等优点。所以，本文采用粒子群算法来解决函数求极值的问题。1 标准粒子群算法粒子群算法的思想来源于对鸟类捕食行为的研究，模拟大的鸟群落通过协同合作的捕食行为。行为基础就是共享自身与种群信息，根据此基础来判断食物所在。1.1 粒子群算法简介鸟群中有很多只鸟，而每一只鸟都是一个问题，称为“粒子”。每个粒子在一个空间内进行搜索。其所在位置的好坏是由适应度函数决定的，也就是 fitness function。而且，每个粒子需要有记忆性和速度以决定飞行的位置与方向。这就需要粒子根据自身的经验与群体的经验来决定1-2。1.2 粒子群算法的实现步骤（1）初始化种群。初始化，包括要达到的群体规模N。每一只鸟，也就是每一个粒子随机初始化位置向量 Xi，随机初始化速度向量 Vi。其中 Xi=（xi1，xi2，xiD），Vi=（vi1，vi2，viD）。（2）将初始生成的随机位置向量中每一个 xi 代入所要求极值的函数 f（xi），所求的函数极值就是适应度值Fitness（i）。（3）计算初始化的粒子的适应度值，将最开始计算的每个初始化粒子的适应度值储存为个体极值 Pbest，将所有初始化粒子的个体极值 Pbest 进行比较，选择最优的作为当前全局最优，存入全局极值 Gbest。（4）算法开始迭代，每迭代一次，对于每一个粒子，用其适应度值 Fitness（i）和与上一次迭代的个体极值Pbest 作对比，如果 Fitness（i）优于个体极值 Pbest，就用适应度值 Fitness（i）替代个体极值 Pbest。如果 Fitness（i）并不优于个体极值 Pbest，则保留个体极值 Pbest3-4。（5）对于每一个粒子，用其适应度值 Fitness（i）与上一次迭代的全局极值 Gbest 作对比，如果 Fitness（i）优于全局极值 Gbest，就用 Fitness（i）替代全局极值Gbest。如果 Fitness（i）并不优于全局极值 Gbest，则保留全局极值 Gbest。（6）更新粒子的位置 Xi 与速度 Vi()()kk 1k 1k 1idid1 1idid2 2ididvwvc r Pbestxc r Gbestx=+（1）11kkkidididxxv=+（2）其中，为惯性因子，较大的 拥有较强的全局搜索能力，较小的 拥有较强的局部搜索能力。c1与 c2为学习因子，也称为加速常数，其中 c1是个体部分，如果 c1过小，则容易陷入局部最优。c2集体部分，如果 c2过小，会导致算法收敛速度变慢。r1，r2为 0,1 范围内的均匀随机数。k 1idx为上一次迭代的粒子位置，k 1idv为上一次迭代的粒子速度。kidx为本次迭代的粒子位置，kidv为本次迭代的粒子速度。（7）如果满足最大循环次数的条件，则停止循环，如果不满足，则返回步骤（4）。算法框如图 1 所示：图 1 传统粒子群算法流程改进的粒子群算法求解函数极值研究钱泽钜（西藏民族大学 陕西 咸阳 712082）【摘要】粒子群算法虽然具有简单易行和设置参数少等优点，但是缺点也很明显，例如容易陷入局部最优、算法后期收敛速度慢以及收敛精度比较低。针对上述问题，提出一种新的改进粒子群算法，该算法有以下改进：对算法整体进行分层，算法前期与后期使用不同的策略，前期负责扩大搜索，后期负责加速收敛；改进粒子的选取策略，在粒子选取的时候，每次提出一部分粒子，对其进行杂交操作，引入新的粒子，防止算法前期就陷入局部最优；改进算法权重 的选取，按照选定的规则，使用自适应权重，前期选择大权重，防止陷入局部最优，后期权重减少，加速收敛。最后通过算法仿真，并且对比传统粒子群算法，验证算法的有效性。【关键词】粒子群算法；分层；遗传算法；自适应权重【中图分类号】TP39 【文献标识码】A 【文章编号】1009-5624（2022）12-0197-03DOI:10.16009/13-1295/tq.2022.12.046198 信息：技术与应用信息记录材料 2022年12月 第23卷第12期 2 改进粒子群算法解决函数求极值问题2.1 算法的改进将算法进行分层，分为两层，第一层负责算法前期，并且混合遗传算法，用来扩大搜索范围；第二层负责算法后期，主要用作精准搜索，加速收敛。这样做，就可以将一个矛盾复杂的要求，分解成两个小的部分，各司其职，来完成算法的搜索5。混合粒子群算法，就是将其他优化算法的一些技术应用到粒子群算法之中，用于提升粒子的多样性，使其可以跳出局部最优，增强全局寻优的能力，本文采用遗传算法中的杂交概念，混合入粒子群算法。针对传统的固定惯性因子，无法兼顾算法前期与后期不同的要求，改为线性递减的惯性因子。其公式为：maxminmaxmaxt*(ww)wwt=（3）其中，wmax为惯性因子的最大值，wmin为惯性因子的最小值，t 为迭代次数，tmax为最大迭代次数。2.2 基于杂交的粒子群算法该算法是借鉴了遗传算法中的杂交概念6，在每次的迭代之中，根据杂交的概率7-8，首先选择一定量的粒子作为父代粒子放入到杂交池子中，让池子中的粒子进行杂交操作，产生与父代粒子个数相同的子代粒子，并用产生的子代粒子替换父代粒子。分层混合粒子群算法的实现步骤：（1）在规定的范围之内，随机设置初始化粒子的位置与速度。（2）计算初始化的粒子的适应度值，将最开始计算的每个初始化粒子的适应度值储存为个体极值 Pbest，将所有初始化粒子的个体极值 Pbest 进行比较，选择最优的作为当前全局最优，存入全局极值 Gbest。（3）设置参数 T，T 小于最大循环次数。当算法循环次数小于T时，进入步骤（4），当算法循环次数大于T时，进入步骤（5）。（4）对每个粒子的速度与位置进行更新。进入步骤（6）。()()kk 1k 1k 1idid1 1idid2 2ididvwvc r Pbestxc r Gbestx=+（4）11kkkidididxxv=+（5）maxminmaxmaxt*(ww)wwt=（6）（5）对每个粒子的速度与位置进行更新。进入步骤（6）。()kk 1k 1idid2 2ididvwvc r Gbestx=+（7）11kkkidididxxv=+（8）maxminmaxmaxt*(ww)wwt=（9）（6）计算每一个更新后的粒子的适应度值，将适应度值与粒子最好位置比较。更新全局极值 Gbest。（7）根据一定的杂交概率选取指定数量的粒子，并将选取的指定数量的粒子放入杂交池。将两个父代个体的部分进行替换重组构成新的个体，并用子代粒子替代父代粒子，子代的位置与速度为：nx=i mx（1）+（1-i）mx（2）（10）mv(1)mv(2)nvmv(mv(1)mv(2)|+=+（）（11）其中，保持 Pbest 和 Gbest 不变。mx（1），mx（2）为两个不同的父代粒子，nx 为交叉操作后的子代粒子的位置，nv 为交叉操作后的子代粒子速度，i 是 0 到 1 之间的随机数。（8）当如果满足结束条件（循环次数满足最大循环要求），则停止循环，如果不满足，则返回步骤（3）。3 算法仿真测试3.1 测试函数介绍为了验证所提出算法是否有效，选取两个类型不同的函数，作为测试函数进行测试验证。n1i 1Y100*(x(i1)x(i)2(1(x(i)2)=+（12）Y2=（cos（x（1）2-x（2）2）-3）/（2+x（1）2+x（2）2）2+0.8 （13）其中，Y1是一个多维函数，Y2是一个复杂的多模函数。通过传统的 PSO 算法与改进的 PSO 算法对两个不同类型函数的对比，来验证算法是否有效。3.2 算法仿真对出传统的 PSO 算法，初试种群选择为 50，c1与 c2学习因子设置为2，惯性权重设置为0.8。改进PSO算法，Y1中设置 T 为 10，Y2中设置 T 为 100，除了 w 惯性权重设置不同外，其余设置与传统 PSO 算法设置相同，其中，惯性权重 w 设置为区间 0.6,0.8。在测试函数时，式（1）取最大迭代次数为 100，式（2）取最大迭代次数为1 000，对两个函数各优化 10 次。算法是否可以快速稳定的收敛，是否可以跳出局部最优得到全局最优，可以衡量一个算法是否优秀。越快收敛，且能跳出局部最优，说明快速有效的求解函数极值。通过对比收敛结果与收敛速度，来展示改进算法的有效性，结论如表 1 和图 2所示：表 1 测试函数优化结果算法最优值平均值Y1传统粒子群算法 0.3000000167102610.300000004170114改进粒子群算法 0.3000000000000000.300000000000000Y2传统粒子群算法 47.93883898144368150.932635954660881改进粒子群算法 50.12041985100339056.803007265070576 199信息：技术与应用信息记录材料 2022年12月 第23卷第12期（a）Y1收敛图（传统粒子群算法）（b）Y1收敛图（改进粒子群算法）（c）Y2收敛图（传统粒子群算法）（d）Y2收敛图（改进粒子群算法）图 2 测试函数适应度值变化 通过以表 1、图 2 可以看出，改进 PSO 算法对比传统PSO 算法在收敛速度与收敛结果这两个方面，新算法收敛速度更快。在收敛结果上，新算法也拥有更好的稳定收敛结果。3.3 仿真结果从上图可以看出，改进的粒子群算法与传统粒子群算法相比，有比较明显的优势。对于测试函数 Y1改进的算法收敛速度更快，基本在 10 步左右就可以收敛，收敛速度快，说明算法求解函数极值的速度快。即便算法前期陷入局部最优解，也可以很快地跳出局部最优。而传统算法侧需要 35 次左右才能收敛，对比改进的算法，收敛速度慢一些，说明算法求解函数极值慢一些，而且，陷入局部最优解时，跳出局部最优比较慢。而收敛结果，改进算法可以稳定收敛到 0.3。但传统算法却无法稳定收敛，在 0.3附近波动。对于测试函数 Y2，改进算法在 100 步左右就可以收敛，收敛速度快，且稳定收敛。而传统算法则需要250 步左右才能收敛，收敛速度不如改进算法，收敛缓慢，且陷入局部最优。4 结语本文提出的改进粒子群算法，是先通过对算法进行分层，再局部融合其他智能算法，同时采取自适应权重的方法实现的。在算法前期，扩大搜索范围，避免陷入局部最优；在算法后期，加速算法的收敛，并用于解决函数求极值的问题。实验结果表明，改进的粒子群算法整体性能良好，可用于求解其他函数求极值的问题。【参考文献】1 刘俊芳，张雪英，宁爱平.PSO 和 ABC 的混合优化算法 J.计算机工程与应用，2011，47(35):32-34，44.2 陈颖，徐晓晖，李志全.基于免疫克隆原理的改进粒子群优化算法的研究 J.系统仿真学报，2008，20(6):1471-1474.3 张晓莉，王秦飞，冀汶莉.一种改进的自适应惯性权重的粒子群算法 J.微电子学与计算机，2019，36(3):66-70.4许少华，李新幸.一种自适应改变惯性权重的粒子群算法J.科学技术与工程，2012，12(9):2205-2208.5 武少华，高岳林.粒子群算法的改进与比较研究 J.合肥工业大学学报(自然科学版)，2019，42(2):184-188，194.6 王联国，洪毅，赵付青，等.一种改进的人工鱼群算法 J.计算机工程，2008，34(19):192-194.7 蔡自兴，龚涛.免疫算法研究的进展 J.控制与决策，2004，19(8):841-846.8 周利军，彭卫，邹芳，等.自适应变异粒子群算法 J.计算机工程与应用，2016，52(7):50-55，149.作者简介：钱泽