檀蕊蓮，柏 鵬，李 哲，盧 虎，王 澈

(1.西安武警工程大學(xué)，陜西西安710086;2.空軍工程大學(xué)，陜西 西安710051)

粒子群優(yōu)化算法(PSO)是由美國(guó)電氣工程師Eberhart和社會(huì)心理學(xué)家Kennedy基于群鳥(niǎo)覓食提出來(lái)的一種智能算法［1-2］。由于該算法算法簡(jiǎn)單、所需參數(shù)少、易于實(shí)現(xiàn)等優(yōu)點(diǎn)從而廣泛應(yīng)用于科學(xué)和工程領(lǐng)域［3-4］。由于算法參數(shù)較少，也使得其容易陷入局部最優(yōu)和維數(shù)災(zāi)難。針對(duì)這些問(wèn)題，尤其是針對(duì)算法參數(shù)調(diào)整方面，相關(guān)學(xué)者針提出了很多改進(jìn)算法［5-7］。其中，Shi和Eberhart最早引入了慣性權(quán)重的概念［5］，即后來(lái)普遍認(rèn)為的標(biāo)準(zhǔn)粒子群算法(SPSO)，這也為后續(xù)學(xué)者在參數(shù)調(diào)整方面的研究奠定了基礎(chǔ);Clerc提出一種帶收縮因子的粒子群算法(CPSO)［6］，使用收縮因子可以通過(guò)平衡局部開(kāi)發(fā)能力與全局搜索能力從而改善粒子群算法收斂性能。然而，對(duì)于如何尋求更合適該算法的參數(shù)問(wèn)題仍然是研究的重點(diǎn)和難點(diǎn)。本文在前人研究的基礎(chǔ)上，提出了一種新的參數(shù)調(diào)整方案，將SPSO算法和CPSO算法的精華部分進(jìn)行融合，根據(jù)粒子運(yùn)動(dòng)的特點(diǎn)進(jìn)行參數(shù)調(diào)整，對(duì)速度更新公式各項(xiàng)配以相應(yīng)的權(quán)重因子，從而提高了算法的尋優(yōu)性能。對(duì)三個(gè)基準(zhǔn)函數(shù)進(jìn)行測(cè)試，并與已有SPSO算法和CPSO算法進(jìn)行對(duì)比，證明了本文所提算法在尋優(yōu)精度和執(zhí)行性能方面都具有較好的性能，在求解高維函數(shù)優(yōu)化問(wèn)題時(shí)亦能有效避免維數(shù)災(zāi)難。

1 標(biāo)準(zhǔn)粒子群算法

假設(shè)由m個(gè)粒子組成種群X=(X1，X2，…，Xm)，則在一個(gè)d維的搜索空間中，問(wèn)題的一個(gè)可能解即為第i個(gè)粒子在d維搜索空間的位置向量 Xi=(Xi1，Xi2，…，Xid)T。若以Pi=(Pi1，Pi2，…，Pid)T代表粒子i所經(jīng)歷的最好位置，Pg=(Pg1，Pg2，…，Pgd)T代表種群的全局最優(yōu)位置，Vi=(Vi1，Vi2，…，Vid)T代表第i個(gè)粒子在d維空間的飛行速度，則在每次迭代過(guò)程中，粒子將按式(1)、式(2)更新自身的速度和位置

式中:ω為慣性權(quán)重;i=1，2…，n;Vid為粒子的速度;c1和c2稱為加速因子，通常取2.0;r1和r2為均勻分布的隨機(jī)數(shù)，分布于［0，1］之間。加入慣性權(quán)重ω的PSO算法即為標(biāo)準(zhǔn)粒子群算法(SPSO)，由于其參數(shù)較少，操作簡(jiǎn)單，尋優(yōu)效果較好而得到廣泛應(yīng)用。按照Shi和Eberhart最早提出的概念，慣性權(quán)重ω按式(3)線性遞減

式中:ωstart為初始慣性權(quán)重;ωend為迭代到最大次數(shù)時(shí)的慣性權(quán)重;k為當(dāng)前迭代次數(shù);Kmax為最大迭代次數(shù)。然而，SPSO算法可調(diào)整參數(shù)過(guò)少，使得該算法的數(shù)學(xué)基礎(chǔ)相對(duì)薄弱，當(dāng)面對(duì)非線性函數(shù)或者是多維函數(shù)的優(yōu)化問(wèn)題時(shí)，往往過(guò)早陷入局部最優(yōu)，尋優(yōu)效果并不理想。

2 改進(jìn)的PSO算法

2.1 帶約束因子的PSO算法

Clerc提出的帶收縮因子的粒子群算法(CPSO)定義如下

