基于模擬退火算法的頻率指配算法優(yōu)化

王更輝

(中國(guó)電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081)

?

基于模擬退火算法的頻率指配算法優(yōu)化

王更輝

(中國(guó)電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081)

模擬退火算法是最早應(yīng)用于頻率指配的智能算法之一，具有設(shè)計(jì)簡(jiǎn)單、頻率指配合理等優(yōu)點(diǎn)。但在某些具體頻率指配環(huán)境中，模擬退火算法存在運(yùn)算時(shí)間較長(zhǎng)的缺點(diǎn)。通過(guò)分析頻率指配影響算法的條件，深入剖析模擬退火算法在頻率指配中的運(yùn)行機(jī)制，縮小鄰域選擇范圍、引進(jìn)貪婪原則改進(jìn)新解產(chǎn)生方式、增加升溫過(guò)程和初始解重新設(shè)置等方式，對(duì)模擬退火算法在頻率指配中的應(yīng)用進(jìn)行了優(yōu)化，在保證符合頻率指配約束條件的情況下，提升了模擬退火算法的運(yùn)算效率。

模擬退火；頻率指配；貪婪原則

0 引言

隨著現(xiàn)代無(wú)線通信技術(shù)的快速發(fā)展，各種新型無(wú)線通信系統(tǒng)不斷涌現(xiàn)，通信網(wǎng)絡(luò)結(jié)構(gòu)日趨復(fù)雜，無(wú)線通信設(shè)備急劇增加，高速增長(zhǎng)的無(wú)線頻率的需求與有限的頻率資源的矛盾變得更加突出。頻率指配作為研究頻率能夠合理規(guī)劃和有效利用的重要內(nèi)容，就是為每個(gè)通信設(shè)備在規(guī)定的頻率范圍內(nèi)指定一個(gè)合理的工作頻率，使得頻譜整體得以有效利用，并且各個(gè)通信設(shè)備的工作頻率不互相干擾。頻率指配算法作為頻率指配的核心，決定了頻率指配的工作效率和頻率指配結(jié)果的合理性[1]。

1 頻率指配簡(jiǎn)介

頻率指配是優(yōu)化頻率利用、提高信道容量和減少干擾的主要手段，通過(guò)頻率指配將無(wú)線電頻率指定給相應(yīng)的無(wú)線電設(shè)備，使其在規(guī)定的條件下使用。當(dāng)前頻率指配主要應(yīng)用于無(wú)線通信網(wǎng)絡(luò)，其最終目的是在保證網(wǎng)絡(luò)中無(wú)線通信設(shè)備能夠正常通信的情況下，最大限度地提高頻率利用率[2-3]，影響頻率指配的主要因素是頻率干擾和可用頻率。

1.1 頻率干擾

頻率干擾是頻率指配考慮的重要因素，頻率干擾的類型包括：同頻干擾、互調(diào)干擾、雜散干擾和鄰道干擾。同頻干擾是指相鄰2個(gè)或多個(gè)無(wú)線設(shè)備的覆蓋重疊內(nèi)，接收點(diǎn)場(chǎng)強(qiáng)是來(lái)自各無(wú)線設(shè)備信號(hào)場(chǎng)強(qiáng)之和，從而產(chǎn)生了互相干擾?；フ{(diào)干擾是由于不同頻率的2個(gè)或多個(gè)射頻信號(hào)在某臺(tái)無(wú)線設(shè)備經(jīng)非線性作用產(chǎn)生了新的等于另一頻點(diǎn)的頻率分量而引起的干擾，一般情況下，互調(diào)干擾主要考慮二階互調(diào)干擾和三階互調(diào)干擾。雜散干擾主要是指由于無(wú)線設(shè)備中的濾波特性不好，使得一些二次和三次諧波分量在輸出時(shí)產(chǎn)生雜波輻射信號(hào)。鄰道干擾是指相鄰的或鄰近波道之間的干擾。其中雜波干擾和鄰道干擾主要因?yàn)闊o(wú)線設(shè)備的技術(shù)指標(biāo)不合格引起的干擾，因此在頻率指配過(guò)程中主要考慮同頻干擾和互調(diào)干擾。

頻率指配通過(guò)頻率間隔合理利用頻率，避免無(wú)線設(shè)備間的頻率干擾。頻率間隔由工作頻率特性和無(wú)線設(shè)備的技術(shù)指標(biāo)來(lái)決定，對(duì)可用頻率的利用效率產(chǎn)生影響。一般情況下，無(wú)線設(shè)備的技術(shù)指標(biāo)確定了該設(shè)備避免頻率干擾的頻率間隔。

