基于自适应Tent混沌搜索的粒子群优化算法

摘 要：

为解决粒子群优化算法易于陷入局部最优问题，提出基于自适应Tent混沌搜索的粒子群优化算法。应用Tent 映射初始化均匀分布的粒群，并以当前整个粒子群迄今为止搜索到的最优位置为基础产生Tent混沌序列，混沌序列的搜索范围采用自适应调整方法。该方法可以有效避免计算的盲目性，还能够快速搜寻到最优解。实验表明该算法在多个标准测试函数下都超越了同类改进算法。

ス丶词：

粒子群优化算法；Tent 映射；自适应；混沌搜索

ブ型挤掷嗪牛 TP273.2

文献标志码：A

英文标题

Particle swarm optimization algorithm based on adaptive Tent chaos search

び⑽淖髡呙

HUANG Meiling, ZHAO Zhijie, PU Lina, WU Fei, ZHAO Meiling, CHEN Hao, CHEN Mingzhe

び⑽牡刂(

Beijing Xinqiao Technology Development Company Limited, Research Institute of Highway Ministry of Transport, Beijing 100101, China

英文摘要

)

Abstract:

To solve the premature convergence problem of Particle Swarm Optimization (PSO), a new PSO algorithm based on adaptive chaos search was proposed. The uniform particles were produced by Tent mapping so as to improve the quality of the initial solutions. Tent chaotic sequence based an optimal location was produced, and the adaptive adjustment of search scopes can avoid the redundant computation and accelerate the convergence speed of the evolutionary process. The experimental results show that the new introduced algorithm outperforms several other famous improved PSO algorithms on many wellknown benchmark problems.

英文关键词

Key words:

Particle Swarm Optimization (PSO) algorithm; Tent mapping; adaptive; chaos search

0 引言

粒子群优化(Particle Swarm Optimization，PSO)算法是一种简单、快速、容易实现的基于迭代的优化算法，目前已广泛应用于函数优化、神经网络训练、模糊系统控制及其他遗传算法的应用领域。PSO 算法亦有不足，如易陷入局部极值点、进化后期收敛速度缓慢、精度较差等。

为了提高算法的性能，国内外学者提出了各种改进的方案［1-11］。如变更公式法通过对基本粒子群优化算法更新公式的改进来提高算法的搜索能力，即通过引入其他附加信息，扩大群体可利用的信息,从而增强算法的寻优能力；分群方法将一个种群按不同要求分成多个种群进行搜索，通过各个种群的独立搜索能力和相互作用，从而提高算法的搜索能力；混合算法将粒子群算法与其他优化算法结合，充分利用其他算法在优化方面的某些优势，来提高粒子群算法的寻优能力；扰动方法主要通过不断的极值扰动，使种群始终处于一种非平衡态，促使粒子对环境不断进行探索，从而提高算法的搜索能力。这些改进方案在一定程度上提高了算法的寻优能力，但粒子在演化过程中不够灵敏，需要较大的迭代次数才能较好地完成搜索工作。为此，本文构造一种基于自适应Tent混沌搜索的粒子群优化（Adaptive Chaos Particle Swarm Optimization, ACPSO）算法，对于每次混沌搜索的范围采用自适应调整方法，改善了粒子群优化算法摆脱局部极值点的能力，提高了算法的收敛速度和精度，实验结果表明，该算法在不同情况下都超越了其他同类改进算法。

1 粒子群优化算法

1.1 基本粒子群算法

PSO算法是一种模拟鸟群飞行觅食的行为，通过个体间的协作来寻找最优解的进化计算技术。假设其搜索空间为N维，粒子总数为 n，第i个粒子在N维空间的位置表示为xi，飞行速度为vi。每个粒子都具有一个由被优化的目标函数决定的适应值，并且知道自己到目前为止所发现的最好位置pi和现在的位置，每个粒子都知道目前为止整个群体所发现的最好位置，每个粒子的位置按式（1）、式（2）进行计算。オ

