混沌動(dòng)態(tài)改變權(quán)值策略的粒子群優(yōu)化算法

孟 倩

(江蘇師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116)

0 引言

粒子群優(yōu)化(particle swarm optimization，PSO)算法是一種進(jìn)化優(yōu)化算法，由Kennedy等[1]于1995年首次提出.PSO算法中可控制粒子速度的慣性權(quán)值(w)是一個(gè)非常重要的參數(shù)，可以調(diào)整算法的局部開(kāi)發(fā)和全局探測(cè)能力[2].PSO算法簡(jiǎn)單、容易實(shí)現(xiàn)，收斂速度快，容易與其他算法結(jié)合，具有深刻的智能背景，既適合科學(xué)研究，又特別適合工程應(yīng)用[3].但是，標(biāo)準(zhǔn)PSO算法的一個(gè)缺點(diǎn)是粒子的飛行速度大小影響著算法的全局收斂性，不能保證PSO算法收斂于函數(shù)的全局極值點(diǎn)[3-4];另一個(gè)缺點(diǎn)是PSO算法容易“早熟收斂”，即參數(shù)選擇不當(dāng)時(shí)，尋優(yōu)過(guò)程中可能會(huì)迅速喪失粒子群體多樣性[5].為解決這些問(wèn)題，學(xué)者們提出了很多有效的改進(jìn)算法,如慣性權(quán)重線性調(diào)整策略(linearly decreased inertia weight,LDIW)[2]、慣性權(quán)重非線性調(diào)整策略(nonlinear deceased inertia weight,NDIW)[6]、凹函數(shù)遞減策略(concave function inertia weight,CFIW)[3]、指數(shù)曲線遞減策略(exponential curve inertia weight,ECIW)[3]、粒距反饋S函數(shù)粒子群權(quán)值調(diào)整策略[7]、混沌搜索策略[8-9]、動(dòng)態(tài)調(diào)節(jié)慣性權(quán)重策略[10-11]及自適應(yīng)動(dòng)態(tài)非線性改變權(quán)值策略[12-13]等.本文借鑒已有文獻(xiàn)思想，提出一種基于混沌和動(dòng)態(tài)改變權(quán)值策略(chaos dynamically changing inertia weight,CDCIW)的改進(jìn)粒子群算法，并通過(guò)基準(zhǔn)測(cè)試函數(shù)來(lái)驗(yàn)證算法的有效性和可行性.

1 基本粒子群算法

在粒子群優(yōu)化算法[14]中，優(yōu)化問(wèn)題的每個(gè)解與搜索空間的一個(gè)粒子相對(duì)應(yīng)，每個(gè)粒子是一個(gè)個(gè)體，由位置矢量和速度矢量組成.粒子在運(yùn)動(dòng)中產(chǎn)生的最優(yōu)位置為

pi=(pi1,pi2,…,piD),i=1,2,…,m，

(1)

式中：m為粒子的個(gè)數(shù)，D為粒子的維數(shù).

第i個(gè)粒子的D維位置矢量為xi=(xi1,xi2,…,xiD)，速度矢量為vi=(vi1,vi2,…,viD)，二者分別決定了第i個(gè)粒子飛行的位置和方向；整個(gè)粒子群歷史搜索到的最優(yōu)位置為pg=(pg1,pg2,…,pgD)，其中g(shù)∈{1,2，…,m}為粒子編號(hào).粒子群初始化后，對(duì)每個(gè)粒子計(jì)算其適應(yīng)值，通過(guò)迭代搜索最優(yōu)解.每個(gè)粒子根據(jù)

vi(k+1)=wvi(k)+c1r1(pi(k)-xi(k))

+c2r2(pg(k)-xi(k)),

(2)

xi(k+1)=xi(k)+vi(k+1)

(3)

來(lái)更新自己的速度和位置.式中：k為迭代次數(shù)；w為慣性權(quán)重；r1,r2為[0,1]之間的隨機(jī)數(shù)；c1,c2為學(xué)習(xí)因子，取值范圍一般在[0,4]之間.

2 改進(jìn)的粒子群優(yōu)化算法

