基于蟻群遺傳算法混合編程的函數優化

摘要:為研究連續函數優化問題，基于圖解的蟻群系統，提出二進制蟻群算法，并實現與遺傳算法混合編程，以提高求解效率。算例表明，蟻群-遺傳算法混合編程求解連續優化問題，收斂速度快，計算精度高，可用于求解實際工程問題。

關鍵詞:連續優化;二進制;蟻群算法;遺傳算法;混合編程

中圖分類號:TP18文獻標識碼:A文章編號:1009-3044(2009)26-7494-03

Function Optimization Based on Programming Mixed Ant Colony Algorithm with Genetic Algorithm

ZHAO Feng-yao， GUAN Xin-Jian

(School of Water Conservancy Environment Engineering， Zhengzhou University， Zhengzhou 450001， China)

Abstract: For the study of continuous optimization problems， a binary ant colony algorithm was introduced based on graph-based ant system. To improve soluation efficiency， the ant colony algorithm programming mixed with genetic algorithm was realized. Practical example showes that the mixed language programming can solve continuous optimization problem with a faster convergence speed and a better precision in calculation， and it can be used on engineering.

Key words: continuous optimization; binary; ant colony algorithm; genetic algorithm

蟻群算法(Ant Colony Algorithm)是一種源于大自然生物世界的新型仿生類算法[1]，20世紀90年代初由意大利學者Dorigo依照螞蟻覓食原理設計而成的一種群體智能算法。蟻群算法在求解一系列困難的組合優化問題上取得成效，成為解決TSP (traveling salesman problem)、JSP (job-shop problem)等典型問題的一種強有力算法。

遺傳算法是受生物進化學說和遺傳學說的啟發而發展起來的，由美國的J.H.Holland教授于1975年創立[2]。它模擬自然選擇和遺傳過程中發生的繁殖、雜交和變異現象，進行群體智能進化計算。由于遺傳算法求解復雜優化問題的巨大潛力，近年來再許多工程領域的得到應用。

本文基于連續優化目的開展基礎性研究，通過蟻群算法與遺傳算法的混合編程，改進算法的性能，以求解連續優化問題。

1求解連續優化問題的蟻群算法

1.1 蟻群算法的基本思想

1)狀態轉移規則:蟻群算法使用的狀態轉移規則為隨機比例規則，是基于求解TSP問題提出的，它給出來位于城市i的螞蟻k選擇移動到城市j的概率。公式為:

其中τ(i，j)表示邊(i，j)的適應值，即“激素”; η(i，j) 為距離L(i，j)的倒數。α，β為兩個參數，分別表示螞蟻運動過程中積累信息和啟發信息的相對重要程度。

在蟻群算法中，選擇方式為:

其中，q為均勻分布在[0，1]上的一個隨機變量，q0為在[0，1]上的參數，而J則是根據等式(1)計算出來的概率分布來進行選擇。

2)全局更新規則:螞蟻算法有不同的更新規則，蟻群系統采用全局全局更新規則，只允許全局最優的螞蟻釋放信息素。這樣做可以使螞蟻的搜索主要集中在當前循環為止所找出的最好路徑的鄰域內。全局更新在所有螞蟻都完成一次搜索后用下邊(3)式進行全局更新:

其中:ρ為信息素揮發參數;Lgb為到目前為止找到的全局最優路徑。

3)局部更新規則:每只螞蟻建立一個解的過程中也同時進行激素跡的更新，規則如下:

其中， r為[0，1]間的參數。

1.2 基于圖解的蟻群系統

用蟻群算法求解最優化問題，首先需要將最優化問題轉化為求解最短路徑問題。為此，文獻[3]提出了有向圖的概念，文獻[4]提出了構造圖的概念，他們的共同特點是通過行程對可行解進行編碼，進而求解優化問題。

