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

王 凡 董 俊 盧冬鳴 姬生云

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

引 言

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

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

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

1 算法原理介紹及設計

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

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

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

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

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

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

1) 可用頻率

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

2) 解

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

3) 代價函數

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

目標優(yōu)化函數可以用下式表示

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

(1)

目標優(yōu)化函數可以根據用戶需求選取其中一項或幾項之和.

4) 鄰集

給定一個當前解S0，它的鄰集V的解定義如下：給定一個新解SN，SN與S0相鄰當且僅當

(2)

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

5) 新解產生方法

為了遍歷所有鄰域解，用一個隨機搜索過程產生當前解S=的新解.

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

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

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

6) 新解接受準則

對于一個新解，根據Metropolis抽樣準則[16]來判斷是否接受新解，即在每一次迭代過程中，從當前解S0的鄰集中選取一個SN，若cost(SN)

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

≥Rand[0,1],

(3)

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

7) 退火過程

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

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

模擬退火算法的全局搜索性能也與退火速度密切相關.一般來說，同一溫度下的“充分”搜索(退火)是相當必要的，但這需要計算時間.實際應用中，要針對具體問題的性質和特征設置合理的退火平衡條件，本算法使用的退火函數為

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

(4)

其中，α表示降溫速度.

8) 終止準則

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

a) 設計終止溫度的閉值；

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

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

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

2 參數設置分析

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

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

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

圖2 不同降溫速度代價值變化曲線圖

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

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

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

圖3 不同初溫代價值變化曲線圖

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

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

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

圖4 不同終止溫度代價值變化曲線圖

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

4) 內循環(huán)次數對算法的影響

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

圖5 不同內循環(huán)次數時代價值變化曲線圖

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

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

3 算法對比分析

3.1 搜索效率和精度分析

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

圖6 代價(干擾)變化曲線對比圖

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

3.2 穩(wěn)定性分析

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

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

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

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

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

4 結 論

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

[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] 王 景, 王振家, 范曉光. 頻率分配算法及性能的仿真評估[C]//中國電子學會電子系統(tǒng)工程分會第五屆軍事信息軟件與仿真學術研討會論文集, 2006: 408-411.

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