混合智能優(yōu)化頻率指配算法

王 凡 董 俊 盧冬鳴 姬生云

(1．電子信息系統(tǒng)復(fù)雜電磁環(huán)境效應(yīng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，河南 洛陽(yáng) 471003；2．中國(guó)電波傳播研究所，山東 青島 266107)

引 言

作為電磁頻譜管理的核心技術(shù)之一，頻率指配(Frequency Assignment)是指對(duì)無(wú)線電設(shè)備指定具體使用頻率，以確保其可以在復(fù)雜的電磁環(huán)境中有效、兼容地工作，是實(shí)行頻譜管理的最終體現(xiàn)[1].頻率指配問(wèn)題在本質(zhì)上講屬于組合優(yōu)化問(wèn)題，是一個(gè)非確定多項(xiàng)式完全(Nondeterministic Polynomial Complete, NPC)問(wèn)題[2]，算法運(yùn)算時(shí)間會(huì)隨問(wèn)題規(guī)模增大成指數(shù)級(jí)“爆炸性”遞增.在早期，由于用頻設(shè)備數(shù)量較少且工作方式較為簡(jiǎn)單，故解決這種小規(guī)模網(wǎng)絡(luò)的頻率指配問(wèn)題并不十分困難，采用傳統(tǒng)的人工分段劃分、窮取法等即可解決.隨著無(wú)線通信技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，各種無(wú)線電業(yè)務(wù)對(duì)頻譜資源的需求迅速增長(zhǎng)，頻率指配問(wèn)題的難點(diǎn)已經(jīng)轉(zhuǎn)化為如何在有限的時(shí)間內(nèi)為大規(guī)模的復(fù)雜網(wǎng)系找到高質(zhì)量的解，傳統(tǒng)方法已經(jīng)難以有效解決.

智能優(yōu)化算法的提出為上述問(wèn)題提供了解決方案.智能優(yōu)化算法，多源于人工智能領(lǐng)域[3-10]，其實(shí)質(zhì)是一種搜索規(guī)則或過(guò)程，它基于某種思想或機(jī)制，也可以是多種思想的結(jié)合，主要思路是采取確定或概率的方法，控制搜索空間的指數(shù)膨脹，在合理的時(shí)間內(nèi)給出最優(yōu)解或次優(yōu)解.由于頻率指配問(wèn)題的困難性，目前國(guó)內(nèi)外學(xué)者研究了大量利用智能優(yōu)化算法解決頻率指配問(wèn)題的技術(shù)[11-14]，包括：禁忌搜索(Tabu Search，TS)算法、模擬退火(Simulated Annealing，SA)算法、遺傳算法(Genetic Algorithm，GA)、蟻群算法(Ant Colony Algorithms，ACO)等.由于各種智能優(yōu)化算法各有優(yōu)缺點(diǎn)，根據(jù)各算法的特點(diǎn)，將兩種乃至兩種以上的智能優(yōu)化算法相結(jié)合的混合算法通常具有更佳的優(yōu)化效果[15].

本文提出了一種結(jié)合禁忌搜索和模擬退火算法優(yōu)點(diǎn)的混合智能優(yōu)化算法來(lái)解決頻率指配問(wèn)題，仿真結(jié)果表明，該方法可有效提升搜索效率和精度，魯棒性強(qiáng)，優(yōu)于兩種算法單獨(dú)應(yīng)用的情況.

1 算法原理介紹及設(shè)計(jì)

1.1 模擬退火和禁忌搜索算法原理介紹

模擬退火算法的出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性，在某一初溫下，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即能夠跳出局部最優(yōu)解并最終趨于全局最優(yōu)解，具有解質(zhì)量高、魯棒性強(qiáng)、通用易實(shí)現(xiàn)等優(yōu)點(diǎn)[12].

禁忌搜索算法模仿人類(lèi)的記憶功能，通過(guò)對(duì)一些局部最優(yōu)解的禁忌達(dá)到接納一部分較差解，從而跳出局部搜索；通過(guò)引入一個(gè)靈活的存儲(chǔ)結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來(lái)避免迂回搜索；同時(shí)赦免禁忌區(qū)域中的一些優(yōu)良狀態(tài)，進(jìn)而保證搜索的多樣性，從而達(dá)到全局最優(yōu)[11].

1.2 混合智能優(yōu)化頻率指配算法設(shè)計(jì)

模擬退火算法在局部極小解處有機(jī)會(huì)跳出并最終趨于全局最優(yōu)的根本原因是通過(guò)概率判斷來(lái)接受新?tīng)顟B(tài)，這在理論上也已得到嚴(yán)格證明，即當(dāng)初溫充分高、降溫足夠慢、各溫度下抽樣次數(shù)足夠多、最終溫度趨于零時(shí)，算法最終以概率1收斂到全局最優(yōu)解[16].一般來(lái)說(shuō)，模擬退火算法為尋求最優(yōu)解，通常要求較高的初溫、較慢的降溫速度、較低的終止溫度以及熱平衡時(shí)間足夠長(zhǎng)(即各溫度下足夠多次的抽樣)，因而模擬退火算法的特點(diǎn)是全局優(yōu)化能力強(qiáng)，但往往優(yōu)化過(guò)程較長(zhǎng).且由于概率突跳特性，模擬退火算法會(huì)接受性能較差的解，所以其最終解可能比運(yùn)算過(guò)程中遇到的最好解性能差.考慮禁忌搜索算法具有記憶功能的優(yōu)點(diǎn)，且局部?jī)?yōu)化能力強(qiáng)，搜索速度快的特點(diǎn)，故將模擬退火算法和禁忌搜索算法的優(yōu)點(diǎn)相結(jié)合，提出一種混合智能優(yōu)化頻率指配算法(SA-TS)，主體結(jié)構(gòu)采用模擬退火算法，為避免搜索過(guò)程中由于執(zhí)行概率接受環(huán)節(jié)而遺失當(dāng)前遇到的最優(yōu)解，增加禁忌搜索算法的記憶功能，通過(guò)增加存儲(chǔ)環(huán)節(jié)，在算法搜索過(guò)程中保留中間最優(yōu)解，并即時(shí)更新.