式中:CPSO 算法中Clerc設(shè)定l=4.1，c1=c2=2.05，則收縮因子 χ為 0.729，后兩項(xiàng)系數(shù)為 0.729 × 2.05ri=1.494 45ri，相當(dāng)于速度跟新公式中所有的項(xiàng)都乘一樣的權(quán)重因子，并未考慮到各個(gè)項(xiàng)的單獨(dú)作用，雖然算法在收斂性方面有所改善，但是必須預(yù)先對(duì)算法進(jìn)行限定，而且必須針對(duì)一定的函數(shù)，否則在給定的迭代次數(shù)下很難找到全局最優(yōu)，應(yīng)用范圍受限。

2.2 改進(jìn)的PSO算法

如何選取合適的參數(shù)從而使得算法具有更好的收斂性是研究的熱點(diǎn)和難點(diǎn)，迭代初期本文期望得到較大的慣性權(quán)重使得算法保存較強(qiáng)的全局搜索能力，而迭代后期則期望得到較小的慣性權(quán)重，有利于算法進(jìn)行更精確的局部搜索。文獻(xiàn)［6］指出通過(guò)設(shè)定約束因子可以得到更好的收斂性能，然而實(shí)際上期望的是在全局最優(yōu)位置一定的情況下粒子的個(gè)體最優(yōu)位置更新得更快，從而使得算法的局部搜索能力與全局搜索能力相平衡，達(dá)到更好的尋優(yōu)效果。綜合SPSO和CPSO的優(yōu)缺點(diǎn)，本文提出一種新的參數(shù)調(diào)整策略，速度更新公式各項(xiàng)配以不同的權(quán)重因子。其表達(dá)式如下

式(7)第一部分是對(duì)當(dāng)前速度的調(diào)整，后兩部分是對(duì)粒子個(gè)體與全局位置的調(diào)整。式(7)第一部分保持SPSO算法的慣性權(quán)重因子，可以使得粒子搜索速度加快;第三部分保持CPSO算法的約束因子，可以保證粒子具有更好的全局尋優(yōu)性能;第二部分則融入了SPSO算法和CPSO算法的精華部分，權(quán)重因子為慣性權(quán)重因子與約束因子相乘，既達(dá)到了約束的目的，又可以保證粒子個(gè)體更新按前期速度加速更新，從而使得個(gè)體尋優(yōu)和全局尋優(yōu)達(dá)到平衡。

2.3 算法實(shí)現(xiàn)

步驟1:初始化參數(shù)。設(shè)置慣性權(quán)重ω的取值范圍，隨機(jī)因子r1和r2，最大迭代次數(shù)Kmax，初始速度Vid，空間維數(shù)D，并在所定義的搜索空間中隨機(jī)生成m個(gè)粒子組成初始種群。

步驟2:計(jì)算種群中每個(gè)粒子的適應(yīng)度函數(shù)值。

步驟3:根據(jù)式(7)更新各粒子的飛行速度，根據(jù)更新的飛行速度按照式(2)更新各粒子的位置，從而產(chǎn)生新的種群，實(shí)現(xiàn)個(gè)體極值和群體極值的更新。

步驟4:判斷是否滿足終止條件，若滿足，則算法結(jié)束，輸出最優(yōu)解;否則轉(zhuǎn)入步驟2，直到達(dá)到最大迭代次數(shù)才終止。

3 仿真實(shí)驗(yàn)及性能分析

3.1 測(cè)試函數(shù)

為檢驗(yàn)本文所提算法的性能，選擇3個(gè)較常用于測(cè)試優(yōu)化算法性能的基準(zhǔn)函數(shù)進(jìn)行測(cè)試，各個(gè)測(cè)試函數(shù)的表達(dá)式及其搜索空間如表1所示。其中，Sphere函數(shù)為非線性對(duì)稱單峰函數(shù)，極易實(shí)現(xiàn)，主要用于測(cè)試算法的尋優(yōu)精度;Rosenbrock函數(shù)是很難極小化的病態(tài)二次函數(shù)，主要用于評(píng)價(jià)優(yōu)化算法的執(zhí)行性能;Rastrigrin函數(shù)為典型的具有大量局部最優(yōu)點(diǎn)的復(fù)雜多峰函數(shù)，極易陷入局部最優(yōu)，主要用于測(cè)試算法的局部尋優(yōu)能力，3個(gè)基準(zhǔn)測(cè)試函數(shù)的最優(yōu)解均為0。

表1 測(cè)試函數(shù)

3.2 仿真結(jié)果與分析

粒子種群規(guī)模分別取20，40，60;最大迭代次數(shù)在維數(shù)為10，20，30 維時(shí)分別對(duì)應(yīng)300，600，900 次;慣性權(quán)重ωstart=0.9，ωend=0.4;每個(gè)基準(zhǔn)測(cè)試函數(shù)獨(dú)立在SPSO 算法，CPSO算法，本文算法中各運(yùn)行100次，分別求出最小適應(yīng)度函數(shù)的平均值最優(yōu)值作為評(píng)價(jià)標(biāo)準(zhǔn)。表2～表4為各基準(zhǔn)函數(shù)在這3種算法中的測(cè)試結(jié)果。

