基于线性递减权值更新的鸡群算法

李春红， 陆安江， 邵丽萍

(贵州大学 大数据与信息工程学院， 贵阳 550025)

0 引 言

随着人工智能神经网络的不断发展，各类算法也相继陆续涌现出来。如遗传算法、模拟蝙蝠回声定位行为提出的蝙蝠算法、差分进化算法、狼群算法等[1-2]。这些算法被广泛应用于各个方面，如求函数最优解、减速器设计、最优路径规划问题等[3-5]。

鸡群算法是由中国学者孟献兵于2014年提出来[6-7]。该算法模拟了鸡群的觅食行为，对鸡群中存在的等级制度和行为进行了数学分析[8-9]。在此基础上，韩斐斐等人[10]提出了一种全局优化的改进鸡群算法，有效地提升了算法的收敛速度。吴定会等人[8，11]对鸡群算法的收敛性进行了马尔科夫链的分析，建立了Markov链数学分析模型。也有学者用鸡群算法来解决神经网络方面的问题。本文针对鸡群算法容易陷入局部最优和收敛较慢的问题提出了一种改进型的算法[12-14]。并用6个基准函数来测试，再和目前的3种智能算法进行比较，以此来测试改进的鸡群算法的有效性。实验表明该改进型算法更容易收敛[15]。

1 基本的CSO算法

鸡群算法(CSO)是受到已有群体智能算法的启发而提出的一种模拟鸡群生活习性，抽象化得出的新型群体智能算法。在实际生活中，鸡群中存在着竞争关系，同时又存在着很严格的等级制度。鸡群中每一个体所具有的优势性能通过其所在位置对应的目标函数适应值来表示，也是待优化问题的最优解。按照鸡群中适应度值的不同，将每个鸡群都划分有公鸡、母鸡和小鸡三个等级。适应度最高的规定为公鸡，适应度最低的规定为小鸡，其余的鸡规定为母鸡。整个鸡群中因为公鸡起着领导作用，母鸡会跟着公鸡觅食。相应的公鸡在鸡群的觅食竞争中具有最大的优势，母鸡其次，而小鸡处在最不利的位置，所以小鸡需要跟随与其有母亲关系的母鸡一起生活，母鸡妈妈对其加以保护，以保证小鸡能正常生活。

设觅食空间为D维，种群规模为pop，其中公鸡数量为NR,母鸡数量为HN，小鸡数量为CN。这里给出算法设计的研究表述如下。

(1)公鸡的位置更新。在公鸡的觅食行为中，第i只公鸡在第j维空间中经过t次觅食后的位置为xtij(i=1,2,3…,NR;j=1,2,3,…,D)，则经过t+1次觅食后的位置更新为：

xt+1ij=xtij*(1+Rand(0,σ2)),

(1)

k∈[1,N],k≠i.

(2)

其中，Rand(0，σ2)表示均值为0，方差为σ2的高斯分布；ε表示一个很小的平衡常数；k表示所有公鸡中除去第i个个体外的任意一个个体。

(2)母鸡的位置更新。在母鸡的觅食行为中，第i只母鸡在第j维空间中经过t次觅食后的位置为xij(i=1,2,3…,HN;j=1,2,3…,D)，则经过t+1次觅食后的位置更新为：

xt+1ij=xtij+S1*Rand*(xtr1,j+xtij)+

S2*(xtr2, j-xtij),

(3)

S1=exp((fi-fr1)/(abs(fi)+ε)),

(4)

S2=exp(fr2-fi),

(5)

其中，Rand∈(0,1)，r1是第i只母鸡所在子群中的公鸡个体，r2是从公鸡和母鸡中随机选择的个体，且r1≠r2。显然，fi>fr1,fi>fr2，因此公式中S2<1

(3)小鸡位置更新。在小鸡的觅食行为中，小鸡跟随自己的母鸡搜索食物，小鸡的位置更新公式如下：

xt+1ij=xtij+FL*(xtm,j-xtij).

(6)

其中，xim, j(m∈[1,N])表示第i只小鸡跟随的母鸡，FL表示小鸡跟随母鸡寻找食物时的跟随系数，由于个体之间的差异性，小鸡的跟随系数FL为[0,2]范围内选择的随机数。

2 改进的CSO算法

2.1 引入权值公式

改进型的鸡群算法主要是在公鸡、母鸡、小鸡的位置更新公式中引入了权值，在母鸡与小鸡的位置更新公式中还引入了向自己群体里最优的个体学习的参数，这不仅可以解决收敛速度慢、易陷入局部最优问题，还可以使公式以更快的速度达到全局最优。权值更新公式如下：

(7)

对权值更新公式用Matlab2014(a)进行仿真分析，仿真分析结果如图1所示。

