吳 麒

(中國西南電子技術(shù)研究所，成都 610036)

?

基于蜜源優(yōu)化策略的頻率分配方法*

吳 麒**

(中國西南電子技術(shù)研究所，成都 610036)

為解決頻率分配問題，提出了一種基于蜜源優(yōu)化的頻率分配方法。首先提出了評估干擾程度的計算方法，對傳統(tǒng)人工蜂群算法的引領(lǐng)蜂搜索行為進行改進，并重新設(shè)計跟隨蜂搜索行為，增加選擇性變異操作，以達到增加蜜源多樣性以及降低陷入局部最優(yōu)解可能性的目的。仿真結(jié)果表明，所提算法在搜索效率和穩(wěn)定性上具有明顯優(yōu)勢，能夠在有效時間內(nèi)找到滿足頻率距離約束的頻率分配方案。

頻譜管理；頻率指配；人工蜂群算法；蜜源交叉；選擇性變異

1 引 言

現(xiàn)代戰(zhàn)爭中參與作戰(zhàn)的各種電子設(shè)備越來越多，而這些設(shè)備也將面臨著越來越復(fù)雜的戰(zhàn)場電磁環(huán)境，因此加強電磁頻譜管控在現(xiàn)代戰(zhàn)爭中至關(guān)重要。頻譜管理的目標(biāo)是從頻域、時域、空域和能域上實現(xiàn)戰(zhàn)場上所有設(shè)備都可兼容工作。合理高效的頻率分配可以減少設(shè)備之間的相互干擾，是確保電磁頻譜管控順利實施的重要手段之一。因此，如何采用更加高效準(zhǔn)確的方式來進行頻率分配是當(dāng)今頻譜管理的一個重要研究課題。

頻率分配問題本質(zhì)上是個約束條件下的組合優(yōu)化問題。作為解決最優(yōu)化問題的有效工具，遺傳算法[1-2]、模擬退火算法[3]、粒子群算法[4]已經(jīng)被成功應(yīng)用于頻率分配。然而，上述算法在尋優(yōu)過程中存在收斂時間過長以及極易陷入局部最優(yōu)的缺點。有研究[5-6]結(jié)果表明，與上述算法相比，人工蜂群算法[7](Artificial Bee Colony Algorithm，ABC)不僅更擅長于全局搜索，而且其收斂性能更加優(yōu)異。已有研究[8-9]利用改進蜂群算法對信道分配問題進行了研究，但其蜜源設(shè)計并沒有很好地反映裝備可用頻率的特征，且其簡單采用0或者1對設(shè)備間的干擾影響進行表示也不能準(zhǔn)確量化頻率以及距離對干擾程度的影響。

針對頻率分配問題的特點以及現(xiàn)有研究的缺陷，本文對頻率分配問題準(zhǔn)確進行了建模和描述，然后提出了基于蜜源優(yōu)化策略的人工蜂群算法(Artificial Bee Colony Algorithm based on Honey Source Optimization Strategy,ABCAHSOS)。該算法對引領(lǐng)蜂搜索機制進行了改進，以適應(yīng)頻率分配問題的特點，并設(shè)計了準(zhǔn)確評估干擾程度影響的計算方法，然后利用交叉和選擇性變異操作對蜜源進行優(yōu)化，達到提高搜索效率的目的。仿真結(jié)果表明，該算法在迭代效率、時間效率以及搜索穩(wěn)定性方面比傳統(tǒng)人工蜂群算法更優(yōu)，并能在有效時間內(nèi)找到滿足頻率距離約束的頻率分配方案。

2 問題描述

