侯 翔，蒲國(guó)林

（四川文理學(xué)院 計(jì)算機(jī)科學(xué)系，四川 達(dá)州635000）

0 引 言

最初的PSO 算法雖然結(jié)構(gòu)簡(jiǎn)單，卻無(wú)法保證算法收斂，為此許多改進(jìn)的PSO 算法應(yīng)運(yùn)而生［1］。比較典型的是線性慣性權(quán)PSO 算法［2］和模糊慣性權(quán)PSO 算法［3］，文獻(xiàn)［4］提出了具有收縮因子PSO 算法等，但以上算法往往會(huì)出現(xiàn)過(guò)早收斂現(xiàn)象。

通常情況下，PSO 算法具有易陷入過(guò)早收斂的缺陷，同時(shí)，易受到維數(shù)災(zāi)難 （curse of dimensionality）的困擾。針對(duì)該問(wèn)題，Van等［5］借鑒遺傳算法的合作協(xié)同進(jìn)化算子，采用降維的方法，提出了一種協(xié)同PSO 算法 （CPSO）。雖然CPSO 算法在解決某些問(wèn)題的同時(shí)可以提高優(yōu)化過(guò)程的收斂性能，但該算法會(huì)出現(xiàn)偽最小值現(xiàn)象，并且不能保證收斂到局部或全局最優(yōu)。文獻(xiàn) ［6］將隨機(jī)PSO 方法引入到CPSO 中，提出了一種以概率1收斂到全局最優(yōu)的改進(jìn)協(xié)同PSO 算法 （ICPSO），該算法的全局收斂性主要由隨機(jī)PSO 保證，CPSO 主要用于提高算法的收斂速度。

本文根據(jù)協(xié)同進(jìn)化原理，通過(guò)對(duì)傳統(tǒng)PSO 算法進(jìn)行協(xié)同優(yōu)化處理，設(shè)計(jì)了一種改進(jìn)的協(xié)同PSO 算法。該算法通過(guò)對(duì)所有粒子經(jīng)歷的最優(yōu)位置采用協(xié)同優(yōu)化策略，為群的全局最優(yōu)提供一個(gè)參考，以提高算法的收斂性能。

1 協(xié)同PSO 算法

對(duì)于經(jīng)典的PSO 算法，通常是由一個(gè)或若干個(gè)群組和而成，而每個(gè)群又包含許多粒子，對(duì)于群中的粒子，其位置信息由與其對(duì)應(yīng)的n 維矢量來(lái)表示，表示問(wèn)題可行解。粒子根據(jù)一定的飛行策略不斷地改變自身的速度和方向，根據(jù)自身的記憶功能和信息分享機(jī)制求出問(wèn)題最優(yōu)解［7，8］。

該進(jìn)化策略將n維空間作為一個(gè)整體，在每次優(yōu)化中，將依據(jù)適應(yīng)值的優(yōu)劣，同時(shí)更新解向量的n 個(gè)分量。該策略使得粒子群逐漸移向問(wèn)題的最優(yōu)解，但是該策略在有些分量上出現(xiàn) “進(jìn)兩步，退一步”的問(wèn)題。例如對(duì)于n 維解空間，適應(yīng)值定義為f（x）＝，當(dāng)n＝3時(shí)，顯然問(wèn)題的最優(yōu)解是 （0，0，0）。假設(shè)第k 次搜索的最優(yōu)解是g＝（0.1，5，0.1），f（g）＝25.02，顯然解的第1個(gè)分量和第3個(gè)分量已經(jīng)比較接近全局最優(yōu)解；在k＋1次搜索中，群中適應(yīng)值最小的粒子位于 （3，1，3）處，其適應(yīng)值為19，根據(jù)上述進(jìn)化策略，粒子群搜索到的最優(yōu)解將更新為g＝ （3，1，3），即使解出第2個(gè)分量已經(jīng)很接近全局最優(yōu)，但是也可能使原來(lái)已經(jīng)很接近最優(yōu)解的分量遠(yuǎn)離最優(yōu)解。鑒于PSO是一種隨機(jī)優(yōu)化算法，因此，上述情況是有可能發(fā)生的。

