共享歷史最優(yōu)信息搜索的粒子群算法

連志剛， 曹 宇， 林蔚天， 計(jì)春雷

（上海電機(jī)學(xué)院 電子信息工程學(xué)院，上海 201306）

粒子群算法思想來自鳥群或者魚群的覓食行為，通過個(gè)體間特殊的信息傳遞方式，使整個(gè)團(tuán)體朝同一個(gè)方向逼近，從而搜索到最終目標(biāo).粒子群算法的思想就是源自此類群體行為理論.該算法由心理學(xué)博士Kennedy和電氣工程師Eberhart提出，通過群體中個(gè)體之間的協(xié)作和信息共享來尋找最優(yōu)解［1－2］.

粒子群算法是一種群優(yōu)化技術(shù)和群搜索算法，它通過群體的合作，進(jìn)行高效搜索.正如文獻(xiàn)［3］所說，社會(huì)行為有兩個(gè)主要目的：一是每個(gè)個(gè)體能夠在搜索食物的過程中協(xié)助其它群內(nèi)的成員；二是群體合作能夠提高搜索效率.粒子群可以認(rèn)為是粒子在搜索空間里，按一定傳遞規(guī)律傳遞信息，并根據(jù)信息變化改變自己的搜索方向.傳統(tǒng)粒子群算法搜索信息主要來自于兩方面：一是群體最優(yōu)位置；二是粒子自身經(jīng)驗(yàn)最優(yōu)位置.群體最優(yōu)位置使得粒子能夠快速收斂，并對全局極值的鄰域進(jìn)行搜索；個(gè)體自身經(jīng)驗(yàn)最優(yōu)位置保證粒子不至于過快收斂到群體最優(yōu)而陷入局部最優(yōu)，使得粒子能夠在一次迭代中對個(gè)體極值和全局極值之間的區(qū)域進(jìn)行搜索［4］.不同的優(yōu)化問題需要很好的平衡局部和全局的比例關(guān)系.文獻(xiàn)［5］提出Iemetic粒子群優(yōu)化算法，利用一種新的specie構(gòu)造方法來保證其能夠發(fā)現(xiàn)不同最優(yōu)解所在的搜索區(qū)域，通過一種適應(yīng)性的局域搜索算子增強(qiáng)specie追蹤到最優(yōu)解的能力，重新初始化策略來進(jìn)一步改善算法在動(dòng)態(tài)多峰環(huán)境中的性能.文獻(xiàn)［6－7］對PSO（particle swarm optimization）在全局優(yōu)化、裝載平衡等方面進(jìn)行了研究.關(guān)于PSO 的應(yīng)用研究報(bào)道較為豐富，如文獻(xiàn)［8］提出一種粒子群與人工免疫學(xué)習(xí)結(jié)合的混合算法解決固定收費(fèi)運(yùn)輸問題.Hamta等在文獻(xiàn)［9］中提出了一種混合PSO 算法優(yōu)化裝配線平衡的多目標(biāo)問題.文獻(xiàn)［10］提出一種有效的二進(jìn)制PSO 算法優(yōu)化多目標(biāo)資源分配問題.文獻(xiàn)［11］應(yīng)用粒子群算法解決工程項(xiàng)目多目標(biāo)執(zhí)行模式優(yōu)化問題.作者［12－13］研究了共享每代種群中粒子最好位置信息，以及結(jié)合局部與全局最優(yōu)的改進(jìn)型粒子群算法，文獻(xiàn)［14］仿真證明其效率較高.

本文提出一種共享歷史最優(yōu)信息搜索的粒子群算法，它除了共享個(gè)體和全局粒子良好信息外，還共享了前次運(yùn)行時(shí)的種群中個(gè)體粒子歷史最優(yōu)信息，并將該算法應(yīng)用于一些典型非線性測試函數(shù)的優(yōu)化，實(shí)驗(yàn)結(jié)果表明了它的有效性.

1 基本粒子群算法