一般在解決頻率分配時，需要考慮以下3類電磁兼容問題：同信道干擾影響、鄰信道干擾影響、指定頻率距離下的干擾影響[10-11]。同信道頻率距離約束問題是指如果要保證信道間隔為0的兩個無線設(shè)備同時兼容工作，那么其距離必須大于d0；鄰信道頻率距離約束問題是指如果要保證信道間隔為1的兩個無線設(shè)備同時兼容工作，那么其距離必須大于d1；頻率距離約束問題是指如果要保證信道間隔小于某些特定值st(st>1)的兩個無線設(shè)備同時兼容工作，那么其距離必須大于dt(dt

假設(shè)存在n個無線設(shè)備，表示為E=(e1,e2,…,en)，ei表示潛在干擾源，ej表示接收機,dij表示設(shè)備i和j之間的距離，其中1≤i≤n，1≤j≤n，i≠j，當(dāng)前可用信道資源表示為F=(f1,f2,…,fm)，分配給設(shè)備ei和ej的信道分別表示為fl和fk，其中1≤l≤m，1≤k≤m，且m≥n，那么分配信道l的干擾源ei對分配信道k的接收機ej的干擾余量表示為

I(i,l,j,k)=Pi+Gi+Gj-Lb(dij)+R(Δflk)-Sj。

(1)

式中：Pi表示潛在干擾源的發(fā)射功率(dB)；Gi表示在接收機方向的天線增益(dBi)；Gj表示接收機在干擾源方向上的天線增益(dBi)；Lb(dij)表示設(shè)備ei與ej之間距離間隔為dij時的傳播損耗值(dB),dij表示設(shè)備ei與ej之間的距離(km)；Δflk表示設(shè)備ei與ej之間頻率差值，Δflk=fl-fk；Sj表示設(shè)備ej的接收靈敏度值；

(2)

式中：P(fl)表示干擾源ei在分配信道fl時，其等效中頻的功率譜密度；H(fk)表示接收機ej在分配頻率fk時的頻率響應(yīng)。

一般而言，我們更關(guān)注設(shè)備的用頻效能，即設(shè)備間的干擾程度，故應(yīng)該使用設(shè)備間干擾程度而不是干擾余量來評估頻率分配方案的好壞程度。此處，采用5級設(shè)定來對發(fā)射設(shè)備ei與接收設(shè)備ej之間干擾程度E(i,l,j,k)進行描述：

(3)

式中：E0、E1、E2、E3表示每級干擾所對應(yīng)的閾值，E=0表示不存在干擾，E=1表示輕微干擾，E=10表示普通干擾，E=100表示較嚴(yán)重干擾，E=1 000表示嚴(yán)重干擾。對于閾值的具體取值，我們一般根據(jù)工程經(jīng)驗或者外場試驗來進行確定。

頻率分配的目標(biāo)就是在一定的距離約束下，對n個無線設(shè)備(e1,e2,…,en)賦予一組信道，使得相互間的干擾影響最小化。形式化描述方法如下：

(4)

式中：E(i,k,j,l)由公式(3)根據(jù)無線設(shè)備ei和ej之間的頻率距離約束計算得知，且當(dāng)信道fk分配給設(shè)備ei時，a(i,k)的值取為1，否則其值取為0；a(j,l)的取值方式與a(i,k)相同。在公式(3)中，當(dāng)無線設(shè)備ei和ej同為發(fā)射機或接收機時，設(shè)備間不會互相影響，那么直接設(shè)定兩者間的干擾影響E(i,k,j,l)為0。對于頻率分配問題而言，最佳頻率分配方案的干擾影響程度E應(yīng)等于0。

3 基于蜜源優(yōu)化的頻率分配方法

3.1 傳統(tǒng)人工蜂群算法

傳統(tǒng)人工蜂群算法[12]是一種模擬蜜蜂群通過協(xié)作行為尋找蜜源的過程來實現(xiàn)搜尋最優(yōu)解的算法。該算法主要由引領(lǐng)蜂、跟隨蜂、偵察蜂等3個基本角色組成。其基本原理如下：初始時刻，隨機生成一定數(shù)量蜜源，而種群由與蜜源數(shù)量相等的引領(lǐng)蜂和跟隨蜂組成。引領(lǐng)蜂在蜜源周邊進行隨機搜索并根據(jù)貪婪原則對優(yōu)秀蜜源進行選擇。待引領(lǐng)蜂回到蜂巢后，跟隨蜂將根據(jù)引領(lǐng)蜂的跳舞行為獲取蜜源信息，并通過在優(yōu)秀食物源的周邊進行領(lǐng)域搜索，獲取優(yōu)秀食物源。如果跟隨蜂搜尋的新蜜源比之前引領(lǐng)蜂尋找的蜜源更好，那么舊蜜源將被新蜜源替代，同時跟隨蜂將取代引領(lǐng)蜂；反之，則保持不變。當(dāng)某個蜜源的優(yōu)秀程度在指定次數(shù)內(nèi)未被更新，那么該蜜源將被放棄，且相應(yīng)的引領(lǐng)蜂將轉(zhuǎn)變?yōu)閭刹旆?，并開始隨機搜尋新蜜源，待找到新蜜源后，該偵察蜂將轉(zhuǎn)變?yōu)橐I(lǐng)蜂，因此充當(dāng)臨時角色的偵察蜂的數(shù)量始終為1。整個算法的運行流程如圖1所示。