图1 权值变化趋势

由图1可以看到，此方法的权值变化范围在0.6～0.9之间。最大惯性权值wmax取0.9，最小惯性权值wmin取0.6时算法的性能最好，t表示当前迭代次数，M表示最大迭代次数。

2.2 改进后鸡群的位置更新公式

在整个鸡群中公鸡的适应度值是最高的，已经是各个群体中的最优个体，因此在公鸡的位置更新公式中只引入了线性递减惯性权值来提高算法的搜索能力。改进的公式如下：

xt+1ij=ω*xtij*(1+Rand(0,σ2))，

(8)

母鸡数量在整个鸡群中是最多的，所以在寻优精度和速度上发挥重要作用。母鸡作为鸡群中的纽带，所以起着信息传递的作用。母鸡的适应度值在群体中不高，所以在母鸡的位置更新公式中引入惯性权值因子和向群体里面最优的个体学习，其中R是取(0，1)之间的随机数。改进公式如下：

xt+1ij=ω*xtij+S1*Rand*(xtr1,j-xtij)+S2*

Rand*(xtr2,j-xtij)+R*(xtbest,j-xtij)，

(9)

小鸡在整个鸡群中适应度值是最低的，学习的空间很大，既可以向公鸡学习，也可以向母鸡学习，所以在小鸡的位置更新公式中既引入了惯性权值因子，也引入了向全局最优个体学习的因子，R是取(0,1)之间的随机数，改进的公式如下：

xt+1ij=ω*xtij+FL*(xtm, j-xtij)+R*(xtbest, j-xtij).

(10)

2.3 算法流程

改进集群算法设计流程如图2所示。由图2可知，改进后的算法流程表述详见如下。

Step 1鸡群规模假设为N，搜索空间维数为D，最大迭代次数为M。

Step 2计算N个个体的适应度值，并设置t=0。

Step 3如果mod(t,G)=0，按照个体适应度值的大小将整个鸡群中的个体进行排序，并确定整个鸡群的等级制度。

Step 4将整个鸡群分为不同的组，母鸡随机选择要跟随的公鸡，并确定小鸡和母鸡在一组中的关系。

Step 5更新各个鸡群的位置。

Step 6计算个体的适应度值。

Step 7更新个体最优和全局最优。

Step 8置t=t+1，若达到最终条件，则转

Step 9,否则，转到Step 3。

Step 9输出全局最优位置。

图2 改进鸡群算法流程图

3 数值分析与实验

3.1 测试函数和实验设置

为了验证改进鸡群算法(ACSO)的有效性，本文选取了6个标准的测试函数进行仿真实验，并与基本的鸡群算法(CSO)、粒子群算法(PSO)、差分算法(DE)进行对比分析。测试函数的基本信息见表1，测试函数的参数设置见表2。

表1 基本测试函数

表2 各算法参数的设置

通过这6个基准函数的不同特点，可以充分考察改进的鸡群算法对不同类型问题的优化性能。这几个函数可以分为单峰函数(F1),多峰函数(F2～F6)，选取这些函数可以考察改进算法的收敛速度、收敛精度、有效性以及全局搜索能力。

3.2 结果分析

在Matlab2014(a)的环境下，对3.1节中表1、表2中的函数和算法进行仿真实验。仿真实验测试结果见图3～图8。

图3 Sphere测试函数

图4 Ackley测试函数

图5 Griewank测试函数

图6 Rastrigin测试函数

图7 Zakharov测试函数

图8 Shekel测试函数

通过上述结果可以看出，对于Sphere函数来说，ACSO明显优于其余三种算法，在迭代次数到150次左右的时候就已经达到最优值。对于Ackley函数来说，在迭代次数到100左右即达到最优值，而且要胜过其余三种算法，对于Griewank函数来说，同样明显优于其余三种算法。对于Rastrigin函数来说，改进的ACSO稍微优于CSO算法，但是要显著优于PSO、DE两种算法。对于Zakharov测试函数来说，在迭代初期并没有其他算法出色，但是到100代左右则明显优于其余测试函数。对于Shekel测试函数，虽然起始并未优于DE和PSO算法，但是到迭代后期达到了最优值。总而言之，ACSO算法在函数寻优过程中，优于传统的鸡群算法、粒子群算法和差分算法。

4 结束语

通过对基本鸡群算法的改进，可以得到一种更好的鸡群算法。改进的鸡群算法在保证种群多样性的情况下，引入线性递减权值，在母鸡和小鸡的更新公式中加入向最优个体学习的因子。如此更新后，通过6个测试函数进行实验，与标准粒子群算法、差分算法、标准鸡群算法三种基本算法做比较，由仿真实验结果可以得到，在其收敛速度和迭代次数方面都有改善。