粒子群算法中的每個(gè)粒子都是D 維解空間的一點(diǎn)，具有速度和位置，但沒有質(zhì)量和體積.空間中的某個(gè)粒子的位置表示為xi＝（xi1，xi2，…，xiD），i＝1，2，…，m，速度為vi＝（vi1，vi2，…，viD）.它所經(jīng)歷過的最好歷史位置為pi＝（pi1，pi2，…，piD）；它能共享的群體的最好位置以索引g表示，記為pg.每個(gè)粒子將根據(jù)自身飛行經(jīng)驗(yàn)和群體飛行經(jīng)驗(yàn)來調(diào)整自己的飛行軌跡，根據(jù)以下公式更新自己的速度和位置.

式中，w 為慣性權(quán)重；學(xué)習(xí)因子c1和c2為正常數(shù)；k為迭代次數(shù)；R1，R2為分布在［0，1］上的隨機(jī)數(shù)；vid（k）為每一個(gè)粒子在第d 維的速度；xid（k）是粒子當(dāng)前位置；pid（k）是每個(gè)粒子到目前為止所出現(xiàn)的最優(yōu)位置；pgd（k）為所有粒子到目前為止所出現(xiàn)的最優(yōu)位置.

式（1）中，第一部分稱為慣性部分，由粒子先前的速度引起；第二部分為自我認(rèn)知部分，代表粒子本身的思考；第三部分為社會(huì)認(rèn)知部分，表達(dá)粒子之間的協(xié)作以及粒子對群體共有信息的認(rèn)可程度.以上3部分共同影響粒子速度和位置的更新.粒子的自我認(rèn)知部分體現(xiàn)了粒子對自身經(jīng)驗(yàn)的積累，粒子的社會(huì)認(rèn)知部分體現(xiàn)了粒子之間的信息傳遞.

基本PSO 算法在進(jìn)化過程中除跟蹤自身最優(yōu)外，只與種群最優(yōu)粒子發(fā)生信息交流.在進(jìn)化過程中，種群最優(yōu)對其影響很大，一旦粒子趕上種群最優(yōu)，粒子會(huì)聚集到相同位置并停止，從而導(dǎo)致算法過早收斂而出現(xiàn)早熟［15］.因而，本文提出一種結(jié)合前次運(yùn)行時(shí)的歷史最優(yōu)信息的改進(jìn)型粒子群算法.該算法的粒子在位置更新時(shí)除共享自身最優(yōu)和種群最優(yōu)外，還將參考算法前次運(yùn)行搜索到的粒子歷史最優(yōu)信息，從而克服算法過早收斂而出現(xiàn)的早熟問題.

2 共享歷史最優(yōu)信息的粒子群算法

基于PSO 算法的特性，本文提出共享歷史最優(yōu)信息搜索的粒子群算法SHOIPSO（share historical optimal information particle swarm optimization algorithm），將其多次運(yùn)行搜索到的歷史最優(yōu)點(diǎn)信息共享于下一次算法的搜索.這種算法模型在一定程度上充分共享、繼承了PSO 算法前次運(yùn)行的歷史最優(yōu)點(diǎn)信息、本次運(yùn)行的歷史最優(yōu)點(diǎn)信息、本次運(yùn)行獲得的全局最優(yōu)信息，其共享的信息具有多樣性，搜索能力及效率將會(huì)更好.算法假設(shè)如下.

假設(shè)在一個(gè)D 維的目標(biāo)搜索空間中，有m個(gè)粒子組成一個(gè)種群，其中第i個(gè)粒子表示為一個(gè)D 維的向量xi＝（xi1，xi2，…，xiD），i＝1，2，…，m，即第i個(gè)粒子在D 維的搜索空間中的位置是xi.vi＝（vi1，vi2，…，viD）是第i個(gè)粒子的飛行速度；pi＝（pi1，pi2，…，piD）是第i個(gè)粒子迄今為止搜索到的最優(yōu)位置pbest；pg＝（pg1，pg2，…，pgD）是整個(gè)粒子群迄今為止搜索到的最 優(yōu) 位 置gbest；PH（t）＝（pt1，pt2，…，ptD）是該算法運(yùn)行第t次種群搜索到的個(gè)體歷史最優(yōu)位置hbest.SHOIPSO 算法的迭代公式為

