耗散结构和差分变异混合的鸡群算法

韩萌

(西安电子科技大学 数学与统计学院， 陕西 西安 710126)

0 引 言

高维优化是指对维数超过100的函数的优化，科学技术和工程实际中有许多高维优化问题[1]，由于其维数较大，传统优化方法面临诸多局限. 为此，国内外出现了大量群智能优化算法[2](swarm intelligence algorithm，SIA)以解决这类问题. 谭皓等[3]将基本粒子群算法和蚁群算法相结合，提出了一种混合的粒子群算法，用以解决高维复杂函数的优化问题，并取得了良好的效果；刘昌芬等[4]将广义的逆向学习方法应用于差分进化算法，提出了一种广义逆向学习方法的自适应差分算法，该算法在处理高维优化问题时可有效提高差分进化算法的寻优精度；盛孟龙等[5]将自适应和交叉变换的方法引入到蝙蝠算法中，在解决高维复杂问题时取得了比较好的结果；龙文等[6]提出了一种基于混沌和精英反向学习的混合灰狼优化算法来解决高维优化问题.

鸡群算法(chicken swarm optimization，CSO)是由MENG 等[7]于2014年提出的一种群智能优化算法. 该算法具有原理简单、易于实现、全局搜索能力较强等优点，被广泛应用于多种工程优化问题： 如非线性约束优化计算[8]、非线性系统的参数估计[9-10]和多分类器系数优化[11]等. 但在求解高维复杂优化问题时，鸡群算法和其他群智能优化算法一样，存在早熟收敛和收敛精度低等缺点，因此，一些学者提出了改进方法.QU等[12]提出了一种精英反向学习的鸡群优化算法，采用自适应t分布代替雄鸡群体中的高斯分布，并将精英反向学习引入雌鸡群体中；孔飞等[13]和WU等[14]通过在小鸡位置更新公式中加入向自身所在子群的雄鸡学习部分，提出了一种改进的鸡群算法，此算法在求解高维优化问题时更容易搜索到全局最优解；李振壁等[15]将模拟退火的思想引入鸡群算法. 以上改进策略有效提高了算法的收敛速度和寻优精度，但在求解高维问题上仍存在早熟及寻优效果差等问题.

为了克服鸡群算法的上述缺陷，本文提出了一种将耗散结构和差分变异混合的鸡群算法(hybrid chicken swarm algorithm with dissipative structure and differential mutation，DMCSO). 通过对多个典型的标准测试函数的寻优仿真表明，DMCSO算法具有较强的跳出局部最优解的能力，且可明显改善算法的收敛速度和寻优精度.

1 基本鸡群算法

鸡群算法是模拟鸡群等级制度和鸡群搜索食物行为的一种随机优化算法. 在描述该算法之前先做4个假设：

假设1整个鸡群有若干子群，子群数目由雄鸡个数确定，即每个雄鸡对应一个子群，每个子群中还包括一些雌鸡和小鸡.

假设2根据适应度值的大小将整个鸡群分为雄鸡、雌鸡和小鸡3种类别. 雄鸡由适应度值较好的若干个体组成，适应度值较差的若干个体作为小鸡，其他个体作为雌鸡. 每只雄鸡作为各自子群的领头鸡，雌鸡随机选择要跟随的雄鸡，雌鸡和小鸡的母子关系也是随机建立的.

假设3鸡群中的等级制度、支配关系和母子关系进化G代后进行更新.

假设4每个子群中的雄鸡可以带领该子群的其他个体搜索食物，并且这些雄鸡可以阻止其他个体偷取自己已经发现的食物；小鸡追随自己所选择的妈妈雌鸡寻找食物；在食物竞争过程中，具有支配地位的个体更具有优势.

1.1 雄鸡位置更新

与适应度值差的雄鸡相比，适应度值好的雄鸡在食物竞争中更具优势，而且能够在更广泛的空间中寻找食物. 雄鸡位置更新公式如下：

(1)

式中randn(0,σ2)表示满足均值为0、标准差为σ2的高斯分布的随机数，为防止式中分母为0，ε为一个很小的常数，k为雄鸡中除去第i个个体外的任意一个个体.

