基于自適應信息素調整的連續空間優化蟻群算法

王團結，侯立剛，蘇成利

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

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

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

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

1 連續空間優化的蟻群算法

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

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

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

1.2 蟻群狀態轉移規則

1.3 信息素更新規則

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

1.4 全局單位空間還原

得到全局最優解之后，將最優解經映射f－1還原到初始空間。

2 自適應調整信息素的蟻群算法

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

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

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

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

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

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

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

2.2 局部路徑上的搜索策略

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

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

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

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

若某螞蟻在本次巡游之后已經達到最優解xbest，那么在下次搜索時，將在該最優解xbest的鄰域內搜索。即在的鄰域范圍內，根據式（13）進行移動。

xmbest表示下次搜索結束時，螞蟻達到的最優解。搜索公式如下：

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

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

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

2.3 自適應的蟻群算法流程

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

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

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

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

4）達到最優解的螞蟻，根據式（13）、式（14）在最優解鄰域附近進行搜索，若在搜索過程中出現了早熟現象，可根據式（15）進行調整，跳出本次搜索，執行步驟2。

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

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

3 實驗驗證

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

3.1 實驗1

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

由于算法的隨機特性，對兩種算法的性能比較只能在統計學意義下進行，優化結果見表1。

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

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

3.2 實驗2

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

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

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

4 結 論

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

[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]楊勇，宋曉峰，王建飛，等.蟻群算法求解連續空間優化問題[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]李向麗，楊慧中，魏麗霞.基于退火的蟻群算法在連續空間優化中的應用[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]熊偉清，余舜浩，魏平.用于求解函數優化的一個蟻群算法設計[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]趙寶江，金俊，李士勇.一種求解函數優化的自適應蟻群算法[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]周曉靜，呂翠英.基于全局單位化的連續函數優化的改進蟻群算法[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.