基于混合粒子群優(yōu)化的頻率指配方法研究

薛寒+劉培國+黃紀(jì)軍

摘 要： 建立適用于頻率指配問題的數(shù)學(xué)模型，將電磁兼容性分析的各類因素轉(zhuǎn)化為約束條件，使得電磁兼容問題可以被定量描述，并在此基礎(chǔ)上構(gòu)建了代價函數(shù)。采用粒子群優(yōu)化算法來解決頻率指配的問題，在算法的迭代過程中引入了遺傳算法思想，加入了自然選擇和雜交的手段。仿真證明算法能夠達(dá)到較快的收斂速度，并有一定的避免陷入局部最優(yōu)的能力。

關(guān)鍵詞： 頻率指配模型； 粒子群優(yōu)化； 遺傳算法； 自然選擇

中圖分類號： TN911?34 文獻標(biāo)識碼： A 文章編號： 1004?373X（2015）16?0001?03

Method for frequency assignment based on hybrid particle swarm optimization algorithm

XUE Han1， 2， LIU Peiguo1， HUANG Jijun1

（1. College of Electronic Science and Engineering， National University of Defense Technology， Changsha 410073， China；

2.Unit 63893 of PLA， Luoyang 471003， China）

Abstract： A mathematical model suitable for frequency assignment is built in this paper， in which certain factors affecting the electromagnetic environment are transformed to the constraints， and then the cost function is constructed， to make the electromagnetic environment to be described quantitatively. Hybrid particle swarm optimization algorithm is used to solve the problem of frequency assignment， in which the thought of genetic algorithm is introduced， and natural selection and hybridization means are added in the iterative process. The simulation results indicate that the algorithm converges quickly and has a certain capability to avoid its falling into local optimum.

Keywords： frequency assignment model； particle swarm optimization； genetic algorithm； natural selection

0 引 言

在現(xiàn)代戰(zhàn)爭中，制信息權(quán)已和制空權(quán)、制海權(quán)一樣成為獲取戰(zhàn)場主動權(quán)的決定要素之一，而靈活高效的電磁頻譜管理，可以在爭奪制信息權(quán)過程中發(fā)揮至關(guān)重要的作用。頻率指配（Frequency Assignment）是給無線電設(shè)備指定具體的使用頻率的過程，是電磁頻譜管理的重要內(nèi)容和最終體現(xiàn)[1] ，頻譜管理的目標(biāo)是從頻域、時域、空域和能域上實現(xiàn)電子信息系統(tǒng)內(nèi)的所有設(shè)備都可兼容使用。在現(xiàn)今的信息對抗訓(xùn)練場上，合理高效的頻率指配方案可以極大地提高訓(xùn)練效果，更高效地提升信息作戰(zhàn)部隊的戰(zhàn)斗力。

頻率指配的技術(shù)目前已成為國內(nèi)外研究的重點之一 [2]，對于使用各類優(yōu)化算法來解決頻率指配問題也有了很多的研究成果[3]。本文擬從頻率指配問題模型的建立和混合了遺傳算法思想的粒子群優(yōu)化算法研究兩方面來探討頻率指配的問題，探討算法的改進方法，以解決實際問題[4?5]。

1 頻率指配問題模型

建立頻率指配問題的數(shù)學(xué)模型，要充分考慮設(shè)備參數(shù)、電波傳播、地形等因素，參考實際的硬性約束如需優(yōu)先確保用頻的裝備等，來進行電磁兼容性分析，將分析結(jié)果轉(zhuǎn)化為數(shù)值約束條件，形成適用于優(yōu)化算法計算的數(shù)學(xué)模型。

1.1 約束條件

考慮多種干擾（同頻干擾、鄰頻干擾、互調(diào)干擾），分別建立相應(yīng)的干擾約束矩陣，用矩陣中的元素代表其行列所代表的設(shè)備間的兩兩約束關(guān)系，這樣可以建立同頻干擾約束矩陣A、鄰頻干擾約束矩陣B、互調(diào)干擾約束矩陣C。假設(shè)A中某元素aij為1，表示設(shè)備i和j不能指配相同頻率；反之若元素aij為0，則表示設(shè)備i和j沒有此約束關(guān)系。而模型中的各種約束關(guān)系的獲得，便需要綜合考慮各類因素進行電磁兼容性分析得到。約束矩陣的密度（即其中非零元素的多少）可以表示網(wǎng)絡(luò)的復(fù)雜度，非零元素越多，代表網(wǎng)絡(luò)各臺站間約束關(guān)系越多，電磁環(huán)境越惡劣。