1.2 雌鸡位置更新

雌鸡不仅跟随其所在子群的雄鸡寻找食物，而且可以随机偷取其他鸡发现的食物. 在食物竞争期间，适应度值高的雌鸡比适应度值低的雌鸡更具优势. 雌鸡更新公式如下：

(2)

其中，s1=exp((fi-fr1)/(|fi|+ε))，s2=exp(fr2-fi)，式中rand为[0,1]之间均匀分布的随机数，r1为第i个雌鸡所在子群中的雄鸡个体，r2是从鸡群的雄鸡和雌鸡中随机选择的任意个体，且r1≠r2.

1.3 小鸡位置更新

小鸡跟随自己的雌鸡寻找食物，小鸡的位置更新公式如下：

(3)

其中，m为第i只小鸡跟随的雌鸡，FL为跟随系数，取值范围为[0,2].

2 耗散结构和差分变异混合的鸡群算法(DMCSO)

2.1 耗散结构

由鸡群算法的原理可知，雄鸡作为鸡群中每个子群的领头鸡，带领鸡群搜索食物；雌鸡参考所在子群的雄鸡位置进行更新；小鸡参考跟随雌鸡的位置进行更新；由此可见，雌鸡和小鸡都依靠雄鸡的信息搜寻食物，雄鸡影响整个鸡群的搜索方向和搜索速度. 因此，当雄鸡陷入局部最优时，整个鸡群的寻优能力会受到影响.

耗散结构是指处在远离平衡态的开放系统，通过不断地与外界进行能量或物质交换，使原来的无序状态变成时间、空间或功能有序的状态[16]. XIE等[17]提出了一种耗散粒子群算法，首次实现了将耗散结构引入到粒子群算法中，在一定条件下通过将种群中个体的位置和速度重新扩散，为种群有效地补充有差异的新个体，增加种群多样性，从而提高算法的优化性能. 本文将耗散结构引入鸡群算法的雄鸡更新公式中，扩大雄鸡个体的搜索空间，增强算法的全局搜索能力，从而有效降低整个鸡群落入局部最优的风险.具体实现如下：

