基于模拟退火的粒子群算法寻优

2020-11-25李晓婉韦根原

科技与创新 2020年22期

李晓婉，韦根原

基于模拟退火的粒子群算法寻优

李晓婉，韦根原

（华北电力大学，河北保定 071003）

粒子群算法是一种基于群体智能的随机寻优算法，特别是针对复杂的工程问题，通过迭代寻优计算，能迅速找到近似解，因此粒子群算法在工程计算机中被广泛应用，但是粒子群优化算法容易陷入局部最优，收敛精度低且不易收敛。因此，针对粒子群优化算法的不足，通过同步改变学习因子以及将模拟退火算法与粒子群算法相结合的方法对函数进行极值寻优。结果表明，同步改变学习因子以及将模拟退火算法与粒子群算法结合后的算法提高了全局寻优能力，其中模拟退火与粒子群结合算法具有最好的收敛性和鲁棒性，求解结果更为精确。

测试函数；粒子群算法；学习因子；模拟退火算法

1 引言

近年来，利用智能算法对函数进行极值寻优是现实生活中很多科学计算和工程问题都采用的方法。将复杂难解的现实问题转化成函数优化问题，并利用智能算法求出该函数模型在可行域内的最优解在工程计算机中广泛应用[1]。本文就是针对粒子群算法寻优存在的容易陷入局部最优，收敛精度低且不易收敛的缺点进行改进，通过同步改变学习因子以及将模拟退火算法与粒子群算法相结合的方法，得到两个不同的寻优结果，仿真结果表明两种方法均提高了全局寻优能力，其中基于模拟退火的粒子群寻优算法，大大提高了全局寻优能力，具有较好的收敛性和鲁棒性，求解结果更为精确。

2 粒子群算法

粒子群算法是一种基于群体的随机优化技术。与基于群体的其他的进化算法相比较而言不同的方面是：进化计算遵循的是适者生存原则，而粒子群算法模拟社会，是对鸟群觅食行为的模拟[2]。算法首先将每只鸟抽象成没有体积和质量的粒子，即将每个可能产生的解表述为群中的一个微粒，每个微粒都具有自己的位置向量和速度向量，以及一个由目标函数决定的适应度。所有微粒在搜寻空间中以一定速度飞行，然后每个粒子通过追随个体最优和全局最优来实时地决定各自的“速度”和“位置”，从而在整个解空间中实现对全局最优解的搜索[3]。具有算法简单、容易实现的特点，但是存在陷入局部极值点和收敛精度低且不易收敛的缺点。

粒子群算法与其他的进化类算法相比不同的是，粒子群算法中没有进化算子，而是将每个个体看作搜索空间中没有质量和体积的微粒，并在搜索空间中以一定的速度飞行，该飞行速度由个体飞行经验和群体的飞行经验进行动态调整[4]。

因为基本微粒算法模型中，微粒的飞行速度直接影响算法的全局收敛性，速度过大，能保证微粒很快飞行全局最优解的区域，但当逼近最优解时，由于微粒飞行缺乏有效的约束和控制，不易收敛到全局最优，因此SHI和EBERHART在算法模型中引入惯性权重系数[5]，微粒速度和位置表达式为：

i，j（+1）={i，j（）+11［i，j－i，j（）］+

22［g，j－i，j（）］} （1）

i，j（+1）=i，j（）+i，j（+1）（=1，…，）（2）

2.1 模拟退火算法

模拟退火是80年代初发展起来的一种随机性质的组合优化方法。它模拟的是高温金属降温的热力学过程，现在广泛用于解决组合优化问题。模拟退火算法是局部搜索算法的扩展，从理论上来说，它是一个全局最优算法，在一定条件下可以以概率1收敛于全局最优解[6]。

在实际应用中将内能模拟为目标函数值，将温度模拟为控制参数，然后从一个给定解开始，从其邻域中随机产生一个新解，接受准则允许目标函数在一定范围内接受使目标函数恶化的解，算法持续进行“产生新解—计算目标函数差—判断是否接受新解—接受或舍弃”的迭代过程[7]，对应着固体在某一恒定温度下趋于热平衡的过程。然后，经过多次的解变化后，就可以求出给定的控制参数值的优化问题的相对最优解。再之后，减少控制参数的值，重复执行上述迭代过程。当控制参数逐渐减小并趋向于零时，系统也会慢慢趋于平衡状态，最后系统状态对应于优化问题的整体最优解。

2.2 基于模拟退火算法的粒子群算法

基于模拟退火的粒子群算法是把模拟退火机制引入基本粒子群优化算法中，结合两种算法的优点，保持粒子群算法简单、容易实现的特点，并改善粒子群算法摆脱局部极值点的能力，提高算法的收敛速度和精度[8]。

