蛙跳螢火蟲算法及其在無線電頻譜分配中的應用*

李衛軍（北方民族大學　網絡信息技術中心，寧夏 銀川 750021）

蛙跳螢火蟲算法及其在無線電頻譜分配中的應用*

李衛軍
（北方民族大學網絡信息技術中心，寧夏 銀川 750021）

螢火蟲算法是一種生物群智能的隨機優化算法，該算法通過模擬螢火蟲在覓食、擇偶中產生熒光而相互吸引、移動、合作等行為來解決最優化問題。雖然該算法具有設置參數少、原理簡單、更新公式清晰等優點，但是存在著種群過早收斂到局部最優解或者種群收斂速度慢等問題。為此本文提出蛙跳螢火蟲算法。該算法利用蛙跳的分群思想來優化螢火蟲算法。利用蛙跳算法對種群進行分群和局部深度優化，不斷地迭代以尋得最優解。在對蛙跳螢火蟲算法研究的基礎上把它應用于無線電頻譜分配中，獲得比較滿意的頻譜分配方式。

螢火蟲算法；蛙跳算法；蛙跳螢火蟲算法；無線電頻譜

0　引言

在當今社會的生產生活中，眾多學者利用進化成功的生物的生活方式來解決經典控制理論及優化方法在解決實際問題時所出現的瓶頸問題。其中蟻群優化算法利用了螞蟻群體分工協作的尋徑方式；隨機蛙跳算法模擬一群青蛙在覓食過程中分組交換信息再重新分組的過程。這類算法都源于學習或模擬某些生物的生存本領，因此此類算法多用于尋優或并行處理，因此又被統稱為群智能優化算法。本文將這兩種算法結合起來取長補短，用于無線電頻譜分配中。

1　螢火蟲算法

1.1算法的仿生原理

螢火蟲算法是一種仿生群智能優化算法，是受螢火蟲個體的發光行為啟發而設計的，最早是由印度學者Krishnanand［1］等人于2005年提出的GSO（Glowworm Swarm Optimization），后來劍橋大學的 Yang［2］也提出類似的算法，稱為FA（Firefly Algorithm）。

在熱帶和溫帶地區，夏天的晚上都會出現數量巨大的螢火蟲群，據統計自然界中有大概 2000種螢火蟲，大多數都會發出短促而有節奏的閃爍熒光，有的是為了求偶，有的是為了捕食或警戒等，科學家對此進行深入的研究發現其中的規律，構造出了螢火蟲算法。螢火蟲算法是模擬螢火蟲發光行為構造出的一種隨機優化算法，該算法根據其搜索區域尋找提供個體，向較優的螢火蟲移動，從而實現位置優化。

螢火蟲根據兩個因素更新自己的位置，一是熒光亮度，二是吸引度［3］。越亮的螢火蟲吸引同伴向其移動的概率就越大，以至于最后都聚集在最亮的螢火蟲周圍。螢火蟲算法是一種群體智能優化算法，通過螢火蟲的種群表示搜索空間中的解，衡量螢火蟲所處的位置的優劣程度（即熒光亮度大小）用目標函數來表示，將螢火蟲種群優勝劣汰過程表示為可行解的替換和變換過程。

1.2螢火蟲算法的數學描述

螢火蟲個體之間相互吸引主要由亮度和吸引度決定。亮度體現了螢火蟲所處位置的優劣，位置又決定了螢火蟲的亮度，亮度又決定了吸引度，吸引度進而決定了位置移動的距離大小和方向。由亮度和吸引度的不斷變化完成目標的優化過程。從數學的角度描述［4-5］如下：

（1）螢火蟲的亮度表達式

式（1）中 Ii，j表示螢火蟲 i對螢火蟲 j的相對亮度即吸引度；Ii表示螢火蟲i在r=0處的熒光亮度，它與相對的目標函數相關，目標函數越優，自身亮點越高；ε表示熒光吸收系數，表示熒光在傳輸過程中隨著傳輸距離的增加而減少的特性。

（2）螢火蟲i被螢火蟲j吸引后的位置移動更新函數其中，xi、xj表示螢火蟲所處的位置坐標，β為步長因子，α為擾動因子，rand為［0，1］的隨機函數，α（rand-）是為了避免種群陷入局部最優解而設定的擾動項。

（3）螢火蟲的移動概率

螢火蟲先確定某個螢火蟲周圍最亮的個體，這個更亮的個體對這個螢火蟲的吸引度，計算這些吸引度的總和，然后根據各個更亮螢火蟲的吸引度占據總吸引度的比例作為螢火蟲移動的概率，計算公式如下：

其中，pij表示螢火蟲個體 j向 i移動的概率，n表示螢火蟲的個體i周圍比它亮的個體數目。

1.3螢火蟲算法流程

算法流程如下：

（1）初始化基本參數：螢火蟲數目 n，光強吸收系數γ，步長因子 β，擾動因子 α，最大迭代次數 tmax等。

（2）根據約束條件隨機初始化螢火蟲個數，計算各個螢火蟲的目標函數作為螢火蟲自身的亮度。

