改進(jìn)的差分演化算法及其在函數(shù)優(yōu)化中的應(yīng)用

(許昌學(xué)院 信息工程學(xué)院，河南 許昌461000)

在復(fù)雜的工程設(shè)計(jì)應(yīng)用領(lǐng)域中經(jīng)常會(huì)涉及到一些較為復(fù)雜函數(shù)優(yōu)化問題, 這些函數(shù)的特點(diǎn)往往是非線性、不可導(dǎo)、不連續(xù)、多峰值、多極值、凹凸性不明確, 而且時(shí)常還帶有各類的約束條件, 因此, 利用傳統(tǒng)的數(shù)學(xué)方法(共軛梯度法、單純性法等)很難得到理想的結(jié)果. 近年來, 許多學(xué)者把演化算法應(yīng)用到復(fù)雜函數(shù)優(yōu)化問題中, 取得較好的效果.差分演化算法就是其中的一種，差分演化算法(Differential Evolution, DE)[1]是由Storn 和Price科學(xué)家在1995年提出的一種高效簡單的全局優(yōu)化算法.本算法最大的優(yōu)勢在于差分變異算子具有較好的自搜索方向、自搜索步長等特點(diǎn).目前，該算法已經(jīng)較成功的應(yīng)用在多個(gè)實(shí)際工程應(yīng)用領(lǐng)域，如神經(jīng)網(wǎng)絡(luò)、模式識(shí)別、數(shù)據(jù)挖掘、濾波器設(shè)計(jì)、電路優(yōu)化設(shè)計(jì)、函數(shù)優(yōu)化等問題中.

原始的差分演化算法里面主要涉及到三個(gè)基本參數(shù)：雜交概率CR；縮放因子F；種群規(guī)模NP；相關(guān)研究[2-4]表明，算法成功的關(guān)鍵就是參數(shù)的正確選擇.傳統(tǒng)的參數(shù)設(shè)置大部分是根據(jù)經(jīng)驗(yàn)來進(jìn)行設(shè)置，如果參數(shù)設(shè)置不合理，可能導(dǎo)致算法效率不高，算法容易陷于局部最優(yōu)，JDE[5]、SADE[6]、CoDE[7]等是目前較好的自適應(yīng)差分演化算法，每種算法也有其各自的優(yōu)劣勢.

基于以上的問題，本文對基本差分演化算法進(jìn)行了改進(jìn), 提出一種改進(jìn)的差分演化算法(本文的算法簡稱IDE算法), 該算法的主要特征是: 提出了混合混沌和逆向?qū)W習(xí)算子來初始化種群，保持種群的多樣性，加快算法的收斂速度，同時(shí)增強(qiáng)算法的全局搜索能力；提出了隨機(jī)排序的選擇策略，避免算法提前陷于局部最優(yōu)，通過國際上標(biāo)準(zhǔn)的測試函數(shù)進(jìn)行驗(yàn)證本算法的優(yōu)越性.

1 問題的描述

本文研究以最小化函數(shù)優(yōu)化為目標(biāo)，如公式1所示，其中S?RD,RD稱為搜索空間,D是變量維數(shù),f(x)為目標(biāo)函數(shù)，X是n維解向量X=[x1,x2,…,xn]T, 每個(gè)自變量xi滿足一定的約束條件，如公式2所示.最終的目標(biāo)為求解目標(biāo)函數(shù)的最小值作為最優(yōu)，記做min(f(x)).

X=(x1,x2,…,xn)∈Rn，

(1)

Li≤xi≤Ui,i=1,2,…,n.

(2)

2 算法思路與框架流圖

差分演化算法求解函數(shù)優(yōu)化問題需要通過對不同個(gè)體進(jìn)行雜交，變異，選擇，優(yōu)勝劣汰等自適應(yīng)操作，經(jīng)過若干代演化，求出算法的相對的最優(yōu)解.基本的差分演化化算法求解問題偽代碼如表1所示[8]，其中從第5行到第13行是DE/rand/1/bin算法的變異策略；第9行是DE/rand/1算法的變異算子；第17行到第19行選擇算子rndint(1,D)函數(shù)表示在[1,D]區(qū)間隨機(jī)均勻生成整數(shù)變量，自變量維數(shù)為D；rndreal[0,1]函數(shù)代表在[0,1]之間隨機(jī)均勻產(chǎn)生浮點(diǎn)數(shù).算法停機(jī)條件設(shè)置為演化代數(shù)、適應(yīng)值的評(píng)價(jià)次數(shù)的極限等，需要用戶預(yù)先設(shè)置.

