一種針對頻率分配問題的改進(jìn)ANTS算法

徐 奇,熊 暉,李 釗,陳大勇

(1.國防科技大學(xué),湖南長沙410073;2.第二炮兵駐石家莊地區(qū)軍事代表室,河北石家莊050081)

0 引言

在現(xiàn)有的頻率分配算法中,模擬退火算法和蟻群算法[1]得到了廣泛應(yīng)用。模擬退火算法在Mettropolis原則的基礎(chǔ)上允許做一些使目標(biāo)函數(shù)增大的“上坡式移動”(Uphill Moves),以便解能從絕大多數(shù)局部駐點(diǎn)中脫離出來,具有快速全局搜索的特性,但它不能利用系統(tǒng)的反饋信息,這導(dǎo)致了過多的無用迭代和求解效率的低下。而ANTS算法通過信息素的積累和更新實(shí)現(xiàn)了分布式、平行搜索和全局收斂,在求解FAP問題時,表現(xiàn)出非常好的特性。但由于在初始階段信息素的缺乏,同樣存在著收斂時間過長的缺點(diǎn),參見文獻(xiàn)[2]。

為了克服每個算法的局限,同時充分利用它們的優(yōu)點(diǎn),本文提出了一種新的針對FAP問題的算法。首先,利用模擬退火算法在規(guī)定時間里求解FAP問題,利用它的快速收斂特性獲得一組次優(yōu)解。然后,利用獲得的次優(yōu)解來分配初始的信息素。最后,利用ANTS算法的平行搜索和正反饋特性來求解最佳解。

1 基于頻率分配的算法

1.1 ANTS算法

1.1.1 算法原理

ANTS算法的主要元素是 ants——獨(dú)立得、反復(fù)地構(gòu)造問題的解的簡單計算代理;求解過程中問題的部分解決方案被稱為states(狀態(tài));每只螞蟻從狀態(tài)a轉(zhuǎn)移到狀態(tài)b,相應(yīng)得構(gòu)造了一個更加完整的局部解決方案。在每一步,每一個螞蟻k都會計算出它當(dāng)前狀態(tài)的可能擴(kuò)展?fàn)顟B(tài),然后依概率相應(yīng)的移動到下一個狀態(tài)。對每只螞蟻k,從狀態(tài)a移動到狀態(tài)b的概率Pkab依賴于動作的吸引力μab(由表明動作先驗(yàn)概率的啟發(fā)式信息計算出來)和動作的軌跡水平 τab(表明在之前選擇該動作的收益,也即該動作的后驗(yàn)概率)2個值的聯(lián)合,參見文獻(xiàn)[4]。

軌跡在每一個迭代之后都進(jìn)行更新,增加好的方案的組成動作的軌跡水平,同時降低那些不好方案的動作的軌跡水平。在每一個動作,定義概率分布的相應(yīng)公式都會用到tabuk,它指出了每一個螞蟻每一次選擇的禁忌動作。

在每一個時間,m只螞蟻形成一個群體,完成一個方案。每一只螞蟻完成方案的相應(yīng)動作的軌跡水平由下式改進(jìn):

式中,系數(shù)ρ的函數(shù)(1-ρ)表明在2個方案形成過程中軌跡水平的衰減程度;τinit為軌跡信息素水平的初始值;ˉz為之前由算法構(gòu)造的L個方案的平均動作代價(當(dāng)不足L個方案時則少于L個),而zi為螞蟻k構(gòu)造的第i個方案的代價。如果zi低于ˉz,則構(gòu)成該方案的動作的軌跡信息素水平相應(yīng)得就增加,否則就減少,即保證了只有好的動作的信息素水平才增加(在螞蟻的實(shí)際尋優(yōu)過程中沒有相應(yīng)的這種機(jī)制)。

1.1.2 局部搜索

當(dāng)每一個螞蟻構(gòu)造的方案完成后,在對其評價賦值之前,都會運(yùn)用一個本地搜索程序(LS)來改善方案質(zhì)量。通過不斷試驗(yàn)驗(yàn)證,以下2種更新方案比較快速、簡單和易于實(shí)現(xiàn)[4]:

①LS1:隨機(jī)選擇方案中得某一臺站(發(fā)射機(jī)),然后選擇頻率域中的頻率替換該臺站(發(fā)射機(jī))頻率,如果替換后的新方案在代價上優(yōu)于原方案,則用新方案替換舊方案,否則保留原方案。反復(fù)這一過程,直到所有的臺站被選擇一遍;

