一种新的基于模拟退火的粒子群算法

赵乃刚

摘要：鉴于标准粒子群优化算法易陷入局部最优、收敛精度低，我们提出了一种改进的基于模拟退火的粒子群算法（NPSO）。将模拟退火算法的思想引入粒子群算法中，并对更新公式进行简化；提出了一种自适应随机惯性权重，实现了自适应平衡局部搜索和全局搜索的能力；提出了“优胜劣汰”的更新机制，加快了算法的收敛速度。与其它几种粒子群算法在4个基准测试函数上的实验比较，实验研究表明，NPSO算法的性能很好。

关键词：粒子群优化算法；惯性权重；优胜劣汰

中图分类号：TP18

文献标识码：A

DOI： 10.3969/j.is sn.1003-6970.2015.07.001

0 引言

粒子群算法（particle swarm optimizer）是1995年由美国的Kennedy博士和Eberhart博士首次提出的一种基于群智能的优化技术。尽管它与别的进化计算技术有很多相似处，但标准的粒子群优化算法并没有用到交叉、变异等进化算子。由于粒子群算法原理简单、需要调节的参数少、实现容易，如今已经受到了海内外学者和学术界的广泛关注，并对它进行了许多方面的改进。而且它已经在轨道电路补偿电容故障诊断、求解整数和混合整数约束优化问题、人脸识别、车牌定位、机位分配等许多领域得到了广泛应用。然而标准粒子群算法也存在如下缺点：寻找到的最优位置可能是局部最优位置而不是全局最优位置；参数的选择存在很大的不确定性；算法寻优初期收敛速度快而寻优后期收敛速度变慢。鉴于粒子群算法的这些缺点，很多学者对粒子群算法做了大量的改进。文献中提出了惯性权重因子并将它引入粒子群算法中，提高了算法的收敛速度和收敛精度；文献在分析了不确定性参数对算法影响的基础上，提出了基于维数选择策略的粒子群算法，并通过数值实验证明了它们有关随机参数的分析是正确可行的。文献分析了惯性权重、学习因子对粒子群算法的影响，构造了随机惯性权重，并在算法中引入了平均个体最优位置，提高了算法的性能；文献提出了基于模拟退火的粒子群算法，有效地对粒子群算法和模拟退火算法两种算法的优点分析并进行了融合，有利的提高了算法的全局寻优性能。

我们在分析了惯性权重的取值对粒子群算法影响的基础之上，将模拟退火算法的思想引入粒子群算法中，并引入了自然界“优胜劣汰”的更新机制。新算法结合了粒子群算法容易实现、全局寻优能力强及模拟退火算法具有概率突跳能力的优点，使得算法有效地降低了在搜索过程中陷入局部最优的可能性。

1 基本粒子群算法

粒子群算法是一种基于群体智能的具有全局搜索能力的优化方法。它通过粒子群体中不同微粒之间的相互合作和竞争来实现在寻优空间中的搜索过程以找到问题的最优解。系统首先随机的初始化一组微粒，然后微粒在搜索空间中跟随两个极值位置来进行搜索。假设粒子群的搜索空间为m维，微粒的个数为popsize，第i个微粒在t时刻的飞行速度和在搜索空间中的位置分别为

，微粒在f时刻的个体极值位置和群体极值位置分别为

其中ω国为惯性权重；C₁，c₂是学习因子，一般取非负数；r₁，r₂是介于[0，1]之间的随机数。对于算法的迭代终止条件，我们一般会根据不同的具体问题而设定不同的值。通常将上面描述的带有惯性权重系数的粒子群算法称为标准的粒子群算法。

2 模拟退火算法

模拟退火算法是模拟金属在高温状态下缓缓降温的热学过程而提出的，如今已经大量的应用于许多现实问题中。模拟退火算法首先给定一个初始温度，随机选择一个初始状态并对它的目标函数值进行评估；对当前所处的状态微扰，计算新状态的目标函数值；以100%的概率接收较好的值，而以事先给定的概率P接受较差的值，直到算法冷却。模拟退火算法在空间搜索时拥有按照一定概率进行突跳的能力，在整个退火的过程中不但能接受较好的值，而且可以按照事先给定的概率P接收较差的值，能防止算法陷入局部最优。

3 改进的粒子群算法

3.1 简化的粒子群算法

