混沌映射的禁忌同步随机学习因子粒子群算法

苏 攀，张 伟

(上海理工大学 光电信息与计算机工程学院，上海 200093)

E-mail：wzhang@usst.com

1 引 言

粒子群算法(Particle Optical Swarm，PSO)最早是由Kenney J和Eberhart R C[1]于1995年提出的，PSO算法的基本思想来自于Kenney J和Eberhart R C对鸟类觅食等群体行为的研究.由于PSO算法的流程简单易实现、参数较少，是近二十多年来的一种比较新颖优化算法，一经问世立即吸引了专家学者们的广泛关注与研究，近些年来不断地涌现出PSO算法的研究新成果，极大的推动了PSO算法的发展.目前PSO的研究主要对算法结构和算法性能加以改进.

参数设置上，Clerc[2]等人将学习因子构建成收缩因子引入PSO算法中，将其代替惯性权重，使算法的全局搜索和局部搜索达到有效的平衡；杜美君[3]等人提出了一种相似度动态调整惯性权重的策略，根据距离最优解的远近赋予不同大小的惯性权重.距离较远的赋予粒子较大的惯性权重，使其跳出局部最优，向最优解靠近.距离较近的赋予粒子较小的惯性权重，使其在最优解附近精细搜索.该方法有效的解决了PSO算法早熟收敛的情况；Ratnawecra[4]等人对学习因子进行改进，提出了线性调整学习因子取值策略，此算法在某些应用背景上获得较好的结果.王磊[5]等人提出了采用自适应惯性权重调节ω，学习因子调节算法调节认知系数和社会系数，使得算法的全局搜索能力和局部搜索能力得到提高；改善粒子多样性上，Lovbjerg M[6]等人提出了自组织临界点控制方法，该方法有效的增强了粒子搜索的多样性；刘昊[7]提出了基于分裂算子的骨干粒子群优化算法，该算法在PSO算法中引入“分裂算子”，通过利用分裂算子的扰动性来丰富粒子群的多样性，从而提高算法的收敛性能；Keenedy[8，9]等人全面系统的分析了多种领域拓扑结构对PSO算法性能的影响，为种群结构的改善提供了重要的理论基础.对于算法融合的研究，研究者们将其他的优化算法引入到PSO算法中，通过利用其他算法的优势来突破PSO算法自身的局限性.目前出现了有与遗传算法结合PSO[10]、与混沌结合的PSO[11]、与天牛须算法结合的PSO[12]、与模拟退火算法结合的PSO[13]、与烟花爆炸机制结合的PSO[14]以及混合PSO[15]等等.

为了提高PSO算法的性能，本文提出一种基于混沌映射的禁忌同步随机学习因子PSO算法(Tabu synchronous stochastic learning factor PSO algorithm for chaotic mapping，TSCPSO).在算法的前期，引入混沌思想，利用混沌的遍历性以及对初始解的敏感特性，通过Logistic映射对PSO算法进行种群初始化，并确定质量较好的种群个体；在算法的后期，引入禁忌搜索策略，把PSO算法寻优搜索的局部最优值放到禁忌表中，利用其较强的“爬山”能力，跳出局部最优，从而提高获得更好全局最优解的机率；最后对PSO算法的学习因子进行改进，通过几个测试函数进行寻优，选取寻优能力突出的区间构造同步随机学习因子，平衡个体经验和群体经验对粒子的影响.通过数值实验验证TSCPSO算法性能，结果表明TSCPSO算法拥有更好的收敛速度、搜索精度同时提高了跳出局部极值，避免陷入局部最优的能力.

2 算法的基本原理

2.1 粒子群算法基本原理

假设在一个D维的目标搜索空间，N个粒子构成一个群落，其中第i个粒子表示一个D维的向量：Xi=(xi1，xi2，…，xiD)，第i个粒子“飞行”速度：Vi=(vi1，vi2，…，viD)；Pbest=(pi1，pi2，…，piD)为第i个粒子的个体极值；gbest=(g1，g2，…，gD)为整个粒子群全局极值.找到个体极值和全局极值时，粒子将通过式(1)和式(2)进行速度和位置的更新：