在PSO算法對(duì)最優(yōu)解搜索的過(guò)程中，針對(duì)其可能發(fā)生的“進(jìn)兩步，退一步”的現(xiàn)象，Van等根據(jù)合作協(xié)同進(jìn)化遺傳算法的主要思想，提出了一種降維分解的PSO 算法，并稱(chēng)之為CPSO （cooperative PSO）算法，該算法的主要思路如下：

對(duì)于n維空間的優(yōu)化問(wèn)題，構(gòu)造n 個(gè)粒子群，每個(gè)群代表n 維空間的一個(gè)分量，并且由m 個(gè)粒子組成。每次迭代，所有粒子采用常規(guī)的PSO 策略更新位置和速度值，并根據(jù)適應(yīng)值最小原則，分別更新每個(gè)粒子所經(jīng)歷的最優(yōu)位置pbest和n 個(gè)粒子群所經(jīng)歷的最優(yōu)位置gbest，再將這n個(gè)gbest聯(lián)合組成一個(gè)n 維向量作為問(wèn)題最優(yōu)解的近似值。

由于計(jì)算適應(yīng)值需要完整的n 維向量，而每個(gè)粒子只對(duì)應(yīng)n維向量的一個(gè)分量，因此為了優(yōu)化n 個(gè)1維粒子群，必須構(gòu)造一個(gè)n 維向量。Van等將前一次迭代得到的問(wèn)題最優(yōu)解的近似值作為一個(gè)常量P，在考慮第i個(gè)粒子群時(shí)，逐一用m 個(gè)粒子替換P 的第i 個(gè)分量，計(jì)算其適應(yīng)值，最小適應(yīng)值對(duì)應(yīng)的粒子為該群本次迭代的最優(yōu)值。

考慮n 維解向量的各分量可能存在某些關(guān)聯(lián)，Van等［5］在此基礎(chǔ)上又提出了CPSO－Sk算法，即根據(jù)某個(gè)分裂因子 （split factor），構(gòu)造若干個(gè)k 維粒子群，每個(gè)粒子代表解空間的連續(xù)k個(gè)分量。算法的執(zhí)行過(guò)程與CPSO 類(lèi)似，這里就不再詳細(xì)闡述。

雖然CPSO算法試圖通過(guò)降維方法解決前面提到PSO 算法中的“進(jìn)兩步，退一步”問(wèn)題，也取得了相應(yīng)的效果，但并沒(méi)有將解向量各維分量相互之間有可能存在的關(guān)聯(lián)關(guān)系考慮在內(nèi)，因此通過(guò)CPSO算法獲得的各維分量的最優(yōu)值的聯(lián)合，并不能等同于問(wèn)題的最優(yōu)解。文獻(xiàn) ［6］研究表明CPSO算法容易產(chǎn)生偽最小值，甚至根本無(wú)法進(jìn)入問(wèn)題最優(yōu)解的鄰域，因此該算法無(wú)法保證收斂到局部或全局最優(yōu)。

2 改進(jìn)的協(xié)同PSO 算法

雖然單純的CPSO 不是一種合適的優(yōu)化算法［9，10］，但將CPSO 算法中的協(xié)同優(yōu)化的思想用到常規(guī)的PSO 算法中，可以改善算法性能。為此，本文提出了一種改進(jìn)CPSO算法，為了敘述的方便及不引起歧議，以下將本文提出的算法記為COPSO，該算法的主要思路如下：

算法由一個(gè)粒子群構(gòu)成，群中粒子的位置信息由一個(gè)n維矢量來(lái)表示，其表示問(wèn)題可行解。通過(guò)迭代，粒子根據(jù)常規(guī)PSO 算法更新位置和速度矢量，并根據(jù)適應(yīng)值最小原則，更新各自所經(jīng)歷的最優(yōu)位置pbest和整個(gè)粒子群經(jīng)歷的最優(yōu)位置gbest。

