基于混沌思想的粒子群优化算法

基于混沌思想的粒子群优化算法

余廷勋

深圳华微激光科技有限公司 广东深圳 518000

摘 要：针对传统粒子群优化算法易早熟收敛的问题，提出一种基于混沌思想的改进粒子群优化算法。该算法利用混沌运动的随机性、遍历性和规律性等特征，综合了混沌初始化、惯性权重的混沌调节、位置的边界处理、陷入早熟时的混沌遍历搜索等改进措施, 改善了粒子群的随机性与多样性，较好解决了算法的早熟收敛问题。通过3个典型高维测试函数的实验测试表明：改进的混沌粒子群算法在收敛速度、寻优精度和稳定性等方面明显优于传统的粒子群算法。

关键词：粒子群优化算法；混沌；优化；综合改进

中图分类号：TP301.6 文献标志码：A

Particle Swarm Optimization Algorithm Based on Chaos

Abstract：To overcome the problem of premature convergence on traditional particle swarm optimization (PSO), an improved particle swarm optimization algorithm based on chaos is proposed in this paper. By use of the properties—randomicity，ergodicity and regularity of chaos, chaos initialization, chaotic inertia weight strategy , position boundary treatment and chaotic search in the premature are integrated, the randomicity and persity of the particle population are improved. Finally, experiments on three benchmark functions with high dimension show that the improved PSO outperforms traditional PSO in convergence speed, searching precision and stability.

Key words: particle swarm optimization (PSO); chaos; optimization; comprehensive improvement

.

0 引 言

粒子群优化算法^[1]（Particle Swarm Optimization，PSO）是一种基于群体智能的元启发式并行搜索算法，它由美国心理学家Kennedy和电气工程师Eberhart受鸟群觅食行为的启发而提出。PSO算法具有控制参数少、收敛速度快、对目标函数要求少和易于实现等优点，是一种通用的全局搜索算法。然而，与其他智能优化算法一样，PSO算法亦存在易陷入局部早熟收敛、全局搜索能力差等不足。为此，许多算法改进策略被提出^[2-6]，但这些策略大多从某单方面的改进进行探讨，未对PSO算法的整体综合改进进行研究。

混沌是非线性确定系统中普遍存在的一种貌似随机的现象，是客观世界中最基本的运动形态之一。混沌运动具有内在随机性、遍历性和对初始条件的高度敏感性等特征^[7]。将混沌机制引入PSO算法，可有效地均衡算法的全局搜索和局部搜索，进而提高算法的快速性、有效性和鲁棒性^[8-12]。本文从种群的初始化、惯性权重的调节、位置边界处理和早熟收敛时的混沌遍历搜索四个方面对传统的PSO算法进行改进。

1、标准PSO算法

在PSO算法中，n维搜索空间上的每个点（称为“粒子”）对应优化问题的一个潜在解（即点的位置），每个粒子都由一个目标函数决定的适应值来评价其位置的优劣。粒子在搜索空间以速度为步长进行位置的更新，而速度的更新由粒子当前速度、个体认知部分和社会认知部分共同决定。设n维空间的一个粒子种群由 个粒子组成，第i个粒子的位置和速度分别为 和 ，其中 。根据文献[1]，粒子速度和位置的更新公式为：

(1)

(2)

式中： 和 称为加速常数或学习因子，通常取值为2，体现了对粒子个体最优历史经验和种群最优历史经验的继承与学习； 和 为0到1之间均匀分布的随机数； 为迄今为止第i个粒子所经历的最佳位置的第j维分量； 为迄今为止种群所经历的最佳位置的第j维分量。通过设置粒子的速度区间 和位置区间 ，对粒子速度和位置的更新进行适当的限制。为更好地均衡PSO算法的全局探索和局部开发能力，Shi Y等引入惯性权重

^[2,3]，将（1）式改为如下：

(3)

