基于交叉熵的粒子群優(yōu)化算法

張 娜,賀興時(shí),屈思凡

(西安工程大學(xué) 理學(xué)院,陜西 西安 710048)

0 引 言

粒子群優(yōu)化算法(particle swarm optimization, PSO)是Eberhart和Kennedy在1995年基于對(duì)鳥(niǎo)群覓食行為的研究,提出的一種解決最優(yōu)化問(wèn)題的群體智能算法[1]。粒子群優(yōu)化算法結(jié)構(gòu)清晰,沒(méi)有過(guò)多約束條件,適合大規(guī)模計(jì)算。因此，該算法一經(jīng)提出就倍受推崇且已經(jīng)成功應(yīng)用于諸多領(lǐng)域。隨著科學(xué)技術(shù)的發(fā)展,人們?cè)诼窂揭?guī)劃[2]、圖像分割[3]、神經(jīng)網(wǎng)絡(luò)[4-5]、數(shù)據(jù)預(yù)測(cè)[6]、噪聲控制[7]等領(lǐng)域面臨的優(yōu)化問(wèn)題愈發(fā)復(fù)雜。傳統(tǒng)的粒子群優(yōu)化算法,容易陷入到局部極小點(diǎn)，存在“早熟收斂”現(xiàn)象,且對(duì)于高維復(fù)雜的多模態(tài)函數(shù)求解無(wú)法滿(mǎn)足實(shí)際的需求。

為提高算法性能,許多學(xué)者提出了不同的改進(jìn)方法。目前對(duì)于算法的改進(jìn)主要從3個(gè)方面進(jìn)行：

1) 參數(shù)設(shè)置：如學(xué)習(xí)因子調(diào)整、慣性權(quán)重調(diào)節(jié)、公式調(diào)整等。郭巳秋等建立了新的慣性權(quán)重調(diào)節(jié)機(jī)制,根據(jù)進(jìn)化中每個(gè)粒子的狀態(tài)調(diào)整慣性權(quán)重,提高了算法的收斂效率,增強(qiáng)了算法的魯棒性[8];趙乃剛在二階震蕩粒子群算法的基礎(chǔ)上,省略速度更新公式并將迭代公式降為一階,既保障了算法收斂精度又提升了搜索速度[9]。

2) 將混合策略引入到基本的粒子群優(yōu)化算法：Mojarrad等為擴(kuò)大種群多樣性，采用混沌映射初始化粒子群優(yōu)化算法[10];劉召軍將自適應(yīng)混沌列入差分進(jìn)化算法，進(jìn)而融合到粒子群優(yōu)化算法中、搜索能力和算法的求解精度及效率[11]。

3) 將其他的智能優(yōu)化算法與標(biāo)準(zhǔn)粒子群優(yōu)化算法結(jié)合：為提高算法的全局尋優(yōu)能力和收斂速度,Chen等在粒子群算法中引入魚(yú)群算法[12];Garg在粒子群優(yōu)化算法中融入遺傳算法中的選擇機(jī)制,改進(jìn)后的算法對(duì)高維復(fù)雜函數(shù)優(yōu)化問(wèn)題，尋優(yōu)效果較為顯著[13]。

目前,不同的改進(jìn)方法對(duì)于粒子群優(yōu)化算法的整體性能在不同程度上均有所提高，但仍未能徹底解決粒子群優(yōu)化算法對(duì)高維復(fù)雜函數(shù)尋優(yōu)能力不佳,易陷入局部最優(yōu)的問(wèn)題。針對(duì)這一問(wèn)題,本文從引入其他智能算法和混合策略入手,通過(guò)引入具有良好全局優(yōu)化能力、自適應(yīng)性以及魯棒性的交叉熵算法,以增強(qiáng)算法的尋優(yōu)能力。隨后，采用粒子重構(gòu)策略擴(kuò)大種群的搜索范圍,避免早熟收斂。

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

1.1 算法介紹

