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

ISSN 1009 3044E-mail: eduf@cce.nel.cnComputer Knowleoge and Technology電脯知識與技術(shù)htp:/://ww dnzs.net.cnVol6,No.21, July 2010, pp.5845-5846Tel:+86- -51- -5690963 5690964群智能優(yōu)化算法研究王大將,蔡瑞英",徐新偉|(1.南京陸軍指揮學(xué)院作戰實(shí)驗中心,江蘇南京210045 ;2.南京T業(yè)大學(xué)信息科學(xué)與工程學(xué)院,江蘇南京2100090)摘要:群智能優(yōu)化算法是一種新型的優(yōu)化算法。該文介紹了幾種常見(jiàn)的群智能優(yōu)化算法,包括粒子群優(yōu)化算法、蟻群優(yōu)化算法、人工免疫算法、人工魚(yú)群算法,分析了它們的優(yōu)缺點(diǎn)及使用情況,提出了群智能優(yōu)化算法的發(fā)展方向。關(guān)鍵詞:智能優(yōu)化算法;粒子群優(yōu)化算法;蟻群優(yōu)化算法;人工免疫算法;人工魚(yú)群算法中圈分類(lèi)號:TP18文獻標識碼:A文章編號:1009 3044(2010)21- -5845- 02Research on Swarm Intelligence Optimization AlgorithmWANG Da-jiang', CAI Rui- ying, XU Xin-weil(1.Army Command College, Experimental Operations Center, Nanjing 210045,China; 2.Nanjing Univenity of Technology, InformationScience and Engineering. Najing 210009, China)Abstract: Intelligence optimization algorithm is a new type optimization algorithm. This paper presents several common Swarm optimiza-tion algorithms, such as particle swarn optimization algorithm, ant colony optimization algorithm, artificial immune algorithm and artificialfish swarmn algorithm, suggests evolutional trend of itelligegnce optimization algorithm based on analyzing charcterstis.Key words: itelligence optimizarion algoithm; particle swarm opinization algorithm; ant colony optimization algorithm; arifcial im-mune algorithm; artifcial fish swarm algorithm優(yōu)化算法的研究是優(yōu)化技術(shù)研兗的關(guān)鍵內容,它基于某種思想和機制,通過(guò)一定的途徑或規則來(lái)得到滿(mǎn)足用戶(hù)要求的問(wèn)題的解。傳統的優(yōu)化算法有線(xiàn)性規劃和非線(xiàn)性規劃法動(dòng)態(tài)規劃法、網(wǎng)絡(luò )流優(yōu)化算法等,其算法復雜度一般很大,只適于求解小規模向題,在實(shí)際工程中往往不適用。20世紀80年代以來(lái),一種新穎的優(yōu)化算法.如遺傳算法、模擬退火算法、蟻群算法、粒子群算法.人工免疫算法及其混合優(yōu)化策略等,通過(guò)模擬或揭示某些自然現象或過(guò)程面得到發(fā)展,為那些傳統優(yōu)化技術(shù)難以處理的組合優(yōu)化問(wèn)題提供了切實(shí)可行的解決方法。在優(yōu)化領(lǐng)城,由于這些算法構造的直觀(guān)性與自然機理.因此通常稱(chēng)作智能優(yōu)化算法。1群智能優(yōu)化算法智能優(yōu)化算法是模擬自然界生物系統,各個(gè)生物體依賴(lài)自身的本能.通過(guò)無(wú)意識的進(jìn)化、尋優(yōu)行為來(lái)優(yōu)化生存狀態(tài),以適應環(huán)境的依賴(lài)優(yōu)化方法,具有許多與傳統優(yōu)化算法不同的特點(diǎn)。智能優(yōu)化算法根據其中個(gè)體的數量.可分為基于個(gè)體的和基于群的兩種,如,模擬退火算法是基于個(gè)體的,而蟻群優(yōu)化算法粒子群優(yōu)化算法、人工免疫算法和人工魚(yú)群算法是基于種群的。以下對幾種常用的群智能優(yōu)化算法作簡(jiǎn)要研究。1.1粒子群優(yōu)化算法粒子群優(yōu)化(Particle Swarm Opimization,PSO)算法是J.Kennedy和R.C.Eberhart 于1995年提出的- -種高效的群集智能協(xié)同優(yōu)化算法,其基本思想來(lái)源于對鳥(niǎo)群社會(huì )模型的研究及行為模擬,以個(gè)體的協(xié)作與競爭來(lái)完成對復雜搜索空閫內優(yōu)解的搜索.即所有粒子根據個(gè)體經(jīng)驗和群體經(jīng)驗不斷調整自已的速度和位置,朗著(zhù)個(gè)體最優(yōu)和群體最優(yōu)的目標飛行來(lái)完成更新優(yōu)化,具有概念簡(jiǎn)單，收斂速度快,可調參數少等優(yōu)點(diǎn),非常適用于復雜環(huán)境中的優(yōu)化問(wèn)題求解。但粒子群算法在后期難以維持種群的多樣性,而且易陷人局部極值。自提出以來(lái),很多研究者從參數設置收斂性、拓撲結構、與其它算法融合等角度對傳統PS0進(jìn)行研究,并針對其不足提出了各種改進(jìn).以提高算法性能。如文獻[1]提出的動(dòng)態(tài)離散粒子群優(yōu)化算法較好地解決了動(dòng)態(tài)環(huán)境下離散優(yōu)化問(wèn)題。文獻[2]提出的并行粒子群優(yōu)化算法,較好地解決了網(wǎng)絡(luò )系統中具有異構性和動(dòng)態(tài)性的資源分配優(yōu)化問(wèn)題。文獻[3]基于混沌思想模糊自適應參數策略的粒子群優(yōu)化算法,有效提高了算法的收斂速度.改善了多維空間的全局搜索能力。目前,PSO已經(jīng)廣泛的應用于函數優(yōu)化,人工神經(jīng)網(wǎng)絡(luò )訓練,模式識別,模糊控制、車(chē)輛調度等領(lǐng)城。1.2蚊群優(yōu)化算法蟻群優(yōu)化(Ant Colony Opimization, ACO)算法是根據自然界中螞蟻群體尋優(yōu)的行為提出來(lái)的一種全局啟發(fā)式優(yōu)化算法,它是對中國煤化工收稿日期:2010-05-12基金項目;江蘇省高校自然科學(xué)基金(05K]JB520048)MHCNMHG作者簡(jiǎn)介:王大將(1983-),女,南京陸軍指揮學(xué)院作戰實(shí)驗中心講師,研究方向為數據挖掘,智能決策;蔡瑞英(1950-),女,南京工業(yè)大學(xué)信息科學(xué)與工程學(xué)院教授,研究方向為計算智能,虛擬制造;徐新偉(1984-),男,南京陸軍指揮學(xué)院圍書(shū)館助理館員,研究方向為計算機網(wǎng)絡(luò )。.....人工俐及識別技術(shù)..5845萬(wàn)芳數據Computer Knowledge and Technology電腦知設與技術(shù)第6卷第21期(2010年7月)真實(shí)蟻群協(xié)作過(guò)程的模擬.每只螞蟻在候選的空間中獨立搜索解,并在所尋得的解上留下一定的信息量。解的性能越好螞蟻留在其上的信息量越大,而信息量越大的解被再次選擇的可能性也越大。所有解上的初始信息量相同,隨若算法的推進(jìn),較優(yōu)解上的信息量逐漸增加,最終收斂到最優(yōu)解或近似最優(yōu)解。該算法具有很強的發(fā)現較優(yōu)解的能力、魯棒性強易于計算機實(shí)現等優(yōu)點(diǎn),在動(dòng)態(tài)環(huán)境下表現出高度的靈活性和健壯性,但也存在著(zhù)一些問(wèn)題,如需要較長(cháng)的搜索時(shí)間,搜索速度慢，且容易出現停滯現象,不能對解空間進(jìn)行全面搜索。人們針對其不足提出了多種改進(jìn),如文獻[4]提出的基于混合行為的自適應蟻群算法,通過(guò)引人具有多行為的混合螞蟻來(lái)擴大搜索空間,避免早熟和停滯現象。目前,蚊群優(yōu)化算法在求解TSP問(wèn)題、分配問(wèn)題job- shop 調度問(wèn)題等方面取得了大量較好的實(shí)驗結果。13人工免疫算法人工免疫(Arificial Immune)算法是基于生物免疫系統提出的一種新型智能算法,它將要分析的數據看作抗原,將算法產(chǎn)生反映抗原特征的數據看作抗體,模擬免疫網(wǎng)絡(luò )抗體抗原之間的相互刺激和作用,按照一定 的算法實(shí)現數據處理,該算法能夠有效提取目標函數的絕大部分局部峰值,并具備群體數量自動(dòng)調節和實(shí)數編碼等優(yōu)良特性,具有搜索效率高.維持多樣性好和學(xué)習記憶力強等優(yōu)點(diǎn),為優(yōu)化問(wèn)題提供了新穎的解決方法和途徑。但該算法頻繁地抽取疫苗和接種疫苗花費了大量時(shí)間,使效率低下;求觶全局.最優(yōu)解需要的群體規模相對較大,從而增加了計算量。針對其不足,人們提出了多種改進(jìn).如文獻[5]提出的協(xié)作型人工免疫網(wǎng)絡(luò )模型,新增記憶細胞間的協(xié)作算子,實(shí)現記憶細胞之間既競爭又協(xié)作的新型關(guān)系,提高了收斂速度,縮短了執行時(shí)間,保證了全局尋優(yōu)能力。目前,人工免疫算法已應用于控制.數據處理、優(yōu)化學(xué)習和故障診斷等領(lǐng)域。1.4人工魚(yú)群算法人工魚(yú)群(ArtificialFishSwarm)算法是基于動(dòng)物行為的自治體尋優(yōu)模式,通過(guò)模擬魚(yú)群的覓食和生存活動(dòng)來(lái)實(shí)現在空間中尋求全局最優(yōu)的一種新思路。該算法采用自下而上的設計方法,即首先構造人工魚(yú)的個(gè)體模型;用公告板記錄最優(yōu)人工魚(yú)個(gè)體的狀態(tài),確定行為評價(jià)方法和終止條件;個(gè)體在尋優(yōu)的過(guò)程中自適應地選擇合適的行為;最后全局最優(yōu)結果通過(guò)群體或某個(gè)個(gè)體表現出來(lái)。該算法具有良好的全局搜索力,并具有對初值.參數選擇不敏感魯棒性強簡(jiǎn)單易實(shí)現等優(yōu)點(diǎn)。但也存在-些缺陷,如搜索精度不高,后期收斂慢等。針對不足,近年來(lái)人們提出了多種改進(jìn)方法,如文獻[6]提出的簡(jiǎn)化人工魚(yú)群算法,在- -次迭代進(jìn)化中同時(shí)根據人工魚(yú)覓食結果、種群中心位置和種群最優(yōu)位置.調螫下一步位置,從而增強了該算法的全局搜索能力,提高了運行速度。文獻[7]提出的基于變異算子的人工魚(yú)群算法,引入變異算子增加了群體的多樣性,避免了人工魚(yú)群算法陷入局部最優(yōu),并提高了收斂速度。目前,人工魚(yú)群算法在機器人路徑規劃、電力系統優(yōu)化等方面得到了應用,取得了較好的使用效果。2總結與展望各種群智能優(yōu)化算法都有其應用的優(yōu)勢與不足,從解央實(shí)際優(yōu)化向題角度出發(fā),融合不同類(lèi)型機制的優(yōu)化算法,充分發(fā)揮它們各自?xún)?yōu)勢,是解決問(wèn)題的必然發(fā)展趨勢。近年來(lái),國內外學(xué)者正是采用智能優(yōu)化算法和傳統優(yōu)化算法相結合、智能優(yōu)化算法與智能優(yōu)化算法相結合等各種混合算法.成功解決了大量實(shí)際工程問(wèn)題。但從現有的成果來(lái)看,這些智能融合算法很多都是針對具體問(wèn)題來(lái)進(jìn)行的.所解決的問(wèn)題不同,其融合策略也就存在著(zhù)很多差異,不具備系統性和一般性。因此,在現有成果的基礎上繼續進(jìn)行深入研究,努力探索智能優(yōu)化算法之間或與其他優(yōu)化算法相融合的統-機制將是一個(gè)非常具有理論意義和應用價(jià)值的課題。參考文獻:[1]羅桂蘭.動(dòng)態(tài)離散粒子群優(yōu)化算法J計算機工程與設計2009.3024):5708- 5711.[2]李志潔改進(jìn)粒子群算法在網(wǎng)格資源分配中的優(yōu)化[J].計算機集成制造系統2009,15(12).2375.-2382.[3]孫勇.基于混沌思想模糊自適應參數策略的粒子群優(yōu)化算法[J].計算機應用研究2010,27():39--41..[4]王運濤.基于混合行為的自適應蟻群算法[],計算機仿真2002612);151-153.[5]劉麗.基于全局粒子群的協(xié)作型人工免疫網(wǎng)絡(luò )優(yōu)化算法[].模式識別與人工智能00924):653- -658.[6]王聯(lián)國.一種簡(jiǎn)化的人工魚(yú)群算卻[]小型微型計算機系統,2009,30(8);1663- 1667.[7]黃華娟.基于變異算子的人工魚(yú)群混合算法[J]計算機工程與應209,4533):28 -30.[8]李福東.聯(lián)合循環(huán)發(fā)電系統燃料熱值智能優(yōu)化控制[J}清華大學(xué)學(xué)報2008.48(2):1737-1741.[9]劉波.融合粒子群與蟻群算法優(yōu)化XML群體智能搜索[].計算機研究與發(fā)展2008.4518):1371-1378.{10]黃平.改進(jìn)的粒子群優(yōu)化算法求解電力經(jīng)濟調度[].華中科技大學(xué)學(xué)報2010,38(1);121-124.中國煤化工MYHCNMHG5846人工警 能及識別技術(shù).....本欄目責任編輯:唐一東.