（3）由式（1）計算各個螢火蟲的相對吸引度，根據吸引度的大小決定螢火蟲向其他螢火蟲移動的概率。

（4）由式（2）計算各個螢火蟲的更新位置，最佳位置的螢火蟲進行隨機擾動。

（5）根據更新后的位置重新計算亮度，即適應值。

（6）當滿足搜索精度或達到最大的搜索次數時轉向（7），否則搜索次數加 1，跳轉到（3），進行下一輪搜索。

（7）輸出全局極致個數和最優個體值。

算法的時間復雜度是 O（n2），n為螢火蟲的數目。

雖然螢火蟲算法有諸多優點，如原理簡單、參數少、更新清晰，但與其他群智算法一樣存在過早收斂到局部最優解或收斂速度過慢的問題，為此本文結合分群的思想進行改進。

2　隨機蛙跳算法

2.1算法的仿生學原理

與螢火蟲算法相似，隨機蛙跳算法［6］也是一種群智優化算法，最初是為了解決組合優化問題，具有高效的計算性能和優良的全局搜索能力。具體思想是［7］：在一片濕地中生活著一群青蛙，它們又分為幾個族群，每個族群內的每個青蛙進行信息共享來一起尋找食物，每個族群在各自尋找食物一段時間以后所有的族群又聚集在一起，以達到共享信息的目的，然后重新分群，各個族群又獨自尋找食物，通過循環這個過程，青蛙共享信息，盡快找到食物。該過程既有局部信息的交流，又有全局的信息交流，算法在執行過程中可以有效防止過早陷入局部最優解，向全局最優解方向移動。

2.2算法的數學描述

（1）初始蛙跳的群體，隨機產生 n只青蛙，每只青蛙的位置表示解空間的一個解，X=（x1，x2，…xm），x1，x2，…xm表示解的分量，m表示解得維數。

（2）根據實際情況狀況計算出每個青蛙的目標值，對目標值優劣進行排序。

（3）對青蛙進行分子群，若分為 p個族群，每族群有q只青蛙，其中p，q滿足p×q=n，第1只青蛙分到第1族群，第2只青蛙分到第2族群，以此類推，第p只青蛙分到第p族群，……，第2p只青蛙分到第p個族群。依次循環直到分配完畢。

利用式（4）隨機從青蛙種群中選取q個進行分組，并將組進行排序，j表示第 j只青蛙，pj表示第 j只青蛙被選中的概率。找出最好的族群 PB和最差的族群 PW，按式（5）和（6）對每個族群進行局部深度搜索。

上面的公式中 rand（）產生 0～1之間的一個隨機數，Dmax表示青蛙的跳動步長，newpw表示更新后青蛙的位置。如果 newpw處于可行解空間，計算 newpw對應的適應值，如果 newpw對應的適應值次于 oldpw所對應的適應值，則采用全集最優解PX代替上面公式中的PB更新oldpw。如果更新之后仍然沒有改進，隨機產生的新的青蛙來代替PW，重復上述過程，直到預設的迭代次數完畢。所有的族群完成深度搜索后，將所有的族群進行混合重新排序，之后再將青蛙分成子族群，繼續全局搜索，直到預設的條件滿足為止。

3　蛙跳螢火蟲算法

蛙跳螢火蟲算法［8］就是把螢火蟲算法和隨機蛙跳算法結合起來，具體結合方式如下：設置好算法各項參數：迭代次數r，族群規模n，分群數目m等，初始化螢火蟲的族群粒子，根據目標函數計算各個螢火蟲粒子的目標值，按照目標值的優劣進行排序，按照蛙跳算法進行分群。分群之后各個子種群按照蛙跳算法獨立進行深度優化，當達到迭代次數后又合為一個種群，對總的種群按照螢火蟲算法進行尋優，達到迭代次數后重新分群，重復以上步驟直到達到要求或者滿足迭代次數。

4　利用蛙跳螢火蟲算法對無線電頻譜進行分配

傳統的頻譜管理機制限定某一頻段內的頻譜只有該頻段的授權用戶可以使用，造成了這些頻道的頻譜利用率低下且存在大量的頻譜空洞。本文利用蛙跳螢火蟲算法對這一情況將分配方法進行改進。

4.1基于蛙跳螢火蟲算法中的基本概念

（1）螢火蟲

每一種頻譜分配方案只有一只螢火蟲，用矩陣X表示，X=［x1，x2，…xn］T，其中 xj是對信道 j的分配向量，xj= ［x1j，x2j，…xNj］，xij∈｛0，1｝，xij=1表示第 i個次級用戶獲得信道j的使用權，反之失敗。同時螢火蟲的位置更新，即每一種方案代表的分配矩陣的元素改變。

（2）熒光亮度

每一只螢火蟲所處的位置都會對應一個熒光亮度，即每一種分配方案都能計算出一個與之對應的目標函數值。個體在當前所處的位置的亮度，取決于目標函數值，目標函數值越高自身亮度越亮。

（3）空間距離 rij

