基于動(dòng)態(tài)因子和共享適應(yīng)度的改進(jìn)粒子群算法

譚熠峰, 孫婷婷, 徐新民

(浙江大學(xué) 信息與電子工程學(xué)院， 浙江 杭州 310027)

表1 測試函數(shù)及其特點(diǎn)

表2 粒子數(shù)較多時(shí)算法的迭代對(duì)比

表3 粒子數(shù)較少時(shí)算法的迭代對(duì)比

?

基于動(dòng)態(tài)因子和共享適應(yīng)度的改進(jìn)粒子群算法

譚熠峰, 孫婷婷, 徐新民*

(浙江大學(xué) 信息與電子工程學(xué)院， 浙江 杭州 310027)

為提高粒子群算法的收斂速度和優(yōu)化性能，避免陷入局部最優(yōu)，提出了一種基于動(dòng)態(tài)學(xué)習(xí)因子和共享適應(yīng)度函數(shù)的改進(jìn)粒子群算法.在慣性權(quán)重w隨著迭代次數(shù)非線性減少而動(dòng)態(tài)調(diào)整學(xué)習(xí)因子的基礎(chǔ)上，引入共享適應(yīng)度函數(shù).當(dāng)算法未達(dá)到終止條件而收斂時(shí)，利用粒子和最優(yōu)解間距離挑選一批粒子重新初始化形成新群體，并用共享適應(yīng)度函數(shù)對(duì)新群體進(jìn)行評(píng)價(jià)，新舊2個(gè)群體分別追隨自己的局部最優(yōu)解直至迭代結(jié)束.對(duì)4個(gè)典型多峰復(fù)雜函數(shù)的測試結(jié)果表明，該改進(jìn)算法不僅加快了尋得最優(yōu)解的速度，而且提高了粒子群算法全局收斂的性能.

動(dòng)態(tài)；學(xué)習(xí)因子；共享適應(yīng)度；粒子群算法

0 引 言

粒子群算法(Particle Swarm Optimization, PSO)的基本概念源于對(duì)鳥群覓食行為的研究，最早用于模擬簡單的社會(huì)系統(tǒng).與遺傳算法、蟻群算法等進(jìn)化計(jì)算方法相比，PSO算法具有收斂速度快、設(shè)置參數(shù)少、程序?qū)崿F(xiàn)簡潔方便等特點(diǎn)，可以解決大量非線性、不可微、連續(xù)多峰的優(yōu)化問題，已廣泛應(yīng)用于神經(jīng)網(wǎng)絡(luò)訓(xùn)練、函數(shù)優(yōu)化和模糊系統(tǒng)控制等領(lǐng)域[1-4].但是，由于PSO算法在優(yōu)化過程中追隨最優(yōu)解，所有粒子趨向同一化，如果該最優(yōu)解所在位置為一局部最優(yōu)點(diǎn)，粒子群就難以跳出局部最優(yōu)，出現(xiàn)早熟收斂現(xiàn)象.

為了克服標(biāo)準(zhǔn)PSO算法早熟收斂的缺點(diǎn)，GANDOMI等[5]提出了混沌增強(qiáng)型PSO算法，WANG等[6]提出通過增加變異算子改進(jìn)PSO算法，張健等[7]提出了動(dòng)態(tài)約束因子法(Dynamic Constrain Factor PSO, DCF-PSO).這些改進(jìn)算法明顯提高了收斂的速度，但在局部收斂方面收效甚微.本文在改進(jìn)動(dòng)態(tài)調(diào)整學(xué)習(xí)因子的基礎(chǔ)上，引入遺傳算法中的共享適應(yīng)度函數(shù)，每當(dāng)算法陷入局部最優(yōu)時(shí)，根據(jù)海明距離對(duì)部分粒子重新初始化，并用共享適應(yīng)度函數(shù)來評(píng)價(jià)新粒子群，對(duì)舊粒子群則通過調(diào)整學(xué)習(xí)因子方法達(dá)到快速精確搜索.通過經(jīng)典測試函數(shù)結(jié)果表明，該改進(jìn)在加快算法收斂速度的同時(shí)，大大提高了全局收斂的成功概率.

1 標(biāo)準(zhǔn)粒子群和動(dòng)態(tài)約束因子算法

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

(1)

(2)

1.2 動(dòng)態(tài)約束因子算法