vi, j(t+1)=ω×vi, j(t)+c1×r1×(yi, j(t)－xi, j(t))+c2×r2×(j(t)－xi, j(t))В1）

xi(t+1)=xi(t+1)+vi(t+1)В2）

其中：vi, j(t)为第i个粒子第t次迭代中飞行速度的第j维分量；xi, j(t)为第i个粒子第t次迭代中位置的第j维分量；j为群体最好位置的第j维分量；yi, j为粒子i最好位置的第j维分量；r1、r2为随机数；c1、c2为权重因子；ω为惯性权重，由式（3）来确定。

Е=ω┆max－(ω┆max－ω┆min)×k/GВ3）

其中：Е鬲┆max、ω┆min分别是ω的最大和最小值；G、k分别为最大迭代次数和当前迭代次数。オ

1.2 GCPSO算法

文献[1-2]提出一种保证收敛的混沌粒子群优化算法(Guaranteed Convergence Particle Swarm Optimization, GCPSO)。

设Е营为当前全局最优微粒的标号，为保证当前全局最优微粒在到达一个局部最优解位置之前能够保持运动，文献［1］提出的当前全局最优微粒速度更新公式为：

v│, j(t+1)=－x│, j(t)+j(t)+ω×v│,j(t)+

ρ(t)(1－2r2,j(t))В4）

将式 （4）代入式（2），就可以得到全局最优微粒的位置更新公式:

x│, j(t+1)=j(t)+ω×v│, j(t)+ρ(t)(1－2r2, j(t))В5）

算法中，其他微粒仍然按照基于邻近粒子信息的粒子群算法的速度和位置更新式（1）、（2）。

式（4）中，Вx│, j(t)项将微粒的位置“重置”到j，ω×v│, j(t)代表了当前最优微粒从该位置上开始的搜索方向，而ρ(t)(1－2r2,j(t))项则在j周围大小为2ρ(t)的样本空间内产生一个随机搜索，搜索半径由尺度因子ρ(t)决定。p(t)的值随迭代次数t更新如下：オ

Е(t+1)=2ρ(t),#successes>sc0.5ρ(t), #failures>fc

ρ(t), 其他В6）

1.3 混沌粒子群优化算法

唐贤伦［4］于2007年提出的一种基于混沌优化思想的混沌粒子群优化（Chaos Particle Swarm Optimization, CPSO）算法，充分利用粒子群优化算法的收敛速度较快及混沌运动的遍历性的优点，改善了粒子群优化算法摆脱局部极值点的能力，提高了算法的收敛速度和精度。

Logistic方程是一个典型的混沌系统：

zn+1=μ・zn・(1－zn)； n=0, 1, 2, …В7）

其中：Е涛控制参量。取μ=4，设0

混沌粒子群优化算法CPSO的算法流程如下。

1）初始化设置最大允许迭代次数或适应度误差限，以及CPSO算法相关参数，即惯性权值、学习因子。

2）混沌初始化粒子位置和速度。

①随机产生一个n维每个分量数值在0~1的向量z1=(z11,z12…,z1n)，n为目标函数中的变量个数，根据式（7），得到N个向量z1,z2…,zN。

②将zi的各个分量载波到对应变量的取值区间。

③计算粒子群的适应值，并从N个初始群体中选择性能较好的M个解作为初始解，随机产生M个初始速度。

3）如果粒子适应度优于个体极值p┆best，则p┆best设置为新位置。

4）如果粒子适应度优于全局极值g┆best，则g┆best设置为新位置。

5）根据式（1）、（2）更新粒子的速度和位置。

6）对最优位置pg=(pg1,pg2,…,pgD)进行混沌优化。将pgi(i=1,2,…,D)映射到Logistic方程的定义域［0,1］，zi=(pgi－ai)/(bi－ai), i=1,2,…,D；然后，用Logistic方程进行迭代产生混沌变量序列zmi(m=1,2,…)；再把产生的混沌变量序列通过逆映射pgi= ai + (bi-ai)zmi返回到原解空间，得：

