一種混合聚類的粒子群差分進(jìn)化算法*

劉　陽,高興寶,劉　睿

(陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院,西安 710119)

?

一種混合聚類的粒子群差分進(jìn)化算法*

劉陽,高興寶,劉睿

(陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院,西安 710119)

摘要：針對(duì)差分進(jìn)化算法在運(yùn)行后期收斂速度慢和容易陷入局部最優(yōu)的不足,提出一種混合聚類的粒子群差分進(jìn)化算法.利用一步K-均值聚類算法改進(jìn)粒子群優(yōu)化算法的速度更新,使用線性遞減的選擇概率將改進(jìn)后的粒子群算法與差分進(jìn)化算法相融合,并在一定條件下對(duì)種群中部分較差個(gè)體進(jìn)行重置.對(duì)9個(gè)典型測試函數(shù)的數(shù)值試驗(yàn)和與其他三種進(jìn)化算法的比較結(jié)果表明：所提算法收斂速度快,尋優(yōu)能力強(qiáng)并且魯棒性好.

關(guān)鍵詞：K-均值聚類;混合算法;差分進(jìn)化;粒子群優(yōu)化;種群重置

進(jìn)化算法(Evolutionary Algorithms,EA)起源于達(dá)爾文生物進(jìn)化理論,通常指模擬自然界生物進(jìn)化的全局優(yōu)化方法[1].由于解決數(shù)值優(yōu)化問題時(shí),進(jìn)化算法僅需要目標(biāo)函數(shù)值,而不要求其解析性質(zhì),因此被廣泛應(yīng)用于科學(xué)和工程各種領(lǐng)域[2].

差分進(jìn)化算法[3](Differential Evolution,DE)和粒子群優(yōu)化算法[4](Particle Swarm Optimization,PSO)是進(jìn)化算法的主要分支,在不同的優(yōu)化問題中表現(xiàn)出很好的性能,且在許多領(lǐng)域均有廣泛應(yīng)用[5-6].作為一種簡單而有效的隨機(jī)搜索算法,DE算法結(jié)構(gòu)簡單,探索能力強(qiáng),但由于其基向量選取的隨機(jī)性,使算法收斂較慢.而作為模仿鳥類覓食行為的群體智能算法,PSO算法具有易于應(yīng)用,控制參數(shù)少和收斂速度快的優(yōu)點(diǎn),但在算法后期容易陷入局部最優(yōu).

為解決DE算法收斂速度慢以及PSO算法容易陷入局部最優(yōu)的問題,研究者對(duì)DE算法和PSO算法分別進(jìn)行了改進(jìn)[7-8],但單一算法不能有效克服算法自身的缺陷,文獻(xiàn)[9]提出了一種新型混合算法,算法采用雙種群進(jìn)化,對(duì)兩個(gè)子種群分別執(zhí)行DE算法和PSO算法,并在子種群之間引入信息交流機(jī)制,但該機(jī)制只針對(duì)子種群中的少數(shù)個(gè)體進(jìn)行,不利于種群進(jìn)化.文獻(xiàn)[10]通過建立粒子早熟判斷機(jī)制,在PSO算法中引入差分進(jìn)化操作.文獻(xiàn)[11]將差分進(jìn)化算法的變異,雜交和選擇操作引入到粒子群算法中,使算法性能有所提高.但是利用差分進(jìn)化算子對(duì)粒子群優(yōu)化算法的改進(jìn),不能充分發(fā)揮兩種算法各自優(yōu)勢.

為充分發(fā)揮DE算法和PSO算法各自優(yōu)勢,本文設(shè)計(jì)了一種混合聚類的粒子群差分進(jìn)化算法.算法運(yùn)用一步K-均值聚類改進(jìn)了粒子群優(yōu)化算法的速度公式,對(duì)DE算法參數(shù)進(jìn)行適應(yīng)性選取;基于優(yōu)勢互補(bǔ)原則,利用線性遞減的選擇概率將DE算法和改進(jìn)后的PSO算法相融合;在種群多樣性較差時(shí)重置種群中部分較差個(gè)體.與其它三個(gè)進(jìn)化算法相比,用9個(gè)典型測試函數(shù)的數(shù)值結(jié)果充分說明了本文算法的有效性.