為了改進(jìn)標(biāo)準(zhǔn)粒子群算法，避免粒子群算法過早收斂，根據(jù)進(jìn)化算法在運(yùn)行初期需加強(qiáng)全局搜索解空間能力，后期需要細(xì)化解空間開拓能力的特點(diǎn)，文獻(xiàn)[7]提出了一種根據(jù)慣性權(quán)重值w的非線性遞減動(dòng)態(tài)調(diào)整學(xué)習(xí)因子c1和c2的DCF-PSO.該算法中w和c1、c2分別按式(3)與(4)更新：

(3)

c1=c2=0.5w2+w+0.5，

(4)

其中，wfinal和winitial分別為w的最大值和最小值，LoopIter表示最大迭代次數(shù)，CurIter表示當(dāng)前迭代次數(shù)，n是冪級(jí)數(shù).

實(shí)驗(yàn)結(jié)果表明，該改進(jìn)有效提高了粒子群算法的收斂速度，但其全局收斂性能未能明顯提高.

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

2.1 共享函數(shù)

GOLDBERG等[9]在遺傳算法中提出用共享函數(shù)度量2個(gè)個(gè)體的相鄰關(guān)系和程度.給定個(gè)體g，其共享函數(shù)由其與種群中其他個(gè)體的關(guān)系決定，每個(gè)個(gè)體有一個(gè)共享函數(shù)值Si，i=1,2,…,P，則個(gè)體的原適應(yīng)度函數(shù)f(i)可調(diào)整為新的適應(yīng)度函數(shù)f(i)new：

(5)

文獻(xiàn)[10-11]提出了基于共享函數(shù)改進(jìn)型粒子群優(yōu)化算法(Fitness Sharing Particle Optimizer, FSPSO).該算法初期同標(biāo)準(zhǔn)PSO，當(dāng)粒子群陷入局部最優(yōu)或暫時(shí)停滯狀態(tài)時(shí)，隨機(jī)選擇部分粒子重新初始化為一個(gè)新群體，同時(shí)保留部分作為舊群體用于繼續(xù)搜索局部最優(yōu).2個(gè)群體在各自最優(yōu)個(gè)體gbest下更新和搜索.新群體利用給定共享半徑dshare得到的共享適應(yīng)度函數(shù)阻止新群體立刻回到局部最優(yōu).該算法能達(dá)到跳出局部最優(yōu)的目的，但速度比標(biāo)準(zhǔn)算法低.

2.2 改進(jìn)的粒子群算法

為同時(shí)提高標(biāo)準(zhǔn)全局版PSO的收斂速度和全局收斂性，保證群體多樣性的存在，防止算法過早成熟，結(jié)合文獻(xiàn)[7]中的DFC-PSO和文獻(xiàn)[10]中的FSPSO，提出了帶有動(dòng)態(tài)學(xué)習(xí)因子和共享適應(yīng)度函數(shù)的粒子群算法.

在算法迭代早期，利用式(1)與(2)動(dòng)態(tài)調(diào)整w和c1、c2，更新粒子的速度和位置.

當(dāng)粒子群陷入局部最優(yōu)時(shí)，對(duì)部分粒子重新初始化形成新群體.由于舊群體用于在早熟區(qū)繼續(xù)尋找最優(yōu)，因此越接近最優(yōu)位置越好，本文將與早熟區(qū)最優(yōu)解之間距離較近的粒子作為舊群體，分布較為分散的部分粒子則進(jìn)行變異，再次初始化.給定個(gè)體xi，其與種群已找到的最優(yōu)位置xg間的距離shi由海明距離決定：

(6)

假定有一個(gè)8個(gè)粒子的群體在某一時(shí)刻局部收斂到位置xg，如圖1左圖所示，且sh8>sh6>sh7>sh1>sh4>sh5>sh3>sh2，按海明距離值的大小順序，取出占粒子總數(shù)前75%(即6個(gè))的粒子作為新群體變異.保留位置較為集中的2個(gè)，構(gòu)成一個(gè)獨(dú)立的舊群體，繼續(xù)搜索早熟區(qū)的最優(yōu)解gbest.

圖1 粒子群分布圖Fig.1 Distribution of a particle swarm

為更好地搜索到最優(yōu)解，本文按粒子類別分類調(diào)整學(xué)習(xí)因子.由于新群體被初始化，按式(3)與(4)計(jì)算w更新粒子，其中式(3)中分母上的迭代總數(shù)LoopIter變?yōu)長oopIternew，LoopIternew為剩下還未發(fā)生的迭代總次數(shù)，以保證w重新從wfinal遞減至winitial.而舊群體用于追隨最優(yōu)解，因此早熟區(qū)粒子的慣性權(quán)重w和認(rèn)知學(xué)習(xí)因子c1繼續(xù)減小，而用于追隨最優(yōu)解的社會(huì)學(xué)習(xí)因子c2：

