改進(jìn)型蛙跳螢火蟲算法及其在CRN頻譜分配中的應(yīng)用

張海嬌 孫文勝

摘 要：原始螢火蟲（GSO）算法存在收斂速度慢、搜索精度不高等缺點(diǎn)，故設(shè)計(jì)一種改進(jìn)型蛙跳螢火蟲（FGSO）算法。該算法采用自適應(yīng)可變步長替換固定步長，并且結(jié)合蛙跳算法的族群劃分策略，提升螢火蟲個(gè)體交流能力，實(shí)現(xiàn)信息群內(nèi)共享，以及跳出局部最優(yōu)的目的。將改進(jìn)算法應(yīng)用到認(rèn)知無線電網(wǎng)絡(luò)CRN頻譜分配問題中，可獲取更為優(yōu)化的頻譜分配方案。實(shí)驗(yàn)仿真結(jié)果表明，從網(wǎng)絡(luò)效益方面考慮，改進(jìn)的蛙跳螢火蟲算法在總體性能及穩(wěn)定性方面均優(yōu)于原始螢火蟲算法，并能給出有效的CRN頻譜分配策略。

關(guān)鍵詞：螢火蟲算法;認(rèn)知無線電網(wǎng)絡(luò);頻譜分配;族群劃分;可變步長

DOI：10. 11907/rjdk. 182268

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-7800（2019）004-0095-04

0 引言

近年來群智能優(yōu)化算法層出不窮，已在圖像處理、數(shù)據(jù)挖掘、工業(yè)優(yōu)化等各個(gè)領(lǐng)域得到了廣泛應(yīng)用[1]。同時(shí)針對(duì)頻譜資源日益緊張的問題，認(rèn)知無線電技術(shù)適時(shí)產(chǎn)生并得到大范圍應(yīng)用。如何利用群智能優(yōu)化算法實(shí)現(xiàn)有效的頻譜分配，是認(rèn)知無線電網(wǎng)絡(luò)研究的熱點(diǎn)[2]。故本文以原始螢火蟲算法為參考，設(shè)計(jì)一種改進(jìn)型蛙跳螢火蟲智能優(yōu)化算法進(jìn)行認(rèn)知無線電網(wǎng)絡(luò)CRN（Cognitive Radio Network）頻譜分配，以改善頻譜資源緊張的現(xiàn)狀。

螢火蟲算法由于具備參數(shù)個(gè)數(shù)較少、操作復(fù)雜度低、收斂速度快等優(yōu)勢(shì)[3]，受到國內(nèi)外學(xué)者青睞，并針對(duì)原始螢火蟲算法有極大可能陷入局部最優(yōu)解與后期收斂速度較慢等缺陷，設(shè)計(jì)了多種改進(jìn)型螢火蟲算法。如余樨源等[4]引入自適應(yīng)變異環(huán)節(jié)，以提高原始螢火蟲算法尋優(yōu)速度與精度;楊旺旺等[5]設(shè)計(jì)一種基于隔代大步長純隨機(jī)游走與優(yōu)勢(shì)保留機(jī)制的螢火蟲算法，以避免陷入局部最優(yōu)解;劉長平[6]將混沌搜索思想引入螢火蟲算法，從而提升整體算法性能;YU等[7]以全局最好位置和個(gè)體最好位置為參考設(shè)置步長，并將該策略引入算法，以提升搜索質(zhì)量;WANG等[8]提出3個(gè)領(lǐng)域搜索與動(dòng)態(tài)參數(shù)調(diào)整策略，以提高螢火蟲算法的魯棒性和搜索精度。

本文設(shè)計(jì)的改進(jìn)型蛙跳螢火蟲算法，考慮到原始算法中固定步長不能維持局部與全局之間平衡性的缺陷[9]，用自適應(yīng)可變步長替代固定步長，綜合利用當(dāng)前迭代次數(shù)和最大迭代次數(shù)建立非線性動(dòng)態(tài)調(diào)節(jié)步長，以提升算法搜索性能。同時(shí)針對(duì)因原始算法中領(lǐng)域集的限制，導(dǎo)致最優(yōu)螢火蟲個(gè)體不能在群內(nèi)共享的問題[10]，將蛙跳算法中的族群劃分策略引入螢火蟲算法，從而進(jìn)一步提升算法尋優(yōu)性能。將該算法用于認(rèn)知無線電網(wǎng)絡(luò)的頻譜分配，仿真結(jié)果表明，該算法在總體性能及穩(wěn)定性等方面均優(yōu)于原始螢火蟲算法，能夠給出有效的CRN頻譜分配方案[11]。

