一種針對頻率分配問題的改進ANTS算法

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

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

0 引言

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

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

1 基于頻率分配的算法

1.1 ANTS算法

1.1.1 算法原理

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

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

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

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

1.1.2 局部搜索

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

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

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

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

1.2 SA算法

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

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

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

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

④使T=KT,如果T＞Tend或在規定迭代次數內解無停滯現象,則轉步驟③,否則算法終止。

1.3 改進的ANTS算法SA-ANTSLocal

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

圖1 SA-ANTSLocal算法流程

在步驟①中的函數SADistribute偽代碼如下:

τab=0

For(m solutions)do

{

τab=C+τab;

}

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

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

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

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

2 算法測試

2.1 問題描述

2.1.1 FAP問題描述

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

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

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

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

根據實際的應用,常將頻率指配問題從優化目標的角度分為4類:最少頻點頻率分配問題、最低阻塞概率頻率分配問題、最小跨度頻率分配問題和最小干擾頻率分配問題。本文中主要從最少頻點和最小干擾的角度來考慮。

信道分配問題可以用圖著色問題來描述,因為圖著色問題是N-P問題,所以信道分配問題也是N-P問題,它獲得最佳解的時間隨著解決問題的規模而指數性增長。

2.1.2 Philadelphia實例

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

2.2 試驗仿真和結果

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

表1 4種算法的仿真結果比較

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

3 結束語

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

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