1標(biāo)準(zhǔn)差分進(jìn)化算法和粒子群算法

1.1標(biāo)準(zhǔn)差分進(jìn)化算法

標(biāo)準(zhǔn)差分進(jìn)化算法[12]以種群為基礎(chǔ),首先對(duì)種群中的每個(gè)個(gè)體(目標(biāo)向量)加入差分項(xiàng)實(shí)現(xiàn)個(gè)體變異產(chǎn)生變異向量,該操作利用種群其它個(gè)體信息對(duì)當(dāng)前個(gè)體進(jìn)行擾動(dòng),使當(dāng)前個(gè)體朝著好的方向前進(jìn);其次對(duì)變異向量的每個(gè)分量執(zhí)行交叉操作生成試驗(yàn)向量,以保證產(chǎn)生的試驗(yàn)向量繼承目標(biāo)向量和變異向量的優(yōu)良信息;最后,在目標(biāo)個(gè)體和對(duì)應(yīng)的試驗(yàn)向量之間選出適應(yīng)度更好的一個(gè)進(jìn)入下一代,保證種群中的個(gè)體總是朝著好的方向發(fā)展.標(biāo)準(zhǔn)差分進(jìn)化算法的步驟如下:

① 初始化操作

設(shè)N為種群規(guī)模,G=0為當(dāng)前種群代數(shù),D為種群維數(shù),初始化種群為Pop=(X1,G,X2,G,…,XN,G),Xi,G=(Xi,1,G,Xi,2,G,…,Xi,D,G)(i=1,2,…,N)表示種群中第i個(gè)個(gè)體,其分量按下式產(chǎn)生:

Xi,j,G=rand(Xi,j,max-Xi,j,min)+Xi,j,min

(1)

其中Xi,j,max和Xi,j,min分別為種群第i個(gè)個(gè)體第j個(gè)分量的最大值和最小值;

② 變異操作

標(biāo)準(zhǔn)差分進(jìn)化算法有多種變異操作,本文采用應(yīng)用最多的DE/rand/1策略,該策略對(duì)種群中的每個(gè)個(gè)體進(jìn)行變異生成變異向量Vi,G=(Vi,1,G,Vi,2,G,…,Vi,D,G) (i=1,2,…,N),變異方式如下:

Vi,G=Xr1,G+F(Xr2,G-Xr3,G)

(2)

其中r1,r2,r3為在區(qū)間[1,N]上隨機(jī)產(chǎn)生的互不相同且不等于i的整數(shù),對(duì)每個(gè)個(gè)體均隨機(jī)產(chǎn)生一次,F為權(quán)衡不同向量的縮放因子,一般情況下F∈[0,1];

③ 交叉操作

對(duì)變異向量Vi,G和目標(biāo)向量Xi,G的每個(gè)分量實(shí)施交叉操作生成試驗(yàn)向量Ui,G=(Ui,1,G,Ui,2,G,…,Ui,D,G) (i=1,2,…,N),常用的交叉操作有:二項(xiàng)式交叉和指數(shù)交叉,本文采用如下的二項(xiàng)式交叉:

(3)

其中jrand是區(qū)間[1,D]上的隨機(jī)整數(shù),它使得試驗(yàn)向量至少繼承了變異向量的一個(gè)分量,交叉概率CR是由用戶指定的區(qū)間[0,1)上的常數(shù);

④ 選擇操作

若Ui,G(i=1,2,…,N)的某個(gè)分量超出預(yù)設(shè)界限,則按如下規(guī)則產(chǎn)生新的對(duì)應(yīng)分量:

(4)

然后依照下面的貪婪法則選擇進(jìn)入下一代的個(gè)體:

(5)

即在Xi,G和Ui,G之間選擇目標(biāo)函數(shù)值更小的進(jìn)入下一代;