干擾數(shù)據(jù)模型是描述無(wú)線設(shè)備之間頻率干擾約束關(guān)系的模型[4-5]，主要以矩陣的方式進(jìn)行表示。無(wú)線設(shè)備之間的干擾約束關(guān)系函數(shù)如下：

根據(jù)干擾約束關(guān)系，可以得到總的干擾數(shù)目[5]，干擾數(shù)目的目標(biāo)函數(shù)如下：

當(dāng)無(wú)線設(shè)備的數(shù)量確定后，干擾數(shù)目對(duì)頻率指配算法產(chǎn)生影響，隨著干擾數(shù)目的增大，頻率指配算法的效率迅速降低。

1.2 可用頻率

可用頻率是指無(wú)線設(shè)備在指配頻率時(shí)可以使用的頻率。為了保證所有無(wú)線設(shè)備的正常工作，需要對(duì)每類無(wú)線設(shè)備的工作頻率范圍進(jìn)行劃分。并且根據(jù)電磁環(huán)境的復(fù)雜性和有意無(wú)意的電磁干擾，無(wú)線設(shè)備在頻率指配之前需要提前將一些被干擾的頻點(diǎn)進(jìn)行剔除。

Fv=FD-Ff，

式中，F(xiàn)v為頻率指配時(shí)無(wú)線設(shè)備可以使用的頻率，F(xiàn)D為無(wú)線設(shè)備的頻率工作范圍，F(xiàn)v為頻率指配時(shí)無(wú)線設(shè)備禁止使用的頻率，包括電磁環(huán)境中被干擾的頻率、已分配給其他無(wú)線設(shè)備的頻率等。當(dāng)無(wú)線設(shè)備的數(shù)量確定后，可用頻率Fv越多，頻率指配算法的效率越高。

2 基于模擬退火算法的頻率指配算法

2.1 模擬退火算法概述

模擬退火算法最早由Metropolis等人于1953年提出，1983年Kirkpatrick將它應(yīng)用于組合優(yōu)化問(wèn)題[6-7]，Duque等人在1993年首先使用模擬退火算法解決頻率指配問(wèn)題[8]。模擬退火算法是一種基于迭代求解策略的隨機(jī)搜索算法[9]，用于在一個(gè)解空間內(nèi)尋找問(wèn)題最優(yōu)解。模擬退火算法模擬了整個(gè)物理退火過(guò)程：將固體加熱至足夠高的溫度，使固體內(nèi)粒子變?yōu)殡S機(jī)無(wú)序狀態(tài)；然后逐步降溫冷卻，使粒子在每個(gè)溫度下漸趨有序狀態(tài)，達(dá)到平衡；最后在常溫時(shí)，固體粒子達(dá)到穩(wěn)定狀態(tài)。

模擬退火算法的核心是基于Metropolis接受準(zhǔn)則[10]，避免模擬退火算法在搜索過(guò)程中陷入局部最優(yōu)的同時(shí)趨向全局最優(yōu)解，在解空間內(nèi)隨機(jī)選擇最新解，再以Metropolis接受準(zhǔn)則，判斷是否接受最新解替代當(dāng)前解，最終收斂于當(dāng)前最優(yōu)解。

Metropolis接受準(zhǔn)則確定如下：

式中，P為溫度tk下i狀態(tài)向j狀態(tài)轉(zhuǎn)變時(shí)接受j狀態(tài)的概率，f(i)為i狀態(tài)下的能量函數(shù)，f(j)為j狀態(tài)下的能量函數(shù)。

2.2 基于模擬退火算法頻率指配

基于模擬退火算法的頻率指配算法的主要結(jié)構(gòu)如下。

2.2.1 解結(jié)構(gòu)

模擬退火算法的解的結(jié)構(gòu)如下：

2.2.2 評(píng)價(jià)函數(shù)

評(píng)價(jià)函數(shù)是判斷算法取得解的判定標(biāo)準(zhǔn)[11]，主要用于判定解是否滿足頻率指配要求和比較2個(gè)解的優(yōu)劣程度。模擬退火算法的評(píng)價(jià)函數(shù)如下：

2.2.3 鄰域結(jié)構(gòu)

在模擬退火算法中，鄰域結(jié)構(gòu)是最重要的概念之一 。頻率指配中鄰域結(jié)構(gòu)的定義：有當(dāng)前解v0，當(dāng)解空間Vl0中任意解vi有且只有一個(gè)無(wú)線設(shè)備所指配的頻率與當(dāng)前解中的無(wú)線設(shè)備頻率不同，Vl0就是v0的鄰域。算法新解的產(chǎn)生就是在當(dāng)前解的鄰域中隨機(jī)選擇，并不斷重復(fù)這個(gè)過(guò)程。