式中，k，w，R1，R2，c1，c2，vid（k），xid（k），pid（k），pgd（k）與SPSO 表示的意義相同.t表示該算法的運(yùn)行次數(shù)，一般運(yùn)行10 次.λ 為在［0，1］之間的一個(gè)常數(shù)，表示共享繼承歷史最優(yōu)信息的程度.λ越大說明共享繼承的力度越大，但容易陷入歷史最優(yōu)，具體取多大算法的效率最好，有待數(shù)據(jù)模擬實(shí)驗(yàn)驗(yàn)證.當(dāng)SHOIPSO 算法運(yùn)行第1 次的時(shí)候，因?yàn)榍按螞]有歷史 最 優(yōu) 信 息 可 供 繼 承，故λ 取0.pHd（t）是SHOIPSO 算法運(yùn)行第t次時(shí)，種群中個(gè)體粒子搜索到的歷史最優(yōu)點(diǎn)的第d 維分量.迭代終止條件根據(jù)具體問題一般選為最大迭代次數(shù)或（和）粒子群迄今為止搜索到的最優(yōu)位置滿足預(yù)定最小適應(yīng)閾值.

SHOIPSO 算法可以擴(kuò)展為隨機(jī)共享歷史最優(yōu)信息搜索的粒子群算法RSHOIPSO（random share historical optimal information particle swarm optimization algorithm），兩者的區(qū)別為，式（5）變?yōu)?/p>

PH由RSHOIPSO 算法運(yùn)行第1次時(shí)到第t－1次時(shí)的種群個(gè)體歷史最優(yōu)信息按比例構(gòu)成，其相互間比例為多大時(shí)算法效率最高，還有待模擬實(shí)驗(yàn)分析.

SHOIPSO 算法和RSHOIPSO 算法迭代公式主要通過4部分來更新粒子i的新速度：粒子i前一次迭代時(shí)刻的速度；粒子i當(dāng)前位置與自己最好位置之間的距離；第t次運(yùn)行搜索到的歷史最優(yōu)位置與自己位置之間的距離；同時(shí)再結(jié)合粒子i當(dāng)前位置與群體最好位置之間的距離.該算法的特點(diǎn)是將歷史最優(yōu)粒子和種群最優(yōu)粒子進(jìn)行結(jié)合，最大限度地共享繼承了歷史最優(yōu)信息.

3 SHOIPSO 算法的函數(shù)優(yōu)化仿真實(shí)驗(yàn)

為了驗(yàn)證SHOIPSO 算法的優(yōu)化效果，下面給出5個(gè)經(jīng)典的測試函數(shù)，并和基本PSO 算法測試比較，分析其優(yōu)化性能.

在測試比較過程中，兩種算法在每一輪比賽中取完全相同的參數(shù)，這樣才能體現(xiàn)出不同算法所產(chǎn)生的效果.分別對每個(gè)目標(biāo)函數(shù)運(yùn)行10次，再從這10次結(jié)果中求出最小值（min）、最大值（max）和平均值（average）.本文將優(yōu)化結(jié)果的主要數(shù)據(jù)抽取出來，列在表1 中.另外，為了作圖方便，每運(yùn)行一次SHOIPSO 和RSHOIPSO 算 法，基 本PSO 也 運(yùn) 行一次進(jìn)行對照（雖然其參數(shù)沒有改變）.SHOIPSO，RSHOIPSO，OPSO 算法搜索最優(yōu)解過程中最優(yōu)收斂性能曲線如圖1所示。

