改進(jìn)的小生境混合遺傳算法在函數(shù)優(yōu)化上的應(yīng)用*

王 聰， 柯滬琦， 胡燕海

(1.寧波大學(xué) 機(jī)械工程與力學(xué)學(xué)院，浙江 寧波 315211；2.寧波戴維醫(yī)療器械股份有限公司，浙江 寧波 315712)

應(yīng)用技術(shù)

改進(jìn)的小生境混合遺傳算法在函數(shù)優(yōu)化上的應(yīng)用*

王 聰1， 柯滬琦2， 胡燕海1

(1.寧波大學(xué) 機(jī)械工程與力學(xué)學(xué)院，浙江 寧波 315211；2.寧波戴維醫(yī)療器械股份有限公司，浙江 寧波 315712)

為了提高經(jīng)典小生境遺傳算法的收斂性能，加強(qiáng)局部尋優(yōu)能力，設(shè)計(jì)了一種新的小生境混合遺傳算法。通過判斷算法的在線性能指標(biāo)Xe(s)，將模擬退火算法巧妙地融入算法的后期，并針對(duì)小生境遺傳算法的特點(diǎn)選用格雷碼編碼，同時(shí)設(shè)計(jì)了自適應(yīng)的遺傳交叉算子。用一個(gè)Shubert多峰值函數(shù)對(duì)改進(jìn)的算法進(jìn)行驗(yàn)證，結(jié)果表明:新算法的收斂性能和進(jìn)化效率得到提高，局部尋優(yōu)能力也有加強(qiáng)。

小生境； 混合遺傳算法； 模擬退火算法； 在線性能指標(biāo)

0 引 言

現(xiàn)今存在的一些優(yōu)化算法，均具有各自的優(yōu)點(diǎn)，但又存在或多或少的缺點(diǎn)。如：模擬退火法、爬山法局部尋優(yōu)能力好，但全局尋優(yōu)能力差；普通的遺傳算法容易早熟，全局尋優(yōu)能力好。因此，根據(jù)經(jīng)驗(yàn)漸漸形成了混合遺傳算法的概念，融合算法之間的優(yōu)點(diǎn)，使求解問題更具效率，求解質(zhì)量也得到提高[1～8]。

基于混合遺傳算法的理念，出現(xiàn)了很多小生境實(shí)現(xiàn)技術(shù)。如文獻(xiàn)[2]中提出了一種基于相似個(gè)體交叉和(μ+λ)確定性擇優(yōu)機(jī)制的小生境技術(shù)，能提高全局收斂可靠性，加快收斂速度。文獻(xiàn)[3]中提出了一種基于小生境模擬退火的遺傳算法，從過程上看，該方法在每一輪進(jìn)化的末尾執(zhí)行了模擬退火操作，實(shí)現(xiàn)方式比較機(jī)械，達(dá)不到最優(yōu)化的混合遺傳算法要求[4～7]；從效果上看，該方法依然只能提高收斂速度，沒有解決局部尋優(yōu)性能差的缺點(diǎn)。

本文提出了一種改進(jìn)的小生境混合遺傳算法，不但能在最適宜的點(diǎn)融入模擬退火算法，而且采用格雷碼代替二進(jìn)制編碼，同時(shí)改進(jìn)了遺傳算子。最后，將該算法運(yùn)用于優(yōu)化一個(gè)具體函數(shù)，結(jié)果表明:算法能加快收斂速度，提高搜索效率，并有較強(qiáng)的局部尋優(yōu)能力。

1 經(jīng)典小生境遺傳算法存在的問題

經(jīng)典小生境遺傳算法對(duì)兩個(gè)在一定距離S之內(nèi)的個(gè)體，比較其適應(yīng)度大小，通過一個(gè)罰函數(shù)，淘汰適應(yīng)度較小的個(gè)體，保留距離S內(nèi)的優(yōu)良個(gè)體。最終，群體不但具有較好的多樣性，還能使個(gè)體之間分布均勻。但是小生境遺傳算法也存在著局部尋優(yōu)能力不強(qiáng)，容易陷入進(jìn)化停滯的問題[9～20]。