p(m)g= (p(m)gi ,p(m)g2 ,…,p(m)gD )；m=1,2,…

在原解空间对混沌变量经历的每一个可行解p(m)g （m=1,2,…）计算其适应值，得到性能最好的可行解p*。

7）用p*取代当前群体中任意一个粒子的位置。

8）若满足停止条件，则搜索停止，输出全局最优位置；否则返回3）。オ

2 基于自适应混沌搜索的粒子群优化算法

2.1 混沌映射与混沌序列

一般将由确定性方程得到的具有随机性的运动状态称为混沌，呈现混沌状态的变量称为混沌变量。混沌是存在于非线性系统中的一种普遍现象，一个混沌变量在一定范围内具有随机性、遍历性和规律性的特点。利用混沌变量的这些特征进行优化搜索，能使算法跳出局部最优，保持群体的多样性，改善算法的全局搜索性能；然而，不同的混沌映射算子对混沌寻优过程有很大的影响。目前文献中引用较多的是Logistic 映射算子。文献［11］通过比较指出Tent 映射比Logistic 映射具有更好的遍历均匀性和更快的迭代速度，并经过严格的数学推理，论证了Tent 映射具有作为优化算法混沌序列的前提条件。Tent 映射又称为帐篷映射，其表达式如下式：

xk+1=2・xk， 0≤xk≤1/2

2(1－xk)， 1/2

理论研究表明［11］，Tent 映射经贝努利移位变换后可以表示成如下形式：

xk+1=(2xk) mod 1В9）

因此，根据Tent 映射，可按如下步骤在可行域中产生粒子iУ幕煦绲懔小＊

1）取初值x0 （x0应避免落入小周期点内），记入标志组z，z(1)=x0，i=j=1。

2）对式（9）进行迭代，i自增1，产生x序列。

3）若迭代达到最大次数，则跳转5）；否则，若x(i)={0,0.25,0.5,0.75}或x(i)=x(i-k)， k={0,1,2,3,4}（即x落入不动点或5周期以内的小循环）,则进入4），否则回到2）。

4）改变迭代初值x(i)=z(j+1)=z(j)+ε，j=j+ 1，返回2）。

5）终止运行，保存x序列。オ

2.2 基于自适应混沌搜索的粒子群优化算法

1.3节的混沌粒子群优化算法，其混沌搜索是以当前整个粒子群迄今为止搜索到的最优位置为基础产生混沌序列，但由于每次搜索的范围比较大，很难搜索到更优位置，且采用的是Logistic映射，其得到的［0,1］范围的分布在［0,0.1］和［0.9,1］取值概率较高，这大大降低了算法的效率。本文针对以上问题提出一种自适应混沌搜索的粒子群优化算法，其基本思想主要体现在两个方面。

1）采用Tent混沌序列进行混沌搜索。Tent 映射比Logistic 映射具有更好的遍历均匀性和更快的迭代速度。采用Tent混沌序列初始化粒子的位置和速度，既不改变粒子群优化算法初始化时所具有的随机性本质，又利用Tent混沌提高了种群的多样性和粒子搜索的均匀遍历性，在产生大量初始群体的基础上，从中择优出初始群体。

2）Ф杂诿看位煦缢阉鞯姆段Р捎米允视Φ髡方法。对当前进化代数（第k代）的所有粒子按适应度从小到大排列，取前面N个（占总共粒子的80%）粒子，分别求得这N个粒子第j维的最小值a(j, k)和最大值b(j, k)，j=1,…,D；把每一维的最大值和最小值作为每一维混沌搜索的范围。以当前整个粒子群迄今为止搜索到的最优位置为基础产生混沌序列，混沌序列的搜索范围为［a(: ,k),b(: ,k)］，把产生的混沌序列中的最优m位置粒子随机替代当前粒子群中的m粒子的位置。引入自适应混沌搜索算法可在迭代中产生局部最优解的许多邻域点，不但能帮助惰性粒子逃离局部极小点，还能够快速搜寻到最优解。オ