（2）和（3）式被认为标准的PSO算法。Shi Y等通过大量的实验研究发现：惯性权重 取值较大有利于全局探索，惯性权重 取值较小有利于局部开发；建议在算法的初期 取较大值，在算法的后期 取较小值，并建议惯性权重按线性递减策略调整：

(4)

式中： 为惯性权重的最大值，常取为0.9； 为惯性权重的最小值，常取为0.4；t为当前进化代数； 为最大进化代数。

尽管标准PSO算法较好地均衡了种群寻优过程的全局与局部搜索，但仍有不足：惯性权重在算法的迭代初期被赋予较大值，导致局部开发能力较弱，即使此时粒子已接近全局最优解，往往也只能与之 “擦肩而过”；而在迭代后期, 随着惯性权重的线性递减则全局探索能力变弱，易陷入早熟收敛或在全局最优解附近“振荡”；另外，惯性权重的取值范围以及最大迭代次数需通过大量反复试验才能确定，很难找到适应不同优化问题的最佳值。

2、改进的PSO算法

2.1 PSO的混沌思想

PSO算法在搜索空间的寻优过程是一个非线性运动过程，也是粒子多样性消失的过程。利用非线性混沌运动的遍历性，即混沌运动在其混沌吸引域内是各态历经的，将最优解的搜索过程对应为混沌轨道的遍历过程，有助于解决算法的早熟收敛问题；混沌运动的内在随机性，有助于改善粒子的多样性，提高算法全局搜索能力。

混沌与噪声表现非常相似，但二者有本质的区别。前者的“内在随机性”是指非线性确定系统产生的非周期解，表现出貌似随机却并非随机，仍有规律可循，存在普适常数等；噪声的表现则属于“外在随机性”，它是由外界因素引起的一种完全无序或无规则的运动^[7]。

Logistic映射是典型的混沌系统^[7]，其迭代公式如下：

(5)

式中： 为控制参量。当 ，初值 且 时， Logistic映射属于完全混沌状态，其Lyapunov指数图和二维仿真图分别如图1中（a）、（b）所示，图（a）中的横轴是控制参量 ，纵轴是对应的Lyapunov指数。可见，Logistic映射产生的混沌变量在混沌区域分布并不均匀，一定程度上影响粒子的全局搜索能力。

（a）Lyapunov指数图

(b)二维仿真图

图1 Logistic映射李氏指数与二维仿真图

(6)

文献[13]采用（6）式作为混沌序列发生器，其映射的方程形式表示如下：

(7)

对 求导数，得 。其Lyapunov指数为：

显然， =0.9163或0.5108，根据夹逼准则，（6）式映射的Lyapunov指数取值范围为：0.5108 。

独立计算（6）式Lyapunov指数5000次，结果如图2（a）所示，图中横轴是计算次数，纵轴是对应的Lyapunov指数，实验结果与上述理论分析吻合。理论分析和实验证明了（6）式的Lyapunov指数大于零，其映射是混沌的。（6）式的二维仿真图如图2（b）所示，可见其产生的混沌序列在混沌区域内分布均匀，有助于算法的全局寻优。本文采用（6）式作为混沌信号发生器，应用于对标准PSO算法种群初始化、惯性权重调节、位置边界处理、早熟收敛时的遍历搜索四个方面的改进。

（a）Lyapunov指数图

(b)二维仿真图

图2 方程（6）李氏指数与二维仿真图

2.2 PSO的混沌初始化

利用（6）式迭代产生大量混沌序列，利用载波的方式将混沌运动轨道的遍历范围映射到粒子位置的取值范围，即按下式进行变换：

(9)

式中： 和 分别为粒子位置的最大值与最小值； 为混沌变量，、 分别为混沌变量的最大值与最小值。由（6）式、（9）式可得到大量的原始粒子，计算每个原始粒子的适应值，选择其中最优的m个粒子作为算法的初始种群，兼顾了粒子种群的随机性和多样性。粒子的初始位置即为个体当前历史最佳位置；全部粒子适应值的最优值为全局最优值，其对应的位置为当前全局历史最佳位置。