1 原始GSO算法

1.1 原始GSO算法基本思想

1.2 原始GSO算法缺陷

缺陷一：原始GSO算法在求解最優(yōu)解過程中采用固定步長進(jìn)行位置更新，但在尋優(yōu)初期，兩個(gè)螢火蟲相距間隔可能過大，若按固定步長移動(dòng)，搜索速率則會(huì)較慢[14];同時(shí)在尋優(yōu)后期，個(gè)體越來越靠近最優(yōu)解，若還是按固定步長移動(dòng)，則可能錯(cuò)過最優(yōu)解。

缺陷二：原始GSO算法中，螢火蟲粒子的交流被限制在自身決策域空間內(nèi)，熒光素值很大的粒子只能影響其決策域內(nèi)的粒子，致使整個(gè)種群不能共享最優(yōu)螢火蟲粒子信息[15]。同時(shí)有可能存在一只螢火蟲i，在其決策域里沒有比它亮的螢火蟲，而其又距離最優(yōu)解較遠(yuǎn)，因此會(huì)固定在某一位置，附近螢火蟲感知到其亮度并向其靠近，從而使一些螢火蟲粒子匯聚到同一位置，失去活動(dòng)能力[16]。圖1對(duì)該現(xiàn)象進(jìn)行了描述，其中最優(yōu)解用正方形代替，找不到亮度強(qiáng)于自身的螢火蟲粒子i用大圓代替，失去活動(dòng)能力的螢火蟲粒子用小圓代替。該現(xiàn)象降低了整個(gè)算法的尋優(yōu)效率和精度。

2 改進(jìn)型FGSO算法

2.1 FGSO算法中的自適應(yīng)步長

針對(duì)原始GSO算法的缺陷一，在改進(jìn)型蛙跳螢火蟲算法中，用自適應(yīng)可變步長[s（t）]取代固定步長[d]，如式（5）所示。

2.2 FGSO算法中的蛙跳思想

針對(duì)原始算法的缺陷二，將蛙跳算法中的族群劃分策略引入螢火蟲算法，以實(shí)現(xiàn)信息在局部和全局內(nèi)的共享。基本思想為：將整個(gè)螢火蟲種群分割成幾個(gè)相同規(guī)模的族群，族群內(nèi)部螢火蟲各自進(jìn)行局部搜索尋優(yōu)，以實(shí)現(xiàn)局部信息交互;若全部族群實(shí)現(xiàn)局部搜索，全體螢火蟲個(gè)體則進(jìn)行新一輪混合，實(shí)現(xiàn)全局信息的交互更新，同時(shí)根據(jù)一定規(guī)則再次分割成幾個(gè)族群[17];一直重復(fù)上述流程，當(dāng)滿足算法結(jié)束條件時(shí)停止。局部搜索尋優(yōu)結(jié)合全局信息交互策略，可以讓全局最優(yōu)信息在整個(gè)種群中實(shí)現(xiàn)傳遞，提升了算法收斂效率。FGSO族群劃分具體策略為：設(shè)一個(gè)種群內(nèi)有n只螢火蟲個(gè)體，n只個(gè)體依照目標(biāo)函數(shù)值降序排列[18]，平均劃分到p個(gè)族群，每個(gè)族群有q只螢火蟲。設(shè)[Ek]表示第k個(gè)族群，[S]為可行解空間，則劃分后得到的族群集合可由式（7）表示。

其劃分過程如圖2所示。

3 認(rèn)知無線電頻譜分配

3.1 頻譜分配模型

3.2 基于FGSO算法的頻譜分配求解步驟

（1）給定算法的基礎(chǔ)參數(shù)及無線分配相關(guān)參數(shù)，初始化螢火蟲粒子，生成空閑頻譜矩陣L、效益矩陣B與干擾矩陣C。

（2）計(jì)算螢火蟲粒子對(duì)應(yīng)目標(biāo)函數(shù)值，同時(shí)按降序排列。

（3）以本文蛙跳族群劃分思想對(duì)種群進(jìn)行劃分，分群完成后，在各個(gè)族群內(nèi)進(jìn)行局部搜索，根據(jù)自適應(yīng)步長進(jìn)行位置更新。

（4）全體族群實(shí)現(xiàn)局部尋優(yōu)搜索后，重新融合成新的種群，并更新螢火蟲全局信息。

