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

劉　鍇　游曉明*　劉　升

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

2(上海工程技術(shù)大學(xué)管理學(xué)院　上海 201620)

?

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

劉鍇1游曉明1*劉升2

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

2(上海工程技術(shù)大學(xué)管理學(xué)院上海 201620)

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

關(guān)鍵詞蟻群算法連續(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引言

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

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

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

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

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

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

(1)

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

(2)

此值應(yīng)該與時(shí)間t無(wú)關(guān)的。

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

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

(3)

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

(4)

1.3信息素更新策略

1.3.1局部更新

(5)

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

(6)

1.3.2全局更新

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

(7)

至此，蟻群返回L0層，根據(jù)上一周期中路徑上信息素殘留按照狀態(tài)轉(zhuǎn)移規(guī)則開(kāi)始尋找下一層結(jié)點(diǎn)，如此循環(huán)，直到滿足終止準(zhǔ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)起始結(jié)點(diǎn)到下層的轉(zhuǎn)移概率;

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

6) if q<=q0

7) if j==1 按式(3)選擇下層結(jié)點(diǎn);

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

9) else 根據(jù)list中上一結(jié)點(diǎn)選擇下層結(jié)點(diǎn);

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

11) else按式(4)選擇下層結(jié)點(diǎn);進(jìn)行信息素局部更新;

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)進(jìn)行全局更新;

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

2算法收斂性分析

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

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

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

(9)

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

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

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

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

=O(f(T))<+∞

3仿真實(shí)驗(yàn)

(10)

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

(11)

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

表1　ACHSA參數(shù)設(shè)置

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

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

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

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

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

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

4結(jié)語(yǔ)

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

參考文獻(xiàn)

[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] 徐洪麗,錢旭,岳訓(xùn),等.一種新的基于logistic混沌映像的自適應(yīng)混沌蟻群優(yōu)化算法求解動(dòng)態(tài)車輛路徑問(wèn)題[J].計(jì)算機(jī)應(yīng)用研究,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] 趙娟平,高憲文,符秀輝,等.移動(dòng)機(jī)器人路徑規(guī)劃的改進(jìn)蟻群優(yōu)化算法[J].控制理論與應(yīng)用,2011,28(4):457-461.

[5] 柳長(zhǎng)安,鄢小虎,劉春陽(yáng),等.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃方法[J].電子學(xué)報(bào),2011,39(5):1220-1224.

[6] 胡中華,趙敏,姚敏.引入偵查子群的二進(jìn)制蟻群算法求解函數(shù)優(yōu)化問(wèn)題[J].小型微型計(jì)算機(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ìn)蟻群算法[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)化問(wèn)題的量子蟻群算法[J].控制理論與應(yīng)用,2008,25(2):237-241.

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

[15] 汪鐳,吳啟迪.蟻群算法在連續(xù)空間尋優(yōu)問(wèn)題求解中的應(yīng)用[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)化問(wèn)題的改進(jìn)蟻群算法[J].系統(tǒng)仿真學(xué)報(bào),2007,19(5):974-977.

中圖分類號(hào)TP18

文獻(xiàn)標(biāo)識(shí)碼A

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

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