2.3 惯性权重的混沌调节

在PSO算法中，惯性权重是均衡粒子探索与开发能力的一个关键参数，其取值较大对应粒子全局探索能力较强、局部开发能力较弱，取值较小则相反。国内外学者对惯性权重的调节策略进行了大量的研究^[2-6,14,15]，这些调节策略大多采用线性或非线性递减模式，若迭代次数很大，每次迭代惯性权重的改变量很小，调节功能的发挥效果不明显；另外，这种单一的调节模式，当粒子在迭代后期陷入局部极值时很难逃逸而发现最优解。受前人研究启发，本文提出如下的惯性权重调节策略：

(10)

式中：u、v为可调参数； 为混沌变量；其余参数和（4）式相同。当 ， ，u=0.4，v=0.7时，惯性权重调节策略如图3所示

图3 惯性权重 曲线

改进的惯性权重调节策略通过引入混沌机制，在保持惯性权重整体递减趋势的同时有效避免了单一变化的模式，增强种群的随机性与多样性，提高粒子逃逸局部极值束缚的能力。

2.4 位置边界处理

粒子在搜索空间寻优时，常有超出位置边界的现象，常规的处理方法是将其设置为位置边界值。这种“一刀切”的处理方式有很大的缺陷，即降低了粒子的随机性和多样性。利用混沌运动随机性与遍历性的特性，对出界粒子按下式进行位置调整：

（11）

式中： 表示第 个粒子的位置的第 分量； 为当前全局最佳位置的第 维分量；k为可调参数；其余参数与前述相同。通过（11）式对出界粒子进行位置调整处理，进一步提高了粒子群的随机性和多样性。

2.5 局部收敛的混沌搜索

标准PSO算法应用于高维复杂优化问题时，易陷入局部早熟收敛。此时，速度更新（3）式中的个体认知模式和社会模式接近于零，速度的更新主要由惯性项决定，由于惯性权重一般小于1，这将导致速度递减趋近于零，即粒子将停滞不动。当种群陷入早熟收敛时，利用混沌运动的遍历性，将粒子的寻优过程对应为混沌运动的遍历搜索过程，使粒子具备逃逸局部收敛点束缚的能力，指导种群逼近全局最优点。

判断算法是否进入早熟收敛是进行混沌遍历搜索的前提，本文采用下式作为判断算法进入早熟收敛的依据：

(12)

式中： 是当前全局最优适应值； 是前一次迭代的全局最优适应值； 是指定的阈值。当算法连续N（比如N为10）次迭代满足（12）式，表明算法进化陷入局部收敛，应转入混沌遍历搜索。

当算法陷入早熟收敛时，经过大量数值仿真实验，本文构造如下以全局最佳位置为中心的混沌搜索区域：

(13)

式中： 为当前全局最佳位置；a、b、c、d为大于等于零的可调参数，经反复试验，a、d一般取值稍小（如小于5），b、c一般取值稍大（如大于30）； 为混沌变量；其余参数与前述相同。计算每个混沌搜索点的适应值，如果搜索点优于当前全局最佳位置，则更新种群最优适应值并用最优搜索点随机替换种群中任一粒子。

2.6 算法步骤

改进的PSO算法步骤如下：

Step1 混沌初始化。通过（6）、（9）式产生大量原始粒子，取适应值最优的前m个精英粒子组成初始种群；

Step2 将粒子的初始位置设置为该粒子的个体历史最佳位置，将初始种群最佳位置设置为种群全局历史最佳位置；

Step3 按照（2）、（3）、（6）、（10）式更新粒子速度和位置；

Step4 计算每个粒子的适应值；

Step5 更新个体历史最佳位置和全局历史最佳位置；

Step6 判断是否陷入早熟收敛，未陷入早熟收敛则转Step7，否则进入混沌遍历搜索：