下面闡述混合智能優(yōu)化算法應(yīng)用到具體的頻率指配問(wèn)題中各要素的設(shè)計(jì)：

1) 可用頻率

設(shè)當(dāng)前指配中可用的頻率資源為：F=(f1,f2,…,fNF)，可用頻率數(shù)為NF.

2) 解

用S=表示，其中fs(v)表示指配給鏈路v的頻率，鏈路數(shù)為N.

3) 代價(jià)函數(shù)

在頻率指配過(guò)程中，代價(jià)函數(shù)(即目標(biāo)優(yōu)化函數(shù))cost(S)可以包含以下幾項(xiàng)：違背約束懲罰值evio；(即不滿(mǎn)足約束關(guān)系的指配頻率的代價(jià)值)；指配解的最高頻率flarge和最低頻率fsmall之差；所用不同頻率的數(shù)目eorder.代價(jià)函數(shù)值在算法運(yùn)行過(guò)程中隨著迭代步數(shù)的變化而變化，算法的最終目標(biāo)是使cost(S)達(dá)到最小，即min(cost(S)).

目標(biāo)優(yōu)化函數(shù)可以用下式表示

cost(S)=μ1evio+μ2(flarge-fsmall)+μ3eorder.

(1)

目標(biāo)優(yōu)化函數(shù)可以根據(jù)用戶(hù)需求選取其中一項(xiàng)或幾項(xiàng)之和.

4) 鄰集

給定一個(gè)當(dāng)前解S0，它的鄰集V的解定義如下：給定一個(gè)新解SN，SN與S0相鄰當(dāng)且僅當(dāng)

(2)