對于同頻干擾，表明一對用頻設(shè)備間除非有足夠的間距或者有合適的地形因素，否則不能指配相同的頻率。具體講，如果f（i）和f（j）分別表示指配給設(shè)備i和j（i≠j）的頻率，那么可以用f（i）-f（j）≠0來表示他們的同頻干擾約束關(guān)系。同頻干擾矩陣A為N×N的矩陣，N為設(shè)備數(shù)，若aij為1則代表設(shè)備i和j有同頻干擾約束，需要滿足f（i）-f（j）≠0才可以[6]。

對于鄰頻干擾，與同頻干擾類似，表明一對設(shè)備在一定的因素下不能指配相鄰的頻率。同樣用f（i）和f（j）分別表示指配給設(shè)備i和j（i≠j）的頻率，那么約束關(guān)系變?yōu)閇fi-fj]≥m，其中m是鄰頻干擾的約束頻率間隔，鄰頻干擾矩陣B也為N×N的矩陣，若bij為1則代表設(shè)備i和j有鄰頻干擾約束，需要滿足[fi-fj]≥m。

對于互調(diào)干擾，矩陣的維數(shù)要高一些，因為條件中同時涉及的頻率不止2個。例如三階Ⅰ型互調(diào)，其約束條件為2 f（i）-f（j）≠f（m），相應(yīng)的矩陣C變?yōu)槿S；又如三階Ⅱ型互調(diào)，其約束條件為f（i）+f（j）-f（m）≠f（n），相應(yīng)的矩陣C變?yōu)樗木S。

1.2 代價函數(shù)

結(jié)合約束矩陣和同頻、鄰頻、互調(diào)的約束條件，設(shè)α，β，γ為分別為同頻干擾、鄰頻干擾、互調(diào)干擾的懲罰因子，即各種干擾的權(quán)值。用E（s）表示指配方案s的干擾代價，那么可以得出：[E（s）=αi=1Nj=i+1Naij+βi=1Nj=i+1Nbij+ γi=1Nj=1Nm=1Nn=1Ncijmn-i=1Nm=1Nciimm] （1）

事實上，式（1）代表的便是在指配方案s下違反同頻、鄰頻、互調(diào)3種約束條件的代價函數(shù)的加權(quán)和。

2 基于混合粒子群優(yōu)化的指配算法

2.1 基于遺傳的混合粒子群優(yōu)化算法

粒子群優(yōu)化算法（Particle Swarm Optimization， PSO）是一種進化計算技術(shù)，由Eberhart博士和Kennedy博士發(fā)明，源于對鳥群捕食的行為研究。PSO算法首先初始化一群隨機粒子，粒子們追隨當(dāng)前的最優(yōu)粒子在解空間中進行搜索，通過迭代獲得最優(yōu)解[7]。

設(shè)d維空間中粒子i的位置和速度為Xi=（xi，1，xi，2，…，xi，d）和Vi=（vi，1，vi，2，…，vi，d）在每一次迭代中，粒子依據(jù)粒子本身所找到的最優(yōu)解pbest，Pi=（pi，1，pi，2，…，pi，d）以及整個種群目前的全局最優(yōu)解gbest，Pg來更新自己的速度和位置，更新公式如下：

[vi，j（t+1）=wvi，j（t）+c1r1pi，j-xi，j（t）+c2r2pg，j-xi，j（t）] （2）

[xi，j（t+1）=xi，j（t）+vi，j（t+1）， i，j=1，2，…，d] （3）

式中：w為慣性權(quán)重；c1和c2為正的學(xué)習(xí)因子；r1和r2為（0，1）均勻分布的隨機值。算法性能在很大程度上取決于算法的控制參數(shù)如粒子數(shù)、最大速度、學(xué)習(xí)因子、慣性權(quán)重等，參數(shù)的選擇依據(jù)實際問題來靈活決定。