ACPSO的算法流程如下：

1）初始化设置最大允许迭代次数或适应度误差限，以及ACPSO算法相关参数：即惯性权值、学习因子。

2）混沌初始化粒子位置和速度。

Б偎婊产生一个n维每个分量数值为0~1的向量z1=(z11,z12…,z1n)，n为目标函数中的变量个数，根据式（7），得到N个向量z1,z2…,zN。

②将zi的各个分量载波到对应变量的取值区间。

③计算粒子群的适应值，并从N个初始群体中选择性能较好的M个解作为初始解，随机产生M个初始速度。

3）如果粒子适应度优于个体极值p┆best，则p┆best设置为新位置。

4）如果粒子适应度优于全局极值g┆best，则g┆best设置为新位置。

5）采用GCPSO算法更新粒子的速度和位置。

6）Ф缘鼻敖化代数（第k代）的所有粒子按适应度从小到大排列，取前面80%的粒子，分别求得这些粒子的第j维的最小值a(j, k)和最大值b(j, k)，j=1,…,D。

7）对最优位置pg=(pg1,pg2,…,pgD)进行混沌优化，将pgi(i=1,2,…,D)映射到Tent方程的定义域(0,1)，zi=(pgi－ai,k)/(bi,k－ai,k), i=1,2,…,D；然后，用Tent方程进行迭代产生混沌变量序列zmi(m=1,2,…)；再把产生的混沌变量序列通过逆映射pgi= ai,k+ (bi,k -ai,k )zmi返回到原解空间，得：

p(m)g= (p(m)gi ,p(m)g2 ,…,p(m)gD )；m=1,2,…

在原解空间对混沌变量经历的每一个可行解p(m)g ，m=1,2,…计算其适应值，得到性能最好的H个可行解p*(h)，h=1,…,H。

8）用p*(h)取代当前群体中任意H个粒子的位置。

9）若满足停止条件，则搜索停止，输出全局最优位置；否则返回3）。オ

3 改进PSO算法的实验研究

3.1 测试函数

本文采用以下5个测试函数对几种改进PSO算法做实验研究，这些函数是EC研究中常用的测试函数。虽然这些测试函数不能完全精确反映算法在所有现实优化问题的上表现的性能，但确实可以用于对算法基本性能的评估。

3.2 各类算法对比测试

对4种算法的性能做分析和评价，分别对标准PSO、GCPSO、CPSO和ACPSO4种PSO算法做大规模计算实验，以上述5个函数为测试函数。所有算法的基本参数均采用Иc1 =c2=2.0，粒子数N=40，粒子维数D=30，最大迭代次数it┆max=3B000，惯性权重W┆max=0.98，W┆min=0.12。算法在Matlab R2009a环境下实现，为衡量本文算法的优化性能，对每个函数独立运行30 次，测试性能如图1~5，测试对比结果如表2所示。オ

表格(有表名)

表1 5个测试函数

函数名表达式搜索范围函数特点

SphereModelf1(x) = ∑ni = 1x2i－100≤xi≤100Т撕数相对比较简单，大多数算法都能够轻松地达到优化效果，主要用于测试算法的寻优精度

GeneralizedRosenbrockf2(x) = ∑ni = 1［100(xi+1-x2i)2+(xi-1)2］－30≤xi≤30Т撕数是很难极小化的典型病态二次函数，其全局最优与可到达的局部最优之间有一道狭窄的山谷，曲面山谷中的点的ぷ钏傧陆捣较蚣负跤氲胶数最小值的最好方向垂直

GeneralizedRastriginf3(x) = ∑ni = 1［x2i-10cos(2πxi)+10］－5.12≤xi≤5.12它是一个典型的具有大量局部最优点的复杂多峰函数，此函数很容易使算法陷入局部最优，而不能得到全局最优解

