面向全局优化的混沌粒子群遗传算法

刘振军

(唐山学院 基础教学部，河北 唐山 063000)

0 引言

在科学和工程的众多领域，优化方法得到了广泛应用。然而，对于全局优化问题，研究者尚未找到一种高效通用并被普遍接受的算法。利用启发式算法求解全局优化问题，成为近年来理论研究和实际应用的热点与趋势。遗传算法(Genetic Algorithm，GA)[1]、粒子群算法(Particle Swarm Optimization，PSO)[2]属于启发式算法，具有并行性、广泛的可适用性和较强的鲁棒性，并且操作简单，易于实现，然而二者存在一个共同的问题即全局优化效率还有待提高。GA是通过模拟达尔文生物进化论中自然选择和遗传学机理的生物进化过程来搜索最优解的一种计算模型，它通过染色体共享信息，获得较好的全局搜索性能，但由于缺乏有效的局部搜索机制，导致其在接近最优解时收敛缓慢，甚至会出现收敛停滞现象，从而陷入局部最优解。PSO是基于群集智能理论的优化算法，它通过种群中粒子间的合作与竞争行为优化搜索，保留了基于种群的全局搜索策略，具有记忆性，而且收敛速度快。然而，PSO在搜索过程中也比较容易陷入局部最优解，从而较难搜索到全局最优解。而且，PSO与GA各自的改进算法[3-6]在计算效率与精度方面虽然都有不同程度的提高，但仍不能满足实际应用的需要。因此，很多学者针对PSO和GA两种算法的特点，扬长避短，开展了将两种算法结合起来形成混合算法的研究工作[7-11]。

混沌运动作为非线性动力学的一个本质特征，具有遍历性、伪随机性等特点[12]，能在一定范围内按其自身的规律不重复地遍历所有状态。正是这些特性，使其在搜索过程中可以避免陷入局部最优解。很多研究者已将混沌搜索成功地运用到智能优化算法中[13-15]。通常的混沌优化方法是采用一维混沌映射作为混沌序列发生器，然后将其产生的混沌序列映射到设计空间进行寻优搜索。

实际上，已经有研究者采用不同的策略将混沌序列运用到粒子群算法中。Xiang等[16]和Meng等[17]在PSO中分别使用了分段线性混沌映射和Logistic混沌映射产生的混沌序列进行了混沌搜索。Jiang等[18-19]运用混沌映射序列改进了PSO中的参数：以惯性权重w和粒子速度更新式中的随机数r1与r2。为了加快算法的收敛速度，Liu等[20]在PSO中加入了局部混沌搜索与自适应惯性权重。Gandomi等[21]运用混沌映射序列代替加速PSO算法(APSO)[22]中的主要参数，进一步提高了算法搜索到全局最优解的能力。Renato等[23]在PSO搜索最优解发生停滞时，引入混沌跳跃，使其能够跳出局部极值点。

本文综合GA和PSO的优点以及混沌运动的特性，对GA与PSO的混合算法加以改进，提出了混沌粒子群遗传算法(CPSO-GA)，以提高全局优化效率。为了考察算法的计算性能及其搜索全局最优解的精度，本文通过五个高维非线性基准函数对算法进行测试和分析。

1 混沌粒子群遗传算法(CPSO-GA)

在混沌优化算法中，普遍使用的一维混沌映射是Logistic映射。当μ=4时，Logistic映射处于混沌状态，混沌序列服从两端大、中间小的Chebyshev分布[24]，不能均匀地遍历整个搜索空间，可能会导致算法的收敛速度较慢或陷入局部最优解。

尽管Tent映射与Logistic映射具有拓扑共轭关系，但是它们的混沌序列的概率分布不同。Tent映射经过Bernoulli位移转换以后可表示为：

zn-1=g(zn)=(2zn)mod1。

(1)

