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