if (randxi=random(ld,ud)
end

(4)

式中cv为扩散因子，取值范围为[0,1]，xi表示当前个体的位置，random(ld,ud)表示随机生成的个体(ld和ud分别表示群体空间的上界和下界)，本文取cv=0.1[18-19].

2.2 差分变异

随着迭代次数的不断增加，鸡群算法在进化后期个体差异程度越来越小，种群多样性逐渐下降，尤其在处理高维时，算法容易过早收敛陷入局部最优，难以获得最优解. 本文将差分变异操作[20-21]引入至鸡群算法中，以增加种群多样性. 具体实现如下：

(5)

其中，G为种群更新代数；fbest(t)表示第t代的最优适应度值；H为随机选取种群规模10%～20%的个体数；本文取H=int(N*0.2)，int表示取整函数；其中a、b、c是从[1,N]中随机选取的3个个体，且a≠b≠c≠k，F为缩放比例因子，ε为早熟检验阀值，本文取δ=1.0×10-10.

如果连续进化G代数，群体中的最优适应度值无明显变化，则进行个体差分变异. 本文从鸡群中随机选择3个不同的个体xa、xb和xc，通过对差分矢量(xb-xc)进行缩放并与xa合并后对鸡群中随机选择的20%的个体进行差分变异操作.F的作用是对差分矢量(xb-xc)进行缩放，以确定当前个体搜索最优解的范围，从而生成新的变异个体. 当F采用较大值时，算法可以在较大范围内进行搜索，但其收敛速度较慢；当F采用较小值时，虽然搜索较快，但易收敛到非最优解. 为此，提出一种随机的缩放因子：

(6)

其中，M表示最大迭代次数，t为当前迭代次数，rand为[0,1]之间均匀分布的随机数，由文献[22]可知，一般情况下，F的取值范围为[0.2,0.9].图1为缩放因子F随迭代次数的变化曲线.

图1 随机缩放因子Fig.1 Random scale factor

从图1中可以看出，rand的加入可以使个体在进化过程中有机会取得较小或较大的缩放因子，使得本算法可以更加灵活地调节局部和全局搜索能力.

2.3 算法的具体步骤

步骤1初始化参数. 鸡群规模为N，鸡群搜索空间的维数为D，种群更新代数G=10[13]，雄鸡个体所占比例为20%，雌鸡个体(包括妈妈雌鸡)所占的比例为60%，小鸡个体所占比例为20%，妈妈雌鸡所占的比例为10%(占雌鸡个数)，最大迭代次数为M，早熟检验阀值δ.

步骤2初始化种群，置t=1，设置适应度函数，计算鸡群中每个个体的适应度值，并初始化算法的个体和全局最优位置.

步骤3若满足mod(t,G)=1，根据个体的适应度值对鸡群中所有个体进行排序，按照假设2对鸡群进行等级划分，根据雄鸡个数确定子群数目，并随机建立雌鸡和小鸡的母子关系.

步骤4鸡群中各雄鸡按照式(1)和(4)更新位置，根据式(2)更新雌鸡位置，按式(3)更新小鸡位置.

步骤5更新鸡群当前的个体最优位置和全局最优位置.

步骤6早熟检验跳出局部最优. 在种群中随机选择一部分个体利用式(5)和(6)进行变异操作，并更新个体最优.

步骤7计算各个体的适应度值，重新进行适应度值排序，按照步骤3重新建立鸡群等级制度，重新对鸡群进行搜索分组.

步骤8置t=t+1，若未达到最大迭代次数则转步骤3；否则继续.

步骤9输出最优解.

为进一步理解DMCSO算法的工作原理，图2给出了其具体操作流程.

图2 DMCSO算法流程图Fig.2 Flow chart of DMCSO algorithm

3 仿真实验与分析

3.1 参数设置

为验证DMCSO算法的性能，选取18个标准的测试函数与基本鸡群算法[7](CSO)、粒子群算法[23](particle swarm optimization，PSO)、蝙蝠算法[24](bat algorithm，BA)和差分进化算法[25](differential evolution algorithm，DE)进行仿真对比分析. 表1给出了这些测试函数的名称、表达式、空间搜索范围和理论最优值. 遵循公平原则，设定各算法初始种群为100，空间维数为100,200(测试表1前5个标准函数)，函数最大迭代次数为1 000，为避免单独运行给算法评价带来的误差，各算法均独立运行30次，其他参数说明详见表2.

表2 5种算法的相关参数

实验环境： 所有实验均在Intel(R) Xeon(R) CPU E5620 @ 2.40GHz、8.00GB内存、2.40GHz主频的计算机上进行，软件运行环境为 Matlab 2016a.

3.2 算法的性能分析

为充分评价DMCSO算法的优化性能，考虑以下几个评价准则： 1)算法寻优精度： 在有限的函数评价次数条件下，算法搜索到的最优适应度值. 2)算法的收敛速度： 算法在达到相同评价次数时，若适应度值较好，则算法收敛速度快. 3)稳定性： 即算法独立运行多次以后，各个算法所得到适应度值的方差.

表1 标准测试函数

3.2.1 混合策略的有效性

为验证2种不同策略混合后用于鸡群算法的有效性和可行性，选取表1前5个具有代表性的测试函数进行仿真实验，其中，f1和f5是单峰函数，用来测试算法的寻优精度；f2、f3、f4为多峰函数，用来验证算法逃离局部极值的能力. 将DMCSO算法与CSO、耗散机制的DCSO算法(CSO算法中引入耗散结构)及差分变异的MCSO算法(CSO算法中引入差分变异)进行比较. 求取4种算法各自在100维的情况下独立运行30次的平均值和标准差. 相关实验数据如表3所示.

函数f1(Sphere)是一种比较简单的单峰二次函数，较容易搜索到最优值. 从表3的数据中可以看出，对于函数f1，DMCSO、MCSO和DCSO算法的寻优精度均较CSO算法有所提高，且DMCSO算法寻优效果最好，较CSO算法提高了5个数量级，较DCSO算法提高了2个数量级，较MCSO算法提高了4个数量级. DMCSO算法稳定性更好.