圖1 人工蜂群算法的基本流程Fig.1 The basic flow of artificial bee colony algorithm

3.2 算法設(shè)計

針對傳統(tǒng)人工蜂群算法搜索機制簡單、搜索易陷入局部最優(yōu)解且其引領(lǐng)蜂行為不適應(yīng)戰(zhàn)場頻率分配求解的問題，采用蜜源交叉和選擇性變異機制實現(xiàn)蜜源優(yōu)化，從而達到對傳統(tǒng)人工蜂群算法進行改進的目的。基于蜜源優(yōu)化策略的人工蜂群算法的流程與傳統(tǒng)人工蜂群算法基本保持一致，僅在偵察蜂執(zhí)行搜索后增加選擇性變異操作。

3.2.1 編碼以及初始化

3.2.2 蜜源質(zhì)量評估

在評估一個蜜源(分配方案)質(zhì)量時，需要根據(jù)發(fā)射機、接收機屬性對編碼進行解碼操作，并計算蜜源中發(fā)射機與接收機兩兩之間的干擾程度，從而獲取整個蜜源的干擾程度，即整個頻率分配方案的干擾程度。

根據(jù)一般人工蜂群算法設(shè)定，用于某個蜜源質(zhì)量評估的適應(yīng)函數(shù)如下：

(5)

式中：E(Xi)表示蜜源Xi的優(yōu)秀程度，可通過公式(3)對Xi中的兩兩設(shè)備進行適應(yīng)度值計算得知。某個蜜源的適應(yīng)度值越大，則該頻率分配方案的干擾程度越小，即該蜜源的質(zhì)量也就越優(yōu)秀。

3.3.3 引領(lǐng)蜂行為

(6)

式中：q為整數(shù)，在[1,M]范圍隨機生成，且q≠i；jrand為整數(shù)，在[1,N]范圍隨機生成；rij為[-1,1]范圍內(nèi)的隨機數(shù)。

(7)

3.3.4 跟隨蜂行為

本文采用與普通人工蜂群算法同樣的輪盤賭策略選擇蜜源，但對跟隨蜂搜索行為進行重新設(shè)計，通過蜜源交叉操作加強蜜源區(qū)域的搜索能力。此外，在進行選擇操作之前，利用上代選擇性變異蜜源對本代中的最差蜜源進行替換操作。

3.3.5 偵察蜂行為

假設(shè)存在引領(lǐng)蜂搜尋蜜源的優(yōu)秀程度在l次循環(huán)后仍然沒有更新，則可以認為該蜜源已經(jīng)陷入局部最優(yōu)，應(yīng)該被放棄。此時，該引領(lǐng)蜂將轉(zhuǎn)變角色為偵察蜂，并隨機生成新蜜源，偵察蜂也將隨之變?yōu)橐I(lǐng)蜂。

3.3.6 選擇性變異

對引領(lǐng)蜂對應(yīng)的蜜源進行適應(yīng)度評估，從中挑選適應(yīng)度值最高的優(yōu)秀蜜源并進行拷貝操作得到h。然后，執(zhí)行以下搜索行為：

Step 1 利用公式(1)選出蜜源h中對其他設(shè)備干擾影響最大的設(shè)備d。

Step 2 從可用頻率資源FN中隨機選擇一個信道分配給設(shè)備d，得到新蜜源h′。

Step 3 利用公式(4)評估新蜜源h′的優(yōu)秀程度，如果新蜜源h′的優(yōu)秀程度大于拷貝蜜源h，則執(zhí)行替換操作，并結(jié)束選擇性變異操作；否則，進入下一步。