混合粒子群算法指的是借鑒其他一些智能優(yōu)化算法思想而形成的粒子群算法，比如應(yīng)用比較廣泛的模擬退火、遺傳、神經(jīng)網(wǎng)絡(luò)以及蟻群等智能算法，每種智能算法都有其特色和優(yōu)點，因而就形成了各類改進的混合智能算法[8]。

本文中借鑒遺傳算法中的選擇機制，可以在每次迭代中，用群體中較好的部分粒子替換較差的部分粒子，這樣可以提高算法收斂的效率，同時為了避免陷入局部最優(yōu)，借鑒遺傳算法中的雜交概念，選取指定數(shù)量的粒子放入雜交池內(nèi)，池中粒子兩兩隨機雜交產(chǎn)生子代（child）粒子，用子代粒子替換親代（parent）粒子。子代的位置由親代位置進行交叉得到：

[childx=p?parent1x+1-p?parent2x] （4）

或者：

[childx=1-p?parent1x+p?parent2x] （5）

式中p為（0，1）范圍的隨機數(shù)。

子代的速度由下式得到：

[childv=parent1v+parent2vparent1v+parent2vparent1v] （6）

或者

[childv=parent1v+parent2vparent1v+parent2vparent2v] （7）

2.2 基于遺傳的混合粒子群優(yōu)化的頻率指配

2.2.1 粒子編碼

本文中使用整數(shù)方式對頻率進行編碼，將所有可用頻點按照頻率值由小到大的順序進行整數(shù)編號。假設(shè)地域內(nèi)有用頻設(shè)備N臺，每一個用頻設(shè)備i的頻率為正整數(shù)fi（i=1，2，…，N），他們的可用頻率范圍形成N個整數(shù)子集。每一個指配方案f=（f1，f2，…，fN）表示為一個正整數(shù)序列。例如，可用的頻點為30個，編號1～30，地域內(nèi)用頻設(shè)備5臺，指配方案f=（4，9，14，25，3）就表示編號為1～5的用頻設(shè)備分別被指配了編號4，9，14，25，3的頻率點。算法中可以將一個指配方案看作一個粒子，這樣的編碼方式一來清晰易于理解，二來解碼非常方便。

2.2.2 適應(yīng)度函數(shù)

本文設(shè)計的算法在編程中是以適應(yīng)度函數(shù)Fitness（x）的最小值為優(yōu)化目標(biāo)的，因而適應(yīng)度函數(shù)的設(shè)置可以直接使用第1節(jié)所建立問題模型中的代價函數(shù)，即有：

[Fitness（x）=αi=1Nj=i+1Naij+βi=1Nj=i+1Nbij+ γi=1Nj=1Nm=1Nn=1Ncijmn-i=1Nm=1Nciimm] （8）

式中：自變量x（向量）即表示一種指配方案f；x[i]代表給設(shè)備i所指配的編碼后頻率。

2.2.3 算法初始化

基本粒子群算法中粒子的初始位置和速度是隨機生成的，也即是在可用頻率子集內(nèi)隨機抽取。為了使算法在初始階段的適應(yīng)度函數(shù)盡可能的最優(yōu)，應(yīng)使粒子群在初始階段盡可能地分散，同時也可以盡可能地消除確保在初始階段各個用頻設(shè)備的同頻沖突和鄰頻沖突。這樣可以大大加快在算法開始階段的收斂速度。

2.2.4 粒子群更新

按照基本粒子群優(yōu)化算法的原理，評價完成每個粒子的適應(yīng)度之后，將當(dāng)前各粒子的位置和適應(yīng)度存儲在各自的pbest中，將所有的pbest中適應(yīng)度最優(yōu)的個體位置和適應(yīng)度存儲在gbest中。按照式（2）和式（3）更新粒子速度與位置后，對于每個粒子將其適應(yīng)值與其經(jīng)歷過的最好位置作比較，并更新當(dāng)前最好位置，接著比較當(dāng)前所有pbest與gbest的至，更新gbest。

根據(jù)2.1中引入遺傳算法自然選擇的機理，在每次粒子迭代過程中，將整個粒子群按照適應(yīng)值進行排序，用群體中最好的一半粒子替換最差的一半的位置和速度，同時保留原來每個個體所記憶的歷史最優(yōu)值；而為防止算法陷入局部最優(yōu)，按照雜交的概率選取粒子進入雜交池，雜交池中的親代（parent）粒子根據(jù)式（4）和式（5）進行交叉獲得子代粒子的位置，根據(jù)式（6）和式（7）交叉獲得子代粒子的速度，并替換親代中的父代（parent1）粒子。

