基于量子行为的鸡群优化算法及其收敛性分析

张秋桥，王 冰，汪海姗，曹智杰

(1. 河海大学能源与电气学院，江苏 南京 211100；2. 南京豪庆信息科技有限公司，江苏 南京 210006)

1 引言

群体优化算法是观察自然界生物群体行为而衍生出的一种随机优化算法[1]，其寻优过程体现了个体与个体之间信息的交互以及群体的更新。因此，像粒子群优化算法(Particle Swarm Optimization，PSO)[2-4]，蚁群优化算法(Ant Colony Optimization，ACO)[5-6]，蝙蝠优化算法(Bat Algorithm，BA)[7-8]等在处理一些复杂的、易陷入局部最优解的问题时得到了广泛的应用。

鸡群优化算法(Chicken Swarm Optimization，CSO)[9]顾名思义是一种模拟鸡群行为的随机优化算法，该算法将整个鸡群分为多个种群，种群根据其自身觅食的特点采用不同的更新方式，不同种群之间还存在相互学习和竞争关系。这种群体智能优化算法相较于其它优化算法具有种群多样性的特点，因此全局搜索能力较强[10]。但是在应用中发现，传统的鸡群优化算法在处理一些复杂的优化问题时效果不佳，无法找到全局最优解，且还会出现收敛速度慢的问题。

本文提出一种基于量子行为的鸡群优化算法，算法在鸡群的每次迭代过程中引入量子行为[11-12]，使得个体可以以一定的概率出现在整个搜索空间的任何位置，既保留了原始鸡群种群多样性的特性，又提高了种群全局搜索的能力。利用随机优化算法的全局收敛性判别准则证明了本文所提算法是全局收敛的。通过对测试函数的实验分析可知，QCSO相对于鸡群算法以及一些传统的优化算法优化效果更好、精度更高。

2 基本鸡群优化算法

公鸡个体的位置更新公式如下

(1)

式中，Randn(0，σ2)服从正态分布，均值为0，方差为σ2。母鸡的位置更新公式如下

(2)

式中，r1是与第i只母鸡相关联的公鸡个体；r2为公鸡或者母鸡个体，且r1≠r2；S1、S2是(0，1)之间的常数。小鸡的位置更新公式如下

(3)

式中，m为与第i只小鸡相关联的母鸡，FL(FL∈[0，2])表示小鸡跟随母鸡觅食的系数。

3 基于量子行为的鸡群优化算法设计

3.1 QCSO算法的思想来源

生物群体具有基本的特点，就是群体内的所有个体的差异性不能无限大，也就是说个体与个体之间具有一定的相似性。这一特点表明，群体中的个体与个体之间存在着相互学习的特点，说明群体具有保留和记忆当前个体最优值的能力。但是个体之间也一定会存在着差异性，正因为这种差异性才导致了群体具有一定的创造性。这种群体的特性统一用聚集性来表示。

聚集性在力学中用粒子的束缚态来描述，产生束缚态的原因是粒子运动的中心存在某种吸引势场。文献[8]中提到，在Pi(t)和G(t)之间存在一个学习倾向点(Learning Inclination Point，LIP)，在量子力场中成为吸引子，具体表示为

pi(t)=φi(t)Pi(t)+[1-φi(t)]Gi(t)

(4)

其中，φi(t)～U(0，1)，pi(t)表示粒子i的局部吸引子，Pi(t)表示粒子i的局部最优位置，Gi(t)表示种群的全局最优位置。

量子空间中的粒子无特定的运动轨迹，粒子可以出现在任何位置。因此，量子模型的随机性更大，这就类似于高等智能群体在做某种决定时会出现丰富的可能性。

经典力学与量子空间不同，实际中的鸡群算法寻优是通过个体的迭代公式进行的，但在量子空间中，所有的个体都是用粒子表示，粒子之间没有差别，所有的粒子运动都是用波函数ψ来确定。

3.2 QCSO算法原理描述

本文提出了基于量子行为的鸡群优化算法。算法的主要设计思想是：在鸡群位置更新后，统计个体最好位置pbest和群体最好位置gbest，并建立量子空间下鸡群个体的概率密度函数，由蒙特卡洛随机采样完成pbest的更新，实现极值点附近的局部搜索。由文献[9]可知，需要在个体的运动中心建立一个量子化的势场，从而在搜索过程中粒子以一定的概率密度搜索量子空间中的每个位置。