复杂多峰函数f2(Rastrigin)、f3(Ackley)、f4(Griewank)有多个局部极值点，较难搜索到全局极小值. 从表3中可以看出，对于函数f2，MCSO算法的寻优精度略高于DMCSO算法，但DMCSO算法取得的优化结果显著优于CSO和DCSO算法. DMCSO算法搜索到了函数f3最好的优化结果. CSO和MCSO算法对函数f4的寻优结果相当，DMCSO算法取得的优化结果和标准差最好.

函数f5(Rosenbrock)是典型的单峰难优化函数，该函数全局极值点处在一个抛物线形的狭长峡谷底端，使得算法在搜索全局最优解时非常困难. 从表3的数据中可以看出，DMCSO算法无论是平均值还是方差在函数f5上取得的结果都明显优于其他算法.

以上分析说明： 相较于MCSO和DCSO算法，DMCSO算法不仅大幅度提高了算法的搜索精度，而且有效减小了算法陷入局部最优的可能.该实验结果充分表明了将2种策略混合后用于鸡群算法是有效和可行的.

3.2.2 算法寻优精度和稳定性比较

为验证DMCSO算法的收敛精度和稳定性，统计PSO、BA、DE、CSO和DMCSO 5种算法对表1中18种测试函数分别独立运行30次的最优适应度值、最差适应度值、平均适应度值和标准差，表4给出了函数f1～f18在100维时的实验数据，表5给出了函数f1～f5在200维时的实验数据.

1) 从表4的数据中可以看出，相较PSO、BA、DE和CSO 4种算法，无论是单峰函数f1还是多峰复杂函数f2、f3、f4，DMCSO算法均取得了较好的寻优效果. 对于难测函数f5、f6和f7，PSO、BA、DE和CSO 4种算法搜索到的优化结果均较差，但DMCSO算法搜索到了较好的优化结果，表现了较强的寻优能力.对于函数f8，DMCSO、CSO算法取得了较PSO、BA和DE 3种算法更好的寻优结果，虽然CSO算法搜索到了最好的最优适应度值，但DMCSO算法的平均适应度、标准差和最差适应度均优于CSO算法. 对于f9、f10、f113个单峰函数，除DMCSO算法外，其他算法取得的优化结果和理论最优解偏差圴较大，寻优精度较低. 对函数f12，DE、DMCSO和CSO算法分别取得了较好的结果，但DMCSO算法的寻优能力更强. 对于函数f13，BA算法的结果较好，DMCSO算法的优化结果和CSO算法的很接近，但DMCSO算法略优于CSO算法. PSO、BA、DE、CSO和DMCSO 5种算法对函数f14均有良好的寻优能力，且DMCSO算法搜索到了最好的优化结果. 对函数f15，DMCSO算法的寻优能力最强，BA和DE算法次之，PSO和CSO算法的优化结果较差. DMCSO和CSO算法对f16函数的搜索精度均较高，取得的优化结果高出PSO、BA、DE算法各10个数量级. 对f17、f18函数，DMCSO算法的寻优精度均高于其他算法，其最优值、平均值、标准差和最差值均较好.

表3 鸡群算法在不同策略下的优化结果

表4 函数f1～f18的测试结果(D=100)

(续表4)

表5 函数f1～f5测试结果(D=200)

从表5的测试数据中可以看出，在200维的情况下，DMCSO算法对函数f1～f5均取得了最好的最优值、平均值、标准差，而PSO、BA和DE 3种算法寻优较困难，均未获得全局最优值.

上述分析表明，相较其他算法，DMCSO算法具有较强的寻优能力，有效提高了解的质量和算法的收敛精度. 从表4和表5的数据中可以看出，DMCSO算法的寻优能力受维数的影响较小，而其余算法的进化能力随着维数的增加都有不同程度下降.

2) 从表4和表5的数据中可以看出，DMCSO算法较PSO、BA、DE和CSO 4种算法的标准差小，说明DMCSO算法稳定性更好.

3.2.3 算法收敛速度比较

对表1中的18个测试函数进行仿真模拟，图3(a)～(r)为CSO、PSO、BA、DE和DMCSO 5种算法求解各函数100维最优适应度值随迭代次数变化的收敛曲线，曲线横坐标表示进化代数，纵坐标表示适应度值.