另外，由于小生境遺傳算法需要計(jì)算每?jī)蓚€(gè)個(gè)體之間的海明距離，并對(duì)適應(yīng)度較低的個(gè)體處以罰函數(shù)，算法復(fù)雜，加大計(jì)算量，對(duì)于種群規(guī)模大的群體，計(jì)算效率難以保證。當(dāng)群體進(jìn)化到后期，優(yōu)質(zhì)個(gè)體的數(shù)量大大增加，或個(gè)體的目標(biāo)函數(shù)值已進(jìn)化到最優(yōu)解附近，此時(shí)如果仍然采用經(jīng)典小生境遺傳算法，將增加計(jì)算負(fù)擔(dān)[21～24]。

2 小生境混合遺傳算法

為了提高小生境遺傳算法的局部尋優(yōu)能力和算法的計(jì)算效率。在經(jīng)典算法中融入了局部尋優(yōu)能力較強(qiáng)的模擬退火算法，并采用格雷碼的編碼方法，以及與編碼方法相對(duì)應(yīng)的自適應(yīng)遺傳算子。

2.1 模擬退火算法

模擬退火算法利用了退火這一金屬熱加工工藝原理, 隨著溫度的降低，物質(zhì)的能量將逐漸趨近于一個(gè)較低的狀態(tài)，并最終達(dá)到某種平衡。運(yùn)用到函數(shù)優(yōu)化中，能以隨機(jī)搜索技術(shù)從概率的意義上找出目標(biāo)函數(shù)的全局最小點(diǎn)。

算法描述如下：

1)設(shè)置一個(gè)初始點(diǎn)，計(jì)算得到目標(biāo)函數(shù)值；

2)規(guī)定循環(huán)計(jì)數(shù)器初值：t=1；

3)設(shè)置初始溫度：θ=T0；

4)使用變異操作于初始點(diǎn)，初始點(diǎn)變異后，計(jì)算得到目標(biāo)函數(shù)值的Δ增量；

5)若Δ<0，則當(dāng)前最優(yōu)點(diǎn)就是新產(chǎn)生的最優(yōu)點(diǎn)；若Δ≥0，則新產(chǎn)生的最優(yōu)點(diǎn)將以p=e(-Δ/θ)的概率成為當(dāng)前最優(yōu)點(diǎn)；

6)如果t小于結(jié)束步數(shù)，則t=t+1，轉(zhuǎn)向第(4)步；

7)如果未達(dá)到冷卻狀態(tài)，則θ=T(t)，轉(zhuǎn)向第(2)步；如果達(dá)到冷卻狀態(tài)，則輸出當(dāng)前最優(yōu)點(diǎn)，計(jì)算結(jié)束。

2.2 格雷碼編碼

格雷碼是二進(jìn)制編碼的一種變形，主要有兩個(gè)特點(diǎn)：1)兩個(gè)連續(xù)的整數(shù)編碼值不同之處只有一個(gè)碼位；2)兩個(gè)整數(shù)所代表的格雷碼之間的海明距離剛好是這兩個(gè)整數(shù)的差。特點(diǎn)(1)使算法的局部搜索能力得到提高，使交叉、變異操作易于實(shí)現(xiàn)。特點(diǎn)(2)在計(jì)算某兩個(gè)點(diǎn)的海明距離時(shí)，只需計(jì)算對(duì)應(yīng)的兩個(gè)整數(shù)的差，可大大簡(jiǎn)化計(jì)算步驟，提高計(jì)算效率。

2.3 遺傳選擇算子

選用稱為穩(wěn)態(tài)復(fù)制的最優(yōu)保存策略進(jìn)化模型，以對(duì)已經(jīng)過模擬退火操作的群體進(jìn)行一次優(yōu)勝劣汰操作。

2.4 自適應(yīng)交叉算子

在進(jìn)化過程的不同時(shí)期，群體中優(yōu)質(zhì)個(gè)體的數(shù)量不同，若自始至終使用同一概率對(duì)種群個(gè)體進(jìn)行交叉操作，群體的優(yōu)化程度得不到保證。比如，在進(jìn)化早期，期望較大的交叉概率，使整個(gè)群體的優(yōu)行能在短時(shí)間內(nèi)完成；但是在進(jìn)化的末期，種群中存在較多好的個(gè)體，為了避免破壞那些已優(yōu)化的個(gè)體，則期望交叉概率較小。為此，設(shè)計(jì)了一種自適應(yīng)交叉概率函數(shù)

