王團結(jié)，侯立剛，蘇成利

（遼寧石油化工大學 信息與控制工程學院，遼寧 撫順 113001）

蟻群算法是一種新興的仿生智能化算法。與其他算法相比，蟻群算法具有更高可靠性、搜索時間更短、更易于計算機實現(xiàn)等優(yōu)點。主要用來求解簡單離散的組合優(yōu)化問題（如旅行商問題[1]、指派問題），在求解連續(xù)問題優(yōu)化方面研究還很少[2-3]。同時，由于蟻群算法產(chǎn)生時間比較短，沒有形成十分系統(tǒng)的理論體系，存在著一些不足之處，例如算法求解效率低，收斂性差，算法求解結(jié)果有較大的分散性的缺點。

為了克服這些缺點，一些學者對基本蟻群算法的參數(shù)進行了很多改進，如信息素分配、路徑搜索、可行解的選擇、信息素揮發(fā)系數(shù)等，并將其用于求解連續(xù)空間優(yōu)化問題。例如，文獻[4]中將在螞蟻巡游路徑上的信息素分布采用特定的分布函數(shù)來近似模擬，將螞蟻每一次巡游得到的路徑值在連續(xù)的解空間上選取。文獻[5]中改進螞蟻移動過程中的信息素更新規(guī)則，并且加入了確定性的局部搜索策略。文獻[6]在文獻[5]基礎上對于容易陷入局部最優(yōu)的路徑搜索過程，加入了退火的思想。文獻[7]中引入遺傳算法中的編碼思想，將函數(shù)優(yōu)化問題轉(zhuǎn)換為在有向圖中搜索出最優(yōu)路徑的問題來解決。文獻[8]中先將連續(xù)空間離散化，再依據(jù)螞蟻巡游過程中得到解的情況調(diào)整螞蟻的路徑選擇策略和信息素更新策略。文獻[9]中將螞蟻每次尋優(yōu)的過程轉(zhuǎn)化為十進制編碼選擇數(shù)字的過程。即：將蟻群每一步尋優(yōu)的過程看成一次從0～9這十個數(shù)字中選擇一個數(shù)字，最終生成一個十進制數(shù)字串的過程。在螞蟻一次尋優(yōu)結(jié)束之后，將本次得到的信息記錄在其巡游的路徑上以指導下一次螞蟻尋優(yōu)時選擇各個數(shù)字的概率。這樣就能動態(tài)地實現(xiàn)了螞蟻巡游路徑及路徑上信息素的更新。

文獻[9]中的信息素更新時，具有很大的隨機因素，目標導向不強，這就將導致搜索時間過長，搜索區(qū)域模糊等弊端。論文對文獻[9]中的算法作了改進，提出了一種能夠自適應地調(diào)整信息素的蟻群算法，算法采用了啟發(fā)式的信息素分配算法及基于給定目標值的確定性搜索方法尋找最優(yōu)解，根據(jù)每次尋優(yōu)時，目標函數(shù)值的變化來動態(tài)地調(diào)整螞蟻的巡游路徑，這樣有利于提高螞蟻的自學習能力，對搜索空間上選擇概率大的區(qū)域作更加精細的搜索，同時為了防止搜索陷入局部極值，在局部搜索過程中加入了模擬退火的思想，為了探索到更大的空間，將采取多樣性的路徑選擇，從而保證能夠快速地找到連續(xù)空間問題優(yōu)化的全局最優(yōu)解。

1 連續(xù)空間優(yōu)化的蟻群算法

文獻[9]中將螞蟻的每次移動看作是為每個數(shù)字位上選擇0～9這十個數(shù)字的過程。考慮到空間復雜性，先將空間單位化。然后作離散化處理，根據(jù)優(yōu)化問題所要求的精度讓螞蟻在自變量的每個數(shù)字位上對0～9十個數(shù)字選擇一個數(shù)字，使最終生成解的過程變成螞蟻在每個數(shù)字位選擇數(shù)字并最終生成含有位十進制數(shù)字的過程。以一個最大值尋優(yōu)問題為例來說明，設其目標函數(shù)為：Max Z＝f（x）。其算法基本思想如下：

1.1 蟻群的位置初始化及信息素初始化