Step 4 對Step 2是否執(zhí)行10次以上進行判斷，如果是，則不做任何操作并結(jié)束選擇性變異操作；否則，返回Step 2。

3.3.7 終止條件

對目前已經(jīng)搜索到的全局最優(yōu)蜜源進行記錄，并對該蜜源的優(yōu)秀程度是否滿足結(jié)束條件進行判斷。如果滿足，則結(jié)束循環(huán)并輸出結(jié)果；否則,繼續(xù)執(zhí)行引領(lǐng)蜂、跟隨蜂、偵察蜂、選擇性搜索行為，直到到達最大迭代次數(shù)tm。

4 仿真實驗

4.1 仿真場景與參數(shù)設(shè)置

測試時，設(shè)當(dāng)前可用頻率資源帶寬為5 MHz，其中最小頻率間隔為25 kHz。地面站點數(shù)量為100個，隨機分布在300 km×300 km的區(qū)域內(nèi)，且每個地面站點僅有一部無線設(shè)備，功率值在40～60 W之間隨機選擇。圖2為100個設(shè)備位置隨機分布圖。

圖2 設(shè)備位置分布Fig.2 The position of equipment

算法采用C++編碼實現(xiàn)，開發(fā)環(huán)境為Microsoft Visual Studio 2010，平臺環(huán)境為Windows XP Professional SP 3操作系統(tǒng)，Intel CoreTM2 Quad CPUQ8400 @2.66 GHz的CPU，內(nèi)存為2 GB。

本文算法(ABCAHSOS)的參數(shù)為，蜜源數(shù)量M=30，迭代最大次數(shù)tm=500，偵察蜂轉(zhuǎn)變?yōu)橐I(lǐng)蜂的限制條件l=10，蜜源交叉概率Pc=0.2；對比測試算法為傳統(tǒng)人工蜂群算法(ABC)，除不使用交叉概率外，其余參數(shù)與本文算法(ABCAHSOS)相同。為了測試方便，上述的參數(shù)主要根據(jù)已有研究成果進行設(shè)置。在實際應(yīng)用過程中，可以針對蜜源數(shù)量M、限制條件l、交叉概率Pc不同取值對算法性能影響效果進行研究，并根據(jù)實際問題的規(guī)模、應(yīng)用限制等進行參數(shù)最優(yōu)設(shè)置，對于參數(shù)優(yōu)化問題，將留到后續(xù)工作中進行。

在進行搜索穩(wěn)定性以及時間消耗測試時，除無線設(shè)備位置、屬性等參數(shù)隨機設(shè)置外，其余算法參數(shù)設(shè)置與上述條件相同，以排除實驗隨機性對結(jié)果的影響。

4.2 實驗結(jié)果

圖3描述了在上述仿真場景下，100個設(shè)備的當(dāng)前最優(yōu)分配方案干擾程度值與迭代次數(shù)的關(guān)系。從圖中可以看出，利用ABC算法開始進行頻率分配時，當(dāng)前最優(yōu)方案干擾程度值隨著迭代次數(shù)的增加快速下降。在迭代次數(shù)為82時，當(dāng)前干擾程度值已經(jīng)從最高7 150下降到241。此后，當(dāng)前干擾程度值隨著迭代次數(shù)的增加緩慢下降，直到迭代次數(shù)為207時，該值等于0，此時算法取得最優(yōu)頻率分配方案。對于ABCAHSOS算法而言，其當(dāng)前干擾程度值在整個運行過程中都隨著迭代次數(shù)的增加快速下降。當(dāng)?shù)螖?shù)為19時，當(dāng)前干擾程度值已經(jīng)從最高7 150快速下降到50；當(dāng)?shù)螖?shù)為31時，當(dāng)前干擾程度值等于0，此時算法取得最優(yōu)頻率分配方案。從以上對比可以看出，ABCAHSOS比ABC算法有更高的迭代效率。

圖3 干擾程度演化對比Fig.3 The evolutionary contrast of interference degree between two algorithms