將鳥(niǎo)群中的每一只鳥(niǎo)抽象為一個(gè)“粒子”,位于n維搜索空間中的每個(gè)粒子都是潛在的最優(yōu)解。其中第i個(gè)粒子的位置為Xi=(xi1,xi2,…,xin),速度為Vi=(vi1,vi2,…vin)。每個(gè)粒子的適應(yīng)度值都可以用目標(biāo)函數(shù)和粒子位置確定。PSO算法根據(jù)粒子自身或者同伴的歷史最優(yōu)位置,通過(guò)更新公式迭代調(diào)整粒子位置以尋求最優(yōu)解。Clerc等將壓縮因子引入速度更新公式,速度和位置更新公式[14]為

(1)

(2)

式(1)、(2)中：Pb和Gb分別表示當(dāng)前個(gè)體最優(yōu)位置和全局最優(yōu)位置;w是慣性權(quán)重;r1,r2是區(qū)間[0,1]的隨機(jī)數(shù),用于維持種群多樣性;c1,c2是學(xué)習(xí)因子,分別代表認(rèn)知因子和社會(huì)因子;K表示壓縮因子,通常取0.729。

1.2 參數(shù)調(diào)整

慣性權(quán)重用于衡量粒子的上一迭代速度對(duì)當(dāng)前速度的影響。選擇了Chatterjee等提出的慣性權(quán)重非線(xiàn)性遞減策略[15],并指出m=1.2時(shí)算法性能最優(yōu),其中w表示為

(3)

式中：wmin為最小值，通常取0.4；wmax為最大值，通常取0.9；T為最大迭代次數(shù)；t表示當(dāng)前迭代次數(shù)；m是冪級(jí)數(shù)。

學(xué)習(xí)因子是體現(xiàn)粒子學(xué)習(xí)能力的參數(shù),分別表示粒子向個(gè)體與全局歷史最優(yōu)位置的學(xué)習(xí)能力。張健等提出一種結(jié)合慣性權(quán)重遞減與約束因子方法的PSO算法[16],在假設(shè)c1=c2的前提下，提出c1,c2取值隨慣性權(quán)重變化而變化的函數(shù)式。結(jié)合文獻(xiàn)[14]對(duì)因子取值的建議，即(c1+c2)/2=1.494 45,將學(xué)習(xí)因子調(diào)整為

(4)

1.3 粒子重構(gòu)

1.3.1 替換概率 粒子重構(gòu)通過(guò)以一定概率替換進(jìn)化能力較弱的粒子實(shí)現(xiàn),替換概率是衡量進(jìn)化能力弱的粒子是否被替換的標(biāo)準(zhǔn)。采用粒子適應(yīng)度值的好壞度量替換概率,如式(5)所示:

(5)

1.3.2 重構(gòu)流程 在算法進(jìn)化過(guò)程中,粒子的進(jìn)化能力各不相同。選擇進(jìn)化能力較好的粒子,根據(jù)式(6)對(duì)其添加高斯擾動(dòng)生成新粒子：

(6)

采用高斯擾動(dòng)后的位置作為替換目標(biāo)進(jìn)行粒子重構(gòu),以避免迭代后期種群多樣性降低而導(dǎo)致早熟收斂。粒子重構(gòu)的基本步驟如下:

1) 排序。計(jì)算每個(gè)粒子對(duì)應(yīng)的適應(yīng)度值并得到適應(yīng)度值序列,將該序列中的元素從小到大排序得到新的矩陣序列。

2) 選擇。計(jì)算該序列的(1-q)分位數(shù),分位數(shù)之前的p個(gè)粒子為進(jìn)化能力強(qiáng)的粒子,末尾的p1(其中p1=N-p)個(gè)進(jìn)化能力較弱的粒子為待替換的粒子。

3) 替換。在第t次迭代中,依次對(duì)進(jìn)化能力較弱的p1個(gè)粒子進(jìn)行替換。根據(jù)式(5)計(jì)算第i個(gè)粒子的替換概率,并根據(jù)式(6)對(duì)該粒子的各個(gè)維度進(jìn)行替換,生成新的粒子。

4) 合并。將新生成的粒子與進(jìn)化能力較強(qiáng)p個(gè)的粒子合并,構(gòu)成新的粒子。

2 交叉熵算法

交叉熵(cross entropy,CE)方法[18-19]是1997年由 Rubinstein等提出的一種可靠性分析與隨機(jī)優(yōu)化設(shè)計(jì)的統(tǒng)一方法,其本質(zhì)是將最優(yōu)化問(wèn)題轉(zhuǎn)化為某一小概率事件估計(jì)問(wèn)題。