Ackleyf4(x) = -20exp-0.2・1n∑ni = 1x2i-おexp-0.21n∑ni = 1cos(2πxi) + 20 + e－32≤xi≤32Т撕数为连续、旋转、不可分离的多峰函数；它的拓扑结构特征是：外部区域几乎平坦，中间出现一个或者峰，从而变得不平滑；此函数具有大量局部最优点

GeneralizedGriewankf5(x) = 14B000∑ni = 1x2i-∏ni = 1 xii+ 1－600≤xi≤600Т撕数为旋转、不可分离的多峰函数；随着维数的增加，忽略局部最小区域的可能性也就越大

表格(有表名)

表2 各算法对5个测试函数进行优化的结果

函数PSOGCPSOCPSOACPSO

fИ19.56E-04±1.2E-041.88E-16±1.5E-157.49E-21±8.1E-225.1E-30±1.56E-29

fИ23.17E+01±2.02E+012.05E+01±2.02E+001.56 E+01±2.32E+004.58E-16±1.24E-16

fИ33.98E+01±8.02E+003.08E+01±9.02E-012.88 E+01±1.02E+002.48E-14±2.04E-14

fИ43.52E+00±2.72E+002.88 E+00±7.72E-012.66E+00±3.72E-014.12E-10±2.14E-9

fИ53.77E-02±8.5E-032.71E-02±3.5E-031.23E-02±1.5E-033.33E-17±4.54E-17

各算法对30维fИ3函数动态寻优过程

从表2可以看出，本文提出的ACPSO算法在最优收敛值、平均收敛值、标准差的求解方面均优于其他3种算法，CPSO对于所有的测试函数性能都优于PSO算法和GCPSO算法，但由于搜索空间较大，每次得到更优解的概率较小，因此很难搜索到最优解。从图1~5 可以看出，ACPSO比其他3种算法在收敛速度和计算精度方面有显著提高，这说明在GCPSO算法中引入自适应Tent混沌搜索，有助于算法摆脱局部极值点的束缚而进行全局寻优，不但具有较快的收敛速度，而且也有很强的全局搜索能力，提高了算法的收敛速度和精度。

为了进一步检验文中提出的ACPSO算法的优化性能，与一些有代表性的新近改进的PSO算法[4-10]进行了实验比较。以表2所述的5个函数为测试函数。本文算法的基本参数与文献［1-7］采用的参数基本相同，其粒子数N=40，粒子维数D=30。в胛南祝4-10］对比结果如表3所示。

图片

图4

各算法对30维fИ4函数动态寻优过程

图片

图5

各算法对30维fИ5函数动态寻优过程

表格(有表名)

表3 各算法对5个测试函数进行优化的结果

函数

TMPSO［10］

CQPSO［9］

PSOHD［8］

CPSO［7］

DDPSO［6］

CRPSO［5］

ACPSO［4］

ACPSO（本文算法）

fИ12.83E0-34(最优)

4.13E0-21(平均)―6.42E0-06

(最优)4. 96E0-6

(最优)2.99E0-21

(最优)―1.99-31(最优)

5.1E0-30(平均)

fИ2―2.03E0-03

(平均)――3.62E0-01

(平均)1.68E0+01

(最优)2.5E0-2

(最优)0(最优)

4.58E0-16(平均)

fИ30(最优)

5.6E0-007(平均)4.03E0-02

(平均)――1.39E0-02

(平均)1.28E0-03

(最优)3.8E0-7

(最优)0(最优)

2.48E0-014(平均)

fИ4―1.92E0-23

(平均)9.15E0-06

(最优)8. 55E0-6

(最优)2.2E0-02

(平均) 4.7E0-8

(最优)1.38E0 -11(最优)

4.12E0-10(平均)

fИ56.14E0-017(最优)

6.14E0-017(平均)3.15E0-03

(平均)8.78E0-06

(最优)7. 21E0-6

(最优)2.67E0-02