标准粒子群算法同时具有速度更新和位置更新两项，使得粒子的搜索方向和步长的大小存在不确定性，导致算法的进化后期收敛速度很慢，搜索精度降低。并且，模拟退火算法在寻找最优位置的过程中拥有按照给定概率进行突跳的能力，可以有效的降低算法陷入局部最优位置的概率。鉴于上述分析，为了尽量避免粒子群算法所拥有的缺点并同时结合模拟退火算法所拥有的优点，我们对标准粒子群算法省略了速度更新部分，使得二阶迭代方程降为一阶，并结合模拟退火算法对位置更新部分进行了改进，如下：

其中，T（pbest_i）表示在模拟退火中当前温度状态下第i个粒子的适配值，zbest是采用轮盘赌策略从所有pbesti中选择出的全局最优点gbest的一个替代值。

3.2 自适应随机惯性权重系数

惯性权重系数是粒子群算法中一个极其重要的系数，它的取值大小在一定程度上影响了当前粒子的前一时刻迭代信息对当前飞行状态的影响程度。在粒子群算法中，如果惯性权重系数选择合适的值，则有利于平衡算法全局搜索和局部搜索之间的矛盾。在大多数的粒子群改进算法中采用了惯性权重线性递减的策略，在算法搜索初期，选择较大的惯性权重值可以使得算法获得较强的全局搜索能力，而在算法搜索后期，选择较小的惯性权重值可以使得算法渐进收敛到全局最优。本文中，我们提出了如下的自适应随机惯性权重：

其中：wmax是惯性权重系数所能取到的最大值；wmln为惯性权重系数所能取到的最小值；rand为[0，1]之间的随机数；randn为服从正太分布的随机数；gen和maxgen分别为算法的当前迭代次数和迭代总次数。σ为方差，用于衡量当前惯性权重与其数学期望的偏离程度。

3.3 “优胜劣汰”更新机制

为了提高粒子群算法的收敛速度，我们提出了“优胜劣汰”的更新策略。具体方式为：当更新完所有粒子的位置后，根据粒子适应度值的大小对粒子进行排序。在算法中将最差的S个粒子用最好的S个粒子代替。若S取值越大，则替换的粒子越多，不利于保持种群的多样性。但如果S的取值很大，则会使算法丧失很多粒子的有效信息，使算法趋于局部搜索；若R取值越小，算法的收敛速度会降低。因此这里的R取

改进的粒子群算法的流程描述如下：

（1）给定算法的参数，如惯性权重、学习因子、变量范围等，随机初始化粒子的位置；

（2）计算每个粒子的适应度值，将第i粒子的位置存储在个体最优位置pbest_i中，将整个粒子群的最好位置存储在群体最优极值gbest中；

（3）给出初始温度；

（4）计算当前时刻温度下所有pbest_i的适配值，并采用轮盘赌方法从pbest_i中选择一个全局最优位置gbest的替代值，并按照式（3）、（4）、（5）对所有粒子的位置进行迭代更新；

（5）分别对粒子的个体最优位置pbest_i和群体最优位置gbest进行更新，并对算法执行降低温度的操作；

（6）判断算法开始时设置的终止条件是否满足。如果满足，结束算法的此次寻优，输出我们需要的数值结果，否则转步骤（4）继续寻优。

5 数值实验

为了验证NPSO算法的可行性及有效性，我们在4个标准测试函数上进行了测试。并与其它三种改进算法，即基于惯性权重递减策略的粒子群优化（LDWPSO）算法、一种更简化而高效的粒子群优化（SSPSO）算法、基于随机惯性权重的简化粒子群优化（SIWSPSO）算法进行了数值实验比较。主要比较以下四个方面：最优解、最差解、平均值、方差。

4个经典测试函数如下：

从表1中可以看出IPSO算法在迭代次数为30时就已经找到了全局最优位置，比其它三种算法的收敛速度快，寻优精度高。而从最优值、最差值、均值和方差四个方面来看，它都远远优于其它三种算法，故该算法的鲁棒性较好。

6 结论

针对标准粒子群算法收敛精度低、容易早熟等缺点，在粒子群算法中引入了模拟退火算法的有效思想，并对算法的迭代方式进行了有效简化；为平衡算法全局和局部搜索能力之间的矛盾，提出了一种新的自适应随机惯性权重；采用“优胜劣汰”的更新机制来加快算法的收敛速度。实验结果验证了本文算法的可行性和高效性。