Tent混沌序列服从均匀分布，全局优化的寻优效果比Logistic映射要好[24]。因此，本文选用Tent映射产生均匀分布的混沌序列，以备混沌粒子群遗传算法之需。

对于无约束优化问题，在混沌优化中混沌变量z与设计变量Xc之间存在如下所示的映射关系：

Xcd=XLd+z(XUd-XLd)。

(2)

式中，Xcd是Xc的第d个分量；XU与XL是优化设计变量的上界与下界，均是D维向量，d=1，2，…，D。

在Jia等[25]提出的算法中采用了混沌局部搜索，方程式为：

(3)

(4)

文献[4]已给出定理——PSO进化过程与粒子的速度无关，并展示了详细证明。本文采用文献[4]中的粒子更新方法，将粒子的速度更新与粒子更新两式合并成一个方程：

(5)

式中，i=1，2，…，n，n为种群个数；d=1，2，…，D；Pi表示种群中第i个粒子；Pg表示种群中最优的粒子；c1与c2是加速常数；r1与r2是[0，1]区间中的随机数。

为了改善粒子群遗传算法的全局优化性能，根据式(4)设计点的迭代形式，结合表达式(5)，本文采用下式来更新粒子：

(6)

在改进的粒子更新式(6)中，第一项表示过去对现在的影响，通过缩放因子a调节影响程度，a越大，其影响程度越大；第二项表示粒子对当前本身最优位置的靠近，依赖程度取决于参数1-a和混沌变量z；第三项表示粒子对当前群体最优位置的靠近，依赖程度也取决于1-a和z，通过它们实现粒子间的信息共享与合作。从a的表达式可以看出，随着进化代数逐渐增加，a呈非线性下降趋势，到进化后期对粒子本身的影响程度减小，而对个体极值与群体极值的影响程度逐渐增大，亦即在进化前期局部搜索能力较强，而进化后期全局搜索能力增强。在后两项中，不同的混沌变量取值，可以增加粒子的多样性，并使粒子从不同的方向靠近个体极值与群体极值，避免陷入局部极值点。从a的表达式还可以看出，m取值越大，收缩的速度越慢，因此m=6比较合适。

本文提出的混沌粒子群遗传算法(CPSO-GA)的流程如图1所示。该算法中粒子的初始化采用的是Tent混沌映射的点序列；交叉、变异、选择的操作均采用实数编码机制，其中为了增加粒子的多样性，在交叉操作中将粒子分别与个体极值和群体极值交叉。

图1 混沌粒子群遗传算法流程图

2 测试分析

为了测试CPSO-GA的性能，将其与GA，PSO，PSO-GA进行比较，选用五个高维非线性基准函数[23-24]进行计算分析，表达式如下：

Sphere函数：

(7)

Rosenbrock函数：

(8)

Ackley函数：

(9)

Griewank函数：

(10)

Rastrigrin函数：

(11)

Sphere函数和Rosenbrock函数是单峰函数。其中，Sphere函数的最优点是x*=(0，0，…，0)，最优值是f*=0；Rosenbrock函数的最优点是x*=(1，1，…，1)，最优值是f*=0。Ackley函数、Griewank函数和Rastrigrin函数均是多峰函数，有无穷多个局部极小点、一个全局极小点，且最优点均是x*=(0，0，…，0)，最优值均是f*=0。

当目标函数的维数越高、自变量范围越大、目标精度越高时，其优化难度就越大。本文对算法的性能评估采用如下方法：①固定进化代数，评估算法的收敛速度与收敛精度；②在目标函数调用次数相接近的情况下，将函数最优值的均值和标准差与文献中已有算法的结果进行比较；③固定收敛精度值，评估算法达到该精度时所需要调用目标函数的次数。

2.1 固定进化代数，评估算法的收敛速度与收敛精度