⑤ 若滿足終止條件則停止,否則返回步②.標(biāo)準(zhǔn)差分進(jìn)化算法具有強(qiáng)大的全局探索能力,能使種群中的個(gè)體探索到搜索空間的各個(gè)領(lǐng)域,并能有效維護(hù)種群多樣性.但由于其基向量選取的隨機(jī)性,使其比粒子群優(yōu)化算法而言收斂速度慢,不能充分開發(fā)優(yōu)勢個(gè)體.

1.2粒子群優(yōu)化算法

在粒子群算法[13]中,一個(gè)群體包含D維搜索空間中飛行的N個(gè)粒子,第t代第i個(gè)粒子Xi,t=(Xi,1,t,Xi,2,t,…,Xi,D,t)(i=1,2,…,N)表示優(yōu)化問題的一個(gè)候選解,其中Xi,j,t表示第t代群體中第i個(gè)個(gè)體的第j(j=1,2,…,D)維分量.在搜索過程中,粒子的位置由粒子自身達(dá)到的歷史最優(yōu)位置Pi,t=(Pi,1,t,Pi,2,t,…,Pi,D,t)以及截止到目前群體達(dá)到的歷史最優(yōu)位置Pg,t=(Pg,1,t,Pg,2,t,…,Pg,D,t)決定.vi,t=(vi,1,t,vi,2,t,…,vi,D,t) (i=1,2,…,N)表示示第t代群體中第i個(gè)個(gè)體的當(dāng)前速度,下一代種群中第i個(gè)粒子的速度和位置更新公式為

vi,j,t+1=ω·vi,j,t+c1·r1·(Pi,j,t-Xi,j,t)+c2·r2·(Pg,j,t-Xi,j,t)

(6)

Xi,j,t+1=Xi,j,t+vi,j,t+1

(7)

式中：ω為慣性權(quán)重；c1和c2分別為認(rèn)知學(xué)習(xí)參數(shù)和社會(huì)學(xué)習(xí)參數(shù),通常情況下取c1=c2=2，r1和r2是(0,1)上均勻分布的隨機(jī)數(shù).由于大的ω值能促進(jìn)算法的全局搜索,而小的ω使算法具有良好的局部搜索能力[13],所以一般使用如下的線性遞減慣性權(quán)重

ω=ωmax-(ωmax-ωmin)·G/Gmax

(8)

其中ωmax和ωmin分別為慣性權(quán)重的最大值和最小值,通常取ωmax=0.9,ωmin=0.4,使PSO算法在運(yùn)行初期具有優(yōu)良的的全局搜索能力,在運(yùn)行后期具有良好的局部搜索能力,Gmax為最大迭代次數(shù).

由式(6)可以看出,粒子由個(gè)體歷史最優(yōu)和全局歷史最優(yōu)引導(dǎo)飛行,能快速收斂到最優(yōu)點(diǎn)附近.但當(dāng)種群中的全局歷史最優(yōu)是目標(biāo)問題的局部最優(yōu)時(shí),種群中所有粒子都會(huì)飛行到當(dāng)前全局歷史最優(yōu)位置的附近區(qū)域,算法陷入局部最優(yōu).

2混合聚類的粒子群差分進(jìn)化算法

2.1一步K-均值聚類算法

聚類算法[14]能對(duì)種群中個(gè)體進(jìn)行分類,使具有相似性質(zhì)的個(gè)體處于一類中.由于聚類算法計(jì)算量大,所需計(jì)算時(shí)間較長,因此本文采用一步K均值聚類算法來獲取種群的關(guān)鍵信息,其主要步驟為

① 從當(dāng)前種群中隨機(jī)選取K個(gè)個(gè)體作為聚類中心:C1,C2,…,CK

② 當(dāng)下式成立時(shí):

‖Xi-Cj‖=min‖Xi-Cp‖ (j=1,2,…,K,p=1,2,…,K,p≠j)

將種群中的個(gè)體Xi(i=1,2,…,N)分配給聚類中心Cj(j=1,2,…,K),其中‖Xi-Cj‖是Xi和Cj之間的歐幾里德距離;

③ 計(jì)算新的聚類中心:

(9)

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