表1中，f 指經(jīng)典的測試函數(shù)；D 為該函數(shù)的維數(shù)；Ps和G 分別為算法的種群規(guī)模和停止迭代的代數(shù)；Best 表示該函數(shù)的理論最優(yōu)值.對于RSHOIPSO 算法，本文模擬實(shí)驗(yàn)采用將第t－1 次運(yùn)行的歷史最優(yōu)按照比例p 插入前面的PH（t－2），為了避免論文數(shù)據(jù)過多、篇幅過大，本文的比例參數(shù)取p＝Ps／10和p＝Ps／5進(jìn)行實(shí)驗(yàn)分析.

將3種算法的仿真結(jié)果進(jìn)行比較，最優(yōu)的那個(gè)值標(biāo)記為黑體.它對應(yīng)的算法代表意義是：在優(yōu)化某個(gè)函數(shù)時(shí)，這種算法效果在3種算法中是最好的.它對應(yīng)參數(shù)的意義是：在優(yōu)化此函數(shù)時(shí)，在這種算法各種參數(shù)組合中，這組參數(shù)的組合效率是最好的.這組參數(shù)將為此算法將來的應(yīng)用提供指導(dǎo)意義.

表1 OPSO，SHOIPSO，RSHOIPSO 算法優(yōu)化函數(shù)的比較Tab.1 Comparisons between optimization functions of OPSO，SHOIPSO and RSHOIPSO algorithms

圖1 SHOIPSO，RSHOIPSO 與OPSO 算法優(yōu)化函數(shù)的收斂比較Fig.1 Comparisons between convergence figures of SHOIPSO，RSHOIPSO and OPSO algorithms

從仿真數(shù)據(jù)可以看出，SHOIPSO 和RSHOIPSO算法在收斂精度上取得了明顯的效果，它們的優(yōu)化精度要比OPSO算法高出至少幾個(gè)數(shù)量級.從表1可以看到，λ分布在（0.5，0.9）之間時(shí)，5個(gè)函數(shù)全部取得最優(yōu)值.因此，作者建議以后進(jìn)行函數(shù)優(yōu)化時(shí)，可以將λ值只設(shè)置在（0.5，0.9）范圍內(nèi)，這樣可以大大提高優(yōu)化效率.特別是權(quán)重系數(shù)w 在取0.3和0.4時(shí)搜索性能相對較強(qiáng).因此，算法參數(shù)設(shè)置時(shí)，w 一般取0.3和0.4.對于優(yōu)化函數(shù)f1和f4，RSHOIPSO的效果都優(yōu)于其它兩種算法，其p 值都為Ps／5，即第t次的種群個(gè)體歷史最優(yōu)按Ps／5插入第t－1次的種群個(gè)體歷史最優(yōu).

從仿真圖來看，SHOIPSO，RSHOIPSO 收斂性能較OPSO 算法明顯好，且收斂精度高.特別從優(yōu)化函數(shù)f2和f4的仿真圖可以看出，該文提出的算法很快跳出了局部最優(yōu)且收斂速度快.從仿真數(shù)據(jù)和收斂圖可驗(yàn)證，本文提出的共享歷史搜索最優(yōu)信息策略是有效的，提高了算法搜索解的多樣性，跳出了局部最優(yōu).故本文提出的新型PSO 算法搜索性能較強(qiáng)，可以作為一種解決高維非線性復(fù)雜問題的優(yōu)化工具.

4 結(jié) 論

本文提出了一種共享歷史最優(yōu)信息搜索的粒子群算法.仿真結(jié)果表明該改進(jìn)型算法在優(yōu)化函數(shù)時(shí)，其收斂效果與收斂速度都有較大提高.本文的意義在于指出了粒子在搜索過程中不僅共享個(gè)體和全局粒子良好信息外，還共享了算法前次運(yùn)行獲得的歷史最優(yōu)信息的思路，為粒子群的搜索擴(kuò)大了范圍，減小了粒子群搜索陷入局部最優(yōu)解的欠缺.所以，可以作為一種改進(jìn)粒子群算法的新思路.另外，本文還通過實(shí)驗(yàn)仿真，給出了對于一般函數(shù)優(yōu)化時(shí)參考的λ和w 的取值范圍，為改進(jìn)算法SHOIPSO 的應(yīng)用提供了參考信息.