（5）判斷是否達(dá)到最大迭代次數(shù)[tmax]，若達(dá)到了則跳轉(zhuǎn)到步驟（6）并輸出結(jié)果;反之繼續(xù)執(zhí)行步驟（2），直到滿足終止條件并輸出結(jié)果為止。

（6）輸出結(jié)果，程序結(jié)束。

基于FGSO算法的CRN頻譜分配具體流程如圖3所示。

4 仿真及實(shí)驗(yàn)結(jié)果

4.1 仿真環(huán)境

為了驗(yàn)證FGSO算法性能，以及將其應(yīng)用于認(rèn)知無線電頻譜分配是否可以得到理想成效，選擇MATLAB R2013a作為仿真實(shí)驗(yàn)平臺(tái)，以最大網(wǎng)絡(luò)效益以及平均網(wǎng)絡(luò)效益為衡量標(biāo)準(zhǔn)，與原始GSO算法進(jìn)行對(duì)比。FGSO參數(shù)設(shè)置如下：初始熒光素大小[l0=5.0]，最小移動(dòng)步長[Smin=1]，最大移動(dòng)步長[Smax=3]，適應(yīng)度變化率[γ=0.6]，螢火素變化率[ρ=0.4]，最大迭代次數(shù)[tmax=200]。

4.2 實(shí)驗(yàn)結(jié)果與分析

4.2.1 網(wǎng)絡(luò)總效益與實(shí)驗(yàn)次數(shù)變化關(guān)系

當(dāng)認(rèn)知用戶數(shù)N=30，空閑頻譜數(shù)量M=10時(shí)，F(xiàn)GSO與GSO算法網(wǎng)絡(luò)總效益隨實(shí)驗(yàn)次數(shù)增加的波動(dòng)曲線如圖4所示。

由圖4可知，隨著實(shí)驗(yàn)次數(shù)增加，基于GSO 與FGSO算法的網(wǎng)絡(luò)總效益均發(fā)生波動(dòng)，但FGSO的整體波動(dòng)相對(duì)較小，證明該算法穩(wěn)定性優(yōu)于GSO算法，同時(shí)FGSO算法的網(wǎng)絡(luò)總效益高于GSO算法。

4.2.2 空閑頻譜數(shù)與平均網(wǎng)絡(luò)總效益變化關(guān)系

當(dāng)認(rèn)知用戶數(shù)N=20，空閑頻譜數(shù)量M的變化區(qū)間為[20，40]，基于FGSO與GSO算法的平均網(wǎng)絡(luò)總效益變化曲線如圖5所示。由圖5可以看出，隨著空閑頻譜數(shù)的增大，基于GSO與FGSO算法的平均網(wǎng)絡(luò)總效益均不斷增加，但基于FGSO算法得到的平均網(wǎng)絡(luò)總效益明顯高于基于GSO算法的平均網(wǎng)絡(luò)總效益。

4.2.3 認(rèn)知用戶數(shù)與平均網(wǎng)絡(luò)總效益變化關(guān)系

當(dāng)空閑頻譜M=30，認(rèn)知用戶數(shù)N的變化區(qū)間為[10，30]，基于FGSO與GSO算法的平均網(wǎng)絡(luò)總效益變化曲線如圖6所示。由圖6可以看出，隨著認(rèn)知用戶數(shù)的增大，基于GSO與FGSO算法的平均網(wǎng)絡(luò)總效益均不斷減小，但基于FGSO算法得到的平均網(wǎng)絡(luò)總效益明顯高于基于GSO算法的平均網(wǎng)絡(luò)總效益，并且隨著N的增大，優(yōu)勢(shì)更為明顯。

5 結(jié)語

本文針對(duì)原始螢火蟲算法的固有缺點(diǎn)，設(shè)計(jì)一種結(jié)合蛙跳算法的族群劃分策略，將固定步長更新為自適應(yīng)變步長的改進(jìn)型蛙跳螢火蟲算法，并利用該算法求解認(rèn)知無線電頻譜分配問題。通過仿真實(shí)驗(yàn)，證明該算法總體性能與穩(wěn)定性優(yōu)于原始螢火蟲算法。同時(shí)，對(duì)認(rèn)知無線電的頻譜分配能夠增加網(wǎng)絡(luò)效益，擴(kuò)大認(rèn)知無線電網(wǎng)絡(luò)的使用范圍與使用場景。但是本文對(duì)算法性能的檢驗(yàn)都是從最大化網(wǎng)絡(luò)效益角度出發(fā)，還可以從最大化最小帶寬角度作進(jìn)一步驗(yàn)證。同時(shí)本文研究的頻譜模型是建立在用戶位置與頻譜資源等條件保持不變的基礎(chǔ)上，但實(shí)際網(wǎng)絡(luò)場景條件是多變的，故可通過改變頻譜分配模型進(jìn)行更深入的探究。

