基于退火算子的差分進(jìn)化算法

胡朝根

摘要：傳統(tǒng)差分進(jìn)化算法存在局部搜索能力不足、后期搜索精度不夠的缺點(diǎn)。本文在模擬退火算法的基礎(chǔ)上，提出一種退火算子（FSA），并將退火算子與差分進(jìn)化算法進(jìn)行有機(jī)結(jié)合，形成基于退火算子的差分進(jìn)化算法（FSADE）。使用MATLAB用標(biāo)準(zhǔn)測(cè)試函數(shù)測(cè)試算法性能，并與其他優(yōu)化算法測(cè)試結(jié)果比較，結(jié)果證明了改進(jìn)算法的有效性。

關(guān)鍵詞：退火算子 差分進(jìn)化算法 MATLAB仿真

中圖分類號(hào)：TP391.9 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2016）07-0125-01

1 引言

差分進(jìn)化算法是一種基于種群的智能優(yōu)化算法，具有全局搜索能力強(qiáng)、結(jié)構(gòu)簡(jiǎn)單、容易實(shí)現(xiàn)等優(yōu)點(diǎn)，但也存在局部搜索能力不足的缺點(diǎn)，使算法在進(jìn)化后期收斂速度變慢，甚至可能導(dǎo)致陷入局部收斂[1]。

單種智能算法總存在一些算法上固有的缺陷。而將兩種或多種智能算法按照某種方式融合在一起形成混合優(yōu)化算法，則可有效地?fù)P長避短，大大提高算法的搜索能力[2]。本文在模擬退火算法的基礎(chǔ)上提出退火算子，并用退火算法對(duì)差分進(jìn)化種群中優(yōu)秀個(gè)體進(jìn)行局部搜索，從而加快算法收斂速度與精度。

2 基于退火算子的差分進(jìn)化算法

本文提出的基于退火算子的差分進(jìn)化算法（Fast Simulated Annealing-Differential Evolution Algorithm， FSADE），具體描述如下：

（1）判斷當(dāng)代群體中的最優(yōu)個(gè)體bestX（g）是否優(yōu)于上一代群體中的最優(yōu)個(gè)體bestX（g-1），若是則用模擬退火算子對(duì)bestX（g）進(jìn)行局部搜索；否則說明差分進(jìn)化算法沒有搜索到更優(yōu)個(gè)體，不需要對(duì)其進(jìn)行局部搜索，以減少運(yùn)算量。

（2）改進(jìn)的退火算子（Fast Simulated Annealing Operator ， FSA）。針對(duì)混合算法收斂速度慢以及模擬退火算法非完全最優(yōu)選擇的特點(diǎn)，采用低溫差模擬退火以加快收斂速度。并將算法運(yùn)行過程中搜索到的優(yōu)于bestX（g）的解進(jìn)行保存。采用自適應(yīng)擾動(dòng)模型，擾動(dòng)大小隨著差分進(jìn)化算法進(jìn)化代數(shù)的增加而減小。自適應(yīng)擾動(dòng)模型如下：

（1）

Φ為擾動(dòng)大小；α為搜索基礎(chǔ)步長；β為搜索倍率，；G為差分進(jìn)化代數(shù)；rand為[0，1]均勻分布隨機(jī)數(shù)。

傳統(tǒng)模擬退火算法，溫差倍數(shù)一般在10000倍以上，同一溫度下的循環(huán)次數(shù)L一般在100以上，降溫系數(shù)a一般為0.95[3]。而本文的FSA算子溫差倍數(shù)為500， L為10，a為0.9。FSA雖然在全局搜索能力降低，但搜索速度有了極大的提高。保證混合算法的搜索速度。DE算法搜索策略采用DE/best/1/bin，增強(qiáng)了混合算法的融合，使混合算法具有較強(qiáng)的全局與局部搜索能力。

3 仿真分析

為了驗(yàn)證本FSADE性能，選取了3個(gè)具有代表性的標(biāo)準(zhǔn)測(cè)試函數(shù)來測(cè)試算法性能。

（1）Sphere Function

（2）

（2）Alpine Function

（3）

（3）Griewank Function

（4）

選取標(biāo)準(zhǔn)差分進(jìn)化算法（DE）、參數(shù)自適應(yīng)差分進(jìn)化算法（jDE）和基于逆向的差分進(jìn)化算法（ODE）進(jìn)行比較，自變量維度設(shè)為100維，使用MATLAB軟件進(jìn)行編程仿真。

算法參數(shù)設(shè)置與仿真結(jié)果如下：種群規(guī)模NP=100，縮放因子F=0.8，交叉率CR=0.9，最大函數(shù)調(diào)用次數(shù)1000。各算法運(yùn)行30次進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)結(jié)果如表1所示。

4 結(jié)語

通過表1的MATLAB仿真結(jié)果我們可以看出，基于退火算子的差分進(jìn)化算法克服了局部搜索能力不足的缺點(diǎn)，較標(biāo)準(zhǔn)差分進(jìn)化算法、參數(shù)自適應(yīng)差分進(jìn)化算法、基于逆向的差分進(jìn)化算法收斂速性能較好、收斂精度更高、魯棒性更好。

參考文獻(xiàn)

[1]張春美.差分進(jìn)化算法理論與應(yīng)用[M].北京：北京理工大學(xué)出版社，2014.

[2]蔡之華，龔文引.差分進(jìn)化算法及其運(yùn)用[M].中國地質(zhì)大學(xué)出版社，2010.

[3]龐龍.模擬退火算法的原理及算法在優(yōu)化問題上的應(yīng)用[D].吉林：吉林大學(xué)，2006.