基于动态变化自适应惯性权重混沌粒子群算法

王 翠，姜学军

(沈阳理工大学信息科学与工程学院，沈阳 110159)

标准粒子群优化算法(Standard Particle Swarm Optimization，SPSO)是一种群智能优化算法[1]，与蚁群算法、群搜索算法、人工蜂群算法、萤火虫算法等类似，均为元启发式优化算法。 SPSO算法具有易于实现、收敛精度高、收敛速度快等优点，被广泛应用于各种优化问题的求解，如软件工程领域的风险因素优先级划分和软件工作量估计、工程优化应用中对最大功率点的跟踪控制[2]。SPSO 算法也与其他全局优化算法存在相同的缺点，即在局部的搜索能力较差，容易陷入最优值而失去搜索多样性。

为克服以上两个缺点，相关研究提出了一些改进方法。 一是对SPSO 算法中惯性权重进行调整。 文献[3]中提出了新的非线性惯性权重函数，同时将柯西变异算子与非线性动态递减权值策略相结合，以达到算法跳出局部最优的目的；文献[4]中通过利用粒子速度信息、最优性能评价值、多样性等指标，在算法运行中动态调整惯性权重和学习因子。 二是将SPSO 算法与其他优化算法(模拟退火算法、遗传算法等)相结合。 文献[5]中将粒子群算法与萤火虫算法相结合处理机械加工参数的优化问题。 三是改变粒子位置的更新规则。文献[6]改变了粒子之间信息交流机制，引入了自适应选择机制，从而扩大粒子的搜索空间，使粒子在合适的时刻自动选择合适的学习目标；文献[7]通过周期性变异操作改变个体的历史最优值和全局最优值，以达到改变粒子运动方向的目的。

上述针对SPSO 改进之后的算法性能在一定程度上有所提高，但仍有陷入局部最优的可能，无法从根本上彻底解决早熟收敛问题。 为此，提出一种综合改进的基于惯性权重动态变化的混沌粒子群优化算法，充分利用混沌运动的遍历性与随机性生成粒子的初始种群[8]，并根据迭代状态动态调整惯性权重的值。 该算法在处理复杂的多极值问题时，收敛速度明显提高，并能在求得较高精度解的同时有效避免早熟问题。

1 SPSO 算法

SPSO 算法的基本思想如下。

设在一个D维的搜索空间中，有一个规模为N的种群，将种群中个体抽象成没有质量和体积、只有速度和位置的粒子，粒子速度随粒子找到的自身最优位置和整个群体找到的最优位置而进行调整，直至找到最优解[9]。 所有粒子通过迭代在搜索空间追踪两个极值：个体极值和全局极值，并根据两个极值对个体的速度和位置进行更新，从而寻求最优解。 其中个体极值为粒子个体找到的最优位置，全局极值为粒子群体找到的最优位置。根据一定的迭代进化规则，第i个粒子从第t代更新到第t＋1 代时，在d(d＝1，2，…，D)维子空间中的速度vid和位置xid的更新公式为

式中各参数说明如下：

(1)ω为惯性权重因子(粒子速度系数)；

(2)c1 为加速因子，在个体搜索历史中粒子所搜寻到的最佳值的权重系数，通常取值在0 ～2之间；

(3)c2 为加速因子，在群体搜索历史中粒子所搜寻到的最佳值的权重系数，通常取值在0 ～2之间；

(4)randdata1、randdata2 为两个彼此相对独立的随机数，且在[0，1]区间上均匀分布；

(5)gbest(t)为历史个体极值；

(6)zbest(t)为历史全局极值；

(7)r为约束因子，在更新粒子位置时，为粒子速度的系数，通常取值为1。

该算法结构简单，运行速度快，但当某一粒子发现当前最优位置后，如果该位置恰好为局部最优，则粒子会迅速向其靠近，从而失去搜索多样性，无法在解空间内重新搜索，即陷入局部最优，导致算法出现早熟收敛现象。

2 自适应惯性权重混沌SPSO 算法

2.1 混沌SPSO 算法

混沌SPSO 算法是在SPSO 算法的基础上加入混沌运动思想，充分发挥混沌运动的随机性、遍历性以及规律性等优势。

算法首先对当前种群的最优粒子进行混沌寻优操作，然后通过迭代过程，用寻优的结果随机替换群体中的某一个粒子，如此反复直至找到最优解，加快粒子群体的进化速度，从而改善SPSO 算法摆脱局部极值点的能力[10]，并在一定程度上提高了算法的收敛速度和精度。

2.2 不同序列的混沌特性比较

本文采用混沌思想对粒子进行迭代寻优。 首先选取常用的六种混沌映射函数：Logistic、Tent、Cubic、Singe、Gaussian、Circle，通过Matlab 进行仿真实验，并完成混沌序列分布图的分析。 六种混沌映射所产生的序列分布图如图1所示。

图1 六种混沌映射的序列分布图

图1中横坐标表示映射区间，除Cubic 的映射区间为[ -1，1]外，其他混沌函数的映射区间均为[0，1]；纵坐标表示落在相应区间内点的个数。

从图1中可以看出，Logistic 和Cubic 的均匀性要好于其他四种混沌映射，虽然Logistic 和Cubic 两种映射产生的序列都具有混沌特性，但均匀性有所不同，当两个映射区间都均分为十等份时，Cubic 映射落在[ -1，-0.8]区间的点有197 个，而Logistic 产生的混沌序列落在[0，0.1]内的点有235 个，由此可见，Logistic 映射落在[0，0.1]区间的点较多，均匀性不如Cubic 映射落在[ -1，-0.8]内的情况。 故本文选取Cubic 映射产生混沌序列。

2.3 动态变化的自适应惯性权重

