郜慶市，孫樹棟，韓 青，鐘 堯

GAO Qingshi,SUN Shudong,HAN Qing,ZHONGYao

西北工業(yè)大學 機電學院，西安 710072

School of Mechanical Engineering,Northwestern Polytechnical University,Xi’an 710072,China

1 引言

蟻群優(yōu)化算法（Ant Colony Optimization，ACO）[1]是一種基于自然界中螞蟻種群覓食行為的新型優(yōu)化算法。最早是由Dorigo及其研究團隊提出，用來解決旅行商（Traveling Salesman Problem，TSP）等一系列的組合優(yōu)化問題。算法具有正反饋、分布式計算與啟發(fā)式函數(shù)相結合的優(yōu)點[2]，更易于發(fā)現(xiàn)更優(yōu)的解，并且易于與其他方法結合，具有較強的魯棒性，使得該算法逐漸引起許多研究者的注意，并將其應用于很多具體的實際問題中[3]。

在ACO算法中，信息素、啟發(fā)式函數(shù)和螞蟻之間的合作直接影響算法的收斂性，而信息式啟發(fā)因子α、期望啟發(fā)因子 β、信息素揮發(fā)因子ρ、信息素增強系數(shù)Q、蟻群數(shù)目K等參數(shù)的選擇對算法的收斂性起到關鍵性作用，恰當選取參數(shù)組合可使得ACO算法更易于得到“利用-探索”平衡關系，收斂到最優(yōu)。然而，到目前為止仍沒有一種行之有效的數(shù)學分析方法來確定ACO算法的參數(shù)組合?，F(xiàn)在普遍采用的方法是基于大量的實驗，靠經驗和直覺選擇參數(shù)組合。本文提出了一種基于博弈論的ACO參數(shù)組合優(yōu)化模型，該模型利用數(shù)學分析方法，理論上優(yōu)化出不同環(huán)境下的參數(shù)組合，使ACO算法能夠在相對較短時間下收斂到最優(yōu)。

2 蟻群算法簡介

蟻群優(yōu)化算法的過程主要包括選擇、更新和調整三個過程。假設蟻群數(shù)目為 K，dij(i=1，2，…，n1;j=1，2，…，n2)為節(jié)點i與 j之間的距離，τij(t)表示t時刻在路徑(i，j)上的信息素。任意一螞蟻k在運動過程中，根據(jù)下式的概率轉移規(guī)則轉移方向：

式中，ηij(t)為啟發(fā)式函數(shù)，一般取 ηij=1/dij；參數(shù) α和 β分別為信息素和啟發(fā)式函數(shù)對整個轉移概率的影響權值；J(i)表示螞蟻k在節(jié)點i處的可行鄰域。

隨著時間的推移，信息素會逐漸揮發(fā)，用參數(shù)(1-ρ)表示信息素揮發(fā)后的剩余度，當一個循環(huán)周期結束后，進入t+1時刻，此時各路徑上的信息素將按照下式更新：

3 蟻群收斂速度分析

本章將從數(shù)學角度給出蟻群收斂速度的分析，為博弈論優(yōu)化蟻群參數(shù)組合模型提供有效的收益函數(shù)。

定義1 γ為ACO算法的收斂時間，Eγ為算法的期望收斂時間。

期望收斂時間表示的是當ACO算法的迭代時間t大于等于Eγ時，ACO算法以概率為1絕對收斂并且達到全局最優(yōu)解的時間。Eγ越大表明算法的收斂速度越慢，效率越低；反之，說明算法的收斂速度越快，效率越高。

定義2σ為ACO算法首次達到全局最優(yōu)解的收斂時間，Eσ為首次達到全局最優(yōu)解收斂時間的期望。

定理1 ACO算法的收斂時間γ等于首次達到最優(yōu)解的收斂時間σ。