基于模擬退火算法的頻率指配算法描述如下[12]：

① 初始化算法參數(shù)。設(shè)置初始溫度T、降溫衰減值K(一個(gè)接近于1的常數(shù))、迭代次數(shù)N等參數(shù)。

② 隨機(jī)產(chǎn)生初始解v0為當(dāng)前解V=v0，并計(jì)算當(dāng)前解的代價(jià)Cost(V)。

③ 在當(dāng)前解的鄰域中隨機(jī)選擇解vi，計(jì)算新解的代價(jià)Cost(vi) 。

④ 如果Cost(vi)

⑧若迭代次數(shù)n≥N，則T=T*K。

⑨ 算法是否結(jié)束，是則停止，否則轉(zhuǎn)③。

基于模擬退火算法的頻率指配算法的流程圖如圖1所示。

圖1 基于模擬退火算法的頻率指配算法流程圖

3 算法的分析與優(yōu)化

3.1 算法分析

模擬退火算法應(yīng)用于頻率指配時(shí)能夠收斂到一個(gè)最優(yōu)解，從而獲得無(wú)干擾的頻率解。然而，模擬退火算法是一個(gè)極其耗時(shí)的迭代計(jì)算過(guò)程,理論上算法需要訪問(wèn)無(wú)窮多個(gè)狀態(tài)[13-14],在實(shí)際頻率指配過(guò)程中發(fā)現(xiàn)了以下特性:

① 頻率解的產(chǎn)生隨機(jī)性太大，造成許多不必要的重復(fù)，在整個(gè)迭代過(guò)程中不能快速地收斂，成為算法運(yùn)行耗時(shí)的主要原因。

② 當(dāng)頻率干擾密度較小且頻率資源遠(yuǎn)遠(yuǎn)大于所需頻率時(shí)，能夠快速獲得最優(yōu)頻率解。

③ 當(dāng)頻率干擾密度較大且頻率資源不太充足時(shí)，算法運(yùn)行時(shí)間較長(zhǎng)，甚至陷入局部最優(yōu)，不能獲得最優(yōu)頻率解。

④ 當(dāng)算法能夠獲取最優(yōu)解的情況下，算法結(jié)束時(shí)間的溫度都處于較高位置，即當(dāng)溫度降低到一定程度后算法能夠獲取最優(yōu)解的概率大大降低。

試驗(yàn)表明，初始溫度值為T=10，溫度冷卻衰減函數(shù)K=0.9。獲取最優(yōu)解的概率如表1所示。

表1 不同溫度下獲取最優(yōu)解的概率

3.2 算法優(yōu)化

3.2.1 頻率新解的產(chǎn)生

模擬退火算法新解是從當(dāng)前解的鄰域中隨機(jī)選擇產(chǎn)生的，搜索的解空間很大，新解被拒絕的概率大大增加，在約束條件苛刻時(shí)產(chǎn)生新解將是一個(gè)耗時(shí)的過(guò)程。

本文針對(duì)頻率新解產(chǎn)生進(jìn)行了以下優(yōu)化：

(1)優(yōu)化鄰域結(jié)構(gòu)

針對(duì)上述問(wèn)題，首先重新構(gòu)建當(dāng)前解的鄰域，從而增加新解被接受的概率。

首先，計(jì)算每個(gè)無(wú)線設(shè)備的評(píng)價(jià)函數(shù)，即每個(gè)無(wú)線設(shè)備與其他無(wú)線設(shè)備的干擾評(píng)估。

式中，Cost(vi)為無(wú)線設(shè)備i的評(píng)估函數(shù)，hvi(j)為無(wú)線設(shè)備i與無(wú)線設(shè)備j的違約代價(jià)。

其次，根據(jù)每個(gè)無(wú)線設(shè)備的評(píng)價(jià)函數(shù)確定每個(gè)無(wú)線設(shè)備增加選擇權(quán)重，就是增大評(píng)估函數(shù)大的無(wú)線設(shè)備的選擇權(quán)重。

最后，隨機(jī)選擇一個(gè)無(wú)線設(shè)備，通過(guò)變換其頻率解(其他無(wú)線設(shè)備的頻率不變)組成當(dāng)前解的鄰域，縮小了鄰域范圍。

(2)優(yōu)化新解產(chǎn)生方式