惯性权重因子影响SPSO 算法性能，其值较大时有利于全局范围的搜索，较小的权重值有利于加快算法的收敛速度，对于局部的细致开发益处较大[11]。 在SPSO 算法中，ω为固定值时，迭代初期算法收敛速度较快，后期粒子更新能力差、易陷入局部最优的缺陷。 改进SPSO 算法的研究中，常常对ω进行动态调整以提高算法的计算效率。 较为常见的是线性权重递减策略，该方法使算法的早期速度较快，后期ω线性递减至一个较小值，导致粒子的更新能力不够，且实际的寻优过程是非线性的，单纯地线性降低惯性权重的值不能有效改善算法的寻优能力。

本文通过对种群粒子在迭代过程中的最大适应度值和最小适应度值的指数变换动态调整惯性权重的值，同时引入随机因子h增加取值的随机性，该策略用公式描述如下。

式中各参数说明如下：

(1)fitnessgmax为当前迭代代数下种群个体的最大适应度值；

(2)fitnessgmin为当前迭代代数下种群个体的最小适应度值；

(3)h为随机因子，[0，1]之间的随机数；

(4)maxgen为最大迭代次数；

(5)b为惯性权重受最大适应度的影响程度，服从[0，1]间的均匀分布。

综合考虑种群粒子适应度和随机分布，提出一种综合改进算法，其具体流程如下。

步骤1：初始化参数，确定种群规模N＝20，进化最大迭代次数maxgen＝1000，加速因子c1 ＝c2 ＝1.49445，ω的初始值设为0.6，h随机选取区间为[0，1]。

步骤2：随机产生一个D维向量，该向量为第1 个粒子，初始化粒子速度。

步骤3：通过使用测试函数，计算粒子适应度值，找到最大适应度值和最小适应度值。

步骤4：根据式(3)、式(4)计算新的ω值。

步骤5：将新的ω值带入式(1)、式(2)，更新粒子的速度和位置。

步骤6：计算更新后粒子的适应度值，更新gbest和zbest，再次获取fitnessgmax和fitnessg-min，并对ω进行动态非线性更新。

步骤7：如未超出预先设定的最大迭代次数，则转向步骤4 继续搜索，否则执行步骤8。

步骤8：在迭代次数达到预先设定的最大值maxgen，或在进化过程中找到符合条件的最优解时，输出全局最优位置，结束算法运行。

3 仿真实验及分析

3.1 测试函数

为验证本文提出的综合改进算法的优化效果，评价其收敛速度和全局搜索能力，采用表1列出的五种经典的测试函数对算法进行测试。

表1 测试函数

表1中f1、f4、f5为单峰函数，用于检验算法的收敛速度和求解精度；f2、f3是多峰函数，用于检验算法的全局搜索能力[12]。

3.2 算法测试及分析

实验环境为：Intel(R)Core(TM)i5-10400F CPU 2.90GHz，RAM 16.00GB，Windows 10，Matlab R2018b。

实验中，取种群规模N＝20，粒子维度D＝10，两个加速因子c1 ＝c2 ＝1.49445，最大迭代次数maxgen＝1000，设置惯性权重ω的初始值为0.6。

分别测试四种算法。 首先对SPSO 算法进行测试；其次，在SPSO 算法的基础上，采用基于Cubic 映射的混沌序列SPSO 算法(Chaos Initialization Standard Particle Swarm Optimization，CISPSO)对粒子位置进行初始化；然后对仅采用自适应动态变化的惯性权重策略算法(Exponential Inertia Weight Standard Particle Swarm Optimization，EIWSPSO)进行测试；最后测试本文提出的综合改进算法。

实验的评价指标为算法优化结果的平均最优值和标准差，将以上四种算法的测试结果进行对比分析，见表2所示。

表2 测试结果对比

从表2可以看出，当种群规模N＝20，粒子维度D＝10 时，本文提出的综合改进算法在f1、f3、f4和f5上都取得了最优效果，而在f2上的结果仅略差于EIWSPSO 算法。

为分析算法在迭代过程中全局最优值与算法适应度曲线的收敛速度之间的关系，本实验将综合改进算法分别运行10 次，记录10 次的全局最优值，并通过选取起始点和接近最低目标函数值的临界点，求得该适应度曲线的平均收敛速度，如表3所示。 由表3可知，全局最优值与适应度曲线的收敛速度互为矛盾关系，即随着迭代次数增加，该算法适应度曲线下降更加明显，收敛速度加快，同时获得的目标函数值更低。

表3 全局最优值与收敛速度对比

收敛速度是衡量算法求解速度的重要指标。为进一步对算法的收敛速度进行分析，将四种算法的最优个体适应度曲线分别在五种测试函数上进行对比实验，结果如图2～6 所示。

图2 算法在函数f1 上的收敛结果对比

图3 算法在函数f2 上的收敛结果对比

图4 算法在函数f3 上的收敛结果对比

图5 算法在函数f4 上的收敛结果对比

图6 算法在函数f5 上的收敛结果对比

由图2～6 可见，本文提出的综合改进算法对应的收敛曲线的下降速度明显快于其他三种算法，且除了f2和f4，在其他三个测试函数上都获得了更低的目标函数值。

4 结论

SPSO 算法具有收敛精度差、在算法后期收敛速度慢的缺点，提出了针对该算法的综合改进算法——基于动态变化自适应惯性权重的混沌粒子群算法。 利用五种经典的测试函数进行测试并与其他三种算法进行对比实验，仿真结果表明：该改进方法寻优效果明显，不仅提高了算法的收敛速度和求解精度，也使算法的全局搜索性能得到提高。 实验结果证实该方法具备一定的可行性和有效性。