本文提出一種改進(jìn)的粒子群優(yōu)化(improved particle swarm optimization,IPSO)算法，改進(jìn)部分主要表現(xiàn)在以下2個(gè)方面：

1)為了有利于粒子進(jìn)行全局搜索和局部搜索，提出一種基于粒距的動(dòng)態(tài)改變權(quán)值w的策略；

2)為了增加粒子多樣性，避免粒子群在優(yōu)化后期陷入局部最優(yōu)解，引入混沌映射.

2.1 基于粒距的動(dòng)態(tài)改變權(quán)值策略

在相關(guān)研究成果[2-3,7-9]的基礎(chǔ)上，提出一種基于粒子距整個(gè)種群的歷史最優(yōu)位置的距離(簡(jiǎn)稱粒距)來(lái)動(dòng)態(tài)改變權(quán)值策略.在該策略下，慣性權(quán)重的計(jì)算公式為

w=wmin(wmax/wmin)1/(1+ε·k/kmax),

(4)

式中ε為由粒距決定的權(quán)值調(diào)節(jié)因子.

第k次迭代,第i個(gè)粒子的粒距定義為

(5)

式中：xij(k)為第k次迭代時(shí)第i個(gè)粒子的位置向量的第j個(gè)分量；pgj(k)為第k次迭代時(shí)，種群歷史最優(yōu)位置向量的第j個(gè)分量.

根據(jù)每個(gè)粒子的粒距選擇ε值來(lái)控制粒子速度,公式為

(6)

式中：εmax和εmin分別表示ε的最大值和最小值，文中分別取15和8；dmax和dmin分別表示最大和最小粒距.粒距di(k)越大，ε就會(huì)越小，該粒子的慣性權(quán)重就會(huì)越大，粒子速度就越大，有利于粒子進(jìn)行全局搜索；反之，di(k)越小，ε就會(huì)越大，慣性權(quán)重就會(huì)越小，粒子速度就越小，有利于粒子進(jìn)行局部搜索.權(quán)值w隨ε的變化趨勢(shì)如圖1所示.

圖1 不同ε取值的慣性權(quán)重變化曲線

2.2 引入混沌映射

基于粒距調(diào)整粒子群慣性權(quán)值策略可以增強(qiáng)粒子的搜索能力，但到了進(jìn)化后期，如果整個(gè)粒子群密集地聚集在一起，粒子多樣性消失，有序性增強(qiáng)，粒子飛行速度越來(lái)越慢，整個(gè)粒子群停滯不前，則仍然可能發(fā)生早熟收斂，陷入局部最優(yōu)解[15].因此，為了避免陷入局部最優(yōu)解，使種群保持多樣性，增加粒子混亂度，本文引入混沌算法,提出基于混沌和粒距的動(dòng)態(tài)改變權(quán)值策略(CDCIW).

混沌遍歷性特點(diǎn)可被用來(lái)進(jìn)行優(yōu)化搜索，且能避免陷入局部極值.本文將混沌算法與粒子群算法結(jié)合，利用混沌算法來(lái)增強(qiáng)全局搜索能力，以提高算法搜索的精度.常用的混沌規(guī)則有Logistic map、Henon map以及tent map等[16].研究表明，Lozi映射的混沌方法比常用的Logistic映射混沌方法具有求解精度高及效率高等優(yōu)點(diǎn)[16].本文選取二維間斷離散混沌動(dòng)力系統(tǒng)Lozi方程[16]

ln=1-a|ln-1|+yn-1，

(7)

yn=bln-1，

(8)

式中：n為迭代次數(shù)，ln∈[0,1]為混沌變量;參數(shù)a>1.5后進(jìn)入混沌運(yùn)動(dòng)(常取1.7)，b常取0.5.

3 IPSO算法

設(shè)f(xi)為優(yōu)化目標(biāo)函數(shù)：

minf(x1,x2,…,xn)，xi∈(ai,bi).

(9)

IPSO算法如下：