此鄰集中的解表示當(dāng)前解有且僅有一條鏈路改變頻率，故當(dāng)前解S0共有N(NF-1)個(gè)鄰域解.這樣構(gòu)造鄰域結(jié)構(gòu)能夠提高效率，每次產(chǎn)生新解時(shí)只更新一個(gè)鏈路的頻率，以免一次更新多個(gè)鏈路的頻率, 使得在某些鏈路找到最優(yōu)頻率的同時(shí), 其它一些已經(jīng)處在最優(yōu)頻率的鏈路又更換了頻率, 很難使所有鏈路同時(shí)找到最優(yōu)頻率.

5) 新解產(chǎn)生方法

為了遍歷所有鄰域解，用一個(gè)隨機(jī)搜索過(guò)程產(chǎn)生當(dāng)前解S=的新解.

a) 隨機(jī)選擇一條鏈路v，(v∈[1,2,…,N])；

b) 隨機(jī)選擇一個(gè)新頻率fi，(i∈[1,2,…,NF])；

c) 將新頻率fi指配給鏈路v，且不同于鏈路v的舊頻率.

6) 新解接受準(zhǔn)則

對(duì)于一個(gè)新解，根據(jù)Metropolis抽樣準(zhǔn)則[16]來(lái)判斷是否接受新解，即在每一次迭代過(guò)程中，從當(dāng)前解S0的鄰集中選取一個(gè)SN，若cost(SN)

min{1,exp[-[cost(SN)-cost(S0)]/t(k)]}

≥Rand[0,1],

(3)

其中: Rand[0,1]為0到1之間的隨機(jī)變量;t(k)表示退火函數(shù).

7) 退火過(guò)程

a) 溫度變化周期：每M(即內(nèi)循環(huán)次數(shù))次迭代之后使溫度下降；

b) 溫度下降策略及退火速度設(shè)置.

模擬退火算法的全局搜索性能也與退火速度密切相關(guān).一般來(lái)說(shuō)，同一溫度下的“充分”搜索(退火)是相當(dāng)必要的，但這需要計(jì)算時(shí)間.實(shí)際應(yīng)用中，要針對(duì)具體問(wèn)題的性質(zhì)和特征設(shè)置合理的退火平衡條件，本算法使用的退火函數(shù)為

t(k+1)=α·t(k),0<α<1,

(4)

其中，α表示降溫速度.

8) 終止準(zhǔn)則

所設(shè)計(jì)的終止準(zhǔn)則由以下兩個(gè)元素組成，當(dāng)溫度降低到低于終止溫度tm時(shí)且當(dāng)搜索到的最優(yōu)解連續(xù)若干次循環(huán)均保持不變時(shí)，算法停止運(yùn)行.

a) 設(shè)計(jì)終止溫度的閉值；

b) 算法搜索到的最優(yōu)值連續(xù)若干次循環(huán)保持不變.

混合智能優(yōu)化頻率指配算法流程如圖1所示.

圖1 混合智能優(yōu)化頻率指配算法流程圖

2 參數(shù)設(shè)置分析

對(duì)于智能優(yōu)化算法來(lái)說(shuō)，參數(shù)是影響算法性能的重要因素，下面仿真分析所設(shè)計(jì)的混合智能優(yōu)化頻率指配算法中各參數(shù)變化對(duì)算法性能的影響.其中：α為降溫速度；M為內(nèi)循環(huán)次數(shù)；t0為初始溫度；tm為終止溫度.

1) 降溫速度對(duì)算法的影響

首先，分析降溫速度對(duì)算法運(yùn)行時(shí)間和解的質(zhì)量的影響，仿真參數(shù)為：鏈路條數(shù)為100，可用頻率個(gè)數(shù)為40，約束矩陣復(fù)雜度為0.3(即30%的被指配對(duì)象間存在頻率間隔約束)，初始溫度為10，終止溫度為0.1，內(nèi)循環(huán)次數(shù)為1 000，圖2給出了降溫速度α=0.8和α=0.95時(shí)，SA-TS混合算法頻率指配過(guò)程代價(jià)值隨迭代步數(shù)的變化曲線圖.

圖2 不同降溫速度代價(jià)值變化曲線圖

