連志剛， 曹 宇， 林蔚天， 計春雷

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

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

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

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

1 基本粒子群算法

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

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

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

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

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

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

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

式中，k，w，R1，R2，c1，c2，vid（k），xid（k），pid（k），pgd（k）與SPSO 表示的意義相同.t表示該算法的運行次數(shù)，一般運行10 次.λ 為在［0，1］之間的一個常數(shù)，表示共享繼承歷史最優(yōu)信息的程度.λ越大說明共享繼承的力度越大，但容易陷入歷史最優(yōu)，具體取多大算法的效率最好，有待數(shù)據(jù)模擬實驗驗證.當(dāng)SHOIPSO 算法運行第1 次的時候，因為前次沒有歷史 最 優(yōu) 信 息 可 供 繼 承，故λ 取0.pHd（t）是SHOIPSO 算法運行第t次時，種群中個體粒子搜索到的歷史最優(yōu)點的第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 算法運行第1次時到第t－1次時的種群個體歷史最優(yōu)信息按比例構(gòu)成，其相互間比例為多大時算法效率最高，還有待模擬實驗分析.

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

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

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

在測試比較過程中，兩種算法在每一輪比賽中取完全相同的參數(shù)，這樣才能體現(xiàn)出不同算法所產(chǎn)生的效果.分別對每個目標(biāo)函數(shù)運行10次，再從這10次結(jié)果中求出最小值（min）、最大值（max）和平均值（average）.本文將優(yōu)化結(jié)果的主要數(shù)據(jù)抽取出來，列在表1 中.另外，為了作圖方便，每運行一次SHOIPSO 和RSHOIPSO 算 法，基 本PSO 也 運 行一次進(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 算法，本文模擬實驗采用將第t－1 次運行的歷史最優(yōu)按照比例p 插入前面的PH（t－2），為了避免論文數(shù)據(jù)過多、篇幅過大，本文的比例參數(shù)取p＝Ps／10和p＝Ps／5進(jìn)行實驗分析.

將3種算法的仿真結(jié)果進(jìn)行比較，最優(yōu)的那個值標(biāo)記為黑體.它對應(yīng)的算法代表意義是：在優(yōu)化某個函數(shù)時，這種算法效果在3種算法中是最好的.它對應(yīng)參數(shù)的意義是：在優(yōu)化此函數(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算法高出至少幾個數(shù)量級.從表1可以看到，λ分布在（0.5，0.9）之間時，5個函數(shù)全部取得最優(yōu)值.因此，作者建議以后進(jìn)行函數(shù)優(yōu)化時，可以將λ值只設(shè)置在（0.5，0.9）范圍內(nèi)，這樣可以大大提高優(yōu)化效率.特別是權(quán)重系數(shù)w 在取0.3和0.4時搜索性能相對較強(qiáng).因此，算法參數(shù)設(shè)置時，w 一般取0.3和0.4.對于優(yōu)化函數(shù)f1和f4，RSHOIPSO的效果都優(yōu)于其它兩種算法，其p 值都為Ps／5，即第t次的種群個體歷史最優(yōu)按Ps／5插入第t－1次的種群個體歷史最優(yōu).

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

4 結(jié) 論

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

［5］王洪峰，王娜，汪定偉.一種求解動態(tài)多峰優(yōu)化問題的Memetic粒子群算法［J］.系統(tǒng)工程理論與實踐，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í)行模式項目調(diào)度［J］.上海理工大學(xué)學(xué)報，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é)報，2011，37（4）：515－520.

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

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

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

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