从图3中可以看出，对大多数函数来说，PSO、BA和DE 3种算法，迭代一段时间后，寻优结果基本不再发生变化，陷入了局部最优无法跳出，取得的优化结果不太理想. CSO算法在部分函数上表现出较好的寻优能力，收敛速度也相对较高，但略逊DMCSO算法. 除函数f13外(对函数f13，在迭代次数小于50时，DMCSO算法的收敛速度更快、收敛精度也更高，但在迭代后期，BA算法的表现更加显著)，DMCSO算法对其他函数均有较强的寻优能力，均以较快的收敛速度搜索到了精度较高的适应度值. 因此，DMCSO算法相较于PSO、BA、DE和CSO 4种算法，收敛速度更快、搜索精度更高.

图3 函数f1～f18的收敛曲线Fig.3 Convergence curves comparison of functions f1～f18

4 结 论

针对鸡群算法在求解高维复杂优化问题中的一些弊端，本文将耗散结构、带有随机缩放因子的差分变异2种策略混合后用于鸡群算法，有效解决了鸡群算法在求解高维复杂问题时难度大、精度低、收敛速度慢的问题.通过与其他群智能算法对18个测试函数进行仿真对比，结果表明： DMCSO算法不仅较明显改善了算法的稳定性，而且其收敛速度和寻优精度得到了有效提高，充分证明了DMCSO算法的有效性和可行性. 当然，此算法也有其局限性： 算法对该扩散因子的设置比较敏感，参数未能实现自适应，仍然需要根据先验知识确定等.

参考文献(References)：

[1] RAHNAMAYAN S, WANG G G. Solving large scale optimization problems by opposition based differential evolution (ODE)[J].WSEASTransactionsonComputers, 2008, 7(10): 1792-1804.

[2] BEHESHTI Z, SHAMSUDDIN S M H. A review of population based metaheuristic algorithms[J].IntJAdvSoftComputAppl, 2013, 5(1): 1-35.

[3] 谭皓，沈春林，李锦. 混合粒子群算法在高维复杂函数寻优中的应用[J].系统工程与电子技术，2005， 27(8)： 1471-1474.

TAN H, SHEN C L, LI J. Hybrid particle swarm optimization algorithm for high-dimension complex functions[J].SystemsEngineeringandElectronics, 2005, 27(8): 1471-1574.

[4] 刘昌芬，韩红桂，乔俊飞，等. 广义逆向学习方法的自适应差分算法[J].智能系统学报，2015(1)： 131-137.

LIU C F, HAN H G, QIAO J F. Self-adaptive DE algorithm via generalized opposition based learning[J].CAAITransactionsonIntelligentSystem, 2015, 10(1): 131-137.

[5] 盛孟龙，贺兴时，王慧敏. 一种改进的自适应变异蝙蝠算法[J].计算机技术与发展，2014(10)： 131-134.

SHENG M L, HE X S, WANG H M. An improved algorithm for adaptive mutation bat[J].ComputerTechnologyandDevelopment, 2014(10): 131-134.

[6] 龙文，蔡绍洪，焦建军，等. 求解高维优化问题的混合灰狼优化算法[J].控制与决策，2016，31(11)： 1991-1997.

LONG W, CAI S H, JIAO J J, et al. Hybrid grey wolf optimization algorithm for high-dimensional opt-imization[J].ControlandDecision, 2016, 31(11): 1991-1997.

[7] MENG X, LIU Y, GAO X, et al. A new bio-inspired algorithm: chicken swarm optimization[C] //InternationalConferenceinSwarmIntelligence. Heidelberg: Springer International Publishing, 2014: 86-94.

[8] CHEN Y L, HE P L, ZHANG Y H. Combining penalty function with modified chicken swarm optimization for constrained optimization[J].AdvancesinIntelligentSystemsResearch, 2015, 126: 1899-1907.

[9] CHEN S, YANG R, YANG R, et al. A parameter estimation method for nonlinear systems based on improved boundary chicken swarm optimization[J].DiscreteDynamicsinNatureandSociety,2016,2016(15)： 1-11.