隨后，借鑒CPSO 中的協(xié)同優(yōu)化方法，對(duì)所有粒子的歷史最優(yōu)位置pbest進(jìn)行逐維優(yōu)化，具體優(yōu)化過(guò)程詳見(jiàn)算法偽代碼，并形成一個(gè)粒子群參考全局最優(yōu)位置G。

最后，比較兩全局最優(yōu)位置gbest和G，如果G 的適應(yīng)值更優(yōu)，則用G 替換gbest，完成后進(jìn)入下一次迭代。圖1為COPSO 算法偽代碼。

圖1 COPSO 算法偽代碼

圖1的第9行提出要更新粒子的位置和速度，但沒(méi)有具體指明用哪種方式更新，這表示可以用任何常規(guī)的PSO算法更新粒子位置和速度。

3 仿真實(shí)驗(yàn)

為了說(shuō)明COPSO 算法的性能，本文分別將其用于慣性權(quán)PSO［11］及帶收縮因子的PSO 算法［12］中，也就是在這兩種常規(guī)PSO 算法中加入本文提出的對(duì)粒子經(jīng)歷的最優(yōu)位置進(jìn)行降維協(xié)同優(yōu)化策略，并對(duì)加入前后的算法性能進(jìn)行比較實(shí)驗(yàn)。本文選取了3個(gè)常用的標(biāo)準(zhǔn)非線性測(cè)試函數(shù)，它們分別是：

（1）Sphere函數(shù)

（2）Rastrigrin函數(shù)

（3）Griewank函數(shù)

式中：x ＝（x1，x2，…，xn）維實(shí)向量。

上述3個(gè)標(biāo)準(zhǔn)函數(shù)的最小值均為0，其中Sphere函數(shù)是單峰值函數(shù)，其它為多峰值函數(shù)。在所有實(shí)驗(yàn)中，上述3個(gè)函數(shù)均取30維，并設(shè)定群中微粒子的數(shù)目為30。慣性權(quán)PSO 算法的參數(shù)設(shè)置為：w＝0.9－0.5t/tmax，c1＝c2＝2，其中t為當(dāng)前進(jìn)化代數(shù)，tmax為最大進(jìn)化代數(shù)；帶收縮因子的PSO 算法的參數(shù)設(shè)置為：k＝0.729，φ ＝4.1。

對(duì)微粒子的初始值采用不對(duì)稱(chēng)的選擇方式，它們的初始值范圍、目標(biāo)精度、微粒子速度和位置的極限值見(jiàn)表1，所有實(shí)驗(yàn)的最大進(jìn)化代數(shù)為5000次。

表1 各測(cè)試函數(shù)的參數(shù)范圍

本文所有仿真實(shí)驗(yàn)均在MATLAB中完成，MATLAB可以顯示的最小數(shù)值為eps＊realmin＝4.9407×10－324，即再小于該數(shù)值，則在MATLAB 中顯示為0。為保證實(shí)驗(yàn)結(jié)果的可信度，每種算法對(duì)每個(gè)測(cè)試函數(shù)的優(yōu)化均進(jìn)行了20次獨(dú)立的仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表2、圖2、表3、圖3所示。

表2是COPSO 與慣性權(quán)PSO 兩種算法的實(shí)驗(yàn)結(jié)果比較統(tǒng)計(jì)表。表中IWPSO 表示慣性權(quán)PSO 算法；It＿av、It＿max、It＿min分別表示在20次獨(dú)立實(shí)驗(yàn)中，達(dá)到目標(biāo)精度所需的平均迭代次數(shù)、最大迭代次數(shù)及最少迭代次數(shù)；F＿av表示經(jīng)過(guò)5000次迭代后所能達(dá)到的解的平均函數(shù)值（或適應(yīng)值）；表中的0表示實(shí)際值小于MATLAB的顯示的最小數(shù)值，可以認(rèn)為算法優(yōu)化已達(dá)到全局最優(yōu)。

表2 COPSO 與慣性權(quán)PSO 比較實(shí)驗(yàn)結(jié)果

表3 COPSO 與帶收縮因子PSO 比較實(shí)驗(yàn)結(jié)果