3 仿真實驗與結(jié)果分析

算法采用64位的Matlab編程實現(xiàn)，系統(tǒng)環(huán)境為64位Windows 8.1操作系統(tǒng)。仿真實驗中設(shè)備數(shù)量設(shè)為6臺，頻率設(shè)為12個。也即是自變量個數(shù)設(shè)為6，可用頻率值為1～12的整數(shù)。粒子個數(shù)設(shè)為20，慣性權(quán)重取0.7，學(xué)習(xí)因子取2，雜交池大小比例為0.2，雜交概率取0.9。一般情況下3種干擾要素中同頻干擾的影響相對較大，因而在仿真中給其更多的關(guān)注，這里將同頻、鄰頻、互調(diào)干擾的懲罰因子分別取為3，2，1。

為了體現(xiàn)算法的優(yōu)點，這里同樣利用基本粒子群算法，在相同的參數(shù)條件下對問題進行了仿真，觀察隨著迭代次數(shù)的增加，代價函數(shù)的變化情況，結(jié)果如圖1所示。

圖1 算法仿真結(jié)果

圖1（a）為基本粒子群優(yōu)化算法的一次結(jié)果，圖1（b）為混合粒子群優(yōu)化算法的一次結(jié)果。仿真結(jié)果表明在絕大多數(shù)情況下，本文所用的算法算法可以在15次迭代以內(nèi)得到最優(yōu)結(jié)果。與基本粒子群算法相比，收斂性能更優(yōu)，且具有一定的防止陷入局部最優(yōu)的能力。

4 結(jié) 論

本文針對頻率指配問題，進行了適用于優(yōu)化算法的數(shù)學(xué)建模，并利用混合的粒子群優(yōu)化算法對問題進行了求解。在算法設(shè)計中，參考遺傳算法的自然選擇思想和交叉的概念，在基本粒子群算法的迭代過程中加入了粒子群替換和雜交的策略，結(jié)合仿真實驗證明了本文的優(yōu)化算法不僅具有較好的收斂性能，而且可以避免計算陷入局部最優(yōu)。

參考文獻

[1] 王先義，陳丹俊，劉斌，等.復(fù)雜電磁環(huán)境戰(zhàn)場頻譜管理[J].中國電子科學(xué)研究院學(xué)報，2008（4）：338?344.

[2] US Department of Defense. Joint Spectrum Vision 2010 [R]. Washington， DC： US Department of Defense， 1999.

[3] 湯毅.頻率指配算法的研究與應(yīng)用[D].長沙：國防科技大學(xué)，2008.

[4] 楊奎.一種基于離散粒子群優(yōu)化的戰(zhàn)場動態(tài)頻譜指配策略[J].電訊技術(shù)，2012，52（5）：755?760.

[5] 孫健，劉慧霞，席慶彪.基于改進粒子群算法的多UAV 協(xié)同偵察任務(wù)規(guī)劃[J].現(xiàn)代電子技術(shù)，2012，35（7）：12?15.

[6] 肖劍.無線電磁頻率管理中頻率指配技術(shù)的研究[D].長沙：中南大學(xué)，2012.

[7] 龔純，王正林.精通Matlab最優(yōu)化計算[M].北京：電子工業(yè)出版社，2014.

[8] 陳自衛(wèi)，石雄.基于遺傳算子的粒子群算法在戰(zhàn)場頻率分配中的應(yīng)用[J].艦船電子工程，2010，30（3）：73?76.

[9] 霍元杰.戰(zhàn)場頻譜態(tài)勢感知及頻譜籌劃系統(tǒng)[J].電訊技術(shù)，2013，53（10）：1265?1268.

[10] 王新增，劉佳楠，肖金保，等.基于粒子群算法的電磁頻率分配方法研究[J].現(xiàn)代電子技術(shù)，2013，36（17）：5?8.

[11] 邵立杰.AIS海上電波傳播模型研究[D].大連：大連海事大學(xué)，2014.