基于模拟退火算法的粒子群算法采用带压缩因子的粒子群算法，速度和位置更新公式如下：

i，j（+1）={i，j（）+11［i，j（）－i，j（）］+

22［i，j（）－i，j（）］} （3）

i，j（+1）=i，j（）+i，j（+1）（=1，…，）（4）

改进后的算法寻优步骤如下：①初始化微粒的位置和速度；②计算种群中每个微粒的目标函数值；③更新微粒的pbest和gbest；④重复执行下列步骤，对微粒的pbest进行SA邻域搜索，更新各微粒的pbest，执行最优选择操作，更新种群gbest，gbest是否满足终止条件？若是，转④，否则转⑤；⑤输出种群最优解。

2.3 同步变化学习因子

为了对比明显，同时对学习因子同步改变粒子群算法进行寻优仿真，与基于模拟退火的粒子群算法仿真结果形成对比，更可以清晰看出改进后的算法的优越性。

对于学习因子一般固定为常数，且取值为2，但在实际应用中，也有一些其他的取值方式，常见的有同步变化和异步变化两种，同步变化的学习因子，指的是将学习因子1和2的取值范围设定为［min，max］，第次迭代式的学习因子取值公式[10]为：

3 仿真实验结果

利用经典测试函数Griewank函数来对算法进行验证，Griewank函数[11]为：

式（6）中，i∈［﹣600，600］。该函数存在许多局部极小点，数目与问题的维数有关，全局最小值0在（1，2，3，…，n）=（0，0，0，…，0）处可以获得，此函数是典型的非线性多模态函数，具有广泛的搜索空间，通常被认为是优化算法最难处理的复杂多模态问题。

该函数图形如图1所示。

通过粒子群算法对Griewank函数进行极值寻优，得到的适应度曲线如图2所示。

通过同步变化学习因子和基于模拟退火的粒子群算法分别对Griewank函数进行极值寻优，得到的适应度曲线，如图3所示。

图1 Griewank函数图形

图2 粒子群寻优适应度曲线

图3 改进粒子群寻优适应度曲线

通过对寻优结果进行对比可以看出，基于模拟退火的粒子群算法随着进化过程的进行，温度会慢慢下降，接收差解的概率会逐渐减小，提高了收敛性能。该算法不但基本保持住了基本粒子群优化算法简便、易实现的优点，而且还增强了粒子群优化算法的全局寻优能力，加快了算法的进化速度，提高了收敛精度。

对于学习因子同步改变粒子群算法而言，可以实现比较好的收敛，但是收敛速度相对于改进算法来说会差一些[11]。

4 结论

通过仿真结果，可以得到基于模拟退火的粒子群算法是有一定有效性和优越性的，既保持了粒子群算法简单、容易实现的特点，又在一定程度上改善了粒子群算法易陷入局部极值点的特点。因此。在解决实际问题的过程中，适当利用相应的智能算法以及不断改进的新算法，通过对函数寻优的方式，是可以高效快速解决实际工程中遇到的问题的。

［1］王荣亮.基于非线性规划和遗传算法的函数寻优［J］.科技与创新，2019（15）：47-48，50.

［2］黄磊.粒子群优化算法综述［J］.机械工程与自动化，2010（5）：197-199.

［3］杨娜，荆园园.基于改进 PSO算法的函数极值寻优研究［J］.计算机仿真，2015，32（9）：263-266.

［4］焦嵩鸣，谭雨林，桑士杰.基于改进粒子群算法的主汽温控制系统PID参数优化［J］.电力科学与工程，2012，28（12）：9-13.

［5］李艳，陈倩.基于惯性权重非线性递减的粒子群优化算法研究［J］.陕西科技大学学报，2020，38（3）：166-171.

［6］王娟，唐秋华，毛永年.基于遗传模拟退火算法的自动化制造单元周期调度［J］.武汉科技大学学报，2020，43（4）：283-289.

［7］高尚，杨静宇，吴小俊，等.基于模拟退火算法思想的粒子群优化算法［J］.计算机应用与软件，2005（1）：103-104，80.

［8］张立彬，应建阳，陈教料.基于IPSO-SA算法的温室番茄产量预测方法［J］.浙江工业大学学报，2019，47（5）：527-533.

［9］郭明杰，韦根原.基于SA-PSO算法的主汽温控制系统参数优化研究［J］.山东电力技术，2019，46（7）：44-47.

［10］胡丁丁，梁翀.基于改进粒子群优化算法的无人机路径规划研究［J］.数字技术与应用，2020，38（4）：104，107.

［11］YAN H，JIAN-PING L.Griewank函数优化过程中的独特现象研究（英文）［J］.Frontiers of Information Technology & Electronic Engineering，2019，20（10）：1344-1361.

TPL8