從表2可以看出，COPSO 對(duì)于3個(gè)測(cè)試函數(shù)的優(yōu)化性能均有所提高。對(duì)于Sphere函數(shù)，與慣性權(quán)PSO 相比，COPSO 首先將達(dá)到目標(biāo)精度的迭代次數(shù)提前了723次，相當(dāng)于將收斂速度提高了近20%；其次，經(jīng)過(guò)5000次迭代，COPSO 的精度提高了10120多倍。對(duì)于Rastrigrin 函數(shù)，COPSO 雖然在收斂速度上有明顯提高，但最終的收斂精度并沒(méi)有顯著改善，進(jìn)一步說(shuō)明COPSO 有利于改善PSO 算法的收斂速度，但還不能保證算法收斂到全局最優(yōu)。COPSO 的性能在對(duì)Griewank函數(shù)的優(yōu)化中表現(xiàn)最為突出，它使得算法收斂速度提高了4倍多，而且達(dá)到全局最優(yōu)。

為了更清晰地顯示實(shí)驗(yàn)過(guò)程，本文將表2中的比較實(shí)驗(yàn)過(guò)程繪制成曲線如圖2所示。圖2包含3組曲線圖，分別表示對(duì)3個(gè)測(cè)試函數(shù)進(jìn)行優(yōu)化的實(shí)驗(yàn)過(guò)程。每一個(gè)曲線圖中的兩條曲線分別表示兩種算法在20次獨(dú)立實(shí)驗(yàn)中解的平均適應(yīng)值的變化過(guò)程。其中PSOco表示COPSO 算法，PSOiw表示慣性權(quán)PSO 算法。

從圖2可以看出，COPSO 使得算法收斂過(guò)程明顯加快，圖2 （a）和圖2 （c）表明COPSO 在算法收斂精度上有顯著提高。圖2 （b）表明兩種算法針對(duì)Rastrigrin函數(shù)沒(méi)有顯著差別，但仍然可以看出，在初始階段，COPSO 的收斂速度明顯加快。

表3是COPSO 與帶收縮因子的PSO 兩種算法的比較實(shí)驗(yàn)結(jié)果的統(tǒng)計(jì)表。表中CFPSO 表示帶收縮因子的PSO算法；N/A 表示在所有20次獨(dú)立實(shí)驗(yàn)中均未能達(dá)到設(shè)定的目標(biāo)精度；表中其它標(biāo)注與表2相同。另外，表中最后一行數(shù)據(jù)表示帶收縮因子PSO 對(duì)Griewank函數(shù)的優(yōu)化結(jié)果，由于在20次獨(dú)立實(shí)驗(yàn)中，有4 次實(shí)驗(yàn)均未能達(dá)到目標(biāo)精度，所以該行數(shù)值為其它16次實(shí)驗(yàn)的統(tǒng)計(jì)結(jié)果。

從表3中可以看出，對(duì)于Sphere函數(shù)和Griewank 函數(shù)，COPSO 無(wú)論在收斂速度還是收斂精度上都有顯著提高，而且從達(dá)到目標(biāo)精度的最大及最小迭代次數(shù)上看，COPSO 算法更為穩(wěn)定。但對(duì)Rastrigrin函數(shù)，COPSO 沒(méi)有顯示優(yōu)勢(shì)，甚至在算法精度上還略遜于CFPSO。

表3所示實(shí)驗(yàn)的過(guò)程曲線如圖3所示，圖中PSOcf表示帶收縮因子的PSO，其它標(biāo)注與圖2 相同。由于對(duì)于Rastrigrin函數(shù)，兩種算法在所有40 次獨(dú)立實(shí)驗(yàn)中，迭代2000次后解的適應(yīng)值均不再變化，所以為了顯示算法初期的變化，只繪制了前2000次迭代的過(guò)程。從圖中可以明顯看出COPSO 算法在對(duì)Sphere函數(shù)和Griewank函數(shù)優(yōu)化時(shí)的顯著優(yōu)勢(shì)。值得一提的是，根據(jù)對(duì)表3 數(shù)據(jù)的分析，對(duì)于Rastrigrin 函數(shù)，COPSO 算法甚至不如帶收縮因子的PSO，但是從圖3 （b）可以看出，COPSO 還是可以明顯提高算法在初始階段的收斂速度。

