新型混沌粒子群混合优化算法

刘军梅

摘要 为避免粒子群算法陷入局部最优、早熟收敛，提出了一种新型的混沌粒子群混合优化算法。利用混沌映射初值敏感性、遍历性特点，随机初始化一个粒子，并通过混沌映射得到多个粒子的初始值，改变初始粒子群的提取过程。利用混沌映射扩大初始粒子群，得到寻优粒子群，使得粒子群在搜索的过程中，种群数量变大，有利于全局寻优，而种群粒子多样化，有利于跳出局部极值。经典的测试函数仿真表明，改进的粒子群算法极大提高了粒子群的寻优精度和寻优效率，增加了粒子的全局寻优能力，具有更为广泛的应用场景。

关键词 粒子群算法；混沌映射；初值敏感性；混合优化

DOI DOI： 10.11907/rjdk.162828

中图分类号： TP312

文献标识码： A 文章编号 文章编号： 16727800（2017）002005904

0 引言

源于对鸟群捕食行为的研究，Eberhart博士和Kennedy博士于1995年提出一种新的进化计算技术，粒子群优化算法（PSO）[13]。在PSO 系统中，每个备选解被称为一个“粒子”（Particle），多个粒子共存、合作寻优，每个粒子根据自身“经验”和群体的最佳“经验”在问题空间中向更好的位置“飞行”，搜索最优解[45]。在问题求解空间中使整个群体的运动实现有序演化过程，进而获得空间最优解。

粒子群算法初期收敛速度快、规则简单、实现容易，因此被广泛应用于许多优化问题求解过程中，但同时后期易陷入早熟收敛、局部最优，因而有很大的改进空间。常见的粒子群优化方法有：①PSO算法参数改进，如调整惯性权重、收敛因子[6]；②拓补结构改进，如混合空间领域、环形拓补方法；③基于生物行为的改进，如Predator-Prey优化模型；④混合策略，如引入混沌技术、遗传算法、梯度信息等。混沌是一种貌似随机的运动，它出现在决定性动力学系统中，其本质是系统的长期行为对初始条件的敏感性，具有 遍历性、初值敏感性、内随机性等特点[78]。随着混沌粒子群算法的优化，人们也越来越多地关注将二者结合在一起的改进算法[912]。本文利用混沌搜索这3个特性，在粒子群优化算法中引入混沌优化思想，能够有效提高粒子群寻优能力，帮助其跳出局部极值，实现全局最优。

1 基本粒子群算法

在D维解空间内选取一组初始粒子群，数量为m，初始化其速度Vi=（vi1，vi2，vi3...viD）和位置Xi=（xi1，xi2，xi3...xiD），其中i代表第i個微粒，选定适应值函数FX，在粒子“飞行”过程中，通过迭代找到两个极值：个体极值记为Pbest即Pi=（pi1，pi2，pi3...piD），全局极值记为Pgbest即式中，i=1，2，3....m；d=1，2，3...D；ω是惯性常数，可以通过调节其大小来控制算法的全局寻优能力和局部寻优能力；c1 、c2 是正常数，常被称作是学习因子；r1、r2是rand（）介于[0，1]之间的随机数；t为种群当前进化代数。同时，粒子速度不能过大或过小，因此设置速度上限Vmax和速度下限Vmin，可知：

粒子群在相应的解空间内，不断地“飞行”，通过速度、位置更新公式，在迭代中更新其自身的历史最优值和全局最优值，并通过不断的对比与找寻，达到寻优目的[13]。

2 混沌映射

混沌现象是一种类似于随机的过程，它在非线性动态系统中确定性出现，可以由十分简单的确定性动力系统产生异常复杂的随机行为，同时，具有非周期、不收敛、但有界、并对初始值极为敏感的特点，混沌序列是遍历的，以下是几种常见的混沌映射：

（1）Logistic映射。