證明 文獻[4-5]中已經證明ACO算法具有Markov性。令ψ(t)表示在第t次迭代的狀態(tài)參數(shù)即信息素集與路徑解集，ψ*表示全局最優(yōu)解下ACO算法的狀態(tài)參數(shù)。根據(jù)Markov性質可知：當 t=σ 時，P(ψ(σ+1)? ψ*|ψ(σ)∈ ψ*)=0 ；P(ψ(σ)∈ψ*)=1時，P(ψ(σ+1)∈ψ*)=1；因此可知當且僅當 t大于σ時，ACO算法以概率為1絕對收斂，則根據(jù)定義1有σ=γ。

因此，可以只通過計算Eσ來得到蟻群的期望收斂時間，下文計算的Eγ實際均為Eσ。

定理2 ACO算法的信息素滿足：

證明 根據(jù)式（2）和文獻[6]可知路徑(i，j)上信息素的最小值為螞蟻在迭代時間t之前沒有探索過該路徑，信息

根據(jù)式（2）和式（3）可知：

利用數(shù)學歸納法可得信息素的上界：

根據(jù)文獻[4]提到可知：

其中n為最優(yōu)路徑解集中節(jié)點的個數(shù)；K為蟻群數(shù)目；plow為在最優(yōu)解集ψ*上概率選擇的理論最小值。

定理3 ACO的期望收斂時間Eγ滿足：

其中ηimax為螞蟻在節(jié)點i時選擇下一可行節(jié)點中啟發(fā)函數(shù)中的最大值。

證明 根據(jù)式（1）可知：

將上式代入到式（5）即可得到定理3結論成立。

4 基于博弈論的ACO算法參數(shù)優(yōu)化設計

4.1 博弈論三要素

博弈論又名對策論，主要研究的是策略相互依賴行為。局中人相互之間有利益沖突，決策行為相互影響，局中人采取理性決策以最大化自身利益。

無論何種博弈論模型，總是包括以下三個要素[7]：

（1）局中人集合 N={1，2，…，n}。

（2）每個局中人i有若干個策略可供選擇，它構成該局中人的純策略空間 Si={λi1，λi2，…，λiki}。定義在 Si的一個概合策略集，其中xim表示選擇純策略λim的概率，其中：

（3）若每個局中人選定一個策略 λi∈Si，就形成了一個局勢 s={λ1，λ2，…，λn}，每個局中人 i都有自己相應的收益函數(shù)，對于局中人i在局勢s下的收益函數(shù)為 Pi(s)=Pi(λ1，λ2，…，λn)。

n人博弈對策可用 Γ=(N，{Si}，{Pi})表示，設 x為對策 Γ的一個混合局勢，記 x||Xi=(x1，…，xi-1，Xi，xi+1，…，xn)，其Xi，其他局中人的混合策略不變，產生的新的混合局勢。

定義3假設x*為對策Γ的一個混合局勢，如果

其中：

則稱 x*為n人對策Γ的一個混合平衡局勢即Nash平衡點[8]。

4.2 參數(shù)組合優(yōu)化設計

對于ACO算法參數(shù)的組合優(yōu)化，由于各個參數(shù)之間相互依賴、相互影響，單獨地研究某一參數(shù)對算法的影響很難得出較優(yōu)的參數(shù)組合，本節(jié)從4.1節(jié)博弈論三要素出發(fā)，構建ACO算法參數(shù)的博弈優(yōu)化模型，并證明其可行性。

（1）將ACO的關鍵參數(shù)視為博弈論模型中的局中人，參數(shù)集合 L={α，β，K，ρ}。

（2）根據(jù)文獻[9-10]驗證的結論可知：ACO算法各參數(shù)都有相對應的取值范圍即純策略集。由于博弈論研究的策略空間為離散的，首先需要將各參數(shù)的純策略集離散化處理：

其中，λi表示參數(shù)可選的第i個策略值；li表示參數(shù)取值范圍的左極限；ui表示參數(shù)取值范圍的右極限；mi表示參數(shù)策略集中策略的個數(shù)。