Vt+1id=Vtid+c1r1(Ptid-Xtid)+c2r2(Ptgd-Xtid)

(1)

Xt+1id=Xtid+Vt+1id

(2)

其中，ω、c1、c2表示群体认知系数.ω为惯性权重，它能够使粒子保持运动惯性；学习因子c1、c2为调节Pbest、gbest相对重要的参数，一般c1、c2取2；Pbest表示粒子本身找到最优解的位置；gbest表示种群找到最优解的位置；r1、r2为[0，1]区间的服从均匀分布随机变量.

2.2 混沌及运动特性

混沌是自然界广泛存在的非线性现象，目前依旧没有对混沌进行严格的定义，通常是将有确定性方程所得到具有随机性的运动状态称为混沌[16，17].

在优化领域里，有多种混沌映射，典型的混沌映射有Logistic、PWLCM、Singer、Sine以及Tent等映射，本文将选用Logistic映射对粒子群进行种群初始，其迭代公式如下：

Zi+1=μZi(1-Zi)，i=0，1，2，…

(3)

其中，μ为控制参量，当μ=4，Z0处于[0，1]区间时，Logistic完全处于混沌状态，同时遍历整个[0，1]区间.混沌运动具有遍历性、随机性以及对初值的敏感依赖性等多种特性，能够在一定的范围内按照其自身的规律不重复地遍历所有状态.

混沌算法的Logistic的使用方法主要以下有两种方式：

1)由[0，1]区间的一个初值通过Logistic方程进行迭代后产生具有混沌性的随机序列Z：a1、a2、a3、…，这些随机序列处于[0，1]区间，通过式(4)进行线性映射，然后将混沌性扩展到优化变量X的取值[a，b]范围内，则实现对优化变量X取值范围的遍历.

Z→X：X=a+Z(b-a)

(4)

2)由[0，1]区间的一个初值通过Logistic方程进行迭代后产生具有混沌性的随机序列Z：a1、a2、a3、…，这些随机序列处于[0，1]区间，通过式(5)载波映射，将混沌性引入gbest附近区域，则可以实现局部混沌搜索.

Z→X：X=gbest+R(Z-0.5)

(5)

其中，R为搜索半径，控制局部搜索范围.

本文将使用第一种Logistic映射的方法对粒子群种群进行初始化.

2.3 禁忌搜索原理

禁忌搜索算法[18，19](Tabu Search，简称TS)最早是由Glover[20]等人于1986年提出的.TS算法是引入灵活的存储结构以及相对应的禁忌准则，来避免重复性的搜索，确保搜索的有效性和多样性，最终实现算法的全局优化.

TS算法主要是给定一个当前解、一种领域，从当前解的领域中选取若干解作为候选解；然后在这些候选解中寻得最佳候选解，并将其对应的目标值与“best so far”状态进行比较，若其对应的目标值比“best so far”状态好，那么最佳候选解对应的目标值禁忌特性可以忽略，这个目标值将代替当前解以及“best so far”状态，并且将其所对应的对象加入到禁忌表中，与此同时，修改表中各对象任期；如果没有优于“best so far”状态的候选解，那么非禁忌状态最佳的候选解为新的当前解，并且不在关注当前解与新当前解的优劣，然后将新当前解所对应的对象加入到禁忌表中，同时修改表中各对象的任期；重复上述的过程，直到达到停止准则为止.

禁忌搜索中的适配值函数、初始解、领域结构、禁忌表(禁忌对象、禁忌长度)、选择策略以及停止准则等构成要素都对算法搜索的质量、速度有极大的影响.

3 粒子群算法的改进

3.1 学习因子的改进

学习因子c1、c2是控制粒子往Pbest和gbest运动的重要参数，它们分别对粒子自我认知以及群体认知产生极大的影响.若c1为0时，则粒子的自我认知会缺失，算法具有扩展搜索空间能力.但是，由于缺少了自我认知，即局部搜索能力，算法反而容易过早熟，结果出现局部最优的状况；若c2为0时，则粒子会失去群体认知，即全局搜索，此时算法中粒子会盲目进行随机搜索，则种群寻得最优值的机率减小.所以，学习因子选取好坏，决定全局搜索与局部搜索之间是否能获得最佳的平衡状态.为了获得种群搜索的更佳平衡状态，本文提出一种基于同步随机的学习因子策略.

