基于網(wǎng)格的改進序列雞群算法

張航　楊靖

摘要：針對傳統(tǒng)雞群優(yōu)化算法存在求解精度偏低、局部搜索能力弱等問題，提出了一種改進的雞群優(yōu)化算法。改進算法選擇利用動態(tài)簇解決單一工作節(jié)點能力有限問題，提出一種基于網(wǎng)格的序列雞群算法，優(yōu)化標準雞群算法的種群分組更新機制，仿真和實驗結(jié)果表明該算法相比傳統(tǒng)算法具有定位精度高、收斂速度快、實時性好等優(yōu)點。

關(guān)鍵詞：無線傳感器網(wǎng)絡;雞群算法;動態(tài)簇;定位精度

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

【Keywords】wirelesssensornetwork;chickenswarmalgorithm;dynamiccluster;positioningaccuracy

作者簡介：張航（1996-），男，碩士研究生，主要研究方向：物聯(lián)網(wǎng)技術(shù)與應用;楊靖（1973-），男，博士，教授，主要研究方向：物聯(lián)網(wǎng)技術(shù)與應用。

0引言

群智能算法作為一種新的優(yōu)化技術(shù)，是從鳥類、魚類等生物群的行為研究中獲得的。這是一種受自然生物群智能現(xiàn)象啟發(fā)的智能方法，并具有自組織、自學習、自適應和內(nèi)部并行的特點。與傳統(tǒng)數(shù)學方法相比，“適者生存”思想采用通用、智能的方法更容易解決問題。這些算法，如粒子群優(yōu)化（PSO）[1]、蟻群優(yōu)化（ACO）[2]、人工蜂群算法（ABC）[3]、人工魚群算法（AFSA）[4]、蝙蝠算法（BA）[5]等，使用工程、管理和計算科學等領域的優(yōu)化又有了新的優(yōu)化技術(shù)。文獻[6]采用改進的人工魚群算法對系統(tǒng)的硬件和軟件進行了劃分。文獻[7]采用粒子群優(yōu)化算法對熱電目標進行動態(tài)跟蹤。文獻[8]模擬電路測試點優(yōu)化通過動態(tài)蟻群算法實現(xiàn)。智能算法在不斷更新，包括磷蝦群優(yōu)化算法[9]、混沌果蠅算法[10]、蜘蛛算法[11]。這些都是基于大自然生物的生命周期表現(xiàn)的規(guī)律進行總結(jié)而得到的新興算法。

2014年，Meng等人[12]共同提出雞群優(yōu)化算法（CSO）來模擬雞群的等級和行為。一只雄雞和多只母雞組成一個亞組，多個亞組構(gòu)成一個雞群，各種雞移動的規(guī)律是不同的。各個雞群間在提前設置的規(guī)定下存在一定競爭。CSO優(yōu)化算法是針對全局的，和其他優(yōu)化算法如差分、蝙蝠等算法相比，在收斂準確性和速度上的優(yōu)勢都十分顯著，然而傳統(tǒng)雞群算法在局部收斂和抗干擾方面還存在很多不足之處。

本文利用動態(tài)簇解決單一工作節(jié)點能力有限問題，提出一種基于網(wǎng)格的序列雞群算法，優(yōu)化標準雞群算法的種群分組更新機制，同時還引入了新的小雞學習公式。仿真和實驗結(jié)果表明該算法具有定位精度高、收斂速度快、實時性好等優(yōu)點。

1雞群算法

1.1算法簡介

2014年，Meng等人針對雞尋覓食物的過程進行模仿，發(fā)現(xiàn)雞群覓食的規(guī)律，并以此為基礎推出CSO算法。關(guān)于雞群覓食的規(guī)律，主要可概述為如下4點：

（1）每個雞群都由多個小組構(gòu)成，領導者是雄雞，組中還有小雞和雌雞，每個小組都有對應的領導者。

（2）雞群中雄雞、雌雞和小雞的身份是由適應度作為標準進行區(qū)分的，雄雞適應度最強，小雞適應性最弱，母雞分組原則實施隨機分配。

（3）雞群中雌雞和雛雞的母子關(guān)系保持，只是每隔一段時間這種關(guān)系就會按照特定的等級秩序和規(guī)則重新分配。

（4）雄雞外出覓食時，雌雞會跟著一同去覓食，而雛雞會在雌雞附近尋覓食物。具有較高適應度值的雞在爭奪食物的過程中將占有優(yōu)勢。

1.2位置更新方法

雞群中雄雞、雌雞和雛雞身份等級的劃分是按照適應度強弱實現(xiàn)的，實驗后得知雛雞和雄雞占據(jù)比例都是20%，雌雞占據(jù)比例高達60%，經(jīng)過該算法進行優(yōu)化，效果較為理想，雄雞、雌雞和雛雞位置都會根據(jù)各自的位置更新算法完成更新。研究內(nèi)容詳述如下。

