改進型蛙跳螢火蟲算法及其在CRN頻譜分配中的應用

張海嬌 孫文勝

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

關鍵詞：螢火蟲算法;認知無線電網絡;頻譜分配;族群劃分;可變步長

DOI：10. 11907/rjdk. 182268

中圖分類號：TP312文獻標識碼：A文章編號：1672-7800（2019）004-0095-04

0 引言

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

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

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

1 原始GSO算法

1.1 原始GSO算法基本思想

1.2 原始GSO算法缺陷

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

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

2 改進型FGSO算法

2.1 FGSO算法中的自適應步長

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

2.2 FGSO算法中的蛙跳思想

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

其劃分過程如圖2所示。

3 認知無線電頻譜分配

3.1 頻譜分配模型

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

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

（2）計算螢火蟲粒子對應目標函數值，同時按降序排列。

（3）以本文蛙跳族群劃分思想對種群進行劃分，分群完成后，在各個族群內進行局部搜索，根據自適應步長進行位置更新。

（4）全體族群實現局部尋優搜索后，重新融合成新的種群，并更新螢火蟲全局信息。

（5）判斷是否達到最大迭代次數[tmax]，若達到了則跳轉到步驟（6）并輸出結果;反之繼續執行步驟（2），直到滿足終止條件并輸出結果為止。

（6）輸出結果，程序結束。

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

4 仿真及實驗結果

4.1 仿真環境

為了驗證FGSO算法性能，以及將其應用于認知無線電頻譜分配是否可以得到理想成效，選擇MATLAB R2013a作為仿真實驗平臺，以最大網絡效益以及平均網絡效益為衡量標準，與原始GSO算法進行對比。FGSO參數設置如下：初始熒光素大小[l0=5.0]，最小移動步長[Smin=1]，最大移動步長[Smax=3]，適應度變化率[γ=0.6]，螢火素變化率[ρ=0.4]，最大迭代次數[tmax=200]。

4.2 實驗結果與分析

4.2.1 網絡總效益與實驗次數變化關系

當認知用戶數N=30，空閑頻譜數量M=10時，FGSO與GSO算法網絡總效益隨實驗次數增加的波動曲線如圖4所示。

由圖4可知，隨著實驗次數增加，基于GSO 與FGSO算法的網絡總效益均發生波動，但FGSO的整體波動相對較小，證明該算法穩定性優于GSO算法，同時FGSO算法的網絡總效益高于GSO算法。

4.2.2 空閑頻譜數與平均網絡總效益變化關系

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

4.2.3 認知用戶數與平均網絡總效益變化關系

當空閑頻譜M=30，認知用戶數N的變化區間為[10，30]，基于FGSO與GSO算法的平均網絡總效益變化曲線如圖6所示。由圖6可以看出，隨著認知用戶數的增大，基于GSO與FGSO算法的平均網絡總效益均不斷減小，但基于FGSO算法得到的平均網絡總效益明顯高于基于GSO算法的平均網絡總效益，并且隨著N的增大，優勢更為明顯。

5 結語

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

參考文獻：

[1] 吳軒. 認知無線電系統的頻譜分配算法研究與優化[D]. 杭州：杭州電子科技大學，2015.

[2] 謝玉鵬. 認知無線電系統中聯合頻譜分配算法研究[D]. 哈爾濱：哈爾濱工業大學，2016.

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

[4] 余樨源，黃學良. 基于改進螢火蟲算法的電動汽車有序充電研究[J]. 信息技術，2018（1）：86-89.

[5] 楊旺旺，白濤，趙夢龍. 基于改進螢火蟲算法的水電站群優化調度[J]. 水力發電學報，2018，37（6）：25-33.

[6] 劉長平. 具有混沌搜索策略的螢火蟲優化算法[J]. 系統管理學報，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] 王吉權，王福林. 螢火蟲算法的改進分析及應用[J]. 計算機應用，2014，34（9）：255-2556.

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

[11] 曹婷婷. 認知無線電網絡中圖著色頻譜分配算法的研究[D]. 燕山：燕山大學，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] 劉洲洲，王福豹，張克旺. 基于改進螢火蟲優化算法的WSN覆蓋優化分析[J]. 傳感技術學報，2013，26（5）：675-682.

[14] 郁書好，蘇守寶. 一種改進的變步長螢火蟲優化算法[J]. 小型微型計算機系統，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]. 微電子學與計算機，2018，35（2）：61-66.

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

[18] 彭振，趙知勁，鄭仕鏈. 基于混合蛙跳算法的認知無線電頻譜分配[J]. 計算機工程，2010，36（6）：210-214.

[19] 項響琴，張滬寅. 漁夫捕魚優化算法的認知無線電頻譜分配[J]. 計算機工程與應用，2014，50（6）：72-76.

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

（責任編輯：黃 健）