由1.2節(jié)知,PSO算法容易陷入局部最優(yōu).因此本節(jié)提出基于一步K-均值聚類的粒子群優(yōu)化算法(Clustering-basedParticleSwarmOptimization,CPSO),該算法首先對(duì)當(dāng)前種群采用一步K-均值聚類對(duì)種群中個(gè)體進(jìn)行分類,并計(jì)算每一類的歷史最優(yōu)位置gk,t(k=1,2,…,K),然后對(duì)群體中第i(i=1,2,…,N)個(gè)粒子使用如下的速度更新公式

vi,j,t+1=ω·vi,j,t+c1·r1·(Pi,j,t-Xi,j,t)+c2·r2·(gk,j,t-Xi,j,t)

(10)

其中g(shù)k,j,t表示粒子所屬聚類k的歷史最優(yōu)位置gk,t的第j個(gè)分量.

不像式(6),式(10)使用粒子飛行的歷史最優(yōu)和其所在聚類飛行過的最優(yōu)位置引導(dǎo)粒子速度,能有效避免所有粒子均由全局歷史最優(yōu)引導(dǎo)而產(chǎn)生的早熟收斂,由于聚類算法根據(jù)粒子位置對(duì)粒子進(jìn)行分類,使用K個(gè)不同區(qū)域的歷史最優(yōu)個(gè)體對(duì)種群中的粒子進(jìn)行引導(dǎo)有助于粒子跳出局部最優(yōu)所在區(qū)域,使粒子更快地收斂到全局最優(yōu).

又考慮到隨著進(jìn)化的進(jìn)行,種群中個(gè)體趨于一致,此時(shí)若繼續(xù)使用聚類算法對(duì)種群進(jìn)行聚類操作會(huì)減緩算法收斂,因此當(dāng)式(11)

fitmax-fitmin

(11)

成立時(shí),采用式(6)更新粒子速度,加快算法的收斂速度.其中fitmax和fitmin分別表示當(dāng)前種群最大和最小適應(yīng)度值.

2.3部分種群重置策略

隨著算法的進(jìn)行,種群多樣性會(huì)逐漸降低,種群容易陷入局部最優(yōu),此外種群中較差的個(gè)體對(duì)種群進(jìn)化的貢獻(xiàn)比較小,因此考慮對(duì)種群較差的部分個(gè)體執(zhí)行重置操作,可以達(dá)到維持種群的多樣性的目的,并引導(dǎo)種群走出局部最優(yōu).在滿足不等式(11)的前提下,當(dāng)種群每一代的最優(yōu)值在連續(xù) m代沒有改進(jìn)時(shí),對(duì)種群中較差的λ%的個(gè)體,利用下面的算法對(duì)該部分個(gè)體進(jìn)行重置,步驟如下:

① 依下式計(jì)算每一維度新解的可能范圍:

rj=max(X(best,j)-Xi,j,min,Xi,j,max-

X(best,j))

(12)

式中：rj為新解在第j維元素搜索范圍的半徑；X(best,j)為當(dāng)前種群中最優(yōu)個(gè)體的第j維分量.

② 生成重置個(gè)體:

Xi,j=X(best,j)+rj·yj

(13)

其中Xi,j表示重置新解Xi的第j維分量,yi由以下的Logistic映射[15]得到

yj+1=4·yj·(1-yj)

(14)

③ 當(dāng)Xi,j超出搜索范圍時(shí),使用下式保證新解在搜索范圍內(nèi):

Xi,j=Xi,j,min+Xi,j,max-Xi,j

(15)

不同于文獻(xiàn)[16],這里使用混沌映射來重置新個(gè)體的原因在于混沌映射具有隨機(jī)性、遍歷性和規(guī)律性的特點(diǎn),使重置個(gè)體能夠分散在搜索空間中,達(dá)到維持種群多樣性的目的;同時(shí),重置后的個(gè)體分散在搜索空間的其他區(qū)域,能幫助陷入局部最優(yōu)的粒子逃離局部最優(yōu),從而快速收斂到全局最優(yōu).

2.4混合粒子群差分進(jìn)化算法