现假设第t次迭代时整个鸡群表示为

Pop={x1(t)，x2(t)，…，xN(t)}

(5)

其中，个体为

(6)

个体最好位置表示为

(7)

全局最好位置表示为

G(t)=[G1(t)，G2(t)，…，GD(t)]

(8)

在吸引子的每一维上建设一个基于δ势阱模型的吸引势场，其势能函数为

V(Y)=-γδ(Y)

(9)

其中，Y=x-p表示个体与吸引子之间的距离，由动力学方程中的Schrodinger方程可得

(10)

其中，ћ是普朗克常数，m是个体质量，方程解为

(11)

其中，L=ћ2/mγ，为δ势阱特征长度。相应的概率密度函数表示为

(12)

量子空间中用于描述粒子的波函数ψ(Y)仅仅给出了粒子出现在相对于p点概率密度函数Q(Y)，但在算法实际设计中，需要给出个体的具体位置。因此，采用蒙特卡洛模拟的方法测量个体位置，即在[0，1]取随机数u，然后令u=e-2|Y|/L，则Y可求得

(13)

又因为Y=x-p，则将其带入式(17)可推导出量子空间的粒子位置公式

(14)

(15)

其中α称为收缩-扩张系数，对参数α的控制线性减小的方式。

本文先根据鸡群个体的三种更新方式找到当前个体的最优位置，再采用下式再次更新获得个体最好位置。

(16)

以个体学习倾向点作为吸引子，使个体产生束缚，在吸引点附近进行搜索。采用平均最好位置来调节δ势阱特征长度，使得所有粒子都参与了全局搜索。并且通过平均最好位置交换了个体之间的位置信息，提高了群体协同工作的能力，最终当粒子都靠近gbest后，再进行局部搜索。

3.3 QCSO算法步骤

步骤1：参数初始化。鸡群规模N，算法最大迭代次数M，个体维度D，鸡群更新频率G，公鸡、母鸡、小鸡所占的百分比p1、p2、p3，妈妈母鸡占母鸡群的百分比p4，跟随系数FL，收缩-扩张系数α。

步骤2：种群初始化。置t=0，在问题空间中初始化鸡群中每个个体的当前位置xi(0)，并设个体最好位置Pi(0)=xi(0)。

步骤3：计算鸡群的平均最好位置。

步骤4：对于鸡群中的每个个体i(1≤i≤N)，执行步骤5～8。

步骤5：计算个体i的当前位置xi(t)适应度值，并于前一次迭代Pi(t-1)的适应度值进行比较，如果xi(t)的适应度值优于Pi(t-1)的适应度值，则置Pi(t)=xi(t)；否则，Pi(t)=Pi(t-1)。

步骤6：对于个体i，将Pi(t)的适应度值与全局最优位置G(t-1)的适应度值进行比较，若优于G(t-1)的适应度值，则置G(t)=Pi(t)；否则，G(t)=G(t-1)。

步骤7：根据式(4)得到一个吸引点的位置。

步骤8：根据式(16)计算个体的新的位置。

步骤9：若算法的终止条件不满足，则置t=t+1，返回步骤3；否则算法结束。

4 算法收敛性分析

QCSO本质上还是属于随机搜索算法[14]，因此本文是在随机搜索算法收敛性准则的框架下研究QCSO算法的全局收敛性。

4.1 随机搜索算法的全局收敛准则

定义1 对于最小化问题给定目标函数f，它是从RD到R的映射，解空间S是RD的一个子集。在S中找一个点x，它能够使函数f的值最小。

假设1：f(H(x，ξ))≤f(x)，并且如果ξ∈S则

f(H(x，ξ))≤f(ξ)

(17)

其中H是搜索空间中产生一个解的函数，H应该满足产生的新的解要优于当前解。ξ是根据相应的算法得到的解空间S中的一系列可行解。

假设2：对于S的任意Borel子集A，若其测度v[A]>0，则有

(18)

其中，μt[A]是由测度μt达到A的概率。式(24)表明对于测度为v的Borel子集A，如果采用随机采样的方法，那么它重复错过A的概率一定为0。