本文在文獻[4]的基礎上，以二進制為基礎，編制了如圖1所示的構造圖。每只螞蟻從初始子結點N00 或N01出發，順序走過N1，N2，…，的其中一個子結點，直到終結點Nk0、Nk1，組成路徑(N0t N1t N2t…Nkt)，(t∈{0，1})。Nkt取二進制數0或1，路徑即可代表一個二進制可行解。

在圖1中，每兩個相鄰結點Ni， Nj之間有4個并行路徑，分別連接他們的子結點:Ni0->Nj0，Ni0->Nj1，Ni1->Nj0，Ni1->Nj1，其信息值分別記為τ(i，j)1， τ(i，j)2， τ(i，j)3， τ(i，j)4，螞蟻行進時只能選擇其中的一條路徑。每只螞蟻行進開始時，首先根據τ(0，1)s，s∈{1，2，3，4}，概率選擇一條路徑，確定前兩個子結點。當第二個子結點為N10 時，根據τ(1，2)1， τ(1，2)2值的大小按概率選擇下一個子結點;當第二個子結點為N11 時，根據τ(1，2)3， τ(1，2)4值的大小按概率選擇下一個子結點。這樣一直概率選擇到最后的子結點Nk0或Nk1，即構成一個完整路徑及可行解。

1.3 用于連續優化的蟻群算法

1)參數取值的二進制編碼:參數取值的二進制編碼與遺傳算法相同。假設優化問題的可行解為{x1， x2，…，xm}，其中變量xi用長度為l的二進制串表示為{bl bl-1…b2b1}，其中bj∈{0，1}，它對應蟻群算法結構圖1中的一段路徑(NL+1，t NL+2，t…NL+l，t)。設xi取值范圍為[ximin， ximax ]，則對應的解碼公式為:

在TSP問題中，最優路徑對應的是最短路徑。在優化問題中，最優路徑為對應目標函數值最優(最大或最小)的螞蟻行進路徑。

2 蟻群算法與遺傳算法的混合編程

2.1 遺傳算法及其實現

基本遺傳算法程序中使用的是二進制編碼，將原問題的解空間映射到位串空間{0，1}上，然后在位串空間上進行遺傳操作，結果再通過解碼過程還原成其表現型以進行適應度評估，其求解過程為:

1) 對待解決問題進行編碼。

2) 隨機初始化群體X(0)=(x1，x2，…，xn)。

3) 對當前群體X(t)中每個個體xi，解碼計算其適應度F(xi)。解碼公式與上式(5)相同。

4) 進行選擇、交叉、變異等遺傳操作，產生下一代個體。

5) 對t=t+1代繼續從3)步進化計算，直到滿足終止條件。終止條件一般為預定的進化代數或誤差限小于設定值或。

2.2 遺傳算法的常用算子

1) 選擇算子(selectio):選擇算子從群體中按某一概率成對選擇個體，某個體被選擇的概率Pi與其適應度值成正比。常用的實現方法是輪盤賭規則。

2) 交叉算子(Crossover):交叉算子將被選中的兩個個體的基因鏈按概率Pc進行交叉，生成兩個新的個體，交叉位置是隨機的。

3) 變異算子(Mutation):變異算子將新個體的基因鏈的各位按概率Pm進行變異，對二值基因鏈(0，l編碼)來說即取反。

2.3 蟻群算法與遺傳算法的混合編程

蟻群算法有一個主要缺陷，即搜索進行到一定程度后，各個螞蟻趨于選擇同一條路徑，算法出現停滯現象。遺傳算法局部搜索能力較差，在應用中體現出收斂速度慢且存在未成熟收斂。但這兩種智能算法工作機理不同，有很強的互補性。兩者融合，互相取長補短可以產生更好的效果。

當蟻群算法與遺傳算法均采用二進制編碼時，很容易實現混合編程。具體實現時，蟻群算法中螞蟻個數與遺傳算法中染色體個數取相等，每進行M次蟻群搜索循環后，將蟻群的二進制路徑看做遺傳算法中種群的染色體，進行N次遺傳算法進化計算，然后再將得到的染色體作為蟻群二進制路徑，繼續進行蟻群算法搜索。