令c1=c2=k，k取0.5、0.7、0.9、1.1、1.3、1.5、1.7、1.9、2.0这9组数据，按顺序依次对3个不同的测试函数进行寻优，通过对实验结果进行研究分析，选取寻优效果相对较好的构成学习因子随机区间.本文分别选取Quadric_Noise、Rosenbrock和Zakharov这3个测试函数对九组不同的学习因子进行迭代寻优.表1给出测试函数的具体数学描述.

表1 测试函数公式Table 1 Test function formula

9组同步学习因子依次通过3个测试函数进行寻优仿真，其中，粒子种群为30，迭代次数为1000，每组仿真次数为30.上述仿真实验得到的最优平均值如表2所示.

将表2仿真最优均值绘制成折线图1、图2、图3进行研究.

表2 最优适应度平均值Table 2 Average value of optimal fitness

图1 Quadric_Noise寻优结果Fig.1 Quadric_noise optimization results

图2 Zakharov寻优结果Fig.2 Zakharov optimization results

图3 Rosenbrock寻优结果Fig.3 Rosenbrock optimization results

从上述9组同步学习因子对3个测试函数仿真寻优结果分析可得，对于Quadric_noise函数而言，当学习因子分布[1.3，2.0]区间时，PSO算法进行迭代寻优的结果精度相对较优；对于Zakhatov函数而言，当学习因子分布[1.3，2.0]区间时，PSO算法进行迭代寻优的结果精度相对较优；对于Rosenbrock函数而言，当学习因子分布[1.1，2.0]区间时，PSO算法进行迭代寻优的结果精度相对较优.

基于测试函数的寻优实验结果，经过分析研究、平衡考虑，对学习因子进行改进，提出同步随机学习因子策略.即令c1=c2，并且学习因子随机均匀分布在[1.3，2.0]区间.这样，个体经验和群体经验能够达到较好的平衡状态，使得最优解更加精准.改进学习因子表达式如下：

c′1=c′2=1.3+(2.0-1.3)rand()

(6)

式(6)代入式(1)，则粒子种群的速度更新公式如下：

Vt+1id=Vtid+c′1r1(Ptid-Xtid)+c′2r2(Ptgd-Xtid)

(7)

3.2 混沌思想、禁忌搜索策略的引入

基本PSO算法在搜索的过程中有以下两个不足：

1)PSO算法的初始化是随机进行的，这就造成了种群个体的质量参差不齐，使得部分粒子距离最值较远.

2)利用式1)和式2)进行速度和位置的更新，其本质是通过利用自身信息、Pbest的信息以及gbest的信息引导粒子进行下一代的迭代.这是一个正反馈过程，所以这就会造成自身信息或Pbest的信息处于优势时，PSO算法就容易过早熟，结果出现局部最优值状况.

针对上述两个不足，本文将混沌思想和禁忌搜索策略与PSO算法进行融合，发挥其各自优势.在PSO算法前期，对粒子种群进行初始化时，引入混沌运动，通过Logistic映射对粒子的位置、速度进行混沌变量初始化.不仅保留了粒子种群的随机性，而且丰富了粒子种群的多样性，同时提高了粒子的遍历性，获得了较好初始解群；当PSO算法进入后期寻优时，算法的收敛速度较为缓慢，易陷入局部其最优，此时引入禁忌搜索策略，并且建立相应的禁忌表.将PSO前期寻得的局部最优值放入禁忌表中，利用禁忌表的“记忆”功能，增强算法的突跳能力，避免陷入局部极值的状况.

综上所述，本文提出基于混沌映射的禁忌同步随机学习因子粒子群算法的步骤如下：

