基于退火加速的差分進(jìn)化算法改進(jìn)及應(yīng)用

陳怡君， 劉軍民

（1.西安航空學(xué)院，西安 710077； 2.西安交通大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，西安 710049）

在理論研究和實際應(yīng)用過程中經(jīng)常會遇到大量的復(fù)雜優(yōu)化問題，對于那些不可微、非線性函數(shù)的優(yōu)化尤為困難［1-2］. 傳統(tǒng)的優(yōu)化方法大多需要計算目標(biāo)函數(shù)的導(dǎo)數(shù)值以及其他一些輔助信息來確定搜索方向，且對函數(shù)的凸性、線性等有諸多限制，求解過程易于陷入局部最優(yōu)，而工程實際中目標(biāo)函數(shù)不可微或不能用函數(shù)表示的現(xiàn)象經(jīng)常存在，因此傳統(tǒng)優(yōu)化技術(shù)雖然具有較強的局部搜索能力，但對于復(fù)雜函數(shù)的優(yōu)化卻不能得到滿意的結(jié)果［3-4］.

20世紀(jì)80年代以來發(fā)展的智能優(yōu)化算法，如遺傳算法、模擬退火算法和粒子群優(yōu)化算法等，都有很好的性能，這些智能優(yōu)化算法具有隱并行性、無須導(dǎo)數(shù)信息和全局優(yōu)化等，具有很好的求解復(fù)雜優(yōu)化問題的潛力［5-7］.在眾多的智能優(yōu)化算法中，差分進(jìn)化算法表現(xiàn)突出，顯示了極大的優(yōu)勢，它被證明是1996年IEEE進(jìn)化算法競賽中速度最快的進(jìn)化算法［8］，但是和其他智能優(yōu)化算法一樣，DE算法也存在局部搜索能力不強的缺點［9-11］. 針對這一問題，已有一些改進(jìn)策略，如與蟻群搜索算法的混合［12］和遺傳算法混合［13-15］，還有與序列二次規(guī)劃算法相結(jié)合等［16-17］. 雖然這些算法對提高DE算法的性能有很大改進(jìn)，但是這些改進(jìn)策略有的利用了目標(biāo)函數(shù)的導(dǎo)數(shù)信息，有的只是針對一類特殊問題而做的改進(jìn)，因此改變了DE算法原有的通用性及無須導(dǎo)數(shù)信息等良好性能［18-19］.

針對上述問題，本文在基本差分進(jìn)化算法的基礎(chǔ)上，對每一個個體以退火概率，用具有較強局部搜索能力的Hooke-Jeeves算法加速，以增強DE算法的局部開發(fā)能力，從而顯著加快了收斂速度.

1 Hooke-Jeeves算法描述

1961年，Hooke和Jeeves率先提出了Hooke-Jeeves算法（又稱為模式搜索法或步長加速法）［20］，該算法的基本思想是利用函數(shù)值去構(gòu)造局部主軸方向，從而盡快找到極小點. 此外，它還具有明顯的幾何意義，它相當(dāng)于從山嶺某處出發(fā)，尋找具有較小函數(shù)值的“山谷”，力圖使迭代產(chǎn)生的序列沿“山谷”走向逼近極小點.Hooke-Jeeves 算法的計算步驟主要由兩大部分組成：一是圍繞基點的局部探測，簡稱為探測移動；二是沿有利的方向向前移動，簡稱為模式移動，具體操作如下.

1.1 探測移動

1.2 模式移動

模式移動是指沿兩個相鄰基點連線方向進(jìn)行. 在第k 步可行解xk探測移動后得到新的基點xk+1，則作模式移動：

其中：β為加速因子，β ＞0 .

步長加速法是一種直接尋優(yōu)的確定性方法，形象直觀，易于理解和掌握，對目標(biāo)函數(shù)要求甚少，適用范圍廣泛.

2 退火加速策略

在差分進(jìn)化算法的進(jìn)化過程中，常常會出現(xiàn)算法早熟收斂現(xiàn)象，這是因為隨著進(jìn)化的進(jìn)行，所有個體均向最優(yōu)個體靠攏，群體的多樣性會逐漸消失. 如果最優(yōu)個體是一全局最優(yōu)點，則所有個體均收斂到全局最優(yōu)點，但如果最優(yōu)個體為一局部最優(yōu)點，則所有個體均收斂于局部最優(yōu)點，就會導(dǎo)致早熟收斂. 出現(xiàn)所有個體向最優(yōu)個體靠攏的原因是差分進(jìn)化算法的“貪婪”選擇機制，這樣雖然會加速收斂速度，但同時也會以較大的概率丟棄在全局最優(yōu)點附近卻適應(yīng)度暫時較差的個體.