c2=4-c1.

(7)

則按式(7)調(diào)整，以便增大粒子的社會(huì)學(xué)習(xí)信息，尋得早熟區(qū)最優(yōu)解.

然而，新群體中的粒子也可能再次進(jìn)入早熟區(qū)，如圖1右圖中的粒子x6.為阻止粒子在迭代過程中再次陷入同一最優(yōu)點(diǎn)，參照文獻(xiàn)[10]利用共享距離dshare對(duì)新個(gè)體的適應(yīng)度進(jìn)行調(diào)整.本文根據(jù)粒子群的分布關(guān)系采用動(dòng)態(tài)計(jì)算方法改變dshare.在初始化之前，根據(jù)shi的大小，以dshare=shm作為早熟區(qū)的判斷條件，其中shm為占粒子總數(shù)百分比為m的粒子的距離.在圖1中當(dāng)m=25%時(shí)，dshare為粒子x3到最優(yōu)解的距離.重新初始化后，計(jì)算新群體中粒子到早熟區(qū)最優(yōu)解的距離d_deci，若d_deci

(8)

其中M為增強(qiáng)適應(yīng)度的一個(gè)常數(shù)，取值1 000.

可見若新粒子進(jìn)入早熟區(qū)，越靠近收斂中心其

對(duì)于粒子群是否陷入局部最優(yōu)，可借鑒文獻(xiàn)[12]中使用的判斷方法，當(dāng)gbest和每個(gè)粒子的pbest均值分別連續(xù)，T1和T2迭代最優(yōu)值沒有得到提升，則選擇部分粒子重新初始化.

算法具體步驟如下：

1)對(duì)粒子的位置和速度進(jìn)行隨機(jī)初始化；

2)分別計(jì)算粒子的適應(yīng)度，判斷迭代次數(shù)是否超過最大值，若是則跳至步驟6，否則繼續(xù)；

3)判斷粒子群是否收斂，若是則跳至步驟5，否則繼續(xù)；

4)按算法動(dòng)態(tài)更新約束因子，更新每個(gè)粒子的位置與速度，跳至步驟2；

5)計(jì)算海明距離值shi及共享距離dshare，選出部分粒子重新初始化，跳至步驟2；

他們的通話內(nèi)容如下：“老公，是不是我想要什么你都會(huì)給我??？”“那當(dāng)然。”“我要星星。”“你養(yǎng)仙人球都死，還養(yǎng)猩猩？一頭猩猩多少錢？”“不是，我要天上的星星！”“這個(gè)啊……晚上回家?guī)憧??！?/p>

6)迭代停止，得到最優(yōu)解.

2.3 改進(jìn)實(shí)驗(yàn)結(jié)果

為了說明改進(jìn)的有效性，在Dell-T7500、操作系統(tǒng)為Windows8、所用仿真軟件Matlab版本為R2013a的環(huán)境下，將標(biāo)準(zhǔn)PSO、n=1.2的DCF-PSO與FSPSO以及本文算法進(jìn)行對(duì)比.其中wfinal=1.0，winitial=0.3，變異比例l=0.6，對(duì)固定系數(shù)的算法選擇c1= c2=2，w=0.729.為更好地對(duì)上述算法進(jìn)行評(píng)估，避免算法性能表現(xiàn)出偶然性，采用4個(gè)經(jīng)典多峰函數(shù)Griewank、Rastrigin、Ackley及Schaffer為適應(yīng)度評(píng)價(jià)函數(shù)，這些函數(shù)存在大量局部最優(yōu)值，很難從中找到全局最優(yōu)值，是評(píng)估算法性能的理想函數(shù)，各測試函數(shù)的特點(diǎn)如表1所示.

[8,11,13]，表2列出了當(dāng)Griewank、Rastrigin、Ackley粒子數(shù)為53、Schaffer粒子數(shù)為8時(shí)，算法的迭代條件及運(yùn)行結(jié)果.同時(shí)作為對(duì)比，表3列出了當(dāng)粒子數(shù)減少，Griewank、Rastrigin、Ackley粒子數(shù)為30、Schaffer粒子數(shù)為5時(shí)算法的迭代條件及運(yùn)行結(jié)果.其中Ps表示成功收斂到最優(yōu)解的次數(shù)，Tave表示達(dá)到門限值時(shí)的平均迭代次數(shù).