參考文獻(xiàn)：

[1] 吳軒. 認(rèn)知無線電系統(tǒng)的頻譜分配算法研究與優(yōu)化[D]. 杭州：杭州電子科技大學(xué)，2015.

[2] 謝玉鵬. 認(rèn)知無線電系統(tǒng)中聯(lián)合頻譜分配算法研究[D]. 哈爾濱：哈爾濱工業(yè)大學(xué)，2016.

[3] 程美英，倪志偉，朱旭輝. 螢火蟲優(yōu)化算法理論研究綜述[J]. 計(jì)算機(jī)科學(xué)，2015，42（4）：20-24.

[4] 余樨源，黃學(xué)良. 基于改進(jìn)螢火蟲算法的電動(dòng)汽車有序充電研究[J]. 信息技術(shù)，2018（1）：86-89.

[5] 楊旺旺，白濤，趙夢(mèng)龍. 基于改進(jìn)螢火蟲算法的水電站群優(yōu)化調(diào)度[J]. 水力發(fā)電學(xué)報(bào)，2018，37（6）：25-33.

[6] 劉長平. 具有混沌搜索策略的螢火蟲優(yōu)化算法[J]. 系統(tǒng)管理學(xué)報(bào)，2013，22（4）：538-543.

[7] YU S，ZHU S，MA Y，et al. A variable step size firefly algorithm for numerical optimization[J]. Applied Mathematics and Computalion，2015，263（C）：214-220.

[8] WANG H， CCI Z，SUN H， et al.Randomly attracted firefly algorithm? with neighborhood search and? dynamic? parameter adjustment mechanism[J]. Soft Computing， 2017，21（18）：5325-5339.

[9] 王吉權(quán)，王福林. 螢火蟲算法的改進(jìn)分析及應(yīng)用[J]. 計(jì)算機(jī)應(yīng)用，2014，34（9）：255-2556.

[10] 王曉靜，彭虎，鄧長壽. 基于均勻局部搜索和可變步長的螢火蟲算法[J]. 計(jì)算機(jī)應(yīng)用，2018，38（3）：715-721.

[11] 曹婷婷. 認(rèn)知無線電網(wǎng)絡(luò)中圖著色頻譜分配算法的研究[D]. 燕山：燕山大學(xué)，2016.

[12] KRISHANDK N，GHOSE D. Glowworm swarm optimisation for simulatancous capture of mutiple local optima of multimodal funcations[J].? Swarm Intelligence， 2009，3（2）：87-124.

[13] 劉洲洲，王福豹，張克旺. 基于改進(jìn)螢火蟲優(yōu)化算法的WSN覆蓋優(yōu)化分析[J]. 傳感技術(shù)學(xué)報(bào)，2013，26（5）：675-682.

[14] 郁書好，蘇守寶. 一種改進(jìn)的變步長螢火蟲優(yōu)化算法[J]. 小型微型計(jì)算機(jī)系統(tǒng)，2014，35（6）：1396-1400.

[15] PENG H，WU Z J，DENG C S. Enhancing differential evolution with commensal learning and uniform local search[J]. Chinese Journal of Electronics， 2017，26（4）：725-733.

[16] 左仲亮，郭星，李煒. 一種改進(jìn)的螢火蟲算法[J]. 微電子學(xué)與計(jì)算機(jī)，2018，35（2）：61-66.

[17] 李衛(wèi)軍. 蛙跳螢火蟲算法及其在無線電頻譜分配中的應(yīng)用[J]. 微型機(jī)與應(yīng)用，2015，34（5）：17-21.

[18] 彭振，趙知?jiǎng)?，鄭仕? 基于混合蛙跳算法的認(rèn)知無線電頻譜分配[J]. 計(jì)算機(jī)工程，2010，36（6）：210-214.

[19] 項(xiàng)響琴，張滬寅. 漁夫捕魚優(yōu)化算法的認(rèn)知無線電頻譜分配[J]. 計(jì)算機(jī)工程與應(yīng)用，2014，50（6）：72-76.

[20] 程啟明. 基于改進(jìn)敏感圖著色算法的認(rèn)知無線電頻譜分配研究[D]. 成都：西南交通大學(xué)，2016.

（責(zé)任編輯：黃 健）