(1)

式中 Pc為當(dāng)前代數(shù)對(duì)應(yīng)的交叉概率；Pn為常規(guī)交叉概率；t為當(dāng)前進(jìn)化代數(shù)；C為一個(gè)常數(shù)。

在實(shí)際操作過程中，在進(jìn)化前期即進(jìn)化代數(shù)t小于進(jìn)化總代數(shù)T的60 %時(shí)，交叉概率固定。當(dāng)進(jìn)化代數(shù)t大于等于進(jìn)化總代數(shù)T的60 %時(shí)，則根據(jù)式(1)確定每一代群體的交叉概率。

2.5 小生境操作

1)按式(2)計(jì)算種群規(guī)模為W的群體中任意兩個(gè)個(gè)體Xi和Xj的海明距離

i=1,2,…，W-1,j=i+1,…，W

(2)

2)當(dāng)個(gè)體Xi和Xj的海明距離小于L時(shí)，對(duì)個(gè)體Xi和Xj中適應(yīng)度較低的個(gè)體施加一個(gè)罰函數(shù)Penalty。

3)對(duì)種群按適應(yīng)度大小進(jìn)行降序排列，保留排名在前n位的個(gè)體，組成新的群體。

3 混合遺傳算法構(gòu)成框架

在線性能指標(biāo)(遺傳算法性能的評(píng)價(jià)指標(biāo)之一)指

(3)

式中fe(t)為在環(huán)境e下t時(shí)刻的平均目標(biāo)函數(shù)值或平均適應(yīng)度；s為算法策略。根據(jù)式(3)，在線性能指標(biāo)的含義是遺傳算法自開始一直到結(jié)束的一段時(shí)間內(nèi)性能值的平均。

小生境遺傳算法存在容易陷入進(jìn)化停滯和局部最優(yōu)性能差的缺陷，因此可利用在線性能指標(biāo)來判斷當(dāng)前目標(biāo)函數(shù)值是否已接近最優(yōu)值，時(shí)可換用模擬退火算法這一類局部尋優(yōu)能力強(qiáng)的優(yōu)化算法，不但可以盡快找到全局最優(yōu)值，而且能提高算法的效率，減少計(jì)算時(shí)間。詳細(xì)見圖1。

圖1 改進(jìn)的小生境遺傳算法流程圖