1）混沌迭代初始化。设置迭代计数器初值和最大迭代次数；

2）按（6）、（13）式进行混沌遍历搜索；

3）计算每次混沌遍历搜索点的适应值，若比当前全局最优值更优，则更新最优信息，并将搜索点替换种群中的任一粒子；

4）更新迭代计数器，若超过最大迭代次数则混沌遍历搜索结束，否则转入2）。

Step7 若满足算法结束条件则寻优过程结束，否则转Step3。

3、算法测试

为检验算法的性能，采用表1中的三个经典测试函数对改进PSO算法和标准PSO算法分别进行仿真测试。其中，Sphere函数和Rosenbrock函数是连续的高维单峰函数，常用于检验算法的收敛速度； Rastrigrin 函数是一个高维多峰函数，存在大量按正弦拐点排列、很深的局部最优点，用于检验算法的全局寻优能力。

算法参数设置如下：粒子群规模m=30； ； ， ；三个函数的最大迭代次数分别500次、1000次、10000次。为减小随机性的影响，连续重复实验50次，取平均值作为最后的响应值。算法进化曲线如图4（a）、图5（a）、图6（a）所示；以收敛精度达 为衡量函数收敛的指标，各次实验寻优结果如图4（b）、图5（b）、图6（b）所示；详细实验测试结果对比如表2所示。

表1 3个标准测试函数

(a) 寻优进化曲线图

（b）寻优结果图

图4寻优进化曲线与寻优结果(Sphere)

(a) 寻优进化曲线图

（b）寻优结果图

图5寻优进化曲线与寻优结果(Rastrigrin)

(a) 寻优进化曲线图

（b）寻优结果图

图6寻优进化曲线与寻优结果(Rosenbrock)

由数值仿真实验可知：改进PSO算法的寻优率达100%，算法鲁棒性明显得到提高；对于Sphere函数，改进的PSO算法和标准PSO算法都能收敛到全局最优值，但改进PSO算法的收敛精度、收敛速度和标准差都远优于标准PSO算法；对于Rastrigrin 函数，改进的PSO算法能较快地收敛到全局最优值，标准PSO算法则陷入局部极值而未能全局收敛；对于Rosenbrock函数，改进的PSO算法同样能以较好的性能收敛至全局最优值，标准PSO算法则迭代至最大迭代次数仍未实现全局收敛。

4、结论

本文将混沌思想深度融合于PSO算法，其

创新点主要体现如下：

表2 标准PSO与改进PSO 测试结果对比

1）将混沌思想应用于种群初始化、惯性权重

的调节、位置边界处理，从不同角度改善种群的随机性和多样性，有效均衡了粒子的全局探索和局部开发能力；

2）当算法陷入早熟收敛时，将粒子的寻优过程对应为混沌运动的遍历搜索过程，指导算法朝全局最优值逼近。

最后，本文用3个典型的测试函数对算法进行仿真实验比较。实验结果表明：改进的PSO算法在收敛速度、收敛精度和全局寻优能力等性能上都比标准PSO算法有明显的改善和提高。

参考文献

[1]Kennedy J, Eberhart R. Particle Swarm Optimization[C]. Proceedings of IEEE International Conference on Neural Networks. Perth, Australia, 1995:1942-1948.

[2]Shi Y, Eberhart R. A Modified Particle Swarm Optimizer[C]. Proceedings of the IEEE Conference on Evolutionary Computation. Anchorage: IEEE Press, 1998:69-73.

[3]Shi Y, Eberhart R. Empirical study of particle swarm optimization[C].Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on. IEEE, 1999:1945-1950.

[4]Clerc M. The Swarm and the Queen: Towards a Deterministic and Adaptive Particle Swarm Optimization[C]. Proceedings 1999 Congress Evolutionary Computation .Piscataway NJ: IEEE Press, 1999:1951-1957.