設(shè)χ上的一個(gè)概率密度函數(shù)族為{h(..,v),v∈ν},將最小化問(wèn)題轉(zhuǎn)化為研究f(x)比給定實(shí)數(shù)γ小的概率問(wèn)題,即

l=Pu(f(x)≤γ)=Eu(I{f(x)≤γ})

(7)

設(shè)X是依據(jù)概率密度h(..;u)產(chǎn)生的隨機(jī)樣本,Eu表示相應(yīng)的期望。通過(guò)構(gòu)造參數(shù)序列{vt,t≥0}和級(jí)別序列{γt,t≥0},同時(shí)更新迭代vt,γt,基本步驟如下:

2) 設(shè)置參數(shù)。包括設(shè)置最大迭代次數(shù)T、隨機(jī)樣本個(gè)數(shù)N、分位數(shù)系數(shù)ρ0、平滑常數(shù)β,初始迭代次數(shù)t=0。

4) 排序。計(jì)算每個(gè)樣本對(duì)應(yīng)的適應(yīng)度值并得到適應(yīng)度函數(shù)值序列；將該序列中的元素從小到大排序,得到新的矩陣序列；計(jì)算該序列的(1-ρ0)分位數(shù)γt。

(8)

式中：L=1，2，…,n。

6) 平滑。

μL=βμL,t+(1-β)μL,t-1

7) 停止。滿(mǎn)足到達(dá)最大迭代次數(shù)后停止迭代,否則返回重新執(zhí)行1)～6)。

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

基于交叉熵的粒子群優(yōu)化算法,基本執(zhí)行過(guò)程為：在每次迭代中先用交叉熵算法產(chǎn)生全局最優(yōu)的替代值,然后引入粒子重構(gòu)策略,通過(guò)替換進(jìn)化能力弱的粒子構(gòu)造新的粒子?；玖鞒倘鐖D1所示。

圖 1 CEPSO算法流程圖

1) 隨機(jī)產(chǎn)生初值,設(shè)置參數(shù)，初始化參數(shù)w,c1,c2，T,N,n等。

2) 計(jì)算初始種群每一個(gè)維度的均值、方差作為交叉熵算法的初始參數(shù)。

5) 選擇適應(yīng)度值差的粒子進(jìn)行重構(gòu)。

6) 根據(jù)式(1)和(2)更新粒子的速度與位置。

7) 根據(jù)式(3)、(4)更新粒子i在第t+1代的慣性權(quán)重及學(xué)習(xí)因子。

8) 如果達(dá)到最大迭代次數(shù),立即停止迭代并輸出最優(yōu)解,否則返回3)。

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

為了驗(yàn)證CEPSO算法的性能,選取了8個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)[20],對(duì)本文算法(CEPSO)、粒子群優(yōu)化算法(PSO)、基于模擬退火的粒子群優(yōu)化算法(SAPSO)、改進(jìn)的粒子群優(yōu)化目標(biāo)跟蹤算法(OTPSO)、采用粒子群優(yōu)化的自適應(yīng)樣條擬合算法(SPSO)等5種算法進(jìn)行仿真對(duì)比。

4.1 參數(shù)設(shè)置

算法的參數(shù)均依據(jù)原始參數(shù)設(shè)置,5種算法的參數(shù)設(shè)置如表1所示。本次實(shí)驗(yàn)對(duì)5個(gè)算法設(shè)置相同的種群規(guī)模和最大迭代次數(shù),以確保實(shí)驗(yàn)結(jié)果的有效性。在SPSO算法中c表示學(xué)習(xí)因子,w表示速度慣性,k表示除自身之外的鄰域個(gè)數(shù)。

表 1 參數(shù)設(shè)置

4.2 測(cè)試函數(shù)

選取了表2所示的8個(gè)不同標(biāo)準(zhǔn)測(cè)試函數(shù)。為驗(yàn)證算法對(duì)復(fù)雜多模態(tài)函數(shù)的求解能力,選取了5個(gè)高維多峰函數(shù)F1～F5,用于測(cè)試算法跳出局部最優(yōu)值的能力；3個(gè)高維單峰函數(shù)F6～F8，用于檢測(cè)算法收斂性能。

