一個蟻群優化模型的期望性能分析
2009-01-01 00:00:00喻學才張田文
計算機應用研究 2009年4期
(哈爾濱工業大學 計算機科學與技術學院， 哈爾濱 150001)
摘 要：
用蟻群優化求解組合優化問題時， 信息素模型及其規則可能使問題的各組件之間的競爭失衡， 從而有可能使蟻群搜索停滯在最差解。 研究了蟻群優化求解k-最小生成樹問題時的信息素模型及其更新規則對性能的影響，對原有的信息素模型作出了新的解釋:直接表示k-最小生成樹問題的邊被選擇的概率。基于新的信息素模型設計了一種新的解的構造過程，這種過程不僅產生可行解， 也產生不可行解；同時研究了使用可行解和全部解更新信息素模型時算法的迭代期望質量隨時間的增減情況，其結果表明， 只使用可行解時迭代期望質量隨時間連續降低， 而使用全部解時算法最終收斂到最優解。為了使用全部解， 定義不可行解的不可行量及擴展目標函數使可行解的目標值不變而不可行解的目標值大于任何一個可行解。
關鍵詞：蟻群優化; 擴展信息素更新; 組合優化; k-最小生成樹問題; 擴展目標函數
中圖分類號：TP301.6文獻標志碼：A
文章編號：1001-3695(2009)04-1311-02
Expected performance of ant colony optimization model
YU Xue-cai， ZHANG Tian-wen
(School of Computer Science Technology， Harbin Institute of Technology， Harbin 150001， China)
Abstract:
When applying ant colony optimization metaheuristic to combinatorial problems， the combination of an ant colony optimization algorithm and a problem instance may be not a CBS and the pheromone model and its updating rule may make the algorithm converge at the worst solution. This paper developed an ant colony optimization model for solving the k-minimum spanning tree problem which was NP-hard and analyzed the influence of two updating rules of the pheromone model over the performance of the ant colony optimization algorithm. Analysis showed that the iteration expected quality of the algorithm continuously decreased with the former while increasing with the latter. To utilize all solutions produced， the augmented objective of each infeasible solution was defined in such way that the objective value of each feasible solution was not altered and that of each infeasible solution must be greater than that of the worst feasible solution.
Key words：ant colony optimization; augment pheromone update; combinatorial optimization problem; k-minimum spanning tree problem; augmented objective
0 引言
自蟻群優化的第一個算法螞蟻系統[1]被提出之后， 人們對其改進和應用[2，3]作了大量研究。但近年來， 研究的熱點已經轉向理解蟻群優化的行為[4~7]， 特別是信息素建模組合優化的關鍵問題[8]。C. Blum等人發現螞蟻系統模型求解某些組合優化問題的實例時， 其信息素模型更新規則實現的正反饋機制可能使算法收斂到最差解， 具體表現為蟻群的迭代期望質量連續下降。研究例子有作業調度問題[5]和k-最小生成樹問題[4，8]。螞蟻系統模型的這種行為在設計螞蟻算法時應該避免，基于這一目標， 本文研究螞蟻系統模型求解k-最小生成樹問題， 其創新點在于: a)對原來的信息素模型參數的意義重新作了規定， 使其直接表示邊被選擇的概率; b) 開發了一種新的解構造規則; c)考慮了使用可行解更新和所有解更新兩種更新規則，并定義了不可行解的不可行量和擴展目標函數。分析表明， 僅使用可行解的更新規則同樣會使蟻群的迭代期望質量連續下降， 算法收斂到最差解；而使用所有解的更新規則則避免了這個問題， 算法收斂到最優解之一。
1 k-最小生成樹
k-最小生成樹(KMST)問題是最小生成樹(MST)問題的一個推廣: 給定一個邊帶權的無向圖G=(V，E)(|V|=n且|E|=m)， 對任意e∈E， 邊權ω(e)∈N(N＞0)。KMST的目標就是在G中找到一棵恰有k條邊的樹Tk使之最小化:
f(Tk)=∑e∈E(Tk)ω(e)(1)
與MST不同的是， 一般的KMST是NP難的。
2 KMST的一個蟻群優化算法
假設圖G的所有邊已經按某個序排好:e1，…，em， 則KMST的解結構定義長度為m的二進制串，第i位對應邊ei。 如果第i位為1， 表示邊ei在二進制串對應的樹Tk中；相反， 如果第i位為0， 表示邊ei不在二進制串對應的樹Tk中。與此解結構相應的信息素模型τ是一個包含m個分量的向量， 每個τi分量對應一個邊ei。信息素模型的值表示對應的邊被選擇的概率， 這與大多數文獻中的描述不同。算法1給出了基于這個信息素模型的求解KMST蟻群優化算法的抽象偽代碼，Nant表示總的螞蟻數。
算法1 KMST的一個蟻群算法
初始化信息素模型τ: InitPherModel(τ);
while 終止條件沒滿足 do
for 螞蟻I=1，…，Nant do
用信息素模型τ構造解TIk=solu(τ);
end for
信息素模型更新update(T1k，…，TNantk);
end while
在算法1中，信息素模型先被初始化， 之后蟻群利用信息素模型參數構造一組解， 被構造的這組解用于更新信息素模型。后面的兩個算法步被迭代地反復執行， 直到終止條件得到滿足， 如超過了時間限制或最大迭代步數。下面詳細定義算法1中的三個操作。
a)initPherModel(τ)， 在算法開始時， 信息素模型的m個分量被設置為相同的值0.5。
b)Solu(τ) 在每個迭代步， 所有的螞蟻構造一個長為m的二進制序列sI。對sI的每個分量i， 螞蟻根據信息素模型參數τi隨機地設置
siI=τi＜rnd?0∶1（2）
其中:rnd是一個均勻分布在[0，1]的隨機數。表達式a＜b?0∶1的意思是如果a c)Update(T1k，…，TNantk) ，在所有的螞蟻構造了一個序列之后， 其中的可行解被允許參加信息素模型的更新。信息素模型參數的更新規則為 τi←(1-ρ)τi+ρ∑{s∈A|ei∈s}(F(s)p(s|τ))/WF(τ)（3） 其中：p(s|τ)是根據當前信息素模型產生序列s的概率;A是可行解的集合;F(s)是可行解s的質量函數;WF(τ)是當前迭代步的期望質量。可行解s的質量函數定義為 F（s）=1/f(s) 當前迭代步的期望質量定義為 WF(τ)=∑s∈AF(s)p(s|τ)/∑s∈Ap(s|τ) 根據式(3)和信息模型參數的初始值， 在算法的整個迭代過程中信息素模型的所有參數值在[0，1]變化[4]， 所以式(2)中直接使用τi作為邊ei被選擇的概率。 如果考慮螞蟻數Nant=∞， 上面描述的蟻群算法構成模型M(KMST， HCF-AS，Nant)。本文主要考慮這個模型的期望質量是否隨時間增加。 3 期望性能分析 考慮如下簡單的2MST問題[2]， 邊的權為 設置為ω(e1)=w(e4)=1和ω(e2)=ω(e3)=2， 稱這個問題實例為2mst_simple_inst。 用上面描述的蟻群算法求解這個實例的搜索樹如圖1所示。16個序列中只有s4、s10、s13是可行解， 分別對應2MST({v1， v2， v3}， {e1， e2})， ({v2， v3，v4}， {e2，e3})， ({v3，v4，v5}， {e3， e4})。根據式(1)， f(s4)=3， f(s10)=4， f(s13)=3， 因此s4和s13是最優解， s10是最差解。設τi（t）表示在離散時間迭代步t=0，1，…， 信息素模型參數的值，根據式(2)序列s4，s10，s13產生的概率分別為 p(s4，t)=τ1(t)τ2(t)(1-τ3(t))(1-τ4(t)) p(s10，t)=(1-τ1(t))τ2(t)τ3(t)(1-τ4(t)) p(s13，t)=(1-τ1(t))(1-τ2(t))τ3(t)τ4(t) 在步t， 迭代期望質量為 WF（τ，t）=[p(s4，t)/f(s4)+p(s10/f(s10)+p(s13，t)/f(s13)]/[p(s4，t)+p(s10，t)+p(s13，t)] 設計蟻群優化算法應當使迭代期望質量WF(τ，t)隨t增加， 這樣才能使蟻群搜索集中在有希望發現最優解的解空間區域。 然而以前的研究表明: 蟻群優化中迭代期望質量WF(τ，t)并不總是隨t增加[2，5]。只有當問題實例與蟻群算法的組合是一個競爭平衡系統時， 迭代期望質量才有可能隨t增加[3]。 不幸的是，M(KMST， HCF-AS，Nant)與2mst_simple_inst的組合是一個典型的競爭失衡的例子。圖2給出了WF(τ，t)的進化。 從圖2可以看出， 算法最終收斂到最差解s10。這是因為: 算法開始時， 三個解產生的概率是相同的，即p(s4，0)=p(s10，0)=p(s13，0)。根據式(3)對信息素模型進行更新， 則邊e2、e3對應的信息素參數τ2(1)、τ3(1)的增加值大于邊e1、e4對應的信息素參數τ1(1)、τ4(1)。因此， 在以后的迭代中，s10產生的概率就會越來越大， 最終為1即算法收斂到最差解。圖3給出了p(s10，t)隨t的進化。 4 擴展更新 用蟻群優化求解一個組合優化問題時， 一般可以由多種信息素模型表示。但對于有很重約束的問題， 卻不存在一個信息素模型與所有問題實例的組合是競爭平衡的[6]。那么， 是不是M(KMST， HCF-AS，Nant)與2mst_simple_inst的組合就不可能使迭代期望質量隨t增加且使算法最終收斂到最優解s4或s13呢? 回答是否定的。下面給出一種考慮不可行序列的新的更新規則。 一個不可行序列的不可行量iFa定義為該序列對應的圖的邊數超過k或低于k的數量與圖中連通子圖多于1的數量和。一個可行序列的不可行量為0；一個不可行序列的擴展目標函數定義為 aug f(Ts)=∑e∈E(Ts)ω(e)+iFa×max{ω(e):e∈E(Ts)}（4） 這樣， 一個不可行序列的目標值比任何一個可行序列的目標值大，這將會促使蟻群搜索集中在可行解空間。 信息素模型的擴展更新規則 τi←(1-ρ)τi+ρ∑{s∈S|ei∈s}augF(s)p(s|τ)/augWF(τ)（5） 其中:S是所有序列的集合； 擴展質量函數及迭代期望質量定義同上。各序列的產生概率可根據圖1和信息素模型參數很容易得到。顯然， 使用擴展更新規則， 四條邊在所有序列中出現的次數是一樣的， 其對應的信息素模型參數值增加的概率也是一樣， 也就是說， 這是一個競爭平衡系統。那么， 使用擴展更新之后， 迭代期望質量WF（τ，t）會不會隨t增加呢? 圖4給出了使用擴展更新后WF(τ，t)和augWF(τ，t)隨t的進化。可見， 使用擴展更新能使M(KMST， HCF-AS，Nant)收斂于2mst_simple_inst的最優解。圖5給出了產生兩個最優解s4和s13的概率p(s4，t)和p(s13，t)隨t的進化。可見， 最優解之一s13的產生概率p(s13，t)最終達到1。 5 結束語 本文研究了螞蟻系統模型求解k-最小生成樹的性能。為此， 設計了一種新的信息素模型和解的構造規則。在允許包括不可行解在內的全部解參與信息素模型更新的情況下， 蟻群的迭代期望質量連續增加， 算法收斂到最優解。 與此相關的另一問題是， 算法為什么收斂到一個最優解而不是同時收斂到兩個最優解(圖5)，這是將來需要解釋的問題。 參考文獻： [1]DORGO M， MANIEZZO V， COLORNI A. Ant system: optimization by a colony of cooperating agents[J]. IEEE Trans on Systems， Man， Cybernetics， Part B， 1996， 26(1): 29-41. [2]夏娜，蔣建國，魏星，等.改進型蟻群算法求解單任務agent聯盟[J]. 計算機研究與發展， 2005， 42(5):734-739. [3]李艷君，吳鐵軍.求解混雜生產調度問題的嵌套混合蟻群算法[J].自動化學報，2003，29(1):95-101. [4]DORIGO M， BLUM C. Ant colony optimization theory: a survey [J]. Theoretical Computer Science， 2005， 344(2): 243-278. [5]BLUM C， DORIGO M. Search bias in ant colony optimization: on the role of competition-balanced system[J]. IEEE Trans on Evolutio-nary Computation， 2005， 9(2): 159-174. [6]BLUM C， DORIGO M. The hyper-cube framework for ant colony optimization[J]. IEEE Trans on Systems， Man， Cybernetics， Part B， 2004， 34(2): 1161-1172. [7]BLUM， SAMPLES， ZLOCHIN. On a particularity in model-based search[C]//Proc of Genetic and Evolutionary Computation Confe-rence. San Francisco:Morgan Kaufmann Publishers，2002. [8]MONTGOMERY. Solution biaes and pheromone representation selection in ant colony optimisation [D]. Queensland: Bond University， 2005.