每只螞蟻的初始位置選擇數(shù)字0，所有路徑上的信息素初始濃度設為一個較小的常值τ0。

1.2 蟻群狀態(tài)轉(zhuǎn)移規(guī)則

1.3 信息素更新規(guī)則

螞蟻k按照基本蟻群算法中的局部更新規(guī)則對信息素進行局部更新[8]。當螞蟻完成一次循環(huán)時，對全局路徑信息進行更新。先按照（3）式對路徑進行解碼，算出螞蟻k對應的自變量值x′（k）。

1.4 全局單位空間還原

得到全局最優(yōu)解之后，將最優(yōu)解經(jīng)映射f－1還原到初始空間。

2 自適應調(diào)整信息素的蟻群算法

算法對搜索過程中的全局信息素更新策略和局部路徑搜索策略進行了改進。主要思想：在全局路徑上，對螞蟻走過的路徑，適當減弱信息素增加的速度；對螞蟻未走的路徑，適當增強信息素增加的速度。而在一只螞蟻要進行下次尋優(yōu)的局部路徑上，根據(jù)螞蟻以往得到解的情況，適當改變下次螞蟻搜索的范圍大小。

2.1 全局路徑上信息素的更新策略，

在基本蟻群算法中 蟻群只有在一個搜索周期結(jié)束之后完成一次信息素的更新，將所有螞蟻要經(jīng)過節(jié)點間的路段上信息素更新狀態(tài)用一個信息素增量Δτij來表示，增量值的大小表示目標值的函數(shù)[7]。n

式中，fk為螞蟻的搜索路徑所對應的目標函數(shù)值，τ（）為非增量函數(shù)，對于螞蟻未走過的路徑，其信息素的增量為零。

這種策略存在如下缺點，對于所有螞蟻走過的路徑，某些路徑上可能得到很差的解，但是由于存在信息素增量，其值會逐漸地增大，變成假的最優(yōu)解；若最優(yōu)解還未被走過時，該路徑上的信息素濃度因為只有蒸發(fā)量而變得越來越小而被忽略。那么在下次搜索中，最優(yōu)解對應的路徑節(jié)點被選取的概率會變小而引入誤導信息，形成大量無效搜索，運算速度會降低。

針對上述缺點，論文采用以下信息素更新算法：在全局路徑上，假設L*（t）是螞蟻搜索了次之后所得到的最佳路徑，L*（t）是螞蟻未走過的路徑，L*（t）并且對應路徑上的目標函數(shù)值滿足：

此規(guī)則不僅減弱了已走過路徑上的信息素更新量速度，避免因為信息素增加過多而導致下次搜索的誤判。而且增強了螞蟻未到達的路徑的信息素更新速度，避免了因為信息素揮發(fā)而導致極值的流失。確保信息素能夠正確地引導螞蟻的下一次搜索，削弱了非最佳路徑上的信息素更新對最佳路徑上信息素的影響，提高搜索效率。

2.2 局部路徑上的搜索策略

由于基本蟻群算法中的信息素是均勻分布的，這將導致在下一搜索周期中，新的搜索對于不同的路徑具有相同的選擇概率，使算法失去多樣性的選擇概率，不能保證得到的是最優(yōu)解。合理的搜索策略應為：對于能夠得到更多較好解的區(qū)域，下一次的搜索應在較小的區(qū)域內(nèi)進行更精細的搜索，即縮短該區(qū)域的“搜索步長”保證得到更多較好解。此種區(qū)域搜索策略可使搜索過程具有較好的收斂性。而對于較少或無較好解的區(qū)域，應保證下次搜索向最優(yōu)解移動的同時，采用擴大空間搜索范圍，即增大該區(qū)域的“搜索步長”，加速搜索速率，以保證解的有效性。

若某螞蟻在本次巡游之后未搜索到最優(yōu)解，那么，在下次搜索時，將以本次搜索所得到的最優(yōu)解作為目標值進行某一概率的定向移動。移動概率：

其中，τbest表示在最優(yōu)解處的信息素大小，τi表示螞蟻在i處的信息素大小。則在下次搜索時，未達到最優(yōu)解的螞蟻將按照式（12）進行搜索。

其中，p0∈（0，1），α∈（0，1）。