鑒于DE算法具有良好的全局探索能力,而CPSO算法又有收斂速度快的特點(diǎn),本文采用自適應(yīng)選擇概率融合DE算法和CPSO算法.

由于算法交替使用DE和CPSO算法,首先采用粒子群優(yōu)化算法的初始化方式,即初始化Xi,G(個(gè)體當(dāng)前位置)和Pi,G(個(gè)體歷史最優(yōu)),以及vi,G(個(gè)體當(dāng)前速度)(i=1,2,…,N);其次使用如下的選擇概率將DE算法和CPSO算法相融合:

p=1-0.5·FES/MaxFES

(16)

其中FES和MaxFES分別為適應(yīng)度評(píng)估次數(shù)和最大適應(yīng)度評(píng)估次數(shù),對(duì)當(dāng)前種群產(chǎn)生(0,1)區(qū)間上均勻分布的隨機(jī)數(shù)r,如果r

由于DE算法每一代均在目標(biāo)向量和試驗(yàn)向量之間進(jìn)行貪婪選擇,其當(dāng)前種群相當(dāng)于粒子群優(yōu)化算法中的個(gè)體歷史最優(yōu)位置集合.使用DE算法時(shí),首先對(duì)種群中的每個(gè)個(gè)體依照下式在給定范圍內(nèi)隨機(jī)選取不同的縮放因子和交叉概率

Fi=Fmin+rand·(Fmax-Fmin)

(17)

CRi=CRmin+rand·(CRmax-CRmin)

(18)

文中算法參考文獻(xiàn)[17]中的取值，即Fmin=0.5,Fmax=0.6,CRmin=0.1,CRmax=0.3,這樣的取值方式有利于保持種群多樣性,減小算法陷入局部最優(yōu)的概率;其次對(duì)目標(biāo)個(gè)體Pi,G執(zhí)行變異和交叉操作生成試驗(yàn)向量Ui,G,則Xi,G=Ui,G,即采用DE算法時(shí),不在Xi,G和其生成的Ui,G之間進(jìn)行貪婪選擇,而是用生成的Ui,G代替?zhèn)€體當(dāng)前位置Xi,G,最后對(duì)當(dāng)前個(gè)體速度采用下式更新:

vi,G+1=Xi,G+1-Xi,G

(19)

該速度更新公式是受粒子群算法速度更新公式(7)的啟發(fā)得到,為方便下一次使用CPSO算法做準(zhǔn)備.

文中算法步驟如下:

① 設(shè)置G=0,FES=0,初始化種群當(dāng)前位置XG,歷史最優(yōu)位置PG,種群飛行速度vG及其他參數(shù);

② 若滿足部分種群重置的條件時(shí),對(duì)較差的部分個(gè)體按照重置策略進(jìn)行重置,并計(jì)算重置后個(gè)體的適應(yīng)度值,種群中其他較好個(gè)體執(zhí)行③,若不滿足重置條件,則對(duì)種群中所有個(gè)體執(zhí)行③;

③ 根據(jù)式(16)選擇要使用的算法,若隨機(jī)數(shù)r

④ 對(duì)種群當(dāng)前個(gè)體Pi,G,使用DE算法產(chǎn)生新的個(gè)體Xi,G+1,并對(duì)每個(gè)個(gè)體的速度進(jìn)行更新,轉(zhuǎn)⑥;

⑤ 對(duì)種群當(dāng)前個(gè)體Xi,G,根據(jù)CPSO算法產(chǎn)生vi,G+1和Xi,G+1;

⑥ 計(jì)算新生成個(gè)體Xi,G+1(i=1,2…,N)的適應(yīng)度值f(Xi,G+1),若f(Xi,G+1)

⑦ 若適應(yīng)度評(píng)估次數(shù)不超過預(yù)設(shè)值,轉(zhuǎn)②,否則輸出最優(yōu)值,算法結(jié)束.

3數(shù)值分析