本次测试参数设置如下：种群规模为30；最大迭代代数为500；交叉概率pc=0.9；变异概率pm=0.1；加速常数c1=c2=2；惯性权重w由0.9减小到0.4；个体极值需要扰动的停滞代数阈值T=3。本文的函数适应度取以10为底的对数，同时，为了避免真数为0和纵坐标范围过大，给函数适应度加上10-25作为截止值。

图2为五个函数在各算法中的适应度进化曲线，从中可以看出，PSO-GA，CPSO-GA解决高维无约束优化问题的能力均好于GA[1]和PSO[2]。其中，CPSO-GA的实现过程与PSO-GA类似，仅在粒子更新时采用式(5)。CPSO-GA的收敛精度和收敛速度最好，均能找到最优解与最优值，甚至可以达到目标的精确解，一般进化代数在200代以内就能够找到全局最优解，收敛速度很快。

图2 f1-f5在四种算法中的适应度进化曲线

表1给出了各算法对测试函数搜索到的最优值的最小值、均值、最大值、标准差以及寻优成功率的比较结果，该表中的结果均是各算法经过100次独立运算后得到的各数值的均值，其中寻优成功率是指搜索到的最优解和理论解的误差在0.001之内的次数与总的运算次数之比。从表1可以看出，GA和PSO对五个测试函数均不能搜索到全局最优值；PSO-GA的寻优成功率较高，寻找到全局最优值的精度也比较高；而CPSO-GA能够100%地寻找到全局最优值，寻优的精度也很高，其中f4和f5已找到精确的最优值，说明该算法具有很好的收敛性。本文所有程序均用Matlab编写，其计算精度是10-308，若小于此精度，函数值默认为0。

表1 各算法对测试函数寻找到最优解的最小值、均值、最大值、标准差以及寻优成功率比较

图2和表1表明，同其他算法相比，CPSO-GA的性能最好。算法在进化过程中，每一代计算出的最优解逐渐向问题的真实解靠近。这是因为粒子在更新时，受到上一代粒子的影响，同时也受到上一代局部和全局最优解的影响。更新的粒子及时纠正局部与全局最优解，最后局部与全局最优解逐渐向问题的真实解靠近，并收敛到问题的真实解。而且当利用具有混沌运动特性的混沌序列更新粒子时，粒子的多样化进一步加强，于是粒子从不同方向靠近问题的真实解，由此缩短了收敛进程。本文提出的算法综合了PSO与GA两种算法的优点，且在搜索时加入了混沌序列，能够快速改变搜索方向，这也是CPSO-GA收敛准确以及收敛较快的原因。

2.2 目标函数调用次数相接近，计算函数最优值的均值和标准差

PSO-GA和CPSO-GA在每代更新时所要调用目标函数的次数较多，亦即计算量较大，此时采用相同的种群数和相同的最大迭代代数与其他算法比较便失去了公平性。因此，为了比较公平地评估两种算法的性能，本文在总的目标函数调用次数相接近的基础上，将这两种算法寻找到的最优值的均值、标准差等数值与文献中算法寻找到的相应数值作比较，结果如表2与表3所示。

表2中来自文献的四种算法PSO-w[26]，UPSO[27]，FIPS[28]，CDPSO[5]均是没有加入混沌运动特性的PSO的改进算法。用六种算法对f1，f3，f4和f5四个函数进行测试，函数维数为10，为了使总的目标函数调用次数相接近，其中PSO-w，UPSO，FIPS，CDPSO四种算法采用的种群粒子数为10，最大迭代代数为3 000，则总的目标函数调用次数是3×104；PSO-GA和CPSO-GA两种算法采用的种群粒子数为10，最大迭代代数是900，则总的目标函数调用次数在2.9×104～3×104之间。每种算法独立运行100次。从表2可以看出，PSO-GA对函数f1可以搜索到精确解，而对其他三个函数搜索效果略差一些；CPSO-GA算法对不同的函数都比较容易跳出局部极小点、收敛到全局最优点，搜索到最优解的精度最高，表明其性能优于其他几种算法。