步驟1粒子初始化.設(shè)置PSO參數(shù)，包括粒子群體大小N(N過(guò)小，容易陷入局部最優(yōu)解，N過(guò)大容易導(dǎo)致算法運(yùn)行時(shí)間過(guò)長(zhǎng)，一般取20～40)，粒子維度D，加速因子c1和c2等.

步驟2隨機(jī)產(chǎn)生種群，初始化粒子速度和位置，初始化每個(gè)粒子歷史最優(yōu)位置(pbest)和所有粒子的最優(yōu)位置(gbest).

步驟3計(jì)算每個(gè)粒子的適應(yīng)度函數(shù)值.如果當(dāng)前粒子適應(yīng)度值優(yōu)于pbest對(duì)應(yīng)的適應(yīng)度值，則將pbest更新為當(dāng)前粒子位置.

步驟4對(duì)每一個(gè)粒子，如其當(dāng)前位置的適應(yīng)度值優(yōu)于全局gbest對(duì)應(yīng)的適應(yīng)度值，則將gbest更新為該粒子的當(dāng)前位置.

步驟5按照本文提出的基于粒距動(dòng)態(tài)改變權(quán)值策略，由公式(4)—(6)計(jì)算慣性權(quán)重w值.

步驟6按照公式(2)和(3)對(duì)每個(gè)粒子的速度和位置進(jìn)行更新.

步驟7對(duì)最優(yōu)位置pg=(pg1,pg2,…,pgD)進(jìn)行混沌優(yōu)化.

1)通過(guò)

li=(pgi-ai)/(bi-ai),i=1,2,…,D,

(10)

將pgi(i=1,2,…,D)映射到[0,1]上.

3)通過(guò)

(11)

對(duì)混沌序列作逆映射，使其回原解空間，從而得到一個(gè)混沌變量可行解序列

(12)

4)計(jì)算可行解矢量的適應(yīng)度值，并保留適應(yīng)度值最優(yōu)時(shí)對(duì)應(yīng)的可行解，記為p*.

5)從當(dāng)前粒子群中隨機(jī)選擇一個(gè)粒子的位置，用p*代替.

步驟8如果滿足迭代停止條件，停止搜索，輸出結(jié)果，否則跳到步驟3.

4 試驗(yàn)結(jié)果

采用3個(gè)標(biāo)準(zhǔn)函數(shù)來(lái)測(cè)試本文提出的IPSO算法的尋優(yōu)性能，并與基于LDIW、CFIW、NDIW和ECIW慣性權(quán)值策略的粒子群算法LDIWPSO、CFIWPSO、NDIWPSO和ECIWPSO做比較.3個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的全局最小值都為0，各PSO算法中粒子數(shù)均取30，c1=c2=2，迭代結(jié)束條件為迭代次數(shù)超過(guò)2 000.為了考察算法的可擴(kuò)展性，對(duì)每個(gè)測(cè)試函數(shù)分別取10維和30維進(jìn)行試驗(yàn).

1)函數(shù)f1(Ackley function):

minf1(x)=f(0,0,…,0)=0.

它是一個(gè)具有大量局部最優(yōu)點(diǎn)的多峰函數(shù)，xi=0時(shí)達(dá)到全局極小點(diǎn)0.2維Ackley函數(shù)圖像見(jiàn)圖2.表1為10、30維時(shí)，每種方案獨(dú)立運(yùn)行30次，5種算法求解的全局最優(yōu)適用度平均值(表中簡(jiǎn)稱平均最優(yōu)值,下同)和標(biāo)準(zhǔn)差，以此作為性能比較的依據(jù).當(dāng)n=30時(shí)，Ackyley函數(shù)最優(yōu)適應(yīng)值隨迭代次數(shù)變化曲線見(jiàn)圖3.

圖2 Ackyley函數(shù)圖像

表1 Ackyley函數(shù)平均最優(yōu)值與標(biāo)準(zhǔn)差

圖3 Ackyley函數(shù)最優(yōu)適應(yīng)值隨迭代次數(shù)變化曲線(n=30)

2)函數(shù)f2(Rosenbrock function):

minf2(x)=f(1,1,…,1)=0.