為測試文中算法的性能,本節(jié)對(duì)9個(gè)具有不同特點(diǎn)的標(biāo)準(zhǔn)測試函數(shù)進(jìn)行數(shù)值試驗(yàn),并與線性遞減慣性權(quán)重的粒子群算法(ParticleSwarmOptimizationwithInertiaWeight,PSO-w)[13]、綜合學(xué)習(xí)的粒子算法(ComprehensiveLearningParticleSwarmOptimization,CLPSO)[8]算法及復(fù)合差分進(jìn)

化算法(CompositeDifferentialEvolution,CoDE)[18]算法進(jìn)行比較,測試函數(shù)見表1.

在表1所列出的8個(gè)測試函數(shù)中,f1～f2為連續(xù)單峰函數(shù),f3是僅有一個(gè)最小值的不連續(xù)階梯函數(shù),f4為嘈雜四次函數(shù),f5～f7為多峰函數(shù)[19],其局部極小的個(gè)數(shù)隨問題維數(shù)的增長呈指數(shù)增長,f8～f9為低維多峰函數(shù),其維數(shù)見表1.

在所有試驗(yàn)中,參數(shù)設(shè)置如下:本文算法中種群規(guī)模N=30,粒子速度的最大值和最小值分別為搜索范圍上下界的0.2倍,m=15,λ=33,對(duì)測試函數(shù)f1～f7,決策變量維數(shù)D=30,f8和f9的維數(shù)如表1數(shù)據(jù)所示.其他算法參數(shù)設(shè)置見對(duì)應(yīng)參考文獻(xiàn),對(duì)于所有算法的終止條件均為適應(yīng)度評(píng)估次數(shù)不超過 次,為公平起見,每個(gè)測試函數(shù)均獨(dú)立運(yùn)行25次.

表1　標(biāo)準(zhǔn)測試函數(shù)表

表2給出了對(duì)比算法和本文算法對(duì)標(biāo)準(zhǔn)測試函數(shù)的優(yōu)化結(jié)果,其中Average表示運(yùn)行結(jié)果的平均最優(yōu)值,Median表示運(yùn)行結(jié)果的中值,Std表示運(yùn)行結(jié)果的標(biāo)準(zhǔn)差.

由表2可以看出,對(duì)測試函數(shù)f3和f8,所有測試函數(shù)在平均值,中值和標(biāo)準(zhǔn)差三方面均達(dá)到了最優(yōu)值;對(duì)其他測試函數(shù)而言,文中算法的優(yōu)化結(jié)果在平均值和中值兩方面均優(yōu)于或等同于其他算法,只有在解決低維多峰函數(shù)f9時(shí)標(biāo)準(zhǔn)差略差于CoDE算法;尤其是對(duì)多峰函數(shù)f6和f7,文中算法能夠快速找到測試函數(shù)的全局最優(yōu)解,同時(shí)標(biāo)準(zhǔn)差也為零,說明文中算法解決多峰問題具優(yōu)良的尋優(yōu)能力，并且穩(wěn)定性更好.

表2　四種算法尋優(yōu)性能比較

為更直觀反映算法的尋優(yōu)性能,圖1～圖4分別給出四種算法對(duì)測試函數(shù)f2、f4、f5和f7的優(yōu)化性能曲線.

圖1　函數(shù)f2進(jìn)化曲線圖

從圖1可以看出,在處理單峰函數(shù)問題時(shí),本文算法具有較快收斂速度;圖2說明本文算法在解決嘈雜問題時(shí),也能以較快的速度收斂到全局最優(yōu)值點(diǎn)附近,圖3表明文中算法與CoDE算法具有同等尋優(yōu)能力，但文中算法優(yōu)于PSO-W和CLPSO，圖4表明本文算法在解決多峰函數(shù)問題時(shí),能有效跳出局部最優(yōu),快速收斂到全局最優(yōu),這是由于在算法初期使用不同區(qū)域的最優(yōu)個(gè)體引導(dǎo)種群進(jìn)化,后期又對(duì)種群中較差的個(gè)體實(shí)施重置操作,維持了種群的多樣性,有效避免算法陷入局部最優(yōu),使算法更快地收斂到全局最優(yōu).

總之,從表1以及圖1～4的仿真結(jié)果可以看出,與其他三種先進(jìn)進(jìn)化算法相比,本文算法能有效避免早熟收斂,快速收斂到問題的全局最優(yōu),并且魯棒性更好.