表2 各算法对测试函数搜索到的最优值的均值和标准差比较

表3 各算法对测试函数搜索到最优值的均值比较

表3中CPSO-I-CPSO-VI六种算法是文献中提出的混沌PSO算法。用八种算法对f1-f5五个函数进行测试，函数维数为30，为了使总的目标函数调用次数接近，其中CPSO-I-CPSO-VI六种算法采用的种群粒子数为30，最大迭代代数为5 000，则总的目标函数调用次数是1.5×105；PSO-GA，CPSO-GA两种算法采用的种群粒子数为30，最大迭代代数是1 000，则总的目标函数调用次数在9.4×104～1.0×105之间。每种算法独立运行100次。从表3可以看出，PSO-GA，CPSO-GA两种算法对测试函数搜索到的最优值的均值比CPSO-I-CPSO-VI六种算法要好、精度要高，其中CPSO-GA对f1，f4和f5均能搜索到目标函数的最优值，对f2搜索到的最优值的精度也比较高。

表2和表3也说明，无论是与不加混沌序列的改进PSO比较，还是与几种混沌PSO比较，在总的目标函数调用次数接近时，CPSO-GA具有最好的全局搜索性能和最高的收敛精度，亦即更准确地搜索到全局最优解。

2.3 固定收敛精度，评估需调用目标函数的次数

在实际的问题优化中，我们不仅想得到较准确的优化结果，而且要尽可能减小算法的计算量，因此，在达到可接受解的条件下，减少目标函数的调用次数显得尤为重要。选用FIPS[28]，CLPSO[29]，CDPSO[5]三种算法，然后与CPSO-GA在目标函数调用次数上加以比较。用f1，f3，f4和f5四个函数作为测试算例，设定函数维数是30，种群粒子数是20。FIPS，CLPSO和CDPSO各算法独立运行30次，而CPSO-GA独立运行100次，得到的达到函数阈值时所调用的目标函数次数的均值如表4所示。此表说明对单峰和多峰值的测试函数，CPSO-GA收敛速度比其他算法更快，达到函数阈值所调用的目标函数次数最少。CPSO-GA综合了PSO和GA的优点，并利用混沌运动的特性，使全局优化能力增强，而且收敛速度加快，甚至计算几代就能获得比较精确的解，大大降低了计算量。尽管在算法计算结果比较过程中，规定了相同的函数维数、种群粒子数以及函数阈值，但由于所编写程序不尽相同，因此在处理某些细节问题上采用的策略也有所不同，可能会造成计算结果的差异。

表4 各算法达到函数阈值时所调用目标函数次数的均值比较

3 结论

GA和PSO均是基于自然界生物进化理论的随机搜索算法。本文结合GA和PSO的优点以及混沌运动的特性，提出了改进的混合算法CPSO-GA，并使用五个高维非线性函数作为测试函数测试此混合算法的性能。

数值试验及分析结果表明，在固定进化代数情况下，CPSO-GA能100%地找到最优解，其收敛效果及寻优能力要好于PSO-GA，GA，PSO以及文献中所提出的算法；在所调用目标函数次数接近时，与其他文献中提出的算法相比，PSO-GA与CPSO-GA两种算法均能够得到较好的收敛结果，收敛速度也很快；在固定收敛精度的情况下，CPSO-GA进化程度和收敛速度很快，并能有效摆脱局部极小点，且调用目标函数次数最少，从而大大降低了计算量。

本文提出的CPSO-GA具有PSO的可记忆性、GA的信息共享与全局收敛性，其更新粒子能够及时纠正每一代局部与全局最优解，而且利用混沌运动的特性加大了粒子的多样性，这不仅扩大了搜索空间，加快了其向全局最优解收敛的速度，而且提高了最优解的精度。CPSO-GA不需要计算目标函数梯度等信息，仅通过生物的进化机制来寻优，操作简单，易于实现，因此，将之应用于实际工程中可以很好地解决优化问题。