基于网格的改进序列鸡群算法

张航　杨靖

摘要：针对传统鸡群优化算法存在求解精度偏低、局部搜索能力弱等问题，提出了一种改进的鸡群优化算法。改进算法选择利用动态簇解决单一工作节点能力有限问题，提出一种基于网格的序列鸡群算法，优化标准鸡群算法的种群分组更新机制，仿真和实验结果表明该算法相比传统算法具有定位精度高、收敛速度快、实时性好等优点。

关键词：无线传感器网络;鸡群算法;动态簇;定位精度

【Abstract】Aimingattheproblemsoflowaccuracyandweaklocalsearchabilityintraditionalchickenflockoptimizationalgorithms，animprovedchickenflockoptimizationalgorithmisproposed.Improvedalgorithmselectionusesdynamicclusterstosolvetheproblemoflimitedcapacityofasingleworkingnode.Agrid-basedsequentialchickenflockalgorithmisproposedtooptimizethepopulationgroupingupdatemechanismofthestandardchickenflockalgorithm.Simulationandexperimentalresultsshowthatcomparedwithtraditionalalgorithms，thisalgorithmhastheadvantagesofhighpositioningaccuracy，fastconvergencespeedandgoodreal-timeperformance.

【Keywords】wirelesssensornetwork;chickenswarmalgorithm;dynamiccluster;positioningaccuracy

作者簡介：张航（1996-），男，硕士研究生，主要研究方向：物联网技术与应用;杨靖（1973-），男，博士，教授，主要研究方向：物联网技术与应用。

0引言

群智能算法作为一种新的优化技术，是从鸟类、鱼类等生物群的行为研究中获得的。这是一种受自然生物群智能现象启发的智能方法，并具有自组织、自学习、自适应和内部并行的特点。与传统数学方法相比，“适者生存”思想采用通用、智能的方法更容易解决问题。这些算法，如粒子群优化（PSO）[1]、蚁群优化（ACO）[2]、人工蜂群算法（ABC）[3]、人工鱼群算法（AFSA）[4]、蝙蝠算法（BA）[5]等，使用工程、管理和计算科学等领域的优化又有了新的优化技术。文献[6]采用改进的人工鱼群算法对系统的硬件和软件进行了划分。文献[7]采用粒子群优化算法对热电目标进行动态跟踪。文献[8]模拟电路测试点优化通过动态蚁群算法实现。智能算法在不断更新，包括磷虾群优化算法[9]、混沌果蝇算法[10]、蜘蛛算法[11]。这些都是基于大自然生物的生命周期表现的规律进行总结而得到的新兴算法。

2014年，Meng等人[12]共同提出鸡群优化算法（CSO）来模拟鸡群的等级和行为。一只雄鸡和多只母鸡组成一个亚组，多个亚组构成一个鸡群，各种鸡移动的规律是不同的。各个鸡群间在提前设置的规定下存在一定竞争。CSO优化算法是针对全局的，和其他优化算法如差分、蝙蝠等算法相比，在收敛准确性和速度上的优势都十分显著，然而传统鸡群算法在局部收敛和抗干扰方面还存在很多不足之处。

本文利用动态簇解决单一工作节点能力有限问题，提出一种基于网格的序列鸡群算法，优化标准鸡群算法的种群分组更新机制，同时还引入了新的小鸡学习公式。仿真和实验结果表明该算法具有定位精度高、收敛速度快、实时性好等优点。

1鸡群算法

1.1算法简介

2014年，Meng等人针对鸡寻觅食物的过程进行模仿，发现鸡群觅食的规律，并以此为基础推出CSO算法。关于鸡群觅食的规律，主要可概述为如下4点：

（1）每个鸡群都由多个小组构成，领导者是雄鸡，组中还有小鸡和雌鸡，每个小组都有对应的领导者。

（2）鸡群中雄鸡、雌鸡和小鸡的身份是由适应度作为标准进行区分的，雄鸡适应度最强，小鸡适应性最弱，母鸡分组原则实施随机分配。

（3）鸡群中雌鸡和雏鸡的母子关系保持，只是每隔一段时间这种关系就会按照特定的等级秩序和规则重新分配。

（4）雄鸡外出觅食时，雌鸡会跟着一同去觅食，而雏鸡会在雌鸡附近寻觅食物。具有较高适应度值的鸡在争夺食物的过程中将占有优势。

1.2位置更新方法

鸡群中雄鸡、雌鸡和雏鸡身份等级的划分是按照适应度强弱实现的，实验后得知雏鸡和雄鸡占据比例都是20%，雌鸡占据比例高达60%，经过该算法进行优化，效果较为理想，雄鸡、雌鸡和雏鸡位置都会根据各自的位置更新算法完成更新。研究内容详述如下。

2.2仿真流程

基于网格，对目标轨迹进行侦测。首先，对环境及相关参数初始化。研究中假设模拟的观测区域是一个20×20m2的正方形区域，分成了20×20个正方形网格，每个网格的区域的面积为1m2。在这个区域内随机分布了60个声波幅度传感器节点，假设跟踪目标在这个区域内的最大移动速度为2m/s，假设声波的传播范围为米，设置传感器节点的门限值为4，在侦测区域内初始目标轨迹。每次节点侦测完目标后会将信息传递给下一个节点，循环直到目标超出侦测范围为止。仿真流程如图1所示。