式（5）中，μ为控制参数，当μ=4时，Logistic 映射将会处于完全混沌状态。

（2）Tent映射。

Tent 映射结构简单，具有很好的遍历均匀性。

（3）Sinusoidal映射。

3 混沌粒子群混合优化算法

3.1 优化方法

在粒子群算法中引入混沌映射，提出一种新的混沌粒子群混合优化算法，以混沌序列初始化粒子群，改变粒子群的提取方法，同时利用混沌映射扩大种群数量，得到寻优粒子群，由混沌映射遍历性和初始值敏感性可知，寻优粒子群尽可能地遍历解空间内的所有状态，粒子群的多样性也会增加，可达到避免粒子群局部聚集状态，帮助粒子群跳出局部极值，从而提高粒子群全局寻优能力，提升粒子群的寻优精度和寻优效率，使得粒子可以在短时间内收敛到全局最优；同时与惯性权重线性递减策略相结合，使得粒子开始时在全局内进行寻优，找到目标范围。随着ω的减小，有利于局部寻优，加快了粒子群的寻优速度，提高了整体收敛精度。

将3种混沌映射即Logistic映射、Tent映射、Sinusoidal映射分别与粒子群算法相结合得出3种优化方法，即NLPSO、NTPSO、NSPSO方法。

3.2 优化算法流程

i代表第i个粒子（i=1，2，3...p）， j 代表维度（j=1，2，3...D），粒子最大速度为Vmax，最小速度为Vmin，Pbest、Pgbest分别代表粒子群个体历史最优解和全局历史最优解，以NLPSO为例：

（1）任意取一个粒子i，在解空间内其位置为x（i，j），速度为v（i，j）。随机初始化i，使得x（i，j）=rand（1，1），v（i，j）=rand（1，1）。

（2）将粒子i的位置和速度，按照式（6）迭代m次，即得到m个初始粒子的位置向量和速度向量，其中速度大小要满足式（3）、式（4）。

（3）将（2）选出的m个初始粒子，利用混沌变量的遍历性，依旧按照式（6）进行迭代n次，得到寻优粒子群p，p=m×n，同时可得到它们的速度向量V=（v1，v2，v3...vp），位置向量X=（x1，x2，x3...xp）。

（4）设置优化过程中迭代的最大次数、优化精度、PSO算法和混沌映射的初始参数。本文中c1 =c2=2，μ= 4 ，计算粒子群初始适应度值，并保存得到的值和位置。

（5）将粒子群按照式（1）、式（2）进行更新，产生新的位置并计算适应值，将新的适应值与之前得到的值进行比较更新，保留其中粒子自身的历史最优值Pbest和全局最优值Pgbest以及它们的位置。

（6）重复（5）达到最大迭代次数时转（7）。

（7） 寻优停止，输出全局历史最优值和相应的最优位置。

4 算法仿真结果

4.1 经典测试函数

为了验证混合优化算法的有效性，采用了4个经典的测试函数Griewank、Rastrigrin、Sphere和Schwefel，它们的表达式如下：

4.2 仿真结果

在本次仿真中，初始粒子群m=50，寻优粒子群p=500，迭代次数是500，解空间为D=10维，寻优精度Griewank是10-3、Rastrigin是100、Sphere是10-2、Schwefel是10-1，PSO代表基本粒子群算法，NLPSO代表优化的混沌粒子群算法。优化粒子群算法（NLPSO）和基本粒子群算法（PSO）测试结果如图1所示。

由图1可知，在4个经典函数的测试中，优化的混沌粒子群算法在收敛速度和收敛精度上都要明显优于基本粒子群算法。为进一步验证优化算法的有效性，对3种改进算法（NLPSO、NTPSO、NSPSO）分别进行实验。3种算法在测试函数上运行50次，3种算法寻优的成功率、平均精度、平均迭代次数和基本粒子群算法（PSO）对比数据如表1所示。