由仿真結(jié)果可知，從相同的初始解(代價(jià)值為13 820)開(kāi)始優(yōu)化，當(dāng)降溫速度分別為α=0.8和α=0.95時(shí)，得到的最優(yōu)解的代價(jià)值分別為120、60，在相同硬件配置條件下所花費(fèi)的時(shí)間分別為20.080 s、90.453 s.由此可知，降溫速度變慢，可以改善解的質(zhì)量，但相應(yīng)會(huì)較大程度增加算法的運(yùn)算時(shí)間，在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體情況的要求權(quán)衡運(yùn)行時(shí)間和解的質(zhì)量設(shè)置降溫速度.

2) 初始溫度對(duì)算法的影響

下面分析初始溫度對(duì)算法運(yùn)行時(shí)間和解的質(zhì)量的影響，仿真參數(shù)為：鏈路條數(shù)為100，可用頻率個(gè)數(shù)為40，約束矩陣復(fù)雜度為0.3，降溫速度為0.9，終止溫度為0.1，內(nèi)循環(huán)次數(shù)為1 000，圖3給出了初始溫度t0=50和t0=10時(shí)，SA-TS混合算法頻率指配過(guò)程代價(jià)值隨迭代步數(shù)的變化曲線圖.

圖3 不同初溫代價(jià)值變化曲線圖

由仿真結(jié)果可知，從相同的初始解(代價(jià)值為13 820)開(kāi)始優(yōu)化，當(dāng)初始溫度t0=50和t0=10時(shí)，得到的最優(yōu)解的代價(jià)值分別為320、80，在相同硬件配置條件下所花費(fèi)的時(shí)間分別為44.627 s、189.255 s.由圖3可知，當(dāng)初始溫度較高t0=50時(shí)，代價(jià)下降的趨勢(shì)比較緩慢，當(dāng)初始溫度較低t0=10時(shí)，代價(jià)以較快的速度下降，因而可知，代價(jià)降到同一個(gè)水平值，初溫高時(shí)耗時(shí)遠(yuǎn)遠(yuǎn)大于初溫低的耗時(shí).由此可見(jiàn)初始溫度會(huì)影響代價(jià)的下降速度，初始溫度較高時(shí)，運(yùn)行時(shí)間較長(zhǎng)，但解的質(zhì)量并未得到相應(yīng)的改善，故算法不需設(shè)置過(guò)高的初始溫度.

3) 終止溫度對(duì)算法的影響

下面分析終止溫度對(duì)算法運(yùn)行時(shí)間和解的質(zhì)量的影響，仿真參數(shù)為：鏈路條數(shù)為100，可用頻率個(gè)數(shù)為40，約束矩陣復(fù)雜度為0.3，降溫速度為0.9，初始溫度為10，內(nèi)循環(huán)次數(shù)為1 000，圖4給出了終止溫度tm=0.01和tm=0.1時(shí)，SA-TS混合算法頻率指配過(guò)程代價(jià)值隨迭代步數(shù)的變化.

圖4 不同終止溫度代價(jià)值變化曲線圖

由仿真結(jié)果可知，從相同的初始解(代價(jià)值為13 820)開(kāi)始優(yōu)化，當(dāng)終止溫度tm分別為0.01和0.1時(shí)，得到的最優(yōu)解的代價(jià)值分別為220、140，所花費(fèi)的時(shí)間分別為48.484 s、70.505 s，由此可知，降低終止溫度可以得到更好的解，但相應(yīng)地會(huì)增加算法的運(yùn)行時(shí)間，在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體情況的要求權(quán)衡運(yùn)行時(shí)間和解的質(zhì)量設(shè)置終止溫度.

4) 內(nèi)循環(huán)次數(shù)對(duì)算法的影響

下面分析內(nèi)循環(huán)次數(shù)對(duì)算法運(yùn)行時(shí)間和解的質(zhì)量的影響，仿真參數(shù)為：鏈路條數(shù)為100，可用頻率個(gè)數(shù)為40，約束矩陣復(fù)雜度為0.3，初始溫度為10，降溫速度為0.9，終止溫度為0.1，圖5給出了內(nèi)循環(huán)次數(shù)M=2 000和M= 1 000情況下SA-TS混合算法頻率指配過(guò)程代價(jià)值隨迭代步數(shù)的變化曲線圖.

