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

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

0 引言

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

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

1 基于頻率分配的算法

1.1 ANTS算法

1.1.1 算法原理

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

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

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

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

1.1.2 局部搜索

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

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

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

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

1.2 SA算法

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

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

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

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

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

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

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

圖1 SA-ANTSLocal算法流程

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

τab=0

For(m solutions)do

{

τab=C+τab;

}

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

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

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

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

2 算法測(cè)試

2.1 問(wèn)題描述

2.1.1 FAP問(wèn)題描述

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

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

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

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

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

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

2.1.2 Philadelphia實(shí)例

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

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

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

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

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

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

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