[10] CHEN S L, YAN R H. Parameter estimation for chaotic systems based on improved boundary chicken swarm optimization[C]//InternationalSymposiumonOptoelectronicTechnologyandApplication2016. Beijing: International Society for Optics and Photonics, 2016: 101571K-101571K-6.

[11] 洪杨，于凤芹.改进的鸡群算法并用于多分类器系数优化[J].计算机工程与应用，2017，53(9): 158-161.

HOMG Y, YU F Q. Improved chicken swarm optimization and its application in coefficients optimization of multi-classifier[J].ComputerEngineeringandApplications, 2017, 53(9): 158-161.

[12] QU C W, ZHAO S A, FU Y M, et al. Chicken swarm optimization based on elite opposition-Based learning[J].MathematicalProblemsinEngineering, 2017, 2017(11): 1-20.

[13] 孔飞，吴定会. 一种改进的鸡群算法[J].江南大学学报(自然科学版)，2015，14(6)： 681-688.

KONG F, WU D H. An improved chicken swarm optimization algorithm[J].JournalofJiangnanUniversity(NaturalScienceEdition), 2015, 14(6): 681-688.

[14] WU D, XU S, KONG F. Convergence analysis and improvement of chicken swarm optimization[J].IEEEAccess, 2016(4): 9400-9412.

[15] 李振璧，王康，姜媛媛. 基于模拟退火的改进鸡群优化算法[J].微电子学与计算机，2017，34(2)： 30-33.

LI Z B, WANG K, JIANG Y Y. The study of improved chicken swarm optimization algorithm based on simulated annealing[J].MicroelectronicsandComputer, 2017, 34(2): 30-33.

[16] 于惠，王洪国，庄波，等. 一种基于耗散理论的遗传算法及其应用[J].计算机工程与应用，2008，44(21)： 113-115.

YU H, WANG H G, ZHUANG B, et al. Genetic algorithm based on dissipative theory and it’s application[J].ComputerEngineeringandApplications, 2008, 44(21): 113-115.

[17] XIE X F, ZHANG W J, YANG Z L. Dissipative particle swarm optimization[C]//EvolutionaryComputation,2002.CEC’02.Proceedingsofthe2002Congresson.Piscataway: IEEE Computer Society, 2002: 1456-1461.

[18] 任小波，杨忠秀. 耗散粒子群算法的性能分析[J].计算机仿真，2010，27(2)： 204-207.

REN X B, YANG Z X. Performance analysis on dissipative particle swarm optimization[J].ComputerSimulation, 2010, 27(2): 204-207.

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

REN X B, YANG Z X. Dynamic diffusion particle swarm optimization[J].JournalofComputerApplications, 2010, 30(1): 159-161.

[20] 刘三阳，张晓伟. 混合差分变异策略[J].智能系统学报，2008，3(6)： 487-491.

LIU S Y, ZHANG X W. A hybrid strategy for differential variation[J].CAAITransactionsonIntelligentSystem, 2008, 3(6): 487-491.

[21] 高卫峰，刘三阳，姜飞，等. 混合人工蜂群算法[J].系统工程与电子技术，2011，33(5)： 1167-1170.

GAO W F, LIU S Y, JIANG F, et al. Hybrid artificial bee colony algorithm[J].SystemsEngineeringandElectronics, 2011, 33(5): 1167-1170.

[22] 袁俊刚，孙治国，曲广吉. 差异演化算法的数值模拟研究[J].系统仿真学报，2007，19(20)： 4646-4648.

YUNA J G, SUN Z G, QU G J. Simulation study of differential evolution[J].JournalofSystemSimulation, 2007, 19(2): 4646-4648.

[23] CLERC M, KENNEDY J. The particle swarm - explosion, stability, and convergence in a multidimensional complex space[J].EvolutionaryComputationIEEETransactionson, 2002, 6(1): 58-73.

[24] YANG X S.A new metaheuristic bat-inspired algorithm[C]//NatureInspiredCooperativeStrategiesforOptimization(NICSO2010). Heidelberg: Springer, 2010: 65-74.

[25] STORN R, PRICE K. Differential evolution-A simple and efficient heuristic for global optimization over continuous spaces[J].JournalofGlobalOptimization, 1997, 11(4): 341-359.