表1 測試函數(shù)及其特點(diǎn)

Table 1 Test functions and their characters

表2 粒子數(shù)較多時(shí)算法的迭代對(duì)比

Table 2 Performance comparison of algorithms with more particles

表3 粒子數(shù)較少時(shí)算法的迭代對(duì)比

Table 3 Performance comparison of algorithms with fewer particles

由表2可知，當(dāng)粒子數(shù)較多時(shí)，DCF-PSO的收斂速度明顯提高，但其全局收斂性與標(biāo)準(zhǔn)PSO無明顯差異；FSPSO的全局收斂性更好，搜索到最優(yōu)解的次數(shù)增加，但其收斂速度與標(biāo)準(zhǔn)PSO幾乎一致.DCF-PSO動(dòng)態(tài)調(diào)整學(xué)習(xí)因子使得算法在不同時(shí)期有不同的搜索能力和速度，提高收斂速度的同時(shí)不至于經(jīng)常陷入局部最優(yōu)；FSPSO始終保證粒子群體的多樣性，能夠及時(shí)從局部最優(yōu)狀態(tài)中跳出，從而提高了全局收斂性.

改進(jìn)算法結(jié)合了DCF-PSO和FSPSO的優(yōu)點(diǎn)，相對(duì)于前述3種算法，其全局收斂性明顯增強(qiáng)，成功搜索到最優(yōu)解的次數(shù)Ps大大增加，幾乎每次都能收斂到最小值；同時(shí)與前3種算法相比，改進(jìn)算法的平均收斂次數(shù)更少，收斂速度提高很多，且均優(yōu)于單獨(dú)改進(jìn)的DCF-PSO或FSPSO.

由表3可知，當(dāng)粒子數(shù)較少時(shí)，各算法成功收斂到最優(yōu)解的次數(shù)都有明顯降低，速度變慢.DCF-PSO和FSPSO與標(biāo)準(zhǔn)PSO相比，其性能與粒子數(shù)較多時(shí)一致，改進(jìn)算法相較于前述3種算法，全局收斂性明顯變好，優(yōu)于單獨(dú)改進(jìn)的DCF-PSO或FSPSO，但其收斂速度與DCF-PSO比無顯著變化，比標(biāo)準(zhǔn)PSO和FSPSO要快.

3 結(jié) 論

PSO算法是一種實(shí)現(xiàn)容易、精度高、收斂快的進(jìn)化優(yōu)化算法.本文在慣性權(quán)重隨著迭代次數(shù)減小、動(dòng)態(tài)改進(jìn)學(xué)習(xí)因子的基礎(chǔ)上，引入遺傳算法中的共享適應(yīng)度函數(shù).在運(yùn)算過程中，隨著算法收斂選擇部分粒子的初始化，將粒子群變異為新舊2個(gè)群體后進(jìn)一步搜索全局最優(yōu)解，通過動(dòng)態(tài)共享距離阻止新群體回到舊群體的局部最優(yōu)值.該改進(jìn)算法相對(duì)于標(biāo)準(zhǔn)PSO計(jì)算量并未顯著增加，對(duì)經(jīng)典多峰復(fù)雜函數(shù)的仿真實(shí)驗(yàn)表明：該算法在不同粒子數(shù)量下均表現(xiàn)出更好的性能，具有很強(qiáng)的適應(yīng)性，不僅加快了其尋得最優(yōu)解的速度以及收斂速度，而且增強(qiáng)了粒子群算法全局收斂的性能.

參考文獻(xiàn)(References)：

[1] 龍泉,劉永前,楊勇平.基于粒子群優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的風(fēng)電機(jī)組齒輪箱故障診斷方法[J].太陽能學(xué)報(bào)，2012,33(1):120-125. LONG Quan, LIU Yongqian, YANG Yongping. Fault diagnosis method of wind turbine gearbox based on BP neural network trained by particle swarm optimization algorithm[J].Acta Energiae Solaris Sinica,2012,33(1):120-125.

[3] 王登科，李忠.基于粒子群優(yōu)化與蟻群優(yōu)化的云計(jì)算任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用與軟件，2013,30(1):290-293. WANG Dengke, LI Zhong. A task scheduling algorithm based on PSO and ACO for cloud computing[J]. Computer Applications and Software,2013,30(1):290-293.

[4] KHARE A, RANGNEKAR S. A review of particle swarm optimization and its applications in solar photovoltaic system[J]. Applied Soft Computing,2013,13(5):2997-3006.