圖5 不同內(nèi)循環(huán)次數(shù)時(shí)代價(jià)值變化曲線圖

由圖5可知，當(dāng)內(nèi)循環(huán)次數(shù)M分別為2 000、 1 000時(shí)，得到的最優(yōu)解的代價(jià)值分別為160、100，所花費(fèi)的時(shí)間分別為48.484 s、95.538 s，由此可知增大內(nèi)循環(huán)次數(shù)可以得到更好的解，但改善不明顯，所花費(fèi)的時(shí)間卻成倍增加，在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體情況的要求權(quán)衡運(yùn)行時(shí)間和解的質(zhì)量設(shè)置內(nèi)循環(huán)次數(shù).

根據(jù)上述內(nèi)容可以得到混合算法參數(shù)設(shè)置的基本規(guī)律及影響效果，在實(shí)際應(yīng)用中，應(yīng)根據(jù)實(shí)際問(wèn)題的規(guī)模、特征等來(lái)設(shè)置算法參數(shù).

3 算法對(duì)比分析

3.1 搜索效率和精度分析

首先，對(duì)模擬退火(SA)、禁忌搜索(TS)、混合智能優(yōu)化(SA-TS)三種頻率指配算法的搜索效率和精度進(jìn)行分析，圖6為SA、TS和SA-TS算法的代價(jià)變化曲線.

圖6 代價(jià)(干擾)變化曲線對(duì)比圖

仿真參數(shù)為：鏈路條數(shù)為100，可用頻率個(gè)數(shù)為40，約束矩陣復(fù)雜度為0.3，SA和SA-TS算法的初始溫度為10，降溫速度為0.9，終止溫度為0.1，內(nèi)循環(huán)次數(shù)為1 000，TS算法的禁忌長(zhǎng)度為20.由仿真結(jié)果可知，SA、TS和SA-TS算法的最優(yōu)解的代價(jià)值分別為100、1 580、110，運(yùn)行時(shí)間分別為91.123 s、46.798 s、47.629 s.因此可知，在相同的初始解前提下，與SA算法相比，SA-TS算法可在遠(yuǎn)小于SA算法的搜索時(shí)間找到優(yōu)化效果差不多的最優(yōu)解，可明顯提高搜索效率；與TS算法相比，在運(yùn)行時(shí)間差不多的情況下，SA-TS可以很大程度地改善指配解的質(zhì)量，提高了搜索精度.

3.2 穩(wěn)定性分析

為了分析算法穩(wěn)定性，分別對(duì)模擬退火(SA)、禁忌搜索(TS)、混合智能優(yōu)化(SA-TS)三種智能優(yōu)化指配算法重復(fù)進(jìn)行100次仿真，各算法仿真參數(shù)同3.1節(jié)，穩(wěn)定性的對(duì)比結(jié)果如圖7所示.

由圖7(a)可知，在100次運(yùn)行結(jié)果中，SA算法得到的指配解的代價(jià)值相對(duì)分散，多集中于代價(jià)值居中的區(qū)域，68%位于298～402，23%位于220～298，9%位于402～480.由圖7(b)可知，TS算法得到的指配解質(zhì)量較差，84%的代價(jià)值位于1 420～2 866，12%位于2 866～5 424，4%位于5 424～ 7 140.由圖7(c)可知，在100次運(yùn)行結(jié)果中，SA-TS混合算法的多數(shù)指配解集中于代價(jià)最低的優(yōu)質(zhì)解附近，84%是代價(jià)值位于40～512的優(yōu)質(zhì)解，14%的代價(jià)值位于512～1 456之間，只有2%的代價(jià)值大于1 792.由此可以看出，SA-TS混合算法的穩(wěn)定性較好，優(yōu)于SA、TS算法.

(a) SA算法100次運(yùn)行結(jié)果最優(yōu)解代價(jià)值分布圖