rij為螢火蟲 i與 j之間的空間距離，螢火蟲的位置用坐標（x1，x2，…xN）表示，其中 xj為對于信道 j的分配向量。公式（1）計算出螢火蟲 i處看到個體j的亮度。

4.2算法的主要流程

（1）輸入螢火蟲算法的各項參數，輸入無線分配的參數等。

（2）初始化螢火蟲粒子，即各個頻譜分配方案，每個粒子可以按如下的方式初始化：

其中，xij表示第 i個次級用戶獲得信道j的使用權。

（3）對各個粒子進行評價，計算出目標適應值，用蛙跳螢火蟲算法對種群進化尋優，達到迭代次數后按目標適應值大小排序，分群。

（4）利用隨機蛙跳算法對各個子種群局部深度優化，在尋優的過程中如果出現不符合約束的粒子則直接舍去，重新初始化新粒子代替，達到迭代次數后各種群重新混合。

（5）迭代次數減 1，判讀迭代次數是否為 0，若不為0轉到（3），否則選出此時最優解，實驗完畢。

4.3實驗仿真

本文利用MATLAB進行仿真，參數設置如表1。

系統中參數的設定不同會造成系統性能差異很大，最大迭代次數是一個很重要的參數，增大 tmax可以提高算法精度，但也增加計算量，因此選擇合適的 tmax至關重要。本文中針對螢火蟲數量分別在60、80、100三種情況下，次級用戶數分別是10，12，14，16，18時，測試收斂的平均迭代次數，測試結果如圖1所示。從圖中可以看出，螢火蟲的數量越多收斂速度越快，并且次級用戶較少時收斂速度也快。除了最大的迭代次數，種群規模也就是螢火蟲的數量n的大小也很重要。n越大算法精度越高，計算量越大，因此選擇一個合適的種群規模對于提高算法整體性能非常重要。

表1　蛙跳螢火蟲算法中相關參數的設定

圖1　螢火蟲數量不同情況下次級用戶數對收斂迭代次數的影響

5　結論

本文主要介紹了螢火蟲算法和隨機蛙跳算法的基本原理，并用數學方法進行描述，對算法的執行流程進行了說明，然后把螢火蟲算法和隨機蛙跳算法兩者結合，形成了蛙跳螢火蟲算法，并且把該算法應用于無線電頻譜分配。實驗表明，蛙跳螢火蟲算法在求解組合優化問題方面是有效的。

［1］KRISHNANAND K N，GHOSE D.Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications［J］.Multiagent and Grid Systems，2006，2（3）：209-222.

［2］Yang Xinshe.Firefly algorithms for multimodal optimization［J］. Lecture Note in Computer Sciences，2010（3）：169-178.

［3］KWIECIEN J，FILIPOWICZ B.Firefly algorithm in optimization of queueing system［J］.Bulletin of the Polish Academy of Sciences.Technical Sciences，2012，60（2）：363-368.

［4］GANDOMi A H，Yang Xinshe，ALAVI A H.Mixed variable structural optimization using firefly algorithm［J］.Computers&Structures，2011，89（23-24）：2325-36.

［5］莫愿斌，劉付永，馬彥追.模擬生物理想自由分布模型的螢火蟲算法［J］.計算機與應用化學，2014，31（2）：153-160.

［6］HENSHALL P，PALMER P.A leapfrog algorithm for coupledconductiveandradiativetransientheattransferin participating media［J］.InternationalJournal ofThermal Sciences，2008，47（4）：388-398.

［7］宋曉華，楊尚東，劉達.基于蛙跳算法的改進支持向量機預測方法及應用［J］.中南大學學報（自然科學版），2011，42（9）：2737-2740.

［8］李洋.蛙跳螢火蟲算法及其在含風電場的電力系統調度中的應用［D］.上海：華東理工大學，2013.

Study on leapfrog firefly algorithm and its application in the radio spectrum allocation

Li Weijun
（Network Information Technology Center，Beifang University of Nationalities，Yinchuan 750021，China）

Firefly algorithm is a stochastic biota intelligent optimization algorithm，which simulates fireflies in foraging，mate choice in fluorescence attract each other，moving，and other acts of cooperation to solve the optimization problem.Although the firefly algorithm has many advantages，such as few parameters，simple principle，clear updating formulas，etc.，there is population of premature convergence to local optima，or populations of slow convergence and other issues.This paper proposes leapfrog firefly clustering algorithm that uses the leapfrog thought to optimize the firefly leapfrog algorithm.In order to find the optimal solution，leapfrog algorithm continuously iterates under clustering and local populations depth optimization.Based on research of the leapfrog firefly algorithm，it is applied to the radio frequency spectrum allocation，to obtain satisfactory way of spectrum allocation.

firefly algorithm；leapfrog algorithm；leapfrog firefly algorithm；radio spectrum

TP311

A

1674-7720（2015）05-0016-03

寧夏自然科學基金（NZ12138）；北方民族大學自然科學基金（2013XYZ028）

（2014-10-12）

李衛軍（1979-），男，博士研究生，講師，主要研究方向：智能信息處理。E-mail：liweijun51@163.com。