鉴于r1、r2对粒子速度更新公式的影响，可以对其作出假设，在r1、r2引入混沌映射，使速度尽可能地遍历到所有的值，可提高粒子的搜索范围，从而提高搜索精度，即对r1、r2同样施以混沌映射，可得出新的粒子群算法（NLRPSO）。这种粒子群算法（NLRPSO）和基本粒子群算法（PSO）测试结果如图2所示。

由图2可知，对r1、r2施以混沌映射时，其寻优效果尚不如基本粒子群算法，故这种方法将不再考虑，即改进的粒子群算法中将不再考虑将混沌映射引入到r1、r2中。

5 结语

本文针对粒子群算法易陷入局部极值、早熟收敛的问题，提出了改进的混沌粒子群混合优化算法。由仿真结果可知，改进的粒子群算法极大提高了收敛精度和寻优效率，但在收敛速度上影响不大，这是未来需要努力的方向。

改进的粒子群算法由于寻优粒子群的扩大，在资源调配中可以有效解决资源匮乏的问题，在发生地震、飞机坠落等灾害时可以发挥极大作用。例如在发生地震时，需要寻找失踪人口，此时，可用较少的寻人飞机，通过混沌映射得出多个虚拟飞机的位置，即本文中提出的寻优粒子群，进而达到利用较少的资源尽可能准确找到目标的目的，同时也极大提高了寻优精度和寻优效率，为灾难中的人们争取到更大的生存幾率。

参考文献：

[1] KENNEDY J，EBERHART R C.Particle swarm optimization [C].Proc.IEEE Int.Conf.on Neural Networks.Perth，WA，Australia：IEEEService Center，1995：19421948.

[2] EBERHART R C，KENNEDY J.A new optimizer using particle swarm theory[C].Proceedings of the Sixth International Sjmposium on Micro Machine and Human Science.Nagoya，Japan，1995：3943，

[3] LOVBJERG M，RASMUSSEN T K，KRINK T.Hybrid particle swarm optimization with breeding and subpopulations[C].Proc.Genetic and Evolutionary Computation Conf.San Francisco：Morgan Kaufmann Publishers，2001：469476.

[4] 刘华蓥，林玉娥，张君施.基于混沌搜索解决早熟收敛的混合粒子群算法[J].计算机工程与应用，2006，42（13）：7779.

[5] S SURESH，P B SUJIT，A K RAO.Particle swarm optimization approach for multiobjective composite boxbeam design [J].Composite Structures （S02638223），2007，81（4）：598605.

[6] MAURICE CLERC.The swarm and the queen：towards a deterministic and adaptive particle swarm optimization [C].Proc.Congress on Evolutionary Computation.Washington DC：Springer，1999：19271930.

[7] AWAD ELGOHARY，A S ALRUZAIZA.Chaos and adaptive control in two prey，one predator system with nonlinear feedback[J].Chaos，Solitons and Fractals （S09600779），2007，34（2）：443453.

[8] B LIU，L WANG，YH JIN，et al.Improved particle swarm optimization combined with chaos[J].Chaos Solitons&Fractals （S09600779），2005，25（21）：12611271.

[9] 高尚，杨静宇.混沌粒子群优化算法研究[J].模式识别与人工智能，2006，19（2）：266270.

[10] 孟红记，郑鹏，梅国晖，等.基于混沌序列的粒子群优化算法[J].控制与决策，2006，21（3）：263266.

[11] 陈国初，俞金寿，郭伟.两群替代微粒群优化算法及其应用[J].华东理工大学学报：自然科学版，2005，31（6）：787791.

[12] 尤勇，王孙安，盛万兴.新型混沌优化方法的研究及应用[J].西安交通大学学报，2003，37（1）：6972.

[13] R KATHIRAVAN，R GANGULI.Strength design of composite beam using gradient and particle swarm optimization[J].Composite Structures，（S02638223），2007，81（4）：471479.

（责任编辑：孙 娟）