若某螞蟻在本次巡游之后已經(jīng)達到最優(yōu)解xbest，那么在下次搜索時，將在該最優(yōu)解xbest的鄰域內(nèi)搜索。即在的鄰域范圍內(nèi)，根據(jù)式（13）進行移動。

xmbest表示下次搜索結(jié)束時，螞蟻達到的最優(yōu)解。搜索公式如下：

式中，ω是螞蟻每次搜索的長度，ω=0.1ω，即一次搜索結(jié)束之后，搜索長度縮小十倍。

在最優(yōu)解鄰域范圍內(nèi)搜索時，可能會遇到最優(yōu)值早熟的問題。這就要求在搜索過程中，引入抑制早熟的機制，以減少大量無效搜索。論文加入模擬退火的思想，模擬退火算法是先接受某一特定解，然后在此解的鄰域中隨機生成另外一個解，根據(jù)制定的規(guī)則，允許目標函數(shù)在一個有限的范圍內(nèi)變化，判斷是否接受新生成的解。其基本算法如下：設給定某一位置點xbest，新的位置點x′best，那么根據(jù)式（15）概率公式判斷是否接受新的解x′best[10]。

其中，ε為允許目標函數(shù)變化的范圍，取ε=（0.2~0.4）fxbest。

2.3 自適應的蟻群算法流程

根據(jù)以上思想，論文提出一種能夠自適應地調(diào)整信息素更新和局部搜索路徑的蟻群算法。改進的算法流程如下：

1）根據(jù)具體問題，確定搜索的最大次數(shù)、螞蟻數(shù)量、蟻群初始化位置和各個路徑上初始信息素濃度。

2）計算出一只螞蟻的在一次搜索周期結(jié)束之后取得最優(yōu)解的位置信息。

3）未達到最優(yōu)解的螞蟻，根據(jù)式（11）、式（12）進行搜索，向本次取得最優(yōu)解的位置移動。

4）達到最優(yōu)解的螞蟻，根據(jù)式（13）、式（14）在最優(yōu)解鄰域附近進行搜索，若在搜索過程中出現(xiàn)了早熟現(xiàn)象，可根據(jù)式（15）進行調(diào)整，跳出本次搜索，執(zhí)行步驟2。

5）對所有的螞蟻完成本次搜索后，按照式（5）、式（6）、式（9）、式（10）進行全局信息素更新。

6）重復步驟2）直到滿足結(jié)束搜索的條件。

3 實驗驗證

為了驗證所提出改進蟻群算法的有效性，論文選取了2個典型函數(shù)進行測試。

3.1 實驗1

對下面的連續(xù)函數(shù)極值問題進行仿真研究，測試函數(shù)，max f1=10sin（5x）+7cos（4x），x∈[0，10]。該優(yōu)化問題具有個局部極值點，且對優(yōu)化變量的取值十分敏感。分別采用本文的蟻群算法和文獻[9]中蟻群算法對該函數(shù)進行測試。算法的參數(shù)設置如下：循環(huán)次數(shù)為20，蟻群規(guī)模為10，變量x∈[0，10]，α=1，ω=1。

由于算法的隨機特性，對兩種算法的性能比較只能在統(tǒng)計學意義下進行，優(yōu)化結(jié)果見表1。

表1 文中算法和文獻中的算法優(yōu)化結(jié)果比較Tab.1 Comparing result via the algorithm in this paper and in References 9

上表表明了該算法能夠用于連續(xù)空間優(yōu)化問題的求解且收斂迅速且耗時少，有著較好的穩(wěn)定性。在搜索過程中，算法雖然有短暫的停滯，但會很快跳出且繼續(xù)優(yōu)化直到找到全局最優(yōu)解。

3.2 實驗2

采用1個二維函數(shù)來驗證所提蟻群算法的有效性。測試函數(shù)如下1，2。參數(shù)取值為蟻群規(guī)模設定為90，算法迭代100次結(jié)束，α=0.8，ω=1，ρ=0.8，τ0=0.1，Q0=0.8。因為蟻群算法的隨機性，取尋優(yōu)20次的平均值作為平均最優(yōu)值，以20次中出現(xiàn)的最好解為最優(yōu)值，取 絕對誤差=|最優(yōu)值一精確最優(yōu)值|。