表 2 測(cè)試函數(shù)

4.3 結(jié)果分析

采用8種標(biāo)準(zhǔn)測(cè)試函數(shù)對(duì)5種算法的收斂速度和收斂精度進(jìn)行測(cè)試。為避免算法的隨機(jī)性對(duì)分析結(jié)果造成影響,每種算法均獨(dú)立運(yùn)行50次,結(jié)果如表3所示。表3中最優(yōu)(差)解、平均值、標(biāo)準(zhǔn)差分別反應(yīng)算法解的質(zhì)量,整體水平以及魯棒性。

表 3 算法運(yùn)行結(jié)果

從表3可以看出:對(duì)函數(shù)F1～F4,CEPSO算法均找到了真實(shí)最優(yōu)值且魯棒性強(qiáng);對(duì)函數(shù)F5～F8,CEPSO算法求解精度比其他幾個(gè)算法提高了幾十個(gè)數(shù)量級(jí)。對(duì)于高維多峰函數(shù)F1、F3,SPSO、CEPSO算法在收斂精度上有顯著優(yōu)勢(shì)；但對(duì)于函數(shù)F2、F4、F5,SPSO算法收斂過(guò)早,而CEPSO算法始終保持著最高的收斂精度。說(shuō)明改進(jìn)后算法可以有效提高算法收斂精度,增強(qiáng)算法對(duì)高維復(fù)雜函數(shù)的求解能力。

圖2～9是5種算法針對(duì)不同測(cè)試函數(shù)的迭代曲線(xiàn)圖。

圖 2 F1迭代曲線(xiàn)

圖 3 F2迭代曲線(xiàn)

圖 4 F3迭代曲線(xiàn)

圖 5 F4迭代曲線(xiàn)

圖 6 F5迭代曲線(xiàn)

圖 7 F6迭代曲線(xiàn) Fig.7 Iterative curves of F6

圖 8 F7迭代曲線(xiàn)

圖 9 F8迭代曲線(xiàn)

從圖2～4可以看出,對(duì)于高維多峰函數(shù)F1～F3,在進(jìn)化初期CEPSO算法的個(gè)體質(zhì)量不如其他算法。但是，隨著迭代次數(shù)不斷增加,PSO、SAPSO、OTPSO等算法都陷入局部最優(yōu)值,而SPSO算法迅速找到了全局最優(yōu)值,隨后CEPSO算法也收斂到全局最優(yōu)值。特別是在圖4中，2種算法幾乎同時(shí)找到最優(yōu)值。從圖5、6可以看出,對(duì)于高維多峰函數(shù)F4、F5,SPSO算法前期收斂速度快,但與其他算法一樣都陷入局部最優(yōu)值,收斂精度不高,CEPSO算法在兼顧收斂速度的同時(shí)最先找到全局最優(yōu)值。從圖7～9可以看出,對(duì)于高維單峰函數(shù)F6～F8,CEPSO算法最先收斂到最優(yōu)值,在收斂速度和收斂精度上都有顯著優(yōu)勢(shì)。由此可見(jiàn)，改進(jìn)的算法在保障收斂速度的同時(shí)能收斂到全局最優(yōu)值,在高維多峰函數(shù)的求解中更具優(yōu)勢(shì)。

5 結(jié) 語(yǔ)

將交叉熵算法與粒子群優(yōu)化算法結(jié)合,同時(shí)對(duì)進(jìn)化過(guò)程中的粒子進(jìn)行重構(gòu),拓寬了種群的搜索范圍,提高了CEPSO算法的收斂性能,使得算法能更高效地找到全局最優(yōu)點(diǎn)。仿真實(shí)驗(yàn)表明,改進(jìn)后的算法在尋優(yōu)精度和尋優(yōu)速度方面均有明顯提升,對(duì)于復(fù)雜多模態(tài)函數(shù)效果尤為顯著。由此可見(jiàn),將交叉熵算法引入粒子群優(yōu)化算法，是一種有效的算法改進(jìn)途徑。下一步將研究 CEPSO算法與其他優(yōu)化算法的比較,并進(jìn)一步研究其在多目標(biāo)規(guī)劃問(wèn)題中的應(yīng)用。