劉　鍇　游曉明*　劉　升

1(上海工程技術大學電子電氣工程學院　上海 201620)

2(上海工程技術大學管理學院　上海 201620)

?

基于分層搜索的蟻群算法及收斂性分析

劉鍇1游曉明1*劉升2

1(上海工程技術大學電子電氣工程學院上海 201620)

2(上海工程技術大學管理學院上海 201620)

摘要針對蟻群算法容易陷入局部最優(yōu)的問題，提出一種新的解決連續(xù)空間優(yōu)化的蟻群分層搜索算法。該算法將蟻群搜索空間逐層分割，用信息素分布函數(shù)給出了基于分層結點的信息素分布方法。定義了適用于連續(xù)域的信息素局部更新、全局更新、狀態(tài)轉移規(guī)則，其中局部更新算子能夠通過選取合適的參數(shù)來增加解的多樣性。實驗結果表明，相比傳統(tǒng)算法，該算法全局搜索能力強，求解精度更高。該算法能達到連續(xù)域問題的理論最優(yōu)值，通過下鞅的停時理論證明了算法以概率1收斂。

關鍵詞蟻群算法連續(xù)空間優(yōu)化分層搜索下鞅

ANT COLONY ALGORITHM BASED ON HIERARCHICAL SEARCH AND ITS CONVERGENCE ANALYSIS

Liu Kai1You Xiaoming1*Liu Sheng2

1(College of Electronic and Electrical Engineering,Shanghai University of Engineering Science,Shanghai 201620,China)2(School of Management,Shanghai University of Engineering Science,Shanghai 201620,China)

AbstractFor ant colony algorithm easily falling into local optimum, we proposed a novel ant colony hierarchical search algorithm for solving continuous space optimisation. The algorithm partitions the ant colony search space hierarchically, and presents a hierarchical nodes-based pheromone distribution approach with pheromone distribution function. We defined the rules of pheromone local update, global update and state transition suitable for continuous domains, in which the local update operator could increase the diversity of solutions by selecting the appropriate parameters. Experimental results showed that comparing with traditional ant colony algorithms, the ant colony hierarchical search algorithm had stronger global search capability and higher solution accuracy. It could achieve the theoretical optimum of continuous domains problem. Moreover, by using the stopping theory of submartingale, it was concluded that the algorithm converges with probability 1.

KeywordsAnt colony algorithmContinuous space optimisationHierarchical searchSubmartingale

0引言

意大利學者M.Dorigo等人從螞蟻覓食行為中受到啟發(fā)，于1991年首次提出了蟻群算法。常見的蟻群算法模型有AS(ant system)模型、ACS(ant colony system)模型、MMAS(max-min ant system)模型等[1]。目前蟻群算法已成功應用于多種優(yōu)化問題，如車輛路徑[2]、資源調配[3]、機器人路徑規(guī)劃[4,5]等。

雖然這種自適應人工智能技術在組合優(yōu)化中應用較廣泛，求解連續(xù)空間優(yōu)化問題的蟻群算法尚缺乏理論基礎，它將搜索周期模擬成個體的進化或覓食過程，將個體對環(huán)境的適應能力作為目標函數(shù)，總體上將個體的覓食過程或優(yōu)勝劣汰過程抽象成用較好可行解取代較差可行解的迭代過程。目前主要有兩種途徑：一是將連續(xù)空間離散化[6]，從而使連續(xù)問題轉化為離散問題，但該方法能否適用于高維優(yōu)化問題還有待研究；二是與其他算法融合[7-9]，引入進化機制或某種算子彌補在連續(xù)域的適用缺陷，但收斂速度較慢。尤其應用于連續(xù)函數(shù)優(yōu)化的蟻群算法其收斂性問題還需要探討。因此，如何應用蟻群算法高效率實現(xiàn)連續(xù)空間優(yōu)化問題求解將是一個很有意義的研究課題。

