協(xié)同粒子群優(yōu)化算法的改進與仿真

2015-12-23 01:00:12蒲國林

計算機工程與設計 2015年6期

侯翔，蒲國林

（四川文理學院計算機科學系，四川達州635000）

0 引言

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

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

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

1 協(xié)同PSO 算法

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

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

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

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

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

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

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

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

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

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

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

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

圖1 COPSO 算法偽代碼

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

3 仿真實驗

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

（1）Sphere函數(shù)

（2）Rastrigrin函數(shù)

（3）Griewank函數(shù)

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

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

對微粒子的初始值采用不對稱的選擇方式，它們的初始值范圍、目標精度、微粒子速度和位置的極限值見表1，所有實驗的最大進化代數(shù)為5000次。

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

［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）.［劉志雄.基于粒子群算法的物流車輛優(yōu)化調(diào)度研究［J］.武漢科技大學學報，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.