4.2 QCSO算法的全局收敛性

若将QCSO置于全局随机搜索算法的框架中研究其全局收敛性，则要证明QCSO算法满足假设1和假设2。下面是具体的证明过程。

首先，证明QCSO算法满足假设1。

证明：由第2节中对QCSO算法的描述可以得出，函数H在QCSO算法中的描述可以定义为

(19)

其中，g(xi，t)由式(4)和(16)确定。将xi(t)用xi，t来表示，t即为算法的迭代次数。

(20)

Gt表示全局最优位置，根据QCSO算法的定义，QCSO算法每次迭代都是保留了种群中的最优解，即序列Gt处的适应度值是单调递减的。因此H的定义是满足假设1的。

然后，证明 QCSO算法满足假设2

证明：通过以上叙述可知，在第t次迭代后，第i个个体的第d维的概率密度函数为

(21)

个体i的概率密度函数可以表示为

(22)

定义μi，t对应于D维双指数概率分布。因此，对于S的任意Borel子集A，当满足v[A]>0时，可以得到

(23)

(24)

其中，Mt是分布μt的支撑。由μt产生的对A的概率测度可以由下式计算得到

(25)

通过式(25)，可得

0<μn[A]<1，n=1，2，…

(26)

因此可得

(27)

故QCSO满足假设2。

综上所述，QCSO算法满足全局收敛算法的两个假设，因此根据定理1可知QCSO算法是一个全局收敛性算法。

5 QCSO算法性能验证

上述过程主要是证明了本文提出的QCSO算法是全局收敛的，下面则要证明这种算法具有很好的寻优能力。本文选取4个标准测试函数来对QCSO算法进行测试，并与CSO、PSO以及QPSO进行对比。将最大迭代次数设置为1000次，种群规模同为100，种群维度设置为30。

为了分析QCSO的寻优能力，采用QCSO、CSO、PSO和QPSO算法分别对于这4个函数重复进行30次运算并取平均值。CCSO的参数设置为：M=1000，N=100，D=30，G=10，p1=0.15，p2=0.7，p3=1-p1-p2，p4=0.5，FL=rand(0.4，0.9)，α采用线性递减的方式，如式(20)所示。

下面主要介绍QCSO算法与传统的一些优化算法的性能比较。表1列出了各函数的寻优结果，各函数的理论最优值均为0。图1～4比较说明了四种算法的收敛速度以及迭代的适应度值大小。

表1 QCSO算法与其它优化算法的结果比较

图1 Sphere函数

图2 Rosenbrock函数

图3 Rastrigin函数

图4 Griewank函数

由表1可知，本文提出的QCSO算法相较于PSO、CSO、QPSO算法性能上有很大提升，对测试函数的求解精度也比其它三种算法高很多。这主要是因为，CSO算法本身的种群多样性使得其性能优于PSO算法，而引入了量子行为后又可以使个体在保持原有最优解的基础之上以大概率去搜索当前最优解附近的位置，以小概率搜索整个可搜索空间中的任意位置，避免了陷入局部最优。当然，QCSO算法的收敛时间相比于其它算法要长，这主要是因为引入量子行为后存在粒子重构的问题，因此耗时较长，但是更容易跳出局部最优解。通过测试函数的验证结果可以看出，对于各种复杂的函数，QCSO都能有很好的求解结果。从图1～4可以看出，PSO算法收敛速度虽然最快，但是其精度不高，本文提出的QCSO算法无论在寻优精度上还是收敛速度上都要优于一些传统的优化算法。

6 结论

本文将量子行为应用到CSO算法中，提出了QCSO算法，通过在随机搜索的框架下证明了本文提出了QCSO算法是全局收敛的。该算法在保留了CSO算法的种群多样性的优势的基础上提高了CSO的寻优精度，解决了CSO易陷入局部最优解的问题。

在每次迭代过程中引入量子行为，使得个体以大概率在当前最优解的附近再次进行搜索，为了跳出局部解粒子又以小概率进行整个量子空间的搜索。引入量子行为之后，不但有利于跳出局部解，还有利于提高收敛速度。最后，利用4个基本测试函数在相同条件下对四种优化算法进行仿真验证，通过对寻优结果的对比分析，本文所提的算法QCSO相对于其它算法具有更大的优势。