②LS2:所有的臺站(發(fā)射機(jī))都被反復(fù)掃描且以一定的概率w被選中。被選中的臺站(發(fā)射機(jī))進(jìn)行隨機(jī)排序且依此順序被重新分配能使代價最小化的頻率。同樣在此搜索中,只有產(chǎn)生改進(jìn)的方案才被保留,否則保留原方案。

在每一次迭代過程中,既可以單獨(dú)使用LS1或者LS2,也可以把二者結(jié)合起來使用。譬如在前十分之一時間使用LS1而在后十分之九時間使用LS2(LS2效果更好而速度較慢)的。假設(shè)所需分配頻點(diǎn)數(shù)為n,則一般m=n/10,ρ=0.4,τinit=0.7,ξ=0.7,參見文獻(xiàn)[3]。

1.2 SA算法

一般的模擬退火算法的步驟如下:

①初始化,隨機(jī)得到初始解,并計算代價cost;

②設(shè)置退火參數(shù)。分別設(shè)置初始溫度T,冷卻系數(shù)k,終止溫度Tend;

③隨機(jī)生成新個體,計算其cost′和cost′-cost=Δcost;如果 Δ cost＜0,則接受新解,否則以概率exp(-Δ cost/T)接受新解;

④使T=KT,如果T＞Tend或在規(guī)定迭代次數(shù)內(nèi)解無停滯現(xiàn)象,則轉(zhuǎn)步驟③,否則算法終止。

1.3 改進(jìn)的ANTS算法SA-ANTSLocal

在ANTS算法的基礎(chǔ)上對其進(jìn)行改進(jìn),產(chǎn)生了一種新的SA-ANTSLocal算法。首先,利用模擬退火算法(SA)生成一個次優(yōu)解,對次優(yōu)解分配初始信息素,再利用ANTS算法尋找全局最優(yōu)解。整個算法流程如圖1所示。

圖1 SA-ANTSLocal算法流程

在步驟①中的函數(shù)SADistribute偽代碼如下:

τab=0

For(m solutions)do

{

τab=C+τab;

}

應(yīng)用local optimization procedure尋找局部最佳方案時,本文使用的是LS1。在LS1中,對每一個臺站采用窮舉的方法來選擇它的最佳頻率。為了進(jìn)一步縮短收斂時間,對LS1進(jìn)行了改進(jìn)。步驟如下:

①計算每只螞蟻搜索得到的方案中所有臺站的違約數(shù),并依從大到小的順序進(jìn)行排序;

②按排序順序選擇違約數(shù)最大的P個臺站,對每個被選擇臺站,依次選擇頻率域中的頻率替換原頻率。如果替換后得到的新方案優(yōu)于原方案,則該方案替換原方案,否則保留原方案。

在改進(jìn)的local optimization procedure中,關(guān)鍵是步驟2中P的選擇。P選擇過小則局部尋優(yōu)得到的不一定是局部最優(yōu)方案,P選擇過大則起不到縮小收斂時間的作用,造成很多無謂的迭代。在下面的試驗(yàn)中,將進(jìn)一步探討P的選擇。

2 算法測試

2.1 問題描述

2.1.1 FAP問題描述

FAP是典型的最佳分配問題,即利用有限的信道在滿足如下電磁兼容約束限制的條件下,進(jìn)行充分分配:

①同信道約束:相同的信道不能同時分配給某些小區(qū);

②臨信道約束:某些相鄰的信道不能同時分配給相鄰小區(qū);

③同址約束:某些間隔較小的信道不能同時分配給同一小區(qū)。

根據(jù)實(shí)際的應(yīng)用,常將頻率指配問題從優(yōu)化目標(biāo)的角度分為4類:最少頻點(diǎn)頻率分配問題、最低阻塞概率頻率分配問題、最小跨度頻率分配問題和最小干擾頻率分配問題。本文中主要從最少頻點(diǎn)和最小干擾的角度來考慮。

信道分配問題可以用圖著色問題來描述,因?yàn)閳D著色問題是N-P問題,所以信道分配問題也是N-P問題,它獲得最佳解的時間隨著解決問題的規(guī)模而指數(shù)性增長。

2.1.2 Philadelphia實(shí)例