為了對搜索最優(yōu)方案的迭代次數(shù)穩(wěn)定性以及時間效率進行分析，利用同樣的參數(shù)設(shè)置重復(fù)實驗100次，并對搜索最優(yōu)方案的迭代次數(shù)和消耗時間進行記錄。圖4描述了在100次測試中兩種算法搜索最優(yōu)方案的收斂性對比情況。從圖中可以看出，ABC算法找到最優(yōu)分配方案的最小迭代次數(shù)為121，最大迭代次數(shù)為501，平均迭代次數(shù)為280.04，標(biāo)準(zhǔn)差為80.77；ABCAHSOS算法找到最優(yōu)分配方案的最小迭代次數(shù)為31，最大迭代次數(shù)為65，平均迭代次數(shù)為47.49，標(biāo)準(zhǔn)差為7.97。

從以上數(shù)據(jù)可以看出，ABCAHSOS算法的平均迭代次數(shù)遠遠少于ABC算法，且標(biāo)準(zhǔn)差也遠遠低于ABC算法。綜上所述，與ABC算法相比，ABCAHSOS算法在解決頻率分配問題時不僅迭代效率更高，而且其搜索過程穩(wěn)定性更好。

圖4 算法收斂性對比Fig.4 The contrast of astringency between two algorithms

圖5描述了在100次測試中兩種算法搜索最優(yōu)方案所消耗時間的對比情況。從圖中可以看出，傳統(tǒng)人工蜂群算法(ABC)找到最優(yōu)分配方案的最短時間為13 s，最大時間為45 s，平均消耗時間為24.91 s，標(biāo)準(zhǔn)差為7.22；ABCAHSOS找到最優(yōu)分配方案的最短時間為6 s，最大時間為14 s，平均消耗時間為10.39 s，標(biāo)準(zhǔn)差為1.75。

從以上數(shù)據(jù)可以看出，ABCAHSOS算法的平均消耗時間低于ABC算法的一半，其標(biāo)準(zhǔn)差更是遠遠低于ABC算法。綜上所述，與ABC算法相比，ABCAHSOS算法在解決頻率分配問題時不僅平均消耗時間更短，而且其所消耗時間的分布更加穩(wěn)定。

圖5 算法運算時間對比Fig.5 The contrast of duration between two algorithms

5 結(jié)束語

本文提出了一種基于蜜源優(yōu)化策略的頻率分配方法。該方法以傳統(tǒng)人工蜂群算法為基礎(chǔ)，對引領(lǐng)蜂搜索機制進行適應(yīng)性改造，使之更加適合頻率分配問題求解;然后，使用交叉機制對跟隨蜂的搜索行為進行改進，并增加選擇性變異操作，優(yōu)化搜索蜜源過程，從而實現(xiàn)提高搜索效率的目的。仿真結(jié)果表明，本文算法可以快速得到最優(yōu)解，其迭代效率、時間效率、穩(wěn)定性皆優(yōu)于傳統(tǒng)人工蜂群算法，而且其蜜源設(shè)計以及干擾影響計算方法更適應(yīng)頻率分配的實際應(yīng)用場景，可以為解決大量設(shè)備的頻率分配問題提供參考。不過，本文算法性能依賴于算法參數(shù)設(shè)定，后續(xù)將根據(jù)實際問題的規(guī)模、應(yīng)用限制等進行參數(shù)最優(yōu)設(shè)置，以達到進一步提高算法性能的目的。

[1] 徐雪飛，李建華，沈迪，等.基于量子遺傳算法的航空通信頻率動態(tài)分配[J].電訊技術(shù).2015,55(12):1311-1317. XU Xuefei，LI Jianhua，SHEN Di,et al.Dynamic aeronautical communication frequency assignment based on quantum genetic algorithm[J].Telecommunication Engineering,2015,55(12):1311-1317.(in Chinese)

[2] GHOSH S C,SINHA B P,DAS N. Channel assignment using genetic algorithm based on geometric symmetry[J].IEEE Transactions on Vehicular Technology,2003,52(4):860-875.

[3] MANUEL D,DIETMAR K,BERNHARD R. Channel assignment for cellular radio using simulated annealing[J].IEEE Transactions on Vehicular Technology,1993,42(1):14-21.

[4] 薛寒，劉培國，黃紀(jì)軍. 基于混合粒子群優(yōu)化的頻率指配方法研究[J].現(xiàn)代電子技術(shù)，2015,38(16):1-3. XUE Han,LIU Peiguo,HUANG Jijun. Method for frequency assignment based on hybrid particle swarm optimization algorithm[J].Modern Electronics Technique,2005,38(16):1-3.(in Chinese)