本文給出了粒子搜索過程中共享歷史最優(yōu)粒子的兩種不同方式.然而在函數(shù)f4優(yōu)化過程中，雖然新算法收斂效果比傳統(tǒng)PSO 算法好，但是最終仍然陷入局部最優(yōu).所以，可以對共享歷史最優(yōu)信息的方式以及參數(shù)設(shè)置作進(jìn)一步研究和討論.

［1］Kennedy J，Eberhart R.Particle swarm optimization［C］∥Proceedings of IEEE International Conference on Neural Networks.Portland：IEEE，2003.

［2］Eberhart R，Kennedy J.A new optimizer using particle swarm theory［C］∥Proceedings of the Sixth International Symposium on Micro Machine and Human Science.Nagoya：IEEE，1995.

［3］Beekman M，Ratnieks F L W.Long－rang foraging by the honey－bee［J］.Functional Ecology，2000，14（4）：490－496.

［4］王存睿，段曉東，劉向東，等.改進(jìn)的基本粒子群優(yōu)化算法［J］.計(jì)算機(jī)工程，2004，30（21）：35－37.

［5］王洪峰，王娜，汪定偉.一種求解動(dòng)態(tài)多峰優(yōu)化問題的Memetic粒子群算法［J］.系統(tǒng)工程理論與實(shí)踐，2013，33（6）：1577－1586.

［6］Ghodrati A，Lotfi S.A hybrid CS／PSO algorithm for global optimization［J］.Intelligent Information and Database Systems，2012，7198（2）：89－98.

［7］Liu Z H，Wang X L.A PSO－based algorithm for load balancing in virtual machines of cloud computing environment［J］.Advances in Swarm Intelligence，2012，7331（4）：142－147.

［8］El－Sherbiny M M，Alhamali R M.A hybrid particle swarm algorithm with artificial immune learning for solving the fixed charge transportation problem［J］.Computers ＆Industrial Engineering，2013，64（2）：610－620.

［9］Hamta N，F(xiàn)atemiGhomi S M T，Jolai F，et al.A hybrid PSO algorithm for a multi－objective assembly line balancing problem with flexible operation times，sequence－dependent setup times and learning effect［J］.International Journal of Production Economics，2013，141（1）：99－111.

［10］Fan K，You W J，Li Y Y.An effective modified binary particle swarm optimization algorithm for multiobjective resource allocation problem［J］.Applied Mathematics and Computation，2013，221（3）：257－267.

［11］周蓉，葉春明.基于粒子群的多目標(biāo)多執(zhí)行模式項(xiàng)目調(diào)度［J］.上海理工大學(xué)學(xué)報(bào)，2013，35（1）：27－32.

［12］Lian Z G.A local and global search combine particle swarm optimization algorithm for job－shop scheduling to minimize makespan［J］.Discrete Dynamics in Nature and Society，2010，2010：1－12.

［13］閆雪麗，王學(xué)武，連志剛.結(jié)合歷史全局最優(yōu)與局部最優(yōu)的粒子群算法［J］.華東理工大學(xué)學(xué)報(bào)，2011，37（4）：515－520.

［14］胡乃平，宋世芳.一種局部與全局相結(jié)合的微粒群優(yōu)化算法［J］.計(jì)算機(jī)工程，2008，34（17）：20－27.

［15］蔡昌新，張頂學(xué).帶鄰近粒子信息的粒子群算法［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45（18）：40－42.

［16］唐柱，丁學(xué)明，劉燦.基于引力搜索和粒子群混合優(yōu)化算法的T－S模型辨識(shí)［J］.上海理工大學(xué)學(xué)報(bào)，2013，35（4）：351－354.

［17］柳寅，馬良，黃鈺.基于模糊粒子群算法的非線性函數(shù)優(yōu)化［J］.上海理工大學(xué)學(xué)報(bào)，2012，34（4）：314－317.