(平均)2.26E0-12

(最优)6.9E0-3

(最优)0(最优)

3.33E0-17(平均)

注：“―”表示原文献无此数据。

从表3可以看出：本文提出的基于Tent 混沌序列的粒子群优化算法在最优收敛值、平均收敛值的求解方面，除了CQPSO［9］求解fИ4外，均优于其他7种算法，这充分说明本文算法的性能均达到或优于其他已有算法。

在对fИ1的测试中，尽管本文ACPSO算法的最优收敛值略差于TMPSO[10]，但是其平均收敛值要优于TMPSO，这充分说明本文ACPSO 算法具有更好的稳定收敛性。在对fИ4的测试中，尽管本文ACPSO算法的平均收敛值略差于CQPSO[9]，但本文ACPSO算法在对f2、f3和f5е凶钣攀樟仓岛推骄收敛值能达到0和1.0E-16级别，而CQPSO只能达到1.0E-03级别，说明本文ACPSO方法对于复杂的高维、多极值点的函数，能够以较小的计算代价获得一定精度的全局极小。本文ACPSO算法在抗早熟能力和收敛速度要明显优于ACPSO［4］，也进一步论证了文献［4］中所述的由于每次搜索的范围比较大，很难搜索到更优位置，造成PSO 算法稳定性差的结论。

可见本文ACPSO算法具有更好的搜索精度, 较强的抗早熟能力和较快的收敛速度，并且算法也更加稳定。

4 结语

本文充分利用粒子群优化算法的收敛速度较快及混沌运动的遍历性的优点，提出一种基于自适应Tent混沌搜索的粒子群优化（ACPSO）算法，对于每次混沌搜索的范围采用自适应调整方法，改善了粒子群优化算法摆脱局部极值点的能力，提高了算法的收敛速度和精度。通过对5个基准测试函数的仿真，并与文献中相应算法优化结果的比较，证明了该算法具有快速收敛和鲁棒性好的特点。本文ACPSO算法对于复杂函数全局优化问题是一种合适的工具，对于高维、多极值点的函数，能够以较小的计算代价获得一定精度的全局极小值。

参考文献:

[1]

van den BERGH F, ENGELBREEHT A P.A new locally convergent particle swarm optimizer［C］// Proceedings of the IEEE Intemational Conference on Systems. Washington, DC: IEEE Computer Society, 2002: 3-6.

［2］

van den BERGH F. An analysis of particle swarm optimizers[D]. Pretoria, South Africa: University of Pretoria, 2002.

［3］

RIGET J, VESTERSTROEM J S．A diversityguided particle swarm optimizer-the ARPSO ［R］. Aarhus, Denmark: University of Aarhus, Department of Computer Science，2002．

［4］

唐贤伦. 混沌粒子群优化算法理论及应用研究［D］. 重庆：重庆大学, 2007.

［5］

王刚, 张定华, 陈冰. 基于分工合作和搜索空间重构的粒子群优化［J］. 计算机工程，2010，46(2):51-54.

［6］

任小波,杨忠秀. 一种动态扩散粒子群算法［J］. 计算机应用，2010，30(1):159-161.

［7］

刘怀亮, 苏瑞娟, 许若宁,等. 协同粒子群优化算法［J］. 计算机应用，2009，29(11):3068-3071.

［8］

刘怀亮, 苏瑞娟, 许若宁,等. 基于Hénon混沌与动态非线性方程的改进粒子群优化算法［J］. 计算机应用研究，2010，30(1):92-95.

［9］

康燕，冯海朋，须文波,等. 合作的具有量子行为粒子群优化算法［J］. 计算机工程与应用，2010，46(4):39-42.

［10］

田东平. 基于Tent 混沌序列的粒子群优化算法［J］. 计算机工程，2010，36(4):180-186.

［11］

单梁, 强浩, 李军,等. 基于Tent映射的混沌优化算法［J］. 控制与决策, 2005, 20(2):179-182.