鑒于上述分析，在進(jìn)化的初期應(yīng)對每個個體以較小的概率加速，以保持其多樣性不喪失，保證全局收斂；在后期應(yīng)該增加每個個體的局部搜索能力，進(jìn)而提高精度. 所以，對每個個體用以下概率p=t/Tmax（t和Tmax分別是當(dāng)前的進(jìn)化代數(shù)和設(shè)定的最大進(jìn)化代數(shù)）來判斷是否利用模式搜索加速. 當(dāng)隨機數(shù)小于p 時對個體加速，大于時則不加速. 從p 的表達(dá)式可知其在初期值較小，后期值較大，這有點類似于模擬退火概率，符合上述分析的要求，兼顧全局搜索和局部搜索的平衡.

3 算法的描述

1）初始化參數(shù)：種群規(guī)模NP；縮放因子F ；變異因子CR；空間維數(shù)D；加速因子β ；進(jìn)化代數(shù)t=0 .（這里的初始化參數(shù)均為標(biāo)量）.

3）個體評價：計算每個個體的適應(yīng)度值.

4）變異操作：按下式計算

5）交叉操作：按下式計算

①給出計算精度ε ＞0，初始向量組：e1,e2,…,eD（通常取為各坐標(biāo)軸上的單位向量）. 初始步長d1=d2=d3=…=dD=d ＞0，加速因子

⑤如果d ≤ε，則計算結(jié)束，取x*≈xk；否則，令d=d/2，y1=xk,xk+1=xk,k=k+1，再令j=1，返回②.

8）終止檢驗：如果達(dá)到最大進(jìn)化代數(shù)或滿足誤差要求，則輸出最優(yōu)值；否則轉(zhuǎn)3）.

4 數(shù)值實驗及結(jié)果分析

下面通過幾個典型函數(shù)的數(shù)值實驗來比較本節(jié)算法的優(yōu)劣. 實驗要測試的函數(shù)如下.1）Sphere Model

2）Rosenbrok function

3）Rastrigin Function

4）Grienwank Function

DE算法有四個主要參數(shù)：種群規(guī)模NP=25；縮放因子F=0.5；變異因子CR=0.1；空間維數(shù)D=10 . 在實驗中，每個函數(shù)的特性和其他參數(shù)如表1所示.

表1 各函數(shù)的參數(shù)設(shè)置及特征說明Tab.1 Parameter setting and characteristic description of each function

在測試中，用DE和改進(jìn)的差分進(jìn)化算法（簡記為MDE）分別隨機連續(xù)運行20次，其結(jié)果見表2.

表2 計算結(jié)果比較Tab.2 Comparison of calculation results

圖1～4是兩種算法的優(yōu)化曲線比較圖. 大圖為測試函數(shù)的平均最優(yōu)值在整個迭代過程中的進(jìn)化情況；小圖為后期進(jìn)化情況優(yōu)化曲線的放大圖. 圖中的虛線（藍(lán)色）為基本差分進(jìn)化算法，實線（紅色）為本文提出的算法.

圖1 函數(shù)f1 的尋優(yōu)曲線Fig.1 Optimization curves of function f1

圖2 函數(shù)f2 的尋優(yōu)曲線Fig.2 Optimization curves of function f2

圖3 函數(shù)f3 的尋優(yōu)曲線Fig.3 Optimization curves of function f3

圖4 函數(shù)f4 的尋優(yōu)曲線Fig.4 Optimization curves of function f4

由表2和圖1～4可知，基于退火加速的差分進(jìn)化算法的收斂速度比基本的差分進(jìn)化算法快，尤其是后期由于采用退火加速策略，后期的收斂速度明顯加快了. 此外由于較好地保持了多樣性，全局搜索能力也得到了加強，精度顯著提高.

5 結(jié)論

DE算法在求解單目標(biāo)及多目標(biāo)優(yōu)化、約束優(yōu)化和動態(tài)優(yōu)化等復(fù)雜優(yōu)化問題領(lǐng)域有著極為廣泛的研究和應(yīng)用價值. 本文針對DE算法存在的收斂早熟及收斂速度慢等問題，在傳統(tǒng)DE算法的基礎(chǔ)上，對每一個個體均具有較強局部搜索能力的Hooke-Jeeves算法加速，以退火概率來增強DE算法的局部開發(fā)能力，提出了基于退火加速的差分進(jìn)化算法. 數(shù)值實驗結(jié)果表明，與傳統(tǒng)DE算法相比，該算法收斂速度快、精度高，在保持較好多樣性的同時顯著加強了全局搜索能力，是一種有效的全局優(yōu)化算法.