2.2仿真流程

基于網(wǎng)格，對目標軌跡進行偵測。首先，對環(huán)境及相關(guān)參數(shù)初始化。研究中假設模擬的觀測區(qū)域是一個20×20m2的正方形區(qū)域，分成了20×20個正方形網(wǎng)格，每個網(wǎng)格的區(qū)域的面積為1m2。在這個區(qū)域內(nèi)隨機分布了60個聲波幅度傳感器節(jié)點，假設跟蹤目標在這個區(qū)域內(nèi)的最大移動速度為2m/s，假設聲波的傳播范圍為米，設置傳感器節(jié)點的門限值為4，在偵測區(qū)域內(nèi)初始目標軌跡。每次節(jié)點偵測完目標后會將信息傳遞給下一個節(jié)點，循環(huán)直到目標超出偵測范圍為止。仿真流程如圖1所示。

圖2～圖4中，黃色圓點表示偵測區(qū)域內(nèi)的傳感器節(jié)點，白色小叉表示目標的實際運動軌跡。顏色的深淺比則表示了信任度的值，顏色越深就表示目標在該區(qū)域出現(xiàn)的可能性越高。

3算法仿真

3.1精確定位階段

這里，研究擬給出定位步驟具體如下。

Step1100個傳感器節(jié)點（包括未知節(jié)點和信標節(jié)點）隨機分布在立方體空間中，空間是邊長為50m的正方體。

Step2信標節(jié)點將信號強度數(shù)值傳遞給未知節(jié)點，未知節(jié)點將其轉(zhuǎn)變成距離值。

Step3對第n個位置節(jié)點坐標進行計算，該節(jié)點接收m個信號，如果m值是0，未知節(jié)點不能捕獲則跳轉(zhuǎn)到Step7。如果m取值在0～4之間，坐標計算利用質(zhì)心算法完成，然后跳轉(zhuǎn)到Step7。如果m取值大于等于4，那么繼續(xù)Step4。

Step4將m個信標節(jié)點按每四個分成一組，組數(shù)為k，并且多個組并非出于相同平面。

Step5利用三面節(jié)點估計法計算出k個坐標值，即：（x1，y1，z1）、…、（xk，yk，zk）。

Step6傳統(tǒng)雞群算法完成優(yōu)化。

Step7如果未知節(jié)點數(shù)量為n，則算法終止;如果未知節(jié)點數(shù)量不為n，則n=n+1回轉(zhuǎn)到Step3繼續(xù)執(zhí)行算法。

3.2仿真分析

節(jié)點隨機分布在100m×100m的平面，分別對比傳統(tǒng)雞群算法與改進雞群算法在通訊半徑、錨節(jié)點占比以及總節(jié)點數(shù)三個方面對定位精度的影響，依次參見圖5～圖7。

由圖5～圖7可以看出，在通信半徑從15變化到35之間，改進的雞群算法相較于傳統(tǒng)雞群算法定位精度提高了15%;在錨節(jié)點的個數(shù)從15變化到40之間，改進雞群算法的定位精度提高了15%左右;當總節(jié)點數(shù)目從100變化到200之間，改進雞群算法的總體定位精度提高了約14%。故可以得出，改進雞群算法相較于傳統(tǒng)雞群算法在不同的通信半徑、錨節(jié)點數(shù)、總節(jié)點數(shù)目等情況下，定位精度都有了明顯改善。

4結(jié)束語

文章以網(wǎng)格法和雞群算法為基礎提出的優(yōu)化算法可以很好地解決傳感器定位誤差偏大的不足。該算法利用動態(tài)簇解決單一工作節(jié)點能力有限問題，優(yōu)化了標準雞群算法的種群分組更新機制，全面提高了定位精度。經(jīng)過仿真驗證文中提出的改進算法可以確保較好的收斂性，而且定位精度也有了明顯改善，實現(xiàn)上也較為簡單。不過密度高的障礙物環(huán)境并沒有考慮進來，所以還需要在障礙物數(shù)量隨意設定的狀態(tài)下對算法做進一步的優(yōu)化。

參考文獻

[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].天津大學學報：自然科學與工程技術(shù)版，2013，46（10）：923-928.

[7]王澤兵，楊衛(wèi)，秦麗.基于粒子群算法的動態(tài)熱釋電目標跟蹤[J].光學學報，2014，34（10）：35-41.

[8]羅慧，蹇興亮，盧偉.基于動態(tài)蟻群算法的模擬電路最優(yōu)測點選擇[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.