它是一個(gè)全局最小值位于一個(gè)非常狹窄的山谷中的非凸的二次函數(shù).由于該函數(shù)解空間有相當(dāng)多的狹窄通道，所以收斂到全局極小點(diǎn)是非常困難的.圖4描繪了n=2時(shí)的Rosenbrock函數(shù)圖像，表2為10、30維時(shí)，每種方案獨(dú)立運(yùn)行30次，5種算法求解的全局最優(yōu)適用度平均值和標(biāo)準(zhǔn)差，以此作為性能比較的依據(jù).當(dāng)n=30時(shí)，Rosenbrock函數(shù)最優(yōu)適應(yīng)值隨迭代次數(shù)變化的曲線如圖5所示.

圖4 Rosenbrock函數(shù)圖像

圖5 Rosenbrock函數(shù)最優(yōu)適應(yīng)值隨迭代次數(shù)變化曲線(n=30)

表2 Rosenbrock函數(shù)平均最優(yōu)值與標(biāo)準(zhǔn)差

3)函數(shù)f3(Rastrigin function)：

xi∈(-5.12,5.12)，

minf3(x)=f(0,0,…,0)=0.

它是一個(gè)具有很多局部最小值點(diǎn)和局部最大值點(diǎn)的多峰函數(shù)，在點(diǎn)xi=(0,0,…,0)處獲得全局最優(yōu)值0.優(yōu)化算法很容易陷入局部極點(diǎn)而不能得到全局最優(yōu)解.2維Rastrigin函數(shù)圖像如圖6所示.表3為10、30維時(shí)，每種方案獨(dú)立運(yùn)行30次，5種算法求解的全局最優(yōu)適用度平均值和標(biāo)準(zhǔn)差，以此作為性能比較的依據(jù).當(dāng)n=30時(shí)，Rastrigin函數(shù)最優(yōu)適應(yīng)值隨迭代次數(shù)變化曲線如圖7所示.

圖6 Rastrigin函數(shù)圖像

圖7 Rastrigin函數(shù)最優(yōu)適應(yīng)值隨迭代次數(shù)變化曲線(n=30)

表3 Rastrigin函數(shù)平均最優(yōu)值與標(biāo)準(zhǔn)差

從表1—3和圖3、5、7中可以看出，本文提出的IPSO算法在3個(gè)測(cè)試函數(shù)上的表現(xiàn)普遍優(yōu)于其他算法，其平均最優(yōu)適應(yīng)值都最小，因此,IPSO算法比其他4種PSO算法精度更高，更穩(wěn)定.當(dāng)增加到30維后，雖然IPSO算法精度丟失較大，但仍優(yōu)于其他算法，而且標(biāo)準(zhǔn)差最小，即結(jié)果較為穩(wěn)定.這是由于IPSO算法慣性權(quán)重選擇較為恰當(dāng)，且引入混沌運(yùn)算，使種群更加多樣化，增強(qiáng)了PSO算法擺脫局部極值點(diǎn)的能力，從而提高了算法的全局搜索能力和精度.LDIWPSO、CFIWPSO、NDIWPSO 3種算法性能較為接近，優(yōu)化結(jié)果都不太理想;ECIWPSO算法性能雖低于IPSO算法，但也較為理想，優(yōu)于其他3種算法.

5 結(jié)論

本文提出了一種基于混沌和粒距的動(dòng)態(tài)改變權(quán)值策略的改進(jìn)的粒子群優(yōu)化算法：根據(jù)粒距在每次迭代動(dòng)態(tài)改變權(quán)值，有助于避免陷入局部最優(yōu)解；為了增加粒子的多樣性，引入混沌優(yōu)化思想.本文算法可有效改善粒子群算法擺脫局部極值點(diǎn)的能力，從而提高粒子群算法的尋優(yōu)能力和精度.在Ackley、Rosenbrock、Rastrigin 3個(gè)基準(zhǔn)測(cè)試函數(shù)上仿真，結(jié)果表明，本文算法對(duì)于多極值點(diǎn)的高維復(fù)雜函數(shù)，能夠獲得精度較高的全局極值，其精度明顯優(yōu)于作比較的其他粒子群優(yōu)化算法.