許多學者提出了用于求解連續(xù)空間優(yōu)化問題的蟻群算法。文獻[10]提出了一種基于密集非遞階的連續(xù)交互式蟻群算法，該算法通過信息素交流和直接通信的融合來指導螞蟻尋優(yōu)，卻帶來了收斂速度慢、評價代價高等缺點；文獻[11]提出TCACS并比較了多組測試函數(shù)的解精度，但僅僅引入了動態(tài)調整禁忌表；文獻[12]提出了MTACO(Modified Touring Ant Colony Optimization)算法。以上這些研究取得了一定的成果，但如何提高全局搜索能力，提高收斂速度仍是有待解決的問題。在國內，大多是從仿真角度進行分析，沒有對算法的收斂性進行分析。文獻[13]將量子計算與蟻群算法相融合，提出一種連續(xù)量子蟻群算法。文獻[14]提出了一種全新的由偵察蟻和覓食蟻協(xié)作搜索的快速連續(xù)蟻群算法。本文針對函數(shù)優(yōu)化問題中的信息素分布方法、解的表示進行了研究，提出了一種蟻群分層搜索算法，相比傳統(tǒng)算法中的信息素區(qū)間分布，本文基于分層結點的分布更合理。給出了算法的收斂性分析，仿真實驗說明了本文算法全局搜索能力強，解的精度高且求解速度快。

1基于分層搜索的蟻群算法求解連續(xù)空間問題

設計連續(xù)空間蟻群算法，需要定義信息素分布函數(shù)、狀態(tài)轉移規(guī)則以及信息素更新策略。搜索空間本質上的連續(xù)性使得分布于路徑上的信息素被區(qū)間淹沒，蟻群分層搜索算法ACHSA(Ant Colony Hierarchical Search Algorithm)是將連續(xù)域中的結點分成有等級的層，信息素也是依層結點進行分布，利用蟻群優(yōu)化框架進行結點搜索。這些螞蟻在其寄居點周圍以分布函數(shù)的形式留存信息素，螞蟻智能體根據(jù)這些結點上的信息素強度確定該結點的吸引力，從而選取其最終的轉移結點。當蟻群搜索完各層后，根據(jù)當前解的函數(shù)值更新各層結點上的信息素強度。對于定義域E上的函數(shù)優(yōu)化問題，要求解的精度為小數(shù)點后位，設計 層結點。把E上的全體整數(shù)作為 層結點，中間層 上結點依次代表解的十分位，百分位，…，各層有10個結點，依次編碼為數(shù)字0~9。在一個搜索周期中，讓螞群往層數(shù)更大的結點上轉移，而不能向層數(shù)減小的結點轉移，隨著層數(shù)的遞增，蟻群的轉移步長就會越來越小。這樣通過 層后形成的通路就代表一個解，并且開始進入下一個搜索周期，螞蟻智能體根據(jù)各結點周圍的信息素強度及路徑的啟發(fā)信息選擇下一層結點。

1.1信息素分布函數(shù)

(1)

其中：xr表示個體在解空間上的位置，f(xr)是目標函數(shù)值，kr是形狀尺度系數(shù)。本文中Ar留存在某結點周圍的信息素強度用定積分式表示：

(2)

此值應該與時間t無關的。

1.2狀態(tài)轉移規(guī)則

我們采用確定性計算和隨機性選擇相結合的策略，螞蟻Ar(r=1,2,…,m)選擇第i層結點j的概率為：

(3)

其中q是區(qū)間(0,1)上的隨機數(shù)，參數(shù)q0用來調節(jié)蟻群的探索能力(exploration)和挖掘能力(exploitation)的相對強弱，q0越大，蟻群的挖掘能力越強，反之，探索能力越強。

(4)

1.3信息素更新策略

1.3.1局部更新

(5)

τi,j(t)=(1-ρ1)τi,j(t)+ρ1Δτi,j(t)

(6)

1.3.2全局更新

當所有螞蟻完成一次循環(huán)之后，會自適應地調整各結點上的信息素分布，來啟發(fā)蟻群探索解的改進方向。將路徑記錄表映射到優(yōu)化問題的解空間，計算對應點的函數(shù)值并選取最優(yōu)值。所有結點周圍殘留信息素強度以ρ2倍的速率蒸發(fā)掉，只有本次循環(huán)中最優(yōu)路徑的信息素得到補償。

(7)