表2 Sphere函數(shù)平均最優(yōu)解比較

表3 Rosenbrock函數(shù)平均最優(yōu)解比較

表4 Rastrigrin函數(shù)平均最優(yōu)解比較

由表2數(shù)據(jù)對(duì)比可以看出，在對(duì)單峰函數(shù)f1(x)的優(yōu)化中，當(dāng)種群規(guī)模為20時(shí)，空間維數(shù)較小則3種算法的平均最優(yōu)解都接近于理論最優(yōu)解，隨著空間維數(shù)和迭代次數(shù)的增加，尋優(yōu)難度相應(yīng)增大，本文算法在相同空間維數(shù)和迭代次數(shù)下取得了更接近理論最優(yōu)值的數(shù)值，隨著種群規(guī)模的增加到60，本文算法比SPSO算法和CPSO算法的最優(yōu)解低了一個(gè)數(shù)量級(jí)，證明本文算法在求解多維函數(shù)時(shí)具有更好的尋優(yōu)精度。

由表3數(shù)據(jù)對(duì)比可以看出，雖然f2(x)為很難極小化的病態(tài)二次函數(shù)，但是當(dāng)空間維數(shù)較小時(shí)，本文算法相較于SPSO算法和CPSO算法，尋優(yōu)結(jié)果更貼近與理論最優(yōu)值，當(dāng)空間維數(shù)由10增加到30，本文算法也表現(xiàn)出更好的尋優(yōu)性能，隨著種群規(guī)模的增加，尋優(yōu)精度更好，證明本文算法在求解多維函數(shù)時(shí)具有更好的尋優(yōu)執(zhí)行能力。

由表4數(shù)據(jù)對(duì)比可以看出，對(duì)于具有大量局部最優(yōu)點(diǎn)的復(fù)雜多峰函數(shù)，CPSO算法在空間維數(shù)增加時(shí)局部尋優(yōu)能力逐漸變?nèi)?，而SPSO算法在種群規(guī)模增加時(shí)尋優(yōu)結(jié)果變動(dòng)不大，證明極有可能以及陷入局部最優(yōu)而無(wú)法跳出，而本文所提算法則隨著種群規(guī)模的增加取得了更好的尋優(yōu)數(shù)值，證明本文所提算法在求解多維函數(shù)時(shí)局部尋優(yōu)能力更強(qiáng)，整體性能更好。

為了更直觀反映算法的尋優(yōu)效果，將SPSO、CPSO和本文算法在粒子種群規(guī)模為60，解空間為30維時(shí)進(jìn)行比較，3種算法對(duì)測(cè)試函數(shù)的收斂曲線如圖1所示。由圖1可見(jiàn)，本文算法在解決多維函數(shù)優(yōu)化問(wèn)題時(shí)亦能取得較好的收斂性能，有效避免了維數(shù)災(zāi)難，再次證明了本文所提算法的有效性。

4 結(jié)語(yǔ)

本文提出了一種改進(jìn)的變參數(shù)粒子群算法，該算法在SPSO算法和CPSO算法的基礎(chǔ)上做出改進(jìn)，融合二者的精華部分，將速度更新公式做各項(xiàng)根據(jù)其運(yùn)動(dòng)特性配以不同的權(quán)重因子，算法操作簡(jiǎn)單，易于實(shí)現(xiàn)。通過(guò)3個(gè)基準(zhǔn)測(cè)試函數(shù)的仿真結(jié)果表明，本文所提算法具有更好的尋優(yōu)精度和執(zhí)行能力，在求解多維函數(shù)優(yōu)化問(wèn)題時(shí)，亦能表現(xiàn)出優(yōu)越的收斂性能。

［1］PEREZ R，BEHDINAN K.Particle swarm approach for structural design optimization［J］. Computers ＆ Structures，2007，85(19/20):1579-1588.

［2］COELHO L，SIERAKOWSKI C.A software tool for teaching of particle swarm optimization fundamentals［J］.Advances in Engineering Software，2008，39(11):877-887.

［3］FAN S，ZAHARA E.A hybrid simplex search and particle swarm optimization for unconstrained optimization［J］.European Journal of Operational Research，2007，181(2):527-548.

［4］LI X.Niching without niching paramenters:particle swarm optimization using a ring topology［J］.IEEE Trans.Evolutionary Computation，2010，14(1):150-169.

［5］SHI Y，EBERHART R.A modified particle swarm optimizer［C］//Proc.IEEE Enternational Conference on Evolutionary Computation.Anchorage，AK:IEEE Press，1998:69-73.

［6］CLERC M.The swarm and the queen:towards a deterministic and adaptive particle swarm optimization［C］//Proc.Congress of Evolutionary Computation.Washington:IEEE Press，1999:1951-1957.

［7］李殷，李飛.基于量子粒子群優(yōu)化算法的圖像矢量量化碼書(shū)設(shè)計(jì)［J］.電視技術(shù)，2012，36(17):54-56.