將論文中提出的改進蟻群算法與文獻[5]、文獻[6]中和文獻[9]中優(yōu)化結(jié)果進行的比較結(jié)果如表2所示。有表中數(shù)據(jù)可知，通過與其他搜索算法的比較可知，為了得到最優(yōu)值，文中蟻群算法只需循環(huán)98次就得到較好的解，而其他搜索算法需要更多次迭代。優(yōu)化結(jié)果表明，改進的蟻群算法不僅可以應用于對連續(xù)問題的求解，同時又能較快地搜索到最好解，且不易陷入局部極值。

表2 文中算法和文獻[5]、文獻[6]、文獻[9]的算法優(yōu)化結(jié)果比較Tab.2 Comparing result via the algorithm in this paper，in References 5，6 and 9

4 結(jié) 論

論文提出的算法主要是對局部路徑上的搜索策略和全局路徑上的信息素更新進行了改進。此算法保證了在搜索過程中，搜索路徑上信息素的分配與所得解的最優(yōu)性成正比，即所得解質(zhì)量越好，所對應的路徑上信息素濃度越高。保證下次搜索的有效性。仿真研究表明，算法能夠自適應地調(diào)整螞蟻巡游過程中所經(jīng)路徑上的信息素更新和局部搜索時的路徑，通過測試并與其他優(yōu)化算法相比較，可以很清晰地看到該算法具有良好的全局搜索能力，避免過早陷入局部最優(yōu)的現(xiàn)象，搜索次數(shù)較少，尋優(yōu)結(jié)果精度高。

[1]Dorigo M，CambardellaL M.Ant colony system：A cooperative learning approach to the traveling salesman problem[J].IEEE Transaefionson Evolutionary Computation，1997，1（1）：53－66.

[2]Bilchev GA，Parmee IC.The Ant Colony MetapHor for Searching Continuous Design Spaces[J].Lecture Notes in Computer Science，1995（993）：25－39.

[3]張紀會，高齊圣，徐心和.自適應蟻群算法[J].控制理論與應用，2000，17（1）：1－8.ZHANG Ji-hui，GAO Qi-sheng，XU Xin-he.Adaptive ant colony algorithm[J].Control Theory and Applications，2000，17（1）：1－8.

[4]WANG Lei，WU Qi-di.Ant system algorithm in continuous space optimization[J].Control and Decision，2003，18（1）：45－48.

[5]楊勇，宋曉峰，王建飛，等.蟻群算法求解連續(xù)空間優(yōu)化問題[J].控制與決策，2003，18（5）：573－576.YANG Yong，SONG Xiao-feng，WANG Jian-feng.Ant colony algorithm for continuous space optimization[J].Control and Decision，2003，18（5）：573－576.

[6]李向麗，楊慧中，魏麗霞.基于退火的蟻群算法在連續(xù)空間優(yōu)化中的應用[J].計算機工程與應用，2007，43（23）：74－76.LI Xiang-li，YANG Hui-zhong，WEI Li-xia.Application of ant colony algorithm in the continuous space optimization based on annealing[J].Computer engineering and Applications，2007，43（23）：74－76.

[7]熊偉清，余舜浩，魏平.用于求解函數(shù)優(yōu)化的一個蟻群算法設計[J].微電子學與計算機，2003，20（1）：23－25.XIONG Wei-qing，YU Shun-hao，WEI Ping.Design of ant colony algorithm for function optimization[J].Microelectronics and Computer，2003，20（1）：23－25.

[8]趙寶江，金俊，李士勇.一種求解函數(shù)優(yōu)化的自適應蟻群算法[J].計算機工程與應用，2007，43（4）：40－43.ZHAO Bao-jiang，JIN Jun，LI Shi-yong.Ant colony algorithm adaptively solving function optimization[J]. Computer Engineering and Applications，2007，43（4）：40－43.

[9]周曉靜，呂翠英.基于全局單位化的連續(xù)函數(shù)優(yōu)化的改進蟻群算法[J].微電子學與計算機，2009，26（4）：54－57.ZHOU Xiao-jing，LV Cui-ying.Improved ant colony algorithm for continuous function optimization based on global unit[J].Microelectronics and Computer，2009，26（4）：54－57.

[10]張影，劉艷秋.軟計算方法[M].北京：科學出版社，2002.