利用式（8）得到ACO算法的參數(shù)純策略集分別為Sρ，SK，Sα，Sβ即

其相對應的混合策略集分別為：

利用式（8）選取參數(shù)的純策略空間時，選取的策略空間越大，優(yōu)化后的參數(shù)組合越準確，但相應會增加模型的運算時間，因此參數(shù)空間不易選擇太大。

（3）根據(jù)定理3給出的ACO算法收斂速度不等式（6）令

選取ACO各參數(shù)的收益函數(shù)為：

定理4博弈論模型規(guī)劃出的ACO算法的最優(yōu)參數(shù)組合與實際ACO算法的最佳參數(shù)組合理論上具有一致性。

證明 根據(jù)定理3中蟻群收斂時間與各個參數(shù)關系的不等式可知：理論上求ACO參數(shù)最優(yōu)組合問題可轉化為求函數(shù)g的最小值問題即在函數(shù)g達到最小值的情況下對應的參數(shù)組合即為最優(yōu)的參數(shù)組合。

根據(jù)最值定理可知：若函數(shù)對未知數(shù)偏導數(shù)值等于零的點存在，則該零點對應的為函數(shù)的最值點；若偏導數(shù)等于零的點不存在，根據(jù)偏導數(shù)實質為未知數(shù)對于函數(shù)的變化率（梯度），可知未知數(shù)對函數(shù)變化率的最小的點即逼近零點的點為理論上的最優(yōu)點。

因此利用博弈論模型求ACO算法參數(shù)組合的最優(yōu)解參數(shù)組合只需要求得函數(shù)g最小值點對應的未知數(shù)的值，也就是理論上實際蟻群參數(shù)的最優(yōu)組合即

其中，i表示ACO算法的參數(shù)。

由定義3可知，博弈論中的Nash均衡點策略組合實質為所有局中人最優(yōu)策略的組合，即局中人的收益函數(shù)最大值點。

令ACO算法博弈優(yōu)化參數(shù)組合模型中收益函數(shù)最大值點表示為：Pimax(s*)。

根據(jù)式（9）與式（10）可知基于博弈論優(yōu)化ACO算法參數(shù)組合模型求解出的參數(shù)最優(yōu)組合與實際的參數(shù)最優(yōu)組況下的參數(shù)最優(yōu)組合解，因此可知兩者理論上具有一致性。

5 模型仿真與分析

為了驗證本文提出的參數(shù)優(yōu)化組合模型的有效性，本文采用TSPLIB[11]中的Oliver30、Eil51問題作為標準化問題，使用Matlab7.11.0環(huán)境下進行算法模型的仿真驗證。分別采用本文構建的博弈模型求解出的最優(yōu)參數(shù)組合與文獻中給出的參數(shù)組合運行經典的TSPLIB問題，比較不同參數(shù)下ACO算法的性能。根據(jù)文獻[9-12]中描述，本文選取參數(shù)的取值范圍如表1所示。

表1 蟻群算法參數(shù)取值范圍

為了驗證不同參數(shù)ACO算法的收斂時間，本文采用的最大循環(huán)次數(shù)為800次，初始信息素τ0=5，信息素增強系數(shù)Q=78。

5.1 OLIVER30

針對Oliver30問題，文獻[10]和文獻[12]中都給出了一組優(yōu)化參數(shù)，基于本文模型同樣得到了一組優(yōu)化參數(shù)如表2。

表2 文獻與仿真得到的參數(shù)組合

圖1為分別采用表2的參數(shù)組合進行了200次實驗的ACO算法的收斂時間與最短路徑的曲線圖。（a）為文獻[10]所提出的參數(shù)組合的仿真曲線圖，（b）為文獻[12]的仿真曲線圖，（c）為本文模型得到的參數(shù)仿真曲線圖。根據(jù)圖1可以得到實驗結果數(shù)據(jù)分析表3。

圖1 Oliver30收斂時間與最短路徑曲線