3 函數優化

3.1 函數優化及其求解

函數優化在工程技術領域應用很廣泛。生產優化、設計優化、投資決策等可通過數學建模直接應用優化方法求解，參數識別、系統控制等問題則可轉化為優化問題再進行求解。

函數優化的解法主要有兩大類。其一為數學方法，即傳統方法，主要利用導數及偏導進行求解，有可靠的理論基礎。由于傳統方法建立在梯度局部下降的基礎上，多數情況下不適合求解全局優化問題，而且對于不可微和病態函數，常常無能為力[5]。

其二是進化算法，如遺傳算法、蟻群算法、免疫算法、粒子群算法等，不需要計算梯度，計算過程對函數性態依賴性較小，適應范圍廣、魯棒性好，適合計算機編程計算。近年來進化算法飛速發展，具有廣闊的應用前景。

3.2 數學算例

由于蟻群算法及遺傳算法程序運行中均存在大量的隨機操作，從理論上對其性能和效率進行分析比較困難，因此這里通過一個測試函數對本文提出的蟻群-遺傳混合算法進行多參數優化效率分析。

測試函數取一簡單的多元平方求和函數，即求:

在函數定義域內其最優解為:當xi=2.0(i=1，2，3)， xi=5.0(i=4，5)時，目標函數取最小值0。分別用蟻群算法、基本遺傳算法、蟻群-遺傳進行進化尋優計算。螞蟻或染色體數目取40，最大進化代數取200代。

在開始計算前，蟻群算法中公式(1)～(4)中的參數α，β，γ，Δτ(i，j)等都預先賦給合適的經驗值，本文各參數取值為:

α=1，β=0，τ0=50，q0=0.1，δ=0.1，r=0.05，Lgb=0.016

β=0意味著不考慮啟發信息的作用， Lgb=0.016時意味公式(3)中Δτ(i，j)s=62.5，即進化計算過程中Δτ(i，j)s始終取一個恒定值。

遺傳算法中的主要計算參數取:交叉概率Pc=0.8，變異概率Pm=0.02。

蟻群-遺傳算法中取每進行6次蟻群搜索循環，進行4次遺傳算法進化計算。

在這個多參數優化問題中，最優路徑為對應目標函數值最小的螞蟻行進路徑。經過200代進化計算后，三種方法的函數優化結果如表1所示。

從表1可以看出，蟻群-遺傳算法得到的識別結果比蟻群算法和基本遺傳算法結果明顯要好，單個變量的識別值與實際值更接近，最后得到的目標函數值也更小，說明采用蟻群-遺傳算法混合編程求解效率與求解精度更高。算例還表明，混合算法可以很好地進行多參數優化求解，這可為求解實際工程技術問題打下良好的基礎。

4 結論

運用蟻群-遺傳算法混合編程進行優化設計，不僅具有較強的全局最優解搜索性能，還有較快的收斂速度和較高的求解精度，更適合解決多參數優化實際問題，具有廣闊的應用前景。

參考文獻:

[1] DorigoO M.Optimization，learning，and natural algorithms[D].Milano:Politecnico di Milano，1992.

[2] 王小平，曹立明.遺傳算法——理論、應用與軟件實現[M].西安:西安交通大學出版社，2002.

[3] Stutzle T.Parallelization Strategies for Ant System[C]//Proceedings of Parallel Problem Solving from Nature.Eileen A，Mchoenauer T B，SchwefelH.Lecture Notesin Computer Science.Berlin:Springer-Verlag，1998(1498):722-741.

[4] Gutjahr W J.A Graph-based Ant System and its convergence[J].Future Generation Computer Systems，2000(16):873-888.

[5] 唐煥文，秦學志.實用最優化方法[M].大連:大連理工大學出版社，2000.