群體智能優(yōu)化算法

第18卷第8期計算機技術(shù)與發(fā)展Vol. 18 No.82008年8月COMPUTER TECHNOLOCY AND DEVELOPMENTAug. 2008群體智能優(yōu)化算法王艷玲,李龍澍,胡哲(安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院,安徽合肥230039)摘要:群體智能優(yōu)化算法利用群體的優(yōu)勢,在沒(méi)有集中控制并且不提供全局模型的前提下,為尋找復雜的分布式問(wèn)題的解決方案提供了基礎。介紹了兩種群體智能算法模型:蟻群算法模型和粒子群算法模型,研究了兩種算法的原理機制、基本模型、流程實(shí)現、改進(jìn)思想和方法;通過(guò)仿真把蟻群算法與其他啟發(fā)式算法的計算結果作對比,驗證了蟻群算法具有很強的發(fā)現較好解的能力,不容易陷入局部最優(yōu);微粒群算法保留了基于種群的并行的全局搜索策略,采用簡(jiǎn)單的速度-位移模型操作,在實(shí)際應用中取得了較高的成功率。關(guān)鍵詞:群體智能;蟻群算法;粒子群算法;啟發(fā)式算法中圖分類(lèi)號:TP18文獻標識碼:A文章編號:1673- 629X(2008)08 -0114- 04Swarm Intelligence Optimization AlgorithmWANG Yan-ling,LI Long-shu, HU Zhe(School of Computer Science and Tech. , Anhui Univ. ,Hefei 230039 ,China)Abstract:By the use of groups' advantages, in the absence of centralized control and without providing the overall model situation, swarmnelligence optimum algorithm provides the foundation on finding complex distributed solutions to the problem. Introduces the two swarmintelligence algorithm models: ant colony algorithm model and the particle swam algorithm model, researches on principle mechanism, thebasic model,process realization and improved ideas and methods; and by comparing the calculation results of the ant c∞olony algorithm andother heuristic algorithm through the simulation,proved that the ant c∞olony algorithm has a strong ability to find better solutions, and isnot easy for a local optimum. The algorithm which besed on the population of reservations, parallel global search strategy, using simplyspeed - displacemnent model operation,has been made in a higher success rate in practical application.Key words:swarm itelligence; ant colony optimization algorithm;pericle swarm optimization; heuristic algorithm0引言法( Particle Swarm Optimization,PSO)[3]。前者是對螞受社會(huì )性昆蟲(chóng)行為的啟發(fā),計算機工作者通過(guò)對蟻群落食物采集過(guò)程的模擬，已經(jīng)成功運用在很多離社會(huì )性昆蟲(chóng)的模擬產(chǎn)生了一系列對于傳統問(wèn)題的新的散優(yōu)化問(wèn)題上;后者是源于對鳥(niǎo)群捕食行為的研究,算解決方法,這些研究就是群體智能的研究。群體智能法簡(jiǎn)單容易實(shí)現并且沒(méi)有許多參數需要調整,目前已中的群體指的是“--組相互之間可以進(jìn)行直接通信或廣泛應用于函數優(yōu)化、神經(jīng)網(wǎng)絡(luò )訓練、模糊系統控制以者間接通信(通過(guò)改變局部環(huán)境)的主體,這組主體能及其他遺傳算法的應用領(lǐng)域。夠合作進(jìn)行分布問(wèn)題求解”。而所謂群體智能指的是“無(wú)智能的主體通過(guò)合作表現出智能行為的特性”。群1蟻群優(yōu)化算法體智能在沒(méi)有集中控制并且不提供全局模型的前提1.1 蚊群算法原理下,為尋找復雜的分布式問(wèn)題的解決方案提供了基礎。受螞蟻覓食時(shí)的通信機制的啟發(fā),20世紀90年在計算智能領(lǐng)域有兩種基于群體智能的算法:蟻代Dorigo提出了蟻群算法來(lái)解決經(jīng)典的“旅行商問(wèn)群算法(Ant Colony Optimization,ACO)1,2]和粒子群算題”。蟻群算法設計虛擬的“螞蟻”將摸索不同路線(xiàn),并留下會(huì )隨時(shí)間逐漸消失的虛擬“信息素”。虛擬的“信息素”也會(huì )揮發(fā),每只螞蟻每次隨機選擇要走的路徑,收稿日期:2007-11-27它們中國煤化工息素比較濃的路徑?；痦椖?國家自然科學(xué)基金資助項目(60273043);安徽省自然科根據"學(xué)基金資助項目(050420204)YCNMHC則，即可選擇出最作者簡(jiǎn)介:王艷玲(1981-),女,安徽亳州人,碩士研究生,研究方向佳路線(xiàn)。出了這個(gè)異法利用」正反饋機制,使得較短為智能軟件;李龍澍,教授,博士生導師.研究方向為智能軟件。的路徑能夠有較大的機會(huì )得到選擇,并且由于采用了第8期王艷玲等:群體智能優(yōu)化算法●115●概率算法,所以它能夠不局限于局部最優(yōu)解。實(shí)驗結蟻群系統:蟻群系統是對AS算法的選路和信息果表明蟻群優(yōu)化算法具有較強的魯棒性和搜索較好解更新策略作了相應的改進(jìn),即:的能力,但同時(shí)也存在一些缺陷,如收斂速度慢、易出1)采用偽隨機比率選擇規則的選路方式,即對于現停滯現象等。在城市i的螞蟻按公式(3)選擇下一個(gè)城市j:1.2 AS 算法模型fang .maex{茹. 囑}ifq≤qo考慮到真實(shí)蟻群的行為與TSP問(wèn)題的相似性,蟻否則,按公式(2)進(jìn)行概率式搜索群算法(AS)首先被應用于平面上n個(gè)城市的TSP向題[41。n個(gè)城市的TSP問(wèn)題即求從某-個(gè)城市出發(fā),經(jīng)其中,q是在[0,1]區間均勻分布的隨機數,qo是一個(gè)過(guò)n- 1個(gè)城市各一次,最后回到出發(fā)點(diǎn)的最短環(huán)路。參數(0≤9qo≤1),s為根據方程式(3)給出的概率分為模擬實(shí)際螞蟻的行為,首先引人如下記號:布所選出的一個(gè)隨機變量。m表示蟻群中螞蟻的數量;n表示城市的數量;2)局部信息更新。螞蟻從城市i轉移到城市j后，di表示城市i和城市j的距離;r;(t)表示t時(shí)刻在邊路徑(i,j)上的信息量按公式(4)進(jìn)行更新:(i,j)上的信息素軌跡強度;w表示邊(i,j)的能見(jiàn)tg=(1-E)●rqj+ξ●τo， ξ∈(0,1) (4)度,在螞蟻算法中,的通常取城市i和城市j之間距離其中τo為常數,ξ∈(0,1) 為可調參數。的倒數,即n;= 1/dy;Of表示螞蟻k在邊(i,j)上留3)全局信息更新。針對全局最優(yōu)解所屬的邊按公下的單位長(cháng)度軌跡信息素量;幬表示螞蟻k的轉移概式(5)進(jìn)行信息更新:率,j是尚未訪(fǎng)問(wèn)的城市。rj(t+ 1) = (1-p). r;(t)+ ρ° O增(t),p∈各路徑上的信息量相等,設rj(0) = C(C為常(0,1)數)。每只螞蟻根據路徑上的保留信息獨立地選擇下一O增= 1/L曲(5)個(gè)城市。在時(shí)刻t,螞蟻k從城市i轉移到城市j的概率其中L勸為當前全局最優(yōu)解的長(cháng)度。格為:最大-最小螞蟻系統(MMAS)[6]:與AS相比,主,ifj∈alwede要作了如下改進(jìn):端=(1)①每次循環(huán)結束后,只有最優(yōu)解所屬路徑上的信否則息被更新;其中,a表示螞蟻在運動(dòng)過(guò)程中所積累的信息量的重②為了避免搜索時(shí)出現停滯現象,各路徑上的信要程度;β表示螞蟻在運動(dòng)過(guò)程中啟發(fā)信息在螞蟻選息量被限制在范圍[τman,Tmx]內;擇路徑中的重要程度。alwele = {0,1,2,,n-1}-③初始時(shí)刻,各路徑上的信息量取最大值。所有tabuk表示螞蟻k下一步允許選擇的所有城市，列表.螞蟻完成一次循環(huán)后,按公式(6)對路徑上的信息作tabu,記錄了當前螞蟻k走過(guò)的城市,當所有n個(gè)城市全局更新:都加人到tabuy中時(shí),螞蟻k便完成了一次循環(huán),此時(shí)rg(t+ 1)=(1- p).q;(t)+ p.0rm(t),p∈螞蟻k所走過(guò)的路徑便是問(wèn)題的一個(gè)解。當所有螞蟻完成一次循環(huán)后,各路徑上的信息要根據(2)式調整:0ro= 1/Lm(6)rv(r+ n)=(1-p).τg(l)+Oτj ρ∈ (0,1)其中,Lou為本次循環(huán)的最優(yōu)解。1.4算法流程O(píng)r。(t)= Z0t()(2)步驟1 nc ←0(nc為迭代步數或搜索次數);各其中pρ表示路徑上信息的蒸發(fā)系數, 1- p表示信息的τ,和Oτ,的初始化;將m只螞蟻置于n個(gè)頂點(diǎn)上;保留系數;0tj表示本次循環(huán)路徑ij上信息的增量,如步驟2將每個(gè)螞蟻的初時(shí)出發(fā)點(diǎn)置于當前解集果螞蟻k沒(méi)有經(jīng)過(guò)路徑i,則0塔的值為零,否則為中;對每個(gè)螞蟻k(k = 1,2.**,m),按概率移至下一Q/L;(其中Q為常數, L&表示第k只螞蟻在本次循環(huán)個(gè)頂點(diǎn)j;將頂點(diǎn)j置于當前解集;中所走過(guò)的路徑的長(cháng)度)。步驟3計算每 個(gè)螞蟻的路徑長(cháng)度LQ(k = 1,2,1.3 蟻群優(yōu)化算法中國煤化工針對AS算法的不足,一些學(xué)者提出了許多改進(jìn)[HCNMHG軌跡強度;的螞蟻算法,如蟻群系統、最大-最小螞蟻系統和帶精步驟5對各邊弧(i,j),置 Otrj←0,nc←mc +英策略的螞蟻系統[$]等。1;計算機技術(shù)與發(fā)展第18卷步驟6若nc <預定的迭代次數且無(wú)退化行為，2.2 基本粒子群模型則轉步驟2;假設m個(gè)粒子組成-一個(gè)種群,在D維的空間步驟7輸出 目前最好解。[Xmm,Xx]D中搜索。第i個(gè)粒子在第t代的位置為1.5蚊群算法的應 用及與其他算法的比較X;(t) = (xi1,Ii2."",xn),速度為V;(t) = (V1,V2,蟻群算法作為一種新的群體智能啟發(fā)式優(yōu)化算.. vp)。粒子本身目前所找到的最優(yōu)解pBest為P;(t)法,主要用于求解組合優(yōu)化問(wèn)題,其中包括旅行商問(wèn)題= (Pi,e.*",po),整個(gè)種群目前找到的最優(yōu)解(TSP)、車(chē)間任務(wù)調度向題(VRP)7]、圖著(zhù)色問(wèn)題gBest為Pg(t) = (P[+)2e.".pn)。按追隨最好位置(GCP)[8]、有序排列問(wèn)題(SOP)以及網(wǎng)絡(luò )路由問(wèn)題等。的原理,在每個(gè)迭代周期中，粒子按(7)、(8)式更新速為了說(shuō)明蟻群算法的優(yōu)點(diǎn)與不足,給出用ACS求度和位置。解TSP的實(shí)驗結果,該實(shí)驗中除ACS外的其他結果都vu(t+1)= w. vu(t) + c1●rand().(pu(t)-來(lái)源于文獻[9],取10次實(shí)驗的平均值。進(jìn)行對比的xu(t)) +c2. rand().(pr(t)- xa(t))(7)優(yōu)化算法有:模擬退火法(SA) ,進(jìn)化計算(EP),遺傳算xu(t+ 1)= xu(t) + vu(t)(8)法(GA)和模擬退火與遺傳算法相結合的算法(AG)其中c1為認知因子,c2為社會(huì )因子,通常c1= c2=2,(見(jiàn)表1)。ACS的參數設為M= 10,β=2,qo=0.9,rand() 為[0,1]之間的隨機數。為了使速度不至于過(guò)a= ρ=0.1,to= (n. Lm)-。大,把Vs限制在[Vai,V]之內,V.和Vx為常表1 TSP問(wèn)題的多種優(yōu)化算法對比數,通常Vma= Xmm，Vmx= Xmxo當vu> V,取標準問(wèn)題名稱(chēng)ACSGAPSAACVu= Vmx;當ou< Vmin,取vu= Vmimo w為遞減的慣Oliver304242120(30城市) (420.371) (NA) (423.74) (NA) (NA)性權值,- -般從0.9遞減到0.4。迭代改數[1470] [3200][40000][24617] [12620]2.3粒子群優(yōu)化EilS0432428426443436粒子群算法可以通過(guò)速度松弛迭代策略增強局部(50城市) (432.172) (N/A) (427.86) (N/A)(NA)搜索能力,加速收斂;用精英集團來(lái)增加多樣性,提高迭代次數[2412] [25000] 00000] [68512] [2111]全局搜索能力。從實(shí)驗結果可以發(fā)現,蟻群算法具有很強的發(fā)現速度松弛迭代策略為:如果當前粒子的適應度好較好解的能力,不容易陷人局部最優(yōu)。這是因為該算于前一代粒子的適應度,那么下一代粒子的速度保持法不僅利用了正反饋原理,在一定程度上可以加快進(jìn)不變,否則就按照速度更新方程(7)對速度更新?；^(guò)程,而且是一-種本質(zhì)并行的算法,個(gè)體間不斷進(jìn)行精英集團選擇:粒子在按(7)式更新速度時(shí),從兩信息交流和傳遞,有利于發(fā)現較好解。個(gè)方面獲得信息,-一個(gè)是粒子本身的信息,本身目前所找到的最優(yōu)解P;另一個(gè)是種群共享信息，整個(gè)種群2粒子群算法目前搜索到的最優(yōu)位置Pg。事實(shí)上,有時(shí)其他一些粒2.1粒子群算法原理子的P;比Pg的解只是稍微差-一點(diǎn),都是較好的解,但粒子群優(yōu)化算法是--種基于種群的迭代搜索算由于(7)式只利用了Pg的信息，沒(méi)有使那些較好P;的法,種群內的個(gè)體(粒子)不斷追隨最優(yōu)個(gè)體進(jìn)行尋優(yōu)信息在種群中共享。精英集團的概念是,在每步迭代搜索。算法首先在搜索空間內隨機初始化一群粒子,中,對P;的適應度從小到大排序取前k(≤m)個(gè)粒子每個(gè)粒子的位置是優(yōu)化問(wèn)題的一個(gè)解,將其帶人目標.作為精英集團0,集團內的個(gè)體都有機會(huì )作為種群的函數計算出適應值,再根據此適應值的大小來(lái)衡量粒最優(yōu)解Pg帶人公式(7)進(jìn)行計算。這樣不但解決了種子的優(yōu)劣。每個(gè)粒子的速度決定了其運動(dòng)的方向和步群的多樣性問(wèn)題，同時(shí)使優(yōu)勢粒子的信息得到了充分長(cháng),粒子根據本身的記憶信息和整個(gè)種群的共享信息，利用。不斷更新自己的速度和位置,去試探搜索空間內的不2.4算法流程同解。在迭代過(guò)程中,每個(gè)粒子更新速度時(shí),總是在原步驟1初始化 m個(gè)粒子的位置和速度;來(lái)速度的基礎上調整以趨向于兩個(gè)位置,一個(gè)是粒子步驟2把每個(gè)粒子的位置 帶入目標函數評價(jià)其本身目前所找到的最優(yōu)解(pBest),另一個(gè)是整個(gè)種群優(yōu)生中國煤化工目前找到的最優(yōu)解(gBest) ,并期望在向兩個(gè)位置移動(dòng)|YHCNMHG值與其本身目前最優(yōu)的過(guò)程中,發(fā)現更好的解,以取代pBest或gBest,通過(guò)位置P;的函數作比較,如果好于P,則將其作為目前種群中粒子的不斷交互。逐漸收斂到最優(yōu)解。最好位置P;第8期王艷玲等:群體智能優(yōu)化算法步驟4對整個(gè)粒子群 目前最優(yōu)位置進(jìn)行P,排求解?？梢圆煌ㄟ^(guò)個(gè)體之間直接通信而是通過(guò)非直接序,前k個(gè)作為精英集團0k;通信進(jìn)行合作,這樣的系統具有更好的可擴充性。由步驟5每個(gè)粒子 從精英集團2中,隨機選取P,于系統中個(gè)體的增加而增加的系統的通信開(kāi)銷(xiāo)在這里作為P十分小。系統中每個(gè)個(gè)體的能力十分簡(jiǎn)單,這樣每個(gè)步驟6如果適應度變壞,P。 代人速度迭代方程，個(gè)體的執行時(shí)間比較短,并且實(shí)現也比較簡(jiǎn)單,具有簡(jiǎn)重新計算速度,否則,速度不變;單性。因為具有這些優(yōu)點(diǎn),雖說(shuō)群體智能的研究還處步驟7檢查速度各個(gè)分量是否在[Vm, Vx]于初級階段,并且存在許多困難,但可預言群體智能的范圍內,如果大于Vax設為V. ;如果小于V.設為研究代表了以后計算機研究發(fā)展的一-個(gè)重要方向。Vm; .步驟8按位置更新方程 ,更新粒子位置;參考文獻:步驟9檢查各個(gè)分量是否在[Xmgn,Xqx] 范圍[1] Dorigo M,Cambrdella L M Ant Colony System:A Coopera-內,如果超出,在[Xmn,Xmx]內隨機取- -個(gè)值, 設為該tive Leaming Approach to the Traveling Sales man Problem分量;[J]. IEEE Transactions on Evolutionary Computations, 1997,1(1):53 - 66.步驟10如果未達到預先設定的最大代數或未[2] Garnberdella L M,Dorigo M Solving Symmeric and Asym-達到足夠好的函數值則返回步驟2。metric TSPs by Colornies[C]//In poeedings of the IEEE In-2.5粒子群算法的應用temational Conference on Evolutionary Computation(ICEC由于粒子群算法出色的性能,目前已廣泛應用于'96).[s.I. ]:IEEE Pres,1996:622 - 627.函數優(yōu)化、神經(jīng)網(wǎng)絡(luò )訓練、模糊系統控制等眾多領(lǐng)域。[3] Kennedy J,Eberhart R C. Paride swarm optinization[C]//下面簡(jiǎn)要介紹粒子群算法在神經(jīng)網(wǎng)絡(luò )中的應用。In: Procedings of IEEE Intemational Conference .on Neural當粒子群算法用于神經(jīng)網(wǎng)絡(luò )訓練網(wǎng)絡(luò )權值時(shí),粒Networks. Piscataway,NJ:[s.n. ],1995:1942 - 1948.子就表示神經(jīng)網(wǎng)絡(luò )的-組權,粒子的緯度就是神經(jīng)網(wǎng)[4] Dorigo M, Maricezo V,Colomi A. The ant systen: opimia-絡(luò )中權值的個(gè)數。一般神經(jīng)網(wǎng)絡(luò )的初治值介工-1和tiom bya olony of c∞operating agents[J]. IEEE Transectionson Systems, Man, and Cybermetics,Part B, 1996,26(1):29-+1之間,訓練結束后的權值也是一1和+1之間,因41此,粒子的范圍可以設定為-1和+1之間。慣性因子[5] Bulnheimer B, Hartl R F, Srauss C. A New Rank - basedw的取值既要考慮到避免陷人局部極小,又要保證收Version of the ant st system:AComputational Study[ R]. Vien-斂性,算法的初期階段讓?xiě)T性因子w取較大的值，有利m: Institute of Management Science, University of Vienna,于跳出局部極小點(diǎn),逐步調整w,使其遞減,以保證算1997.法的收斂性。實(shí)驗結果表明,粒子群優(yōu)化算法訓練的[6] Stuzle T,Hoos H H. MAX - MIN Ant System[J]. Future神經(jīng)網(wǎng)絡(luò )收斂速度明顯加快。Generation Computer Systems,2000, 16(8):889 - 914.[7] Colormi A,Dorigo M,Maniezo V,et al. Ant system for job-3結束語(yǔ)shop scheduling[J]. Belgian Joumal of Operations Resarch,Stistis and Computer Scienoe(JORBEL), 1994, 34:39一群體智能是新興的用于尋找全局最優(yōu)解的算法，s3.已經(jīng)廣泛地應用于許多領(lǐng)域,取得很好的效果。群體8] Costa D,Hertz A. Ants can∞olor graphs[J]. Journal of Operae-智能的特點(diǎn)和優(yōu)點(diǎn)是:群體中相互合作的個(gè)體是分布tional Research Society,1997 ,48:295 - 305.式的,這樣更能夠適應當前網(wǎng)絡(luò )環(huán)境下的工作狀態(tài);沒(méi)9] Durbin R,illshaw D. An Analogue Approach to the Travel.有中心的控制與數據,這樣的系統更具有魯棒性,不會(huì )ling Salesman Problem Using an Elastic Net Method[J]. Na-由于某一個(gè)或者某幾個(gè)個(gè)體的故障而影響整個(gè)問(wèn)題的ture, 1987(326):689 - 691.(上接第113頁(yè))[7] 金玉堅,劉 焱.新型網(wǎng)絡(luò )信息檢索效果評價(jià)指標體系設技術(shù)與發(fā)展,2007,17(9):66 - 70.計[J].現代情報,2005(4);185 - 188.[10] Zamir 0O,Erzioni 0. Web Daument Cusering:A Feasblity[8]李振龍.web信息檢索的技術(shù)分析與發(fā)展策略研究[J].計中國煤化工R'98. New York:ACM箅機科學(xué),2006,33(4):181 - 184.[9] 衛琳.基于搜索結果的個(gè)性化推薦系統研究[J].計算機YHCNMHG