至此，蟻群返回L0層，根據(jù)上一周期中路徑上信息素殘留按照狀態(tài)轉移規(guī)則開始尋找下一層結點，如此循環(huán)，直到滿足終止準則[16]：

(8)

參數(shù)取值ε1=ε2=10-4。

1.4算法描述

2) for i=1:m

3) for j=1:d

4) if j==1 按式(4)起始結點到下層的轉移概率;

5) else 按式(4)中間層的轉移概率; end

6) if q<=q0

7) if j==1 按式(3)選擇下層結點;

8) tau1(idex)=(1-ρ1rho1)*tau1(idex)+ρ1*τ0;

9) else 根據(jù)list中上一結點選擇下層結點;

10) tau(list,idex)=(1-ρ1rho1)*tau(list,idex)+ρ1*τ0;

11) else按式(4)選擇下層結點;進行信息素局部更新;

12) for i=1:m

13) for k=1:d

14) x(i)=x(i)+list(i,k)×10-k;y(i)=f(x(i)); end

15) for k=1:d-1 按式(7)進行全局更新;

16) end [y_best,x_bestidex]=min(y_min);

2算法收斂性分析

本節(jié)在轉移路徑向量列的馬氏性基礎上證明函數(shù)最小值序列是非負下鞅，并從鞅過程的停止定理證明算法以概率1收斂。

引理1最優(yōu)函數(shù)值序列{f(n),n=1,2,…}是非負下鞅。

證明螞蟻Ar的本次轉移與蟻群在前一個搜索周期到達的狀態(tài)有關，由信息素局部更新規(guī)則，第t+1步轉移概率由前一步結點周圍殘留的信息素強度決定，決定了蟻群在n+1個循環(huán)中各步轉移后的狀態(tài)，即f(n+1)只與Γ1(n),Γ2(n),…,Γm(n)有關。

(9)

式中Γ1(n),Γ2(n),…,Γm(n)是第n個周期中蟻群的搜索通路，υjk是螞蟻Ar所在結點位置，為避免信息素不斷蒸發(fā)，而算法在某幾個循環(huán)中還未改進解，信息素強度設置一個下限τmin。

定理1最優(yōu)函數(shù)值序列{f(n),n=1,2,…}以概率1收斂。

證明蟻群首次發(fā)現(xiàn)最優(yōu)解時即滿足算法終止準則，迭代次數(shù)T是最優(yōu)路徑Γ*(1),Γ*(2),…,Γ*(T)的函數(shù)，T是關于下鞅{f(n),n=1,2,…}的停時。

對于下鞅序列{f(n)}n≥1，有Ef(n)≤Ef(T)，n

=O(f(T))<+∞

3仿真實驗

(10)

ming=5e-0.5xsin(30x)+e0.2xsin(20x)+6x∈[0,8]

(11)

兩個算例中相同參數(shù)的設置如表1所示，形狀系數(shù)kr在信息素局部更新中有利于增加解的多樣性。主要結果如表2所示，兩算例都可達到理論最優(yōu)值，實驗結果優(yōu)于文獻[18]中給出的最優(yōu)值及魯棒性，min g=1.3652，R=3.24%。

表1　ACHSA參數(shù)設置

表2　測試函數(shù)優(yōu)化結果

本文算法求解式(10)的收斂曲線及找到的最優(yōu)解位置分別如圖1、圖2所示，最優(yōu)解位置用*號標識。算法的全局搜索性能較好，并且在150代以內收斂。求解式(11)的收斂曲線及找到的最優(yōu)解位置分別如圖3、圖4所示，最優(yōu)解位置用*號標識，對比文獻[18]中的收斂曲線，本文算法求解精度更高，收斂性能稍好。

圖1　測試函數(shù)f的ACHSA收斂曲線

圖2　ACHSA得到的最優(yōu)解位置

圖3　測試函數(shù)g的ACHSA收斂曲線

圖4　ACHSA得到的最優(yōu)解位置

4結語

針對連續(xù)域優(yōu)化問題，本文提出ACHSA，用分層結點模擬連續(xù)域中自變量的每位，以結點為對稱中心的分布函數(shù)來表示信息素，并經過局部更新、全局更新合理地實現(xiàn)了迭代搜索過程，最終找到最優(yōu)解。最后證明了最優(yōu)函數(shù)值序列是非負下鞅并且算法以概率1收斂，給出了算法參數(shù)的取值，仿真對比說明了本文算法的有效性，并且改善了傳統(tǒng)蟻群算法的全局搜索性能。