[5] GANDOMI A H, YUN G J, YANG X S, et al. Chaos-enhanced accelerated particle swarm optimization[J]. Communications in Nonlinear Science and Numerical Simulation,2013,18(2):327-340.

[6] WANG G G, GANDOMI A H, YANG X S, et al. A novel improved accelerated particle swarm optimization algorithm for global numerical optimization[J]. Engineering Computations,2014,31(7):1198-1220.

[7] 張健，朱旭東，王真.一個(gè)新的動(dòng)態(tài)約束因子PSO算法[J].河北工業(yè)大學(xué)學(xué)報(bào)，2010,39(003):51-55. ZHANG Jian, ZHU Xudong, WANG Zhen. A new dynamic constrain factor particle swarm optimization algorithm[J]. Journal of Heibei University of Technology,2010,39(3):51-55.

[8] KENNEDY J. Particle Swarm Optimization[M]// SAMMUT C, WEBB G I. Encyclopedia of Machine Learning. New York: Springer US,2010:760-766.

[9] GOLDBERG D E, RICHARDSON J. Genetic algorithms with sharing for multimodal function optimization[C]// Proceedings of the Second International Conference on Genetic Algorithms on Genetic Algorithms and Their Application. Hillsdale: L Erlbaum Associates Inc,1987:41-49.

[10] LI T, WEI C, PEI W. PSO with sharing for multimodal function optimization[C]//Proceedings of the 2003 International Conference on Neural Networks and Signal Processing, 2003. Nanjing: IEEE,2003(1):450-453.

[11] 白瑞林，王利峰.一種基于共享法的改進(jìn)型粒子群優(yōu)化算法[C]//2005中國控制與決策學(xué)術(shù)年會(huì)論文集(上).沈陽：東北大學(xué)出版社，2005：795-798. BAI Ruilin, WANG Lifeng. A modified particle swarm optimization algorithm based on sharing method[C]//Proceeding of 2005 Chinese Control and Decision Conference. Shenyang: Northeastern University Press,2005:795-798.

[12] 劉衍民，隋常玲，牛奔.解決約束優(yōu)化問題的改進(jìn)粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用，2011(12):23-26. LIU Yanmin, SUI Changling, NIU Ben. Improved particle swarm optimizer for constrained optimization problems[J]. Computer Engineering and Applications,2011(12):23-26.

[13] 鄔嘯.一種對(duì)粒子群算法慣性權(quán)重的改進(jìn)[J].計(jì)算機(jī)時(shí)代，2010(10):25-27. WU Xiao. An improvement for inertia weight of particle swarm optimization[J]. Computer Era,2010(10):25-27.

[14] 周飛紅,廖子貞.自適應(yīng)慣性權(quán)重的分組并行粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用，2014,50(8)：40-44. ZHOU Feihong, LIAO Zizhen. Grouping parallel particle swarm optimization algorithm with adaptive inertia weight[J]. Computer Engineering and Applications,2014,50(8)：40-44.

TAN Yifeng, SUN Tingting, XU Xinming

(CollegeofInformationScience&ElectronicEngineering,ZhejiangUniversity,Hangzhou310027,China)

A modified particle swarm optimization algorithm based on dynamic learning factors and sharing method. Journal of Zhejiang University(Science Edition), 2016,43(6):696-700

To improve the global convergence ability and rate of particle swarm optimization, an improved particle swarm optimization algorithm based on dynamic learning factors and sharing method is proposed. The inertia weight factor of the algorithm decreases non-linearly, and the learning factor changes dynamically with the descending. A sharing fitness function is introduced on the basis of dynamic regulation. When the algorithm is stagnated without reaching termination, part of the particles will be selected according to the distance between particles and optimal solution. The chosen particles will be re-initialized as a new swarm and be evaluated by sharing fitness. The old and new swarms follow their own local solutions respectively until the end of the iteration. Simulation results of four typical multimodal functions show that the modified algorithm can greatly enhance the rate of the optimal solution searching and improve the global convergence performance of PSO.

dynamic; learning factor; sharing fitness; particle swarm optimization

2014-03-04.

浙江省公益技術(shù)研究工業(yè)項(xiàng)目(2015C31073).

譚熠峰(1991-)，ORCID:http://orcid.org/0000-0003-1151-9206,男，碩士研究生，主要從事嵌入式研究.

*通信作者，http://orcid.org/0000-0002-0910-2375,E-mail:xuxm@zju.edu.cn.

10.3785/j.issn.1008-9497.2016.06.014

TP 301.6

A

1008-9497(2016)06-696-05