張航　楊靖

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

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

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

【Keywords】wirelesssensornetwork;chickenswarmalgorithm;dynamiccluster;positioningaccuracy

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

0引言

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

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

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

1雞群算法

1.1算法簡介

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

（1）每個(gè)雞群都由多個(gè)小組構(gòu)成，領(lǐng)導(dǎo)者是雄雞，組中還有小雞和雌雞，每個(gè)小組都有對(duì)應(yīng)的領(lǐng)導(dǎo)者。

（2）雞群中雄雞、雌雞和小雞的身份是由適應(yīng)度作為標(biāo)準(zhǔn)進(jìn)行區(qū)分的，雄雞適應(yīng)度最強(qiáng)，小雞適應(yīng)性最弱，母雞分組原則實(shí)施隨機(jī)分配。

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

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

1.2位置更新方法

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

2.2仿真流程

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

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

3算法仿真

3.1精確定位階段

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

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

Step2信標(biāo)節(jié)點(diǎn)將信號(hào)強(qiáng)度數(shù)值傳遞給未知節(jié)點(diǎn)，未知節(jié)點(diǎn)將其轉(zhuǎn)變成距離值。

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

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

Step5利用三面節(jié)點(diǎn)估計(jì)法計(jì)算出k個(gè)坐標(biāo)值，即：（x1，y1，z1）、…、（xk，yk，zk）。

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

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

3.2仿真分析

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

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

4結(jié)束語

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

參考文獻(xiàn)

[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ìn)人工魚群算法的軟硬件劃分方法[J].天津大學(xué)學(xué)報(bào)：自然科學(xué)與工程技術(shù)版，2013，46（10）：923-928.

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

[8]羅慧，蹇興亮，盧偉.基于動(dòng)態(tài)蟻群算法的模擬電路最優(yōu)測(cè)點(diǎn)選擇[J].儀器儀表學(xué)報(bào)，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.