在新解產(chǎn)生過(guò)程中引進(jìn)貪婪算法[15]，通過(guò)在鄰域中多次隨機(jī)選擇頻率解，根據(jù)Metropolis接受準(zhǔn)則，接受選擇的頻率解。產(chǎn)生頻率解的過(guò)程如下：

① 初始化新解為當(dāng)前新解s0，計(jì)算當(dāng)前解的代價(jià)Cost(s0)。

② 隨機(jī)從鄰域中選擇新解si，計(jì)算當(dāng)前解的代價(jià)Cost(si)。

③ 若Cost(s0)≥Cost(si)，則轉(zhuǎn)⑤，否則在(0,1)區(qū)間上產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)ξ。

⑤s0=si，并令Cost(s0)=Cost(si)。

⑥若 完成M次選擇，則將當(dāng)前新解最為最終解返回，否則轉(zhuǎn)②。

在優(yōu)化的新解產(chǎn)生過(guò)程中，選擇次數(shù)M尤其重要，如果M過(guò)大則使模擬退火算法迅速收斂到局部最優(yōu)，M過(guò)小則使模擬退火算法收斂效果不明顯。通過(guò)試驗(yàn)證明M值與可用頻率數(shù)基本一致。

3.2.2 溫度控制和初始解重置

模擬退火算法在溫度較高時(shí)，接受大于當(dāng)前解代價(jià)的新解的概率比較大，從而跳出局部極值，使當(dāng)前狀態(tài)落入包含最優(yōu)解的全局中；而當(dāng)溫度降低時(shí)，接受的概率迅速減小。當(dāng)溫度降低到一定程度，算法只接受比當(dāng)前干擾評(píng)估低的新解，算法最終退化為局部搜索。

初始解是模擬退火算法開始迭代的起點(diǎn)。模擬退火算法是一種“健壯”的算法，初始解的優(yōu)劣不是使算法導(dǎo)出質(zhì)量高的最優(yōu)解必要條件。但初始解是模擬退火算法在解空間中隨機(jī)選取的解，使得各無(wú)線設(shè)備的頻率處于隨機(jī)狀態(tài)。在算法陷入局部最優(yōu)時(shí)可以作為突發(fā)狀態(tài)，重新設(shè)置初始解可以使算法跳出局部搜索。

依據(jù)以上特性，模擬退火算法運(yùn)算過(guò)程中在陷入局域搜索時(shí)通過(guò)重置初始溫度和初始解，使算法的狀態(tài)跳出局部搜索，重新在全局搜索最優(yōu)解，增加獲取最優(yōu)解的概率。

4 算法性能驗(yàn)證

為了驗(yàn)證優(yōu)化后的算法的性能對(duì)比，本節(jié)將在相同的模擬環(huán)境下，通過(guò)運(yùn)行2種算法分別進(jìn)行試驗(yàn)。模擬環(huán)境的條件如下：選用相同的無(wú)線設(shè)備參數(shù)，無(wú)線設(shè)備的數(shù)量為50臺(tái)；計(jì)算無(wú)線設(shè)備的干擾，選取干擾數(shù)目為20、60、100、150、180。

在相同模擬環(huán)境下，當(dāng)無(wú)線設(shè)備的可用頻率數(shù)量為50個(gè)時(shí)，2種算法計(jì)算8次的試驗(yàn)數(shù)據(jù)如表2所示。當(dāng)無(wú)線設(shè)備的可用頻率數(shù)量為75個(gè)時(shí)，2種算法計(jì)算8次的試驗(yàn)數(shù)據(jù)如表3所示。

表2 可用頻率為50個(gè)的性能對(duì)比

表3 可用頻率為75個(gè)的性能對(duì)比

從表3中可以看出，在相同模擬環(huán)境中進(jìn)行頻率指配時(shí)，優(yōu)化的模擬退火算法雖然在干擾數(shù)目少時(shí)出現(xiàn)了性能略微下降，但隨著干擾數(shù)目的增加，優(yōu)化的模擬退火算法的性能比原有算法有了大幅提升，最終能夠穩(wěn)定在一個(gè)可接受的范圍。通過(guò)對(duì)2個(gè)表中的數(shù)據(jù)進(jìn)行對(duì)比，在頻率資源不同的情況下，頻率資源的多少對(duì)優(yōu)化模擬算法的影響要小于對(duì)原有算法的影響。

5 結(jié)束語(yǔ)