圖2　函數(shù)f4進(jìn)化曲線圖

圖3　函數(shù)f5進(jìn)化曲線圖

圖4　函數(shù)f7進(jìn)化曲線圖

4結(jié) 論

1) 為解決差分進(jìn)化算法收斂速度慢和容易陷入局部最優(yōu)的問題,設(shè)計(jì)了一種混合聚類的粒子群差分進(jìn)化算法.運(yùn)用一步K-均值聚類算法改進(jìn)了粒子群優(yōu)化算法的速度更新,將改進(jìn)后的粒子群優(yōu)化算法融合到差分進(jìn)化算法中,在種群多樣性較差時(shí)采用部分種群重置策略.

2) 改進(jìn)后的算法有效發(fā)揮了差分進(jìn)化算法和粒子群優(yōu)化算法各自的優(yōu)勢,權(quán)衡了算法的全局探索能力和局部開發(fā)能力,賦予了種群中個(gè)體逃離局部最優(yōu)的能力.

3) 在9個(gè)標(biāo)準(zhǔn)測試函數(shù)的數(shù)值仿真結(jié)果表明:改進(jìn)后的算法在解決單峰函數(shù)、嘈雜函數(shù)以及多峰函數(shù)時(shí)均表現(xiàn)出良好的性能,算法的收斂速度也大大提高.

參 考 文 獻(xiàn)：

[1]KANARACHOS A,KOULOCHERIS D,VRAZOPOULOS H.Evolutionary Algorithms with Deterministic Mutation Operators used for the Optimization of the Trajectory of a Four-bar Mechanism[J].Mathematics and Computers in Simulation,2003,63:483.

[2]FUJIWARA Y,SAWAI H.Evolutionary Computation Applied to Mesh Optimization of a 3-D Facial Image[J].IEEE Transactions on Evolutionary Computation,1999,3(2):113.

[3]STORN R,PRICE K.Differential Evolution-A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Space[R].International Computer Science Institute,Berkeley,1995.

[4]KENNEDY J,EBERHART R C.Particle Swarm Optimization[C]//Proceedings of IEEE International Conference on Neural Networks,Piscataway:IEEE Press,1995:1942.

[5]趙艷麗.差分進(jìn)化算法在圖像處理中的應(yīng)用研究[D].東營:中國石油大學(xué),2010.

ZHAO Yanli.Research on the Application of Differential Evolution in Image Processing[D].Dongying:College of Computer & Communication Engineering China University of Petroleum,2010.(in Chinese)

[6]PEDRO F,JOAO S,ZITA V,et al.Modified Particle Swarm Optimization Applied to Integrated Demand Response and DG Resources[J].IEEE Transaction on Smart Grid,2013,4(1):606.

[7]湯小為,唐俊,萬爽,等.改進(jìn)變異策略的自適應(yīng)差分進(jìn)化算法及其應(yīng)用[J].宇航學(xué)報(bào),2013,34(7):1001.

TANG Xiaowei,TANG Jun,WAN Shuang,et al.Adaptive Differential Evolution Algorithm with Modified Mutation Strategy and Its Application.[J].Journal of Astronautics,2013,34(7):1001.(in Chinese)

[8]LIANG J J,QIN A K,SUGANTHAN P N,et al.Comprehensive Learning Particle Swarm Optimizer for Global Optimization of Multimodal Function[J].IEEE Transaction on Evolutionary Computation,2006,10(3):281.

[9]欒麗君,譚立靜,牛奔.一種基于粒子群優(yōu)化算法和差分進(jìn)化算法的新型混合全局優(yōu)化算法[J].信息與控制,2007,36(6):708.

LUAN Lijun,TAN Lijing,NIU Ben.A Novel Hybrid Global Optimization Algorithm Based on Particle Swarm Optimization and Differential Evolution[J].Information and Control,2007,36(6):708.

(in Chinese)

[10]劉建平.基于混沌和差分進(jìn)化的混合粒子群優(yōu)化算法[J].計(jì)算機(jī)仿真,2012,29(2):208.

