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

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

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

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

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

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

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

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

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

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

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

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

1.4 全局單位空間還原

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

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

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

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

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

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

這種策略存在如下缺點(diǎn)，對(duì)于所有螞蟻?zhàn)哌^(guò)的路徑，某些路徑上可能得到很差的解，但是由于存在信息素增量，其值會(huì)逐漸地增大，變成假的最優(yōu)解；若最優(yōu)解還未被走過(guò)時(shí)，該路徑上的信息素濃度因?yàn)橹挥姓舭l(fā)量而變得越來(lái)越小而被忽略。那么在下次搜索中，最優(yōu)解對(duì)應(yīng)的路徑節(jié)點(diǎn)被選取的概率會(huì)變小而引入誤導(dǎo)信息，形成大量無(wú)效搜索，運(yùn)算速度會(huì)降低。

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

此規(guī)則不僅減弱了已走過(guò)路徑上的信息素更新量速度，避免因?yàn)樾畔⑺卦黾舆^(guò)多而導(dǎo)致下次搜索的誤判。而且增強(qiáng)了螞蟻未到達(dá)的路徑的信息素更新速度，避免了因?yàn)樾畔⑺負(fù)]發(fā)而導(dǎo)致極值的流失。確保信息素能夠正確地引導(dǎo)螞蟻的下一次搜索，削弱了非最佳路徑上的信息素更新對(duì)最佳路徑上信息素的影響，提高搜索效率。

2.2 局部路徑上的搜索策略

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

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

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

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

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

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

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

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

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

2.3 自適應(yīng)的蟻群算法流程

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

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

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

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

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

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

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

3 實(shí)驗(yàn)驗(yàn)證

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

3.1 實(shí)驗(yàn)1

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

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

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

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

3.2 實(shí)驗(yàn)2

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

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

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

4 結(jié) 論

論文提出的算法主要是對(duì)局部路徑上的搜索策略和全局路徑上的信息素更新進(jìn)行了改進(jìn)。此算法保證了在搜索過(guò)程中，搜索路徑上信息素的分配與所得解的最優(yōu)性成正比，即所得解質(zhì)量越好，所對(duì)應(yīng)的路徑上信息素濃度越高。保證下次搜索的有效性。仿真研究表明，算法能夠自適應(yīng)地調(diào)整螞蟻巡游過(guò)程中所經(jīng)路徑上的信息素更新和局部搜索時(shí)的路徑，通過(guò)測(cè)試并與其他優(yōu)化算法相比較，可以很清晰地看到該算法具有良好的全局搜索能力，避免過(guò)早陷入局部最優(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ì)會(huì)，高齊圣，徐心和.自適應(yīng)蟻群算法[J].控制理論與應(yīng)用，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)化問(wèn)題[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)化中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，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)化的一個(gè)蟻群算法設(shè)計(jì)[J].微電子學(xué)與計(jì)算機(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)化的自適應(yīng)蟻群算法[J].計(jì)算機(jī)工程與應(yīng)用，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ìn)蟻群算法[J].微電子學(xué)與計(jì)算機(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]張影，劉艷秋.軟計(jì)算方法[M].北京：科學(xué)出版社，2002.