表1 求解問題偽代碼

3 實(shí)現(xiàn)的關(guān)鍵技術(shù)設(shè)計(jì)

3.1 混沌算子和逆向?qū)W習(xí)算子混合初始化種群

基本的差分演化算法采用隨機(jī)方法來生成初始化種群，由于隨機(jī)函數(shù)的性質(zhì)，導(dǎo)致種群的不確定性，最終帶來結(jié)果的不穩(wěn)定，為了盡量減小初始化種群對算法結(jié)果的最終影響，本文提出了混沌算法來初始化種群, 有效的改善了種群多樣性與穩(wěn)定性，加快了算法的收斂速度.生成初始化種群的方法如表2所示，部分參數(shù)如下：迭代次數(shù)N=500，m=3.88，X=(X1,X2,Xi,…,XSD) 為最終的種群.

表2 初始化種群的方法

3.2 改進(jìn)的選擇策略

在演化算法中，群體的多樣性對算法能否快速收斂到全局最優(yōu)解極為重要，群體的多樣性越大，算法陷入局部最優(yōu)解的可能性越小，為了盡可能保持群體的多樣性，本文算法克服傳統(tǒng)的算法容易陷于局部最優(yōu)解的思想，提出了采用了隨機(jī)排序選擇策略來保持種群的多樣性，避免陷于局部最優(yōu)解，根據(jù)適應(yīng)度函數(shù)值進(jìn)行排序時(shí)，通過一個(gè)隨機(jī)排序控制參數(shù)μ來控制排序過程，從而可以對排序結(jié)果進(jìn)行一定的擾動(dòng)，算法隨機(jī)排序過程描述為表3.

表3 算法隨機(jī)排列過程表

通過實(shí)驗(yàn)發(fā)現(xiàn)μ值越大， 其隨機(jī)擾動(dòng)就會(huì)越小，NP代表種群的規(guī)模，文中設(shè)置為100，種群所有個(gè)體執(zhí)行每代算法后，按照小到大順序排序，按照排序的結(jié)果，從中選擇α個(gè)個(gè)體形成選擇群體，本文的α=4.

4 實(shí)驗(yàn)與結(jié)論

4.1 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

為了驗(yàn)證本文提出了IDE算法的性能，我們選擇了國際通用標(biāo)準(zhǔn)22個(gè)測試函數(shù)[9]進(jìn)行了測試，測試函數(shù)大概可以劃分為三大類(1)單峰測試函數(shù)f1-f5;(2)多峰測試函數(shù)f06-f14;(3)混合單峰、多峰測試函數(shù)(f15-f22).這些測試函數(shù)絕大多數(shù)具有位移或旋轉(zhuǎn)等特性，用普通的數(shù)學(xué)辦法很難求得最優(yōu)解.

本文中所有參數(shù)如下:群體規(guī)模:M=100; 雜交概率: CR=0.85; DE策略: DE/rand/1/bin; 最大評(píng)價(jià)次數(shù)極限: NFFE=250 000; 父個(gè)體數(shù)目:P=6; 停機(jī)精度:ε=1e-30; 決策變量分塊大小: 當(dāng)自變量維數(shù)N>8時(shí),F=2; 其他,F=N; 等式約束容差:η=0.000 01，每個(gè)函數(shù)獨(dú)立運(yùn)行50次，各類算法在相同條件下，運(yùn)行的最優(yōu)解如下表4所示.

4.2 結(jié)果與分析

本文提出的IDE算法以及被比較的其它三種算法，按照相同的測試函數(shù)重復(fù)進(jìn)行50次獨(dú)立實(shí)驗(yàn)，得出實(shí)驗(yàn)數(shù)據(jù)，從表4來看，對于絕大多數(shù)測試函數(shù), IDE算法比其它SADE、JDE和CODE算法都獲取了較理想的最優(yōu)解，其它測試函數(shù)(如f12,f18,f19,f20)IDE與其它方法基本持平，表中加粗的部分表示四種方法的最好結(jié)果.因此本文提出用混沌算法與逆向?qū)W習(xí)算子相結(jié)合來初始化種群與隨機(jī)排序的選擇策略應(yīng)用在函數(shù)優(yōu)化問題中，在絕大多數(shù)測試函數(shù)本文的方法均優(yōu)于被比較的其它算法.

表4 五種不同算法最優(yōu)結(jié)果數(shù)據(jù)比較表