(b) TS算法100次運(yùn)行結(jié)果最優(yōu)解代價(jià)值分布圖

(c) SA-TS算法100次運(yùn)行結(jié)果最優(yōu)解代價(jià)值分布圖圖7 不同方法最優(yōu)解代價(jià)值分布圖

4 結(jié) 論

針對(duì)模擬退火算法全局優(yōu)化能力強(qiáng)，但優(yōu)化過(guò)程較長(zhǎng)、搜索效率較差的特點(diǎn)，考慮禁忌搜索算法局部?jī)?yōu)化能力強(qiáng)，搜索速度快，且擁有記憶功能的優(yōu)點(diǎn)，提出了一種將二者相結(jié)合的混合智能優(yōu)化頻率指配算法，主體結(jié)構(gòu)采用模擬退火算法，增加禁忌搜索算法的記憶功能，避免模擬退火算法搜索過(guò)程中由于執(zhí)行概率接受環(huán)節(jié)而遺失當(dāng)前最優(yōu)解，通過(guò)增加存儲(chǔ)環(huán)節(jié)，在搜索過(guò)程中保留中間最優(yōu)解，并即時(shí)更新.仿真表明，混合算法可快速得到高質(zhì)量的解，搜索效率和精度優(yōu)于單用模擬退火或禁忌搜索算法，為解決大規(guī)模復(fù)雜網(wǎng)系的頻率指配問(wèn)題進(jìn)行了有益的探索.

[1] DUNKIN N, ALLEN S. Frequency Assignment Problems: Representations and Solutions[R]. London: Royal Holloway, University of London, 1997.

[2] SMITH D H, ALLEN S M, HRULEY S, et al. Frequency Assignment: Methods and Algorithms[R/OL]. 1999[2012-10-27]. ftp://ftp.rta.nato.int/pubfulltext/RTO/MP/RTO-MP-013/$MP-013-$K.pdf

[3] GLOVER F. Tabu search: part I[J]. ORSA Journal on Computing, 1989, 1(3): 190-206.

[4] GLOVER F. Tabu search: part II[J]. ORSA Journal on Computing, 1990, 2(1): 4-32.

[5] KIRKPATRICK S, GELATT Jr C D, VECCHI M P. Optimazation by simulated annealing[J]. Science, 1983, 220(4598): 671-680.

[6]METROPOLIS N, ROSENBLUTH A, ROSENBLUTH M, et al. Equation of state calculations by fast computing machines[J]. Journal of Chemical Physics, 1953, 2: 1087-1092.

[7] HOLLAND J H. Adaptation in Natural and Artificifal System[M]. Cambridge:University of Michigan Press, 1975.

[8] RUDOLPH G. Convergence analysis of canonical genetic algorithms[J]. IEEE Transactions on Neural Networks, 1994, 5(1): 96-101.

[9] DORIGO M. Optimization, Learning and Natural Algorithms[D]. Milano: Politecnico di Milano, 1992.

[10] KENNEDY J, EBERHART R. A new optimizer using particle swarm theory[C]// 6th International Symposium on Micromachine and Human Science. Nagoya, October 4-6, 1995: 39-43.

[11] CASTELINO D J, HURLEY S, STEPHENS N M. A tabu search algorithm for frequency assignment[J]. Annals of Operations Research, 1996, 63(2): 301-319.

[12]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.

[13] 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.

[14] MANIEZZO V, CARBONARO A. An ANTS Heuristic for the frequency assignment problem[J]. Future Generation Computer System, 2000, 16(8): 927-935.

[15] 王 景, 王振家, 范曉光. 頻率分配算法及性能的仿真評(píng)估[C]//中國(guó)電子學(xué)會(huì)電子系統(tǒng)工程分會(huì)第五屆軍事信息軟件與仿真學(xué)術(shù)研討會(huì)論文集, 2006: 408-411.

[16] 汪定偉, 王俊偉, 王洪峰, 等. 智能優(yōu)化方法[M]. 北京: 高等教育出版社, 2007: 136-142.