图2～图4中，黄色圆点表示侦测区域内的传感器节点，白色小叉表示目标的实际运动轨迹。颜色的深浅比则表示了信任度的值，颜色越深就表示目标在该区域出现的可能性越高。

3算法仿真

3.1精確定位阶段

这里，研究拟给出定位步骤具体如下。

Step1100个传感器节点（包括未知节点和信标节点）随机分布在立方体空间中，空间是边长为50m的正方体。

Step2信标节点将信号强度数值传递给未知节点，未知节点将其转变成距离值。

Step3对第n个位置节点坐标进行计算，该节点接收m个信号，如果m值是0，未知节点不能捕获则跳转到Step7。如果m取值在0～4之间，坐标计算利用质心算法完成，然后跳转到Step7。如果m取值大于等于4，那么继续Step4。

Step4将m个信标节点按每四个分成一组，组数为k，并且多个组并非出于相同平面。

Step5利用三面节点估计法计算出k个坐标值，即：（x1，y1，z1）、…、（xk，yk，zk）。

Step6传统鸡群算法完成优化。

Step7如果未知节点数量为n，则算法终止;如果未知节点数量不为n，则n=n+1回转到Step3继续执行算法。

3.2仿真分析

节点随机分布在100m×100m的平面，分别对比传统鸡群算法与改进鸡群算法在通讯半径、锚节点占比以及总节点数三个方面对定位精度的影响，依次参见图5～图7。

由图5～图7可以看出，在通信半径从15变化到35之间，改进的鸡群算法相较于传统鸡群算法定位精度提高了15%;在锚节点的个数从15变化到40之间，改进鸡群算法的定位精度提高了15%左右;当总节点数目从100变化到200之间，改进鸡群算法的总体定位精度提高了约14%。故可以得出，改进鸡群算法相较于传统鸡群算法在不同的通信半径、锚节点数、总节点数目等情况下，定位精度都有了明显改善。

4结束语

文章以网格法和鸡群算法为基础提出的优化算法可以很好地解决传感器定位误差偏大的不足。该算法利用动态簇解决单一工作节点能力有限问题，优化了标准鸡群算法的种群分组更新机制，全面提高了定位精度。经过仿真验证文中提出的改进算法可以确保较好的收敛性，而且定位精度也有了明显改善，实现上也较为简单。不过密度高的障碍物环境并没有考虑进来，所以还需要在障碍物数量随意设定的状态下对算法做进一步的优化。

参考文献

[1]KENNEDYJ，EBERHARTR.Particleswarmoptimization[C]//ProceedingsofIEEEInternationalConferenceonNeuralNetworks.Perth，Australia：IEEEPress，1995：1942-1948.

[2]DORIGOM，MANIEZZOV，COLORNIA.Antsystem：optimizationbyacolonyofcooperatingagents[J].IEEETransactionsonSystemsManandCybernetics，PartB：Cybernetics，1996，26（1）：29-41.

[3]KarabogaD.Anideabasedonhoneybeeswarmfornumericaloptimization[R].Kayseri：ErciyesUniversity，2005.

[4]LIXiaolei，SHAOZhijiang，QIANJixin.Anoptimizingmethodbasedonautonomousanimats：fish-swarmalgorithm[J].SystemsEngineeringTheoryandPractice，2002，22（11）：32-38.

[5]YANGXS.Anewmetaheuristicbat-inspiredalgorithm[C]//NatureInspiredCooperativeStrategiesforOptimization（NICSO2010）.Berlin：Springer，2010，284：65-74.

[6]全浩军，张涛，郭继昌.基于改进人工鱼群算法的软硬件划分方法[J].天津大学学报：自然科学与工程技术版，2013，46（10）：923-928.

[7]王泽兵，杨卫，秦丽.基于粒子群算法的动态热释电目标跟踪[J].光学学报，2014，34（10）：35-41.

[8]罗慧，蹇兴亮，卢伟.基于动态蚁群算法的模拟电路最优测点选择[J].仪器仪表学报，2014，35（10）：2231-2237.

[9]GANDOMIAH，ALAVIAH.Krillherd：Anewbio-inspiredoptimizationalgorithm[J].CommunicationsinNonlinearScienceandNumericalSimulation，2012，17（12）：4831-4845.

[10]LEIX，DUM，XUJ，etal.Chaoticfruitflyoptimizationalgorithm[C]//5thInternationalConferenceonSwarmIntelligence.Hefei：SpringerInternationalPublishing，2014：74-85.

[11]CUEVASE，CIENFUEGOSM，ZALDVARD，etal.Aswarmoptimizationalgorithminspiredinthebehaviorofthesocial-spider[J].ExpertSystemswithApplications，2013，40（16）：6374-6384.

[12]MENGXianbing，LIUYu，GAOXiaozhi，etal.Anewbio-inspiredalgorithm：Chickenswarmoptimization[M]//TANY，SHIY，COELLOCAC.Advancesinswarmintelligence.ICSI2014.LectureNotesinComputerScience.Cham：Springer，2014：86-94.