Step 1.混沌初始化.随机产生一个d维的，分量值在0到1之间的向量Z1=(z11，z12，…，z1d).然后根据式(3)，得到Z1，Z2，…，ZN.接着将Zi的各个分量载波到优化变量取值范围Xij=aj+(bj-aj)zij.计算目标函数，最后从N个初始群体得到较好的解作为算法的初始解.

Step 2.设置相关参数，并置空禁忌表.

Step 3.按照适应度函数，评估粒子的适应度值，然后更新算法的Pbest和gbest两个极值.

Step 4.根据式(1)和式(7)更新粒子种群速度和位置.

Step 5.判断PSO算法是否进行后期寻优，若进行后期寻优，则算法进入禁忌搜索的状态.

Step 6.利用初始解产生相对应的领域解，并从产生的领域解中选出若干候选解.

Step 7.对候选解进行判段，如果满足特设准则，那么其将替换原先的当前解，成为新的当前解，并且将原先当前解所对应禁忌对象替换成新当前解所对应禁忌对象.与此同时，更新禁忌表以及最优状态，然后执行Step 9；如果不符合特设准则，那么就转入Step 8.

Step 8.判断候选解对象禁忌属性，此时当前解是由非禁忌对象与之对应的最优解产生.而最早进入禁忌表中的禁忌对象将由新当前解所对应的禁忌对象所代替，最后更新禁忌表.

Step 9.判断所设置的收敛准则是否到达满足条件，如满足，则输出此时最优解，远行结束；反之，则转到Step 6.

4 试验仿真

本文根据PSO算法的不足对其加以改进，为了验证TSCPSO算法的性能，选取了4种类型不同的测试函数对其进行评估，然后将其仿真结果与禁忌搜索算法(TS)、混沌PSO算法(CPSO)以及线性调整学习因子PSO算法仿真结果进行对比.

表3 测试函数数学描述Table 3 Mathematical description of the test function

进行测试评估的测试函数分别是Sphere、Rastrigin、Griewank以及Ackley函数.他们的具体数学描述如表3所示.

使用Sphere、Rastrigin、Griewank以及Ackley函数对4个智能算法进行迭代寻优，其中3个改进的PSO算法常用参数的设置如表4所示.

表4 参数设置Table 4 Parameter Settings

TS算法的禁忌长度为4到10之间随机整数，并且迭代次数与其他算法一样为1000.4种算法在测试函数进行仿真寻优结果如表5所示.

表5 仿真结果对比Table 5 Comparison of simulation results

4种算法在Sphere、Rastrigin、Griewank以及Ackley函数迭代寻优的收敛轨迹如图4、图5、图6、图7所示.

通过对上述仿真结果对比数据以及算法在测试函数寻优轨迹图进行分析，实验证明本文提出的TSCPSO的搜索寻优能力强于TS算法、线性调整学习因子PSO算法以及CPSO算法；TSCPSO的收搜精度与另外3个算法相比也有显著提升；TSCPSO的方差、标准差也小于另外3个算法，说明改进算法性能比较稳定；同时，TSCPSO算法的平均迭代次数与其他3个算法相比，有明显的进步，证明其收敛速度也有所提升.综上，本文所提出的TSCPSO算法相比于另外3个算法而言，算法的性能都有所改善.

图4 Sphere函数寻优对比Fig.4 Comparison of Sphere function optimization

图5 Rastrigin函数寻优对比Fig.5 Comparison of Rastrigin function optimization

图6 Griewankan函数寻优对比Fig.6 Comparison of Griewankan function optimization

图7 Ackley函数寻优对比Fig.7 Comparison of Ackley function optimization

4 结 论

为了改善粒子群算法初始化个体质量参差不齐，算法后期收敛性能较差以及易陷入局部最优的缺点，本文提出了基于混沌映射的禁忌同步随机学习因子PSO算法.该算法保证了初始化个体质量，改善了后期收敛性能，提升了算法后期的突跳能力，避免陷入局部最优的状况.并且提出了同步随机学习因子策略，使算法个体经验和群体经验达到较好的平衡状态，增强寻优能力.仿真实验证明，TSCPSO算法在寻优能力、收敛速度、搜索精度以及稳定性等性能上都有显著的提升.