針對(duì)基于模擬退火算法的頻率指配算法，通過(guò)頻率干擾模型對(duì)頻率指配算法的影響，對(duì)基于模擬退火算法的頻率指配算法進(jìn)行了深入的分析，主要包括頻率指配解的獲取方法、模擬退火算法的溫度控制和初始解對(duì)最終解的影響。根據(jù)模擬退火算法運(yùn)行機(jī)制的特點(diǎn)，對(duì)基于模擬退火算法的頻率指配算法進(jìn)行了優(yōu)化設(shè)計(jì)。仿真結(jié)果表明，優(yōu)化后的頻率指配算法效率大大提高，盡最大努力避免了頻率指配算法陷入局部最優(yōu)解的可能性。

[1] 丁鮮花,方箭,劉艷潔,等.無(wú)人機(jī)通信鏈路頻率劃分研究[J].無(wú)線電工程,2015,45(5):76-80.

[2] 李銳，周自力，劉松淘，等.一種提高頻普利用率的航空導(dǎo)航臺(tái)站頻率指配算法[J].電訊技術(shù)，2016(12)：1359-1364.

[3] 李軍芳,韓建敏.基于Bertrand博弈論的動(dòng)態(tài)頻譜分配算法[J].無(wú)線電工程,2011,41(8)：44-46.

[4] 譚云婷,熊珊.基于空間相鄰分析的基站數(shù)據(jù)模型與算法研究[J].移動(dòng)通信，2016,40(1)：34-38.

[5] 王海超,王樂,劉杰群,等.基于頻率和時(shí)間的蜂窩間干擾管理方法研究[J].移動(dòng)通信,2016,40(1)：54-58.

[6] 陳浩.遺傳算法在頻率指配問(wèn)題中的應(yīng)用研究[D].北京：北京交通大學(xué)，2009.

[7] Kirkpartrick S，Gelatt C D，Vecchi M P．Optimization by Simulated Annealing[J]．Science，1983，220：671-680．

[8] Duque-Ant on M，Kunz D，Ruber B.Channel Assignment for Cellular Radio Using Simulated Annealing[J].IEEE Transactions on Vehicular Technology,1993,42:14-21.

[9] 朱顥東,鐘勇.一種改進(jìn)的模擬退火算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2009,19(6):32-35.

[10]盧才武,唐曉靈,張志霞,等.計(jì)算智能[M].西安：陜西科學(xué)技術(shù)出版社，2008.

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

[12]陳華根,吳建生,王家林,等.模擬退火算法機(jī)理研究[J].同濟(jì)大學(xué)學(xué)報(bào),2004,32(6):802-805.

[13]王強(qiáng).模擬退火算法的改進(jìn)及其應(yīng)用[J].應(yīng)用數(shù)學(xué),1993,4(3):392-397.

[14]孫坪，吳建軍.直接搜索模擬退火算法的自適應(yīng)改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用，2015，51(23)：31-37.

[15]張超.基于貪婪算法的遙感地面站任務(wù)調(diào)度技術(shù)[J].無(wú)線電工程,2011,41(1)：58-60.

Frequency Assignment Algorithm Optimization Based on Simulated Annealing Algorithm

WANG Geng-hui

(The 54th Research Institute of CETC，Shijiazhuang Hebei 050081，China)

Simulated annealing algorithm is one of the earliest intelligent algorithms applied in frequency assignment，which has the advantages of simple design and reasonable frequency assignment.However，in some specific frequency assignment environments，simulated annealing algorithm has the disadvantage of long run time.In order to optimize the application of simulated annealing algorithm in frequency assignment，a variety of research methods are used in this paper，including analyzing the condition that affects the frequency assignment algorithm，making a deep analysis on the operating mechanism of annealing algorithm in frequency assignment，narrowing the range of neighborhood selection，introducing the greedy principle to improve the way of creating new solutions，adding the process of temperature rising and resetting the initial solution.The operating efficiency of simulated annealing algorithm is promoted while the compliance with frequency assignment constraint condition is ensured.

simulated annealing；frequency assignment；greedy principle

2017-05-18

王更輝(1977—)男，高級(jí)工程師，主要研究方向：通信網(wǎng)絡(luò)管理。

10.3969/j.issn.1003-3114.2017.05.13

王更輝.基于模擬退火算法的頻率指配算法優(yōu)化[J].無(wú)線電通信技術(shù),2017,43(5):57-61.

[ WANG Genghui.Frequency Assignment Algorithm Optimization Based on Simulated Annealing Algorithm[J].Radio Communications Technology，2017,43(5):57-61.]

TP393

A

1003-3114(2017)05-57-5