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

李衛(wèi)軍（北方民族大學(xué)　網(wǎng)絡(luò)信息技術(shù)中心，寧夏 銀川 750021）

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

李衛(wèi)軍
（北方民族大學(xué)網(wǎng)絡(luò)信息技術(shù)中心，寧夏 銀川 750021）

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

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

0　引言

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

1　螢火蟲算法

1.1算法的仿生原理

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

在熱帶和溫帶地區(qū)，夏天的晚上都會出現(xiàn)數(shù)量巨大的螢火蟲群，據(jù)統(tǒng)計自然界中有大概 2000種螢火蟲，大多數(shù)都會發(fā)出短促而有節(jié)奏的閃爍熒光，有的是為了求偶，有的是為了捕食或警戒等，科學(xué)家對此進(jìn)行深入的研究發(fā)現(xiàn)其中的規(guī)律，構(gòu)造出了螢火蟲算法。螢火蟲算法是模擬螢火蟲發(fā)光行為構(gòu)造出的一種隨機優(yōu)化算法，該算法根據(jù)其搜索區(qū)域?qū)ふ姨峁﹤€體，向較優(yōu)的螢火蟲移動，從而實現(xiàn)位置優(yōu)化。

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

1.2螢火蟲算法的數(shù)學(xué)描述

螢火蟲個體之間相互吸引主要由亮度和吸引度決定。亮度體現(xiàn)了螢火蟲所處位置的優(yōu)劣，位置又決定了螢火蟲的亮度，亮度又決定了吸引度，吸引度進(jìn)而決定了位置移動的距離大小和方向。由亮度和吸引度的不斷變化完成目標(biāo)的優(yōu)化過程。從數(shù)學(xué)的角度描述［4-5］如下：

（1）螢火蟲的亮度表達(dá)式

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

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

（3）螢火蟲的移動概率

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

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

1.3螢火蟲算法流程

算法流程如下：

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

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

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

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

（5）根據(jù)更新后的位置重新計算亮度，即適應(yīng)值。

（6）當(dāng)滿足搜索精度或達(dá)到最大的搜索次數(shù)時轉(zhuǎn)向（7），否則搜索次數(shù)加 1，跳轉(zhuǎn)到（3），進(jìn)行下一輪搜索。

（7）輸出全局極致個數(shù)和最優(yōu)個體值。

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

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

2　隨機蛙跳算法

2.1算法的仿生學(xué)原理

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

2.2算法的數(shù)學(xué)描述

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

（2）根據(jù)實際情況狀況計算出每個青蛙的目標(biāo)值，對目標(biāo)值優(yōu)劣進(jìn)行排序。

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

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

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

3　蛙跳螢火蟲算法

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

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

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

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

（1）螢火蟲

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

（2）熒光亮度

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

（3）空間距離 rij

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

4.2算法的主要流程

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

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

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

（3）對各個粒子進(jìn)行評價，計算出目標(biāo)適應(yīng)值，用蛙跳螢火蟲算法對種群進(jìn)化尋優(yōu)，達(dá)到迭代次數(shù)后按目標(biāo)適應(yīng)值大小排序，分群。

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

（5）迭代次數(shù)減 1，判讀迭代次數(shù)是否為 0，若不為0轉(zhuǎn)到（3），否則選出此時最優(yōu)解，實驗完畢。

4.3實驗仿真

本文利用MATLAB進(jìn)行仿真，參數(shù)設(shè)置如表1。

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

表1　蛙跳螢火蟲算法中相關(guān)參數(shù)的設(shè)定

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

5　結(jié)論

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

［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，F(xiàn)ILIPOWICZ 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］.計算機與應(yīng)用化學(xué)，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］宋曉華，楊尚東，劉達(dá).基于蛙跳算法的改進(jìn)支持向量機預(yù)測方法及應(yīng)用［J］.中南大學(xué)學(xué)報（自然科學(xué)版），2011，42（9）：2737-2740.

［8］李洋.蛙跳螢火蟲算法及其在含風(fēng)電場的電力系統(tǒng)調(diào)度中的應(yīng)用［D］.上海：華東理工大學(xué)，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

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

（2014-10-12）

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