由表3可以看出圖1（c）仿真的實驗結果明顯優(yōu)于圖1（a）、圖1（b），即利用博弈論模型得出的參數(shù)組合可使ACO算法在尋找最優(yōu)路徑時有很好的穩(wěn)定性（標準偏差較?。?，Antcycles（Ant-cycles為實驗的螞蟻種群K與平均收斂時間的乘積）較小，蟻群算法運行時間較短。

表3 Oliver30實驗數(shù)據(jù)結果

5.2 EIL51

本節(jié)對Eil51問題進行進一步的仿真驗證，利用文獻[10]與博弈模型給出的ACO參數(shù)組合來驗證模型的有效性，表4對應參數(shù)組合。

表4 文獻與仿真得到的參數(shù)組合

圖2中（a）為文獻[10]中參數(shù)的實驗仿真曲線圖，（b）為本文模型得到的參數(shù)仿真曲線圖。

圖2 Eil51收斂時間與最短路徑曲線

根據(jù)圖2得到的數(shù)據(jù)結果表5同樣可以看出基于博弈論的ACO算法參數(shù)組合模型得出的參數(shù)組合在極大提高算法收斂時間的同時仍具有較好的穩(wěn)定性，進一步說明模型的正確性和有效性。

表5 Eil51實驗數(shù)據(jù)結果

6 結束語

本文將博弈論模型與蟻群算法結合，提出了一種基于博弈論對ACO算法的參數(shù)進行組合優(yōu)化的模型。本文利用算法參數(shù)的相互依賴、相互影響的特性，將參數(shù)看做博弈論中的局中人進行參數(shù)組合優(yōu)化。仿真實驗結果證明了該模型的有效性，并且針對不同的環(huán)境，該模型可以規(guī)劃出相應的較優(yōu)參數(shù)組合，更加有利于ACO算法的應用。

[1]Dorigo M，Maria L.Ant colony system：a cooperative learning approach to the traveling salesman problem[J].IEEE Trans on Evolutionary Computation，1997，1（1）：53-66.

[2]李士勇.蟻群算法及其應用[M].哈爾濱：哈爾濱工業(yè)大學出版社，2004.

[3]段海濱，王道波，朱家強，等.蟻群算法理論及應用研究的進展[J].控制與決策，2004，19（12）：1321-1326.

[4]Huang Han，Wu Chunguo，Hao Zhifeng.A pheromone rate-based analysis on the convergence time of ACO algorithm[J].IEEE Trans on Systems，2009，39（4）：910-923.

[5]Duan Haibin，Wang Daobo，Yu Xiufen.Markov chains and martingale theory based convergence proof of ant colony algorithm and its simulation platform[C]//Proceedings of the 6th World Congress on Intelligent Control and Automation，Dalian，China，2006.

[6]朱慶保.蟻群優(yōu)化算法的收斂性分析[J].控制與決策，2006，21（7）：763-766.

[7]沈士根，馬絢，蔣華，等.基于演化博弈論的WSNs信任決策模型與動力學分析[J].控制與決策，2012，27（8）：1133-1138.

[8]謝政.對策論[M].長沙：國防科技大學出版社，2004.

[9]詹士昌，徐婕，吳俊.蟻群算法中有關算法的最優(yōu)選擇[J].科技通報，2003，19（5）：381-386.

[10]Botee H M，Bonabeau E.Evolving ant colony optimization[J].Adv Complex Systems，1998，1：149-159.

[11]孫凱，吳紅星，王浩，等.蟻群與粒子群混合算法求解TSP問題[J].計算機工程與應用，2012，48（34）：60-63.

[12]蔣玲艷，張軍，鐘樹鴻.蟻群算法的參數(shù)分析[J].計算機工程與應用，2007，43（20）：31-36.

[13]Dorigo M，Maniezzo V，Colorni A.Ant system：optimization by a colony of cooperating agents[J].IEEE Trans on Systems，Man and Cybernetics，1996，26（1）：29-41.