比較智能優(yōu)化算法的重要指標(biāo)關(guān)鍵看2個方面:是否收斂以及在單位時間內(nèi)的收斂率。為了驗(yàn)證SA-ANTSLocal算法的有效性,采取存在公認(rèn)理論邊界值的Philadelphia實(shí)例(21小區(qū)模型)為測試對象,參見文獻(xiàn)[4]。21小區(qū)模型是最早研究的實(shí)例之一,是典型的蜂窩網(wǎng)絡(luò)移動通信模型,每個小區(qū)都由一個基站與大量的移動臺組成,通信方式為雙工方式,基站分別與每個移動臺之間占用一對頻點(diǎn),用正六邊形表示小區(qū),每個小區(qū)需要一定數(shù)量的頻點(diǎn),由于干擾具有對稱性,也即基站與基站的頻率約束間隔同移動臺與移動臺之間的頻率約束間隔是相等的,故可取待分配主體為基站,移動臺分配的頻點(diǎn)只需在基站頻點(diǎn)的基礎(chǔ)上加一固定間隔即可。該問題的實(shí)例可由需求向量D、約束矩陣C、同頻復(fù)用距離d、相鄰小區(qū)頻率間隔acc來描述。需求向量D表示的是各個小區(qū)的所需分配的頻點(diǎn)數(shù),約束矩陣C表示的是小區(qū)之間的約束關(guān)系。21小區(qū)問題具體的實(shí)例數(shù)據(jù)參考文獻(xiàn)[4]。

2.2 試驗(yàn)仿真和結(jié)果

為了驗(yàn)證算法的有效性,針對典型21小區(qū)問題分別利用模擬退火算法(SA)、蟻群算法(ANTS)和改進(jìn)的混合算法(SA-ANTSLocal)進(jìn)行仿真,選取其中典型的6個問題,且對每個問題都限制用理論最小信道數(shù)進(jìn)行分配。仿真是在CPU位Intel Celeron M 723 1.20GHz,內(nèi)存為1 G的計算機(jī)上進(jìn)行,采用Matlab語言編程,對上述算法分別進(jìn)行10次仿真,每次迭代次數(shù)為30次。其中,若實(shí)例中待分配臺站數(shù)為L,一般P設(shè)為L/2。仿真結(jié)果如表1所示。

表1 4種算法的仿真結(jié)果比較

從表1可以看出,SA算法收斂時間最短,但很難得到最佳解,只有在極簡單的情況下才能得到可用解。收斂時間由低到高依次是SA、SA-ANTSLocal、ANTS。其中,在解質(zhì)量相當(dāng)?shù)那闆r下,SA-ANTSLocal要比ANTS算法節(jié)約大概1/3～1/2的時間。尤其在可用頻點(diǎn)數(shù)較寬裕、對解質(zhì)量要求不是特別高的情況下,可以通過設(shè)定P值的大小,進(jìn)一步縮短收斂時間。

3 結(jié)束語

本文針對FAP問題提出了一種結(jié)合模擬退火算法的ANTS算法。與模擬退火的算法相比,該算法能夠較好地避免陷入局部收斂,特別是在解決較難較復(fù)雜的頻率分配問題時能取得更優(yōu)的分配結(jié)果。與單純的ANTS算法相比,該算法在保證一定的收斂率和違約數(shù)情況下,明顯加快了運(yùn)行速度,能較快得到分配結(jié)果。該算法不僅適用于頻率分配問題,還可以應(yīng)用到其他優(yōu)化問題中。該算法有待在實(shí)際工程中進(jìn)一步驗(yàn)證。

[1]COLORNI A,DORIGO M,MANIEZZO V.An Investigation of Some Properties of an Ant Algorithm.Proc.of the Parallel Problem Solving from Nature Conference(PPSN'92)[C].Brussels,Belgium:Elsevier Publishing,1992:509-520.

[2]MANIEZZO V.Exact and Approximate Nondeterministic Treesearch Procedures for the Quadratic Assignment Problem[J].Inform.J.Computing,1999,11(4):358-369.

[3]THAVARAJAH A,LAM W H.A Heuristic Algorithm for Channel Assignment in Cellular Mobile Systems[J].IEEE Transactions on Vehicular Technology,1998,45(6):1690-1694.

[4]MONTEMANNI R,SMITH D H,ALLEN S M.An ANTS Algorithm forthe Minimum-span Frequency-assignment Problem With Multiple Interference[J].IEEE Transactions on Vehicular Technology,2002,51(5):949-953.