由仿真結(jié)果可以得出，COPSO 算法能夠明顯地提高了收斂速度和收斂精度，甚至可以收斂到全局最優(yōu)，這也再次說(shuō)明COPSO 算法不能保證收斂到全局最優(yōu)。

4 結(jié)束語(yǔ)

本文根據(jù)協(xié)同進(jìn)化基本原理，通過(guò)在常規(guī)PSO 算法中加入簡(jiǎn)單的降維協(xié)同優(yōu)化策略，以提高常規(guī)PSO 算法在高維優(yōu)化問(wèn)題中的性能。大量仿真比較實(shí)驗(yàn)結(jié)果表明，本文所提出的改進(jìn)協(xié)同PSO 算法有利于提高算法收斂的速度，對(duì)某些問(wèn)題可以顯著提高算法的收斂精度，甚至可以收斂到全局最優(yōu)。但是COPSO 算法無(wú)法保證算法收斂到全局最優(yōu)，這也是需要進(jìn)一步研究的地方。

［1］Cooren Y，Clerc M，Siarry P.MO－TRIBES，an adaptive multiobjective particle swarm optimization algorithm ［J］.Computational Optimization and Applications，2011，49 （2）：379－400.

［2］Chen WN，Zhang J，Chung HS，et al.A novel set－based particle swarm optimization method for discrete optimization problems［J］.IEEE Transactions on Evolutionary Computation，2012，14 （2）：278－300.

［3］Shi SY，Eberhart R.Fuzzy adaptive particle swarm optimization ［C］//Proceedings of the Congress on Evolutionary Computation，2001：101－106.

［4］Clerc M，Kennedy J.The particle swarm－explosion，stability and convergence in a multidimensional complex space ［J］.IEEE Transactions on Evolutionary Computation，2002，6（1）：58－73.

［5］Frans VDB，Andries PE.A cooperative approach to particle swarm optimization ［J］.IEEE Transactions on Evolutionary Computation，2004，8 （3）：225－239.

［6］Shi YH，Eberhart R.Empirical study of particle swarm optimization ［C］//Proceedings of the Congress on Evolutionary Computation，1999.

［7］LIU Zhixiong.Logistics vehicle scheduling optimization based on particle swarm optimization ［J］.Wuhan University of Science and Technology，2012，32 （6）：615－618 （in Chinese）.［劉志雄.基于粒子群算法的物流車(chē)輛優(yōu)化調(diào)度研究 ［J］.武漢科技大學(xué)學(xué)報(bào)，2012，32 （6）：615－618.］

［8］Monay F，Gatica－Perez D.Modeling semantic aspects for CROSmedia image indexing［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，29 （10）：1802－1817.

［9］Xu Xinli，Hao Ping，Wang Wanliang，et al.Multi－agent dynamic scheduling method and its application to dyeing shops scheduling ［J］.Computer Integrated Manufacturing Systems，2012，16 （3）：612－620.

［10］Feng Hongkui，Bao Jinsong，Jin Ye.Hybrid particle swam optimization algorithm for multiple vehicle dragging goods problem ［J］.Computer Integrated Manufacturing Systems，2012，16 （7）：1428－1436.

［11］Zhou XC，Zhou ZX，Zhou KJ，et al.Remanufacturing closedloop supply chain network design based on genetic particle swarm optimization algorithm ［J］.Journal of Central South University of Technology，2012，19 （2）：482－487.

［12］HAN Pengfei，SUN Zhanlei，ZHAO Gang.Improved discrete particle swarm algorithm and its application in the study of eating machine assembly task scheduling ［J］.Graphics Sinica，2013，34 （1）：60－65 （in Chinese）. ［韓鵬飛，孫占磊，趙罡.改進(jìn)離散粒子群算法及其在吃機(jī)裝配任務(wù)調(diào)度中的應(yīng)用研究 ［J］.圖學(xué)學(xué)報(bào)，2013，34 （1）：60－65.］