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