LIU Jianping.Hybrid Particle Swarm Optimization Algorithm Based on Chaos and Differential Evolution[J].Computer Simulation,2012,29(2):208.

(in Chinese)

[11]段玉紅,高岳林.基于差分演化的粒子群算法[J].計(jì)算機(jī)仿真,2009,26(6):212.

DUAN Yuhong,GAO Yuelin.A Particle Swarm Optimization Algorithm Based on Differential Evolution[J].Computer Simulation,2009,26(6):212.

(in Chinese)

[12]DAS S,ABRAHAM A,CHAKRABORTY U K,et al.Differential Evolution Using a Neighborhood-based Mutation Operator[J].IEEE Transation on Evolutionary Computation,2009,13(3):526.

[13]SHI Y,EBERHART R C.Parameter Selection in Particle Swarm Optimization[C]//International Conference on Evolutionary Programming VII,London:Springer-verlag,1998:591.

[14]CAI Zhihua,GONG Wenyin,LING C X,et al.A Clustering-based Differential Evolution for Global Optimization[J].Applied Soft Computing,2011,11:1363.

[15]匡芳君,張思揚(yáng),金鐘,等.混沌差分進(jìn)化粒子群協(xié)同優(yōu)化算法[J].微電子學(xué)與計(jì)算機(jī),2014,31(8):29.

KUANG Fangjun,ZHANG Siyang,JIN Zhong,et al.Chaotic Differential Evolution Particle Swarm Cooperative Optimization Algorithm[J].Microelectronics & Computer,2014,31(8):29.(in Chinese)

[16]DONG L,JIE C,BIN X.A Novel Differential Evolution Algorithm with Gaussian Mutation that Balances Exploration and Expoitation[C]//IEEE Symposium on Differential Evolution,Singapore:IEEE,2013:18.

[17]WANG Yong,CAI Zixing.Combining Multiobjective Optimization with Differential Evolution to Solve Constrained Optimization Problems[J].IEEE Transactions on Evolutionary Computation,2012,16(1):117.

[18]WANG Yong,CAI Zixing,ZHANG Qingfu.Differential Evolution with Composite Trial Vector Generation Strategies and Control Parameters[J].IEEE Transactions on Evolutionary Computation,2011,15(1):55.

[19]SHANG Yunwei,QIU Yuhuang.A Note on the Extended Rosenbrock Function[J].Evolutionary Computation,2006,14(1):119.

(責(zé)任編輯、校對(duì)張立新)

A Hybrid Clustering Particle Swarm and Differential Evolution Algorithm

LIU Yang,GAO Xingbao,LIU Rui

(School of Mathematics and Information Science,Shaanxi Normal University,Xi’an 710062,China)

Abstract:A hybrid differential evolution algorithm is introduced because the basic differential evolution algorithm has disadvantages of low convergence speed and local optimum.Firstly,K-means cluster algrithm was used to modify the velocity updating formula of the particle swarm optimization algorithm.Then the modified particle swarm optimization algorithm was combined with the differential evolution algorithm by means of a linear decreasing selective probability.Finally some individuals with poor performance were reset under certain conditions.Numerical experiments on nine typical benchmark functions illustrate that the proposed algorithm is fast in convergence speed,strong in search ability and good in robustness.

Key words:K-means clusters;hybrid algorithms;differential evolution;particle swarm optimization;population reset

DOI:10.16185/j.jxatu.edu.cn.2016.05.003

收稿日期：2015-10-14

基金資助：國家自然科學(xué)基金(61273311;61173094)

作者簡介：劉陽(1990-),女,陜西師范大學(xué)碩士研究生. 通訊作者：高興寶(1966-),男,陜西師范大學(xué)教授,主要研究方向?yàn)樽顑?yōu)化理論與方法、智能計(jì)算、神經(jīng)網(wǎng)絡(luò)等.E-mail:xinbaog@snnu.edu.cn.

文獻(xiàn)標(biāo)志碼:中圖號(hào)：TP301.6A

文章編號(hào)：1673-9965(2016)05-0357-08