圖1中的P(0

4 多峰值函數(shù)應(yīng)用

為了測(cè)試經(jīng)改進(jìn)的小生境混合遺傳算法的性能，本文選用了Shubert多峰值函數(shù)，并與經(jīng)典小生境遺傳算法對(duì)Shubert函數(shù)的優(yōu)化結(jié)果進(jìn)行了比較。

4.1Shubert函數(shù)

Shubert函數(shù)可描述為

(4)

這是一個(gè)二元多峰值函數(shù)，如圖2所示，其定義域內(nèi)共有760個(gè)局部最小點(diǎn)，其中18個(gè)點(diǎn)為全局最小點(diǎn)，全局最小值為f=-186.731。

用小生境遺傳算法求解函數(shù)時(shí)，需用式(5)進(jìn)行目標(biāo)函數(shù)值到個(gè)體適應(yīng)度的變換處理

(5)

圖2 Shubert多峰值函數(shù)圖像

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

經(jīng)典小生境遺傳函數(shù)參數(shù)設(shè)定為：二進(jìn)制編碼串長(zhǎng)度l=20×2(其中每個(gè)變量用10位二進(jìn)制編碼來表示);初始種群規(guī)模M=100;交叉概率PC=0.8;變異概率Pm=0.05;最大進(jìn)化代數(shù)T=5000;小生境之間的距離參數(shù)L=0.5;罰函數(shù)Penalty=10～30。終止條件：算法進(jìn)化代數(shù)為最大值500時(shí)，實(shí)驗(yàn)次數(shù)為50次。

改進(jìn)的小生境混合遺傳函數(shù)參數(shù)設(shè)置為：格雷碼編碼串長(zhǎng)度l’=20×2(相同長(zhǎng)度的格雷碼與二進(jìn)制編碼串精度相同);初始種群規(guī)模M=100;自適應(yīng)交叉概率P’C根據(jù)公式(1)得到;變異概率為P’m=0.05;小生境之間的距離參數(shù)L’=0.5;罰函數(shù)Penalty’=10～30;判斷是否進(jìn)入模擬退火算法的概率p=0.9。終止條件：小生境遺傳算法和模擬退火算法的總進(jìn)化代數(shù)為最大值500時(shí)，實(shí)驗(yàn)次數(shù)為50次。

4.3 實(shí)驗(yàn)結(jié)果

圖3為兩種算法各實(shí)驗(yàn)50次所繪制的平均進(jìn)化圖。算法1為經(jīng)典小生境遺傳算法，算法2為改進(jìn)的小生境混合遺傳算法。

由圖3中“解的變化”曲線可知：算法1收斂到全局最優(yōu)解大概需要進(jìn)化25代左右，而算法2收斂到全局最優(yōu)解只需進(jìn)化10代左右的時(shí)間。可見，算法2的收斂速度得到了明顯提高。由圖中“種群均值的變化”曲線可知：使用算法2進(jìn)化的種群，其均值變化幅度明顯減小，可見，算法2的局部尋優(yōu)能力也得到加強(qiáng)。

從運(yùn)行到終止條件而停止時(shí)，算法1需要平均步數(shù)為281步，算法2需要平均步數(shù)為116步?？梢?，算法2的進(jìn)化步數(shù)明顯小于算法1，證明了當(dāng)目標(biāo)函數(shù)值達(dá)到最優(yōu)值的90 %后，使用模擬退火算法尋優(yōu)的確可以提高進(jìn)化速度。

圖3 兩種算法進(jìn)化結(jié)果比較

5 結(jié) 論

本文針對(duì)經(jīng)典的小生境遺傳算法存在容易陷入進(jìn)化停滯和局部尋優(yōu)性能差的缺陷，提出了一種改進(jìn)的小生境混合遺傳算法，對(duì)遺傳算子改進(jìn)的同時(shí)，引入模擬退火算法，并給出了算法流程框圖。經(jīng)實(shí)驗(yàn)證明，新算法能有效提高算法效率，加強(qiáng)局部尋優(yōu)能力。

[1] 周 明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京:國(guó)防工業(yè)出版社，1999:70-79.

[2] 喻壽益，郭觀七.一種改善遺傳算法全局搜索性能的小生境技術(shù)[J].信息與控制，2001，30(6):526-530.

[3] 趙 敏，林道榮，瞿 波，等.一種新的基于小生境模擬退火的遺傳算法[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，32(3):45-51.

[4] 宗德才，王康康.一種混合局部搜索算法的遺傳算法求解旅行商問題[J].計(jì)算機(jī)應(yīng)用與軟件，2015(3):15-21.

[5] 王秋芬，梁道雷.一種求解0—1背包問題的啟發(fā)式遺傳算法[J].計(jì)算機(jī)應(yīng)用與軟件,2013(2):68-73.

[6] 屈志毅，文雪飛，范志明，等.基于遺傳模擬退火算法的多約束QOS組播路由優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用與軟件，2007(12):44-49.

[7] 張志鵬，黃 明.基于改進(jìn)多目標(biāo)遺傳算法求解混合流水車間調(diào)度問題[J].計(jì)算機(jī)應(yīng)用與軟件，2015(10):88-95.

[8] 姜封國(guó).結(jié)構(gòu)系統(tǒng)基于可靠性的優(yōu)化設(shè)計(jì)研究[D].哈爾濱:哈爾濱工程大學(xué)，2009.

[9] 袁麗華.基于物種進(jìn)化的遺傳算法研究[D].南京:南京航空航天大學(xué)，2009.

[10] 楊曉華.參數(shù)優(yōu)選算法研究及其在水文模型中的應(yīng)用[D].南京:河海大學(xué)，2002.

[11] 劉 楠.改進(jìn)的小生境遺傳算法在多目標(biāo)車間調(diào)度中的應(yīng)用研究[D].大連:計(jì)算機(jī)應(yīng)用技術(shù)，2010.

[12] 黃聰明，陳湘秀.小生境遺傳算法的改進(jìn)[J].北京理工大學(xué)學(xué)報(bào)，2004，6(8):46-52.

[13] 程紹清.自適應(yīng)微型遺傳算法在動(dòng)態(tài)本構(gòu)參數(shù)反演中的應(yīng)用[D].長(zhǎng)沙:湖南大學(xué)，2010.

[14] 鄒臘梅，龔向堅(jiān)，肖 芳，等.基于模擬退火算法與隱馬爾可夫模型的Web信息抽取[J].南華大學(xué)學(xué)報(bào)，2011，10(1):151-156.

[15] 王友釗，彭宇翔，潘芬蘭.基于貪心算法和遺傳算法的倉(cāng)儲(chǔ)車輛調(diào)度算法[J].傳感器與微系統(tǒng)，2012，31(10):88-93.

[16] 張榮祥，李正強(qiáng)，鄭世杰.基于遺傳算法的雙閾值小波去噪方法研究[J].傳感器與微系統(tǒng)，2007，26(6):46-52.

[17] 朱海燕，王力虎.基于遺傳算法的合作演化仿真[J].傳感器與微系統(tǒng)，2010，29(12):111-116.

[18] 汪 蕓，涂啟玉，陳 華.洪水演算中馬斯京根法的新改進(jìn)[J].人民長(zhǎng)江，2008，24(2):36-41.

[19] 涂啟玉.基于小生境遺傳算法的區(qū)域水資源優(yōu)化配置[J].水利科技與經(jīng)濟(jì)，2008，5(3):78-83.

[20] 李 兵.瑞雷波技術(shù)在巨粒土路基檢測(cè)中的應(yīng)用[D].重慶:重慶交通大學(xué)，2011.

[21] 虞安軍.基于遺傳算法的高速公路路面養(yǎng)護(hù)決策優(yōu)化研究[D].長(zhǎng)沙:長(zhǎng)沙理工大學(xué)，2007.

[22] 周洪偉.遺傳算法“早熟”現(xiàn)象和改進(jìn)策略研究[D].鄭州:解放軍信息工程大學(xué)，2004.

[23] Zheng Q，Sha J，Shu J，et al.A variant constrained genetic algorithm for solving conditional nonlinear optimal perturbations[J].Advances in Atmospheric Sciences，2014，31(1):219-229.

[24] Ulas K，Kürsat A.Optimal power flow solution of two-terminal HVDC systems using genetic algorithm[J].Electrical Enginee-ring，2014，96(1):65-77.

王 聰(1992- )，男，碩士，研究方向?yàn)檫z傳算法，嵌入式工程。

胡燕海(1965- )，男，通訊作者，博士，教授，從事機(jī)電液產(chǎn)品開發(fā)，生產(chǎn)計(jì)劃與控制領(lǐng)域研究工作，E—mail：373980986@qq.com。

Application of improved niche hybrid genetic algorithm in function optimization*

WANG Cong1， KE Hu-qi2, HU Yan-hai1

(1.Faculty of Mechanical Engineering and Mechanics,Ningbo University,Ningbo 315211,China;2.Ningbo David Medical Device Corporation,Ningbo 315712,China)

In order to improve the convergence of classical niche genetic algorithm,strengthen local optimizing ability,a new niche hybrid genetic algorithm is designed.By judging online performance indicatorsXe(s)of algorithm, the simulated annealing algorithm is cleverly fused into later algorithm, and aiming at characteristics of the niche genetic algorithm,choose Gray code coding,at the same time,adaptive genetic crossover operator is designed.Using a Shubert multimodal function to validate the improved algorithm,the results show that the convergence of the new algorithm and evolutionary efficiency is improved,the local optimization ability is also strengthened.

niche； hybrid genetic algorithm； simulated annealing algorithm； online performance indicators

10.13873/J.1000—9787(2017)05—0153—04

2016—07—21

國(guó)家自然科學(xué)基金資助項(xiàng)目(51408323)； 寧波市重大科技專項(xiàng)資助項(xiàng)目(2015C110033)

TP 18

A

1000—9787(2017)05—0153—04