[5]Chen G M, Jia J Y, Han Q. Study on the Strategy of Decreasing Inertia Weight in Particle Swarm Optimization Algorithm [J]. Journal of Xi'an Jiao tong University, 2006, 40 (1):53-61.（陈贵敏,贾建援,韩琪.粒子群优化算法的惯性权值递减策略研究[J].西安交通大学学报,2006, 40 (1):53-61.）

[6]Gao L Q, Li R P, Zou D X. A Global Particle Swarm Optimization Algorithm [J]. Journal of Nort_heastern University (Natural Science), 2011, 32 (11): 1538-1541.（高立群,李若平,邹德旋.全局粒子群优化算法[J].东北大学学报(自然科学版),2011, 32 (11): 1538-1541.）

[7]Yu S M. Chaotic Systems and Chaotic Circuits: Principle, Design and Its Application in Communications [M]. Xi'an: Xidian University Press, 2011.（禹思敏.混沌系统与混沌电路——原理、设计及其在通信中的应用[M].西安:西安电子科技大学出版社, 2011.）

[8]Gao Y, Xie S L. Chaos Particle Swarm Optimization Algorithm[J]. Computer Science, 2004,31(8):13-15.（高鹰,谢胜利.混沌粒子群优化算法[J].计算机科学,2004,31 (8):13-15.）

[9]Dai D X, Wang Q, Ruan Y S, et al. Chaos-based particle swarm optimization algorithm and its application [J]. Huazhong Univ. of Sci. & Tech. (Nature Science Edition), 2005, 33 (10): 53-55.（戴冬雪, 王祁, 阮永顺等. 基于混沌思想的粒子群优化算法及其应用[J].华中科技大学学报(自然科学版), 2005, 33 (10): 53-55.）

[10]Zhang J S, Li Q Q, Wang Z X. Hybrid particle swarm optimization algorithm based on the chaos search [J]. Journal of Shandong University (Engineering Science), 2007, 37 (1): 47-50.（张劲松,李歧强,王朝霞.基于混沌搜索的混和粒子群优化算法[J].山东大学学报(工学版), 2007, 37 (1): 47-50.）

[11]Zhao Z G, Chang C. Adaptive Chaos Particle Swarm Optimization Algorithm [J]. Computer Engineering, 2011, 37 (15): 128-130.（赵志刚,常成.自适应混沌粒子群优化算法[J].计算机工程, 2011, 37 (15): 128-130.）

[12] Meng H J, Zheng P, Mei G H, et al. Particle Swarm Optimization Algorithm Based on Chaotic Series[J]. Control and Decision, 2006, 21(3): 263-266. （孟红记, 郑鹏, 梅国晖, 等. 基于混沌序列的粒子群优化算法[J]. 控制与决策, 2006, 21(3): 263-266.）

[13]Liu L, Zhong W M, Qian F. An Improved Chaos-Particle Swarm Optimization Algorithm [J]. Journal of East China University of Science and Technology (Natural Science Edition), 2010, 36 (2): 267-272.（刘玲,钟伟民,钱锋.改进的混沌粒子群优化算法[J].华东理工大学学报(自然科学版), 2010, 36 (2): 267-272.）

[14]Wu Q B, Wang Y C, Zhao Q L, et al. Particle Swarm Optimization Algorithm with Chaotic Inertia Weight Adjusting Strategy[J].Computer Engineering and Applications, 2009, 45 (9): 49-51.（吴秋波,王允诚,赵秋亮,等.混沌惯性权值调整策略的粒子群优化算法[J].计算机工程与应用, 2009, 45 (9): 49-51.）

[15] Pandey B B, Debbarma S, Bhardwaj P. Particle Swarm Optimization with Varying Inertia Weight for Solving Nonlinear Optimization Problem[C]Electrical, Electronics, Signals, Communication and Optimization (EESCO), 2015 International Conference on. IEEE, 2015: 1-5.