[5] 向萬里.混合群體智能優(yōu)化算法及應(yīng)用研究[D].天津：天津大學(xué),2013. XIANG Wanli. Research on hybrid swarm intelligence optimization algorithms with applications[D].Tianjing:Tianjing University,2013.(in Chinese)

[6] 張超群.混合爆炸式人工蜂群算法及應(yīng)用研究[D].上海：東華大學(xué),2015. ZHANG Chaoqun. Research on hybrid explosion-based artificial bee colony algorithm and its applications[D].Shanghai:Donghua University，2015.(in Chinese)

[7] 寧愛平.人工蜂群算法及其在語音識別中的應(yīng)用研究[D].太原：太原理工大學(xué),2013. NING Aiping. Research on artificial bee colony algorithm and its application in speech recognition[D].Taiyuan:Taiyuan University of Technology，2013.(in Chinese)

[8] 劉俊霞，賈振紅，覃錫忠，等.改進人工蜂群算法在信道分配上的應(yīng)用[J].計算機工程與應(yīng)用,2013,49(7):119-122. LIU Junxia，JIA Zhenhong，QIN Xizhong，et al.Application in channel assignment based on improved artificial bee colony algorithm[J].Computer Engineering and Application,2013,49(7):119-122.(in Chinese)

[9] 高珊，馬良，張惠珍.改進人工蜂群算法求解信道分配問題[J].計算機與應(yīng)用化學(xué)，2015,31(1):98-102. GAO Shan，MA Liang，ZHANG Huizhen. Solving frequency assignment problem using an improved bee algorithm[J].Computers and Applied Chemistry,2015,31(1):98-102.(in Chinese)

[10] SMITH D H,TAPLIN R K,HURLEY S. Frequency assignment with complex co-site constraints[J].IEEE Transactions on Electromagnetic Compatibility,2001,43(2):210-218.

[11] 熊健，喻歆.一種基于模因演算法的頻率分配新策略[J].電訊技術(shù),2012,52(5):748-754. XIONG Jian,YU Xin. A new frequency assignment strategy based on memetic algorithm[J].Telecommunication Engineering,2012,52(5):748-754.(in Chinese)

[12] 劉婷.改進人工蜂群算法及其在多用戶檢測中的應(yīng)用[D].天津:天津大學(xué),2013. LIU Ting. Research on improved artificial bee colony and its application in multiuser detection[D].Tianjing:Tianjing University,2013.(in Chinese)

A Frequency Assignment Method Based on Honey Source Optimization Strategy

WU Qi

(Southwest China Institute of Electronic Technology,Chengdu 610036,China)

In order to solve the frequency assignment problem,a frequency assignment method based on the honey source optimization strategy is proposed.To increase the diversity of the honey and reduce the possibility of falling into the local optimal solution,a traditional artificial bee colony algorithm is improved. Firstly,a method to evaluate the interference is proposed. Secondly,the searching behave of leading bee is improved,and searching behave of following bee is redesigned. Finally,selective mutation operation is added after the searching of reconnoitering bee. The simulation results show that the proposed algorithm has more advantages in searching efficiency and stability and can find frequency assignment strategy satisfying frequency-distance constraints with acceptable time consumption.Key words：spectrum management;frequency assignment;artificial bee colony;honey crossing;selective mutation

10.3969/j.issn.1001-893x.2017.07.008

吳麒.基于蜜源優(yōu)化策略的頻率分配方法[J].電訊技術(shù)，2017,57(7):778-783.[WU Qi.A frequency assignment method based on honey source optimization strategy[J].Telecommunication Engineering,2017,57(7):778-783.]

2017-03-17；

2017-06-05 Received date:2017-03-17；Revised date：2017-06-05

TN92

A

1001-893X(2017)07-0778-06

吳 麒(1985—)，男，四川眉山人，2012年于四川大學(xué)獲博士學(xué)位，現(xiàn)為工程師，主要研究方向為數(shù)據(jù)挖掘、通信偵察、信號分選。

Email:acuteleopard@163.com

**通信作者：acuteleopard@163.com Corresponding author：acuteleopard@163.com