參考文獻

[1] Neto T,Fernandes R,Filho G,et al.A software model to prototype ant colony optimization algorithms[J].Expert Systems with Applications,2011,38(1):249-259.

[2] 徐洪麗,錢旭,岳訓,等.一種新的基于logistic混沌映像的自適應混沌蟻群優(yōu)化算法求解動態(tài)車輛路徑問題[J].計算機應用研究,2012,29(6):2058-2060.

[3] Zhang Na,Feng Zuren,Ke Liangjun.Guidance-solution based ant colony optimization for satellite control resource scheduling problem[J].Applied Intelligence,2011,35(3):436-444.

[4] 趙娟平,高憲文,符秀輝,等.移動機器人路徑規(guī)劃的改進蟻群優(yōu)化算法[J].控制理論與應用,2011,28(4):457-461.

[5] 柳長安,鄢小虎,劉春陽,等.基于改進蟻群算法的移動機器人動態(tài)路徑規(guī)劃方法[J].電子學報,2011,39(5):1220-1224.

[6] 胡中華,趙敏,姚敏.引入偵查子群的二進制蟻群算法求解函數(shù)優(yōu)化問題[J].小型微型計算機系統(tǒng),2010,31(6):1175-1178.

[7] Chang L,Liao C,Lin W B,et al.A Hybrid method based on differential evolution and continuous ant colony optimization and its application on wideband antenna design[J].Progress In Electromagnetics Research,2012,122:105-118.

[8] 李擎,張超,陳鵬,等.一種基于粒子群參數(shù)優(yōu)化的改進蟻群算法[J].控制與決策,2013,28(6):873-878.

[9] Ciornei I,Kyriakides E.Hybrid Ant Colony-Genetic Algorithm (GAAPI) for Global Continuous Optimization[J].IEEE Transactions on Systems,Man and Cybernetics-Part B:Cybernetics,2012,42(1):234-245.

[10] Dero J,Siarry P.Continuous interacting ant colony algorithm based on dense heterarchy[J].Future Generation Computer Systems,2004,5(20):841-856.

[11] Karimi A,Nobahari H,Siarry P.Continuous ant colony system and tabu search algorithms hybridized for global minimization of continuous multi-minima functions[J].Computational Optimization and Applications,2010,45(3):639-661.

[12] Karaboga N,Kalinli A,Karaboga D.Designing digital IIR filters using ant colony optimization algorithm[J].Engineering Application of Artificial Intelligence,2004,17(2):301-309.

[13] 李盼池,李士勇.求解連續(xù)空間優(yōu)化問題的量子蟻群算法[J].控制理論與應用,2008,25(2):237-241.

[14] 馬衛(wèi),朱慶保.求解函數(shù)優(yōu)化問題的快速連續(xù)蟻群算法[J].電子學報,2008,36(11):2120-2124.

[15] 汪鐳,吳啟迪.蟻群算法在連續(xù)空間尋優(yōu)問題求解中的應用[J].控制與決策,2003,18(1):45-48.

[16] Socha K,Dorigo M.Ant colony optimization for continuous domains[J].European Journal of Operational Research,2008,185(3):1155-1173.

[17] Liu Kai,You Xiaoming,Liu Sheng.The martingale process of ant colony optimization algorithms and its convergence analysis[J].ICIC Express Letters,Part B:Applications,2014,5(4):1105-1110.

[18] 段海濱,馬冠軍,王道波,等.一種求解連續(xù)空間優(yōu)化問題的改進蟻群算法[J].系統(tǒng)仿真學報,2007,19(5):974-977.

中圖分類號TP18

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.049

收稿日期：2014-06-21。國家自然科學基金項目(61075115)；上海市教委科研創(chuàng)新重點項目(12ZZ185)；上海市學科專業(yè)建設項目(XK CZ1212)。劉鍇，碩士生，主研領域：嵌入式系統(tǒng)與智能信息處理。游曉明，教授。劉升，教授。