王 聰， 柯滬琦， 胡燕海

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

應用技術

改進的小生境混合遺傳算法在函數優(yōu)化上的應用*

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

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

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

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

0 引 言

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

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

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

1 經典小生境遺傳算法存在的問題

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

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

2 小生境混合遺傳算法

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

2.1 模擬退火算法

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

算法描述如下：

1)設置一個初始點，計算得到目標函數值；

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

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

4)使用變異操作于初始點，初始點變異后，計算得到目標函數值的Δ增量；

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

6)如果t小于結束步數，則t=t+1，轉向第(4)步；

7)如果未達到冷卻狀態(tài)，則θ=T(t)，轉向第(2)步；如果達到冷卻狀態(tài)，則輸出當前最優(yōu)點，計算結束。

2.2 格雷碼編碼

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

2.3 遺傳選擇算子

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

2.4 自適應交叉算子

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

(1)

式中 Pc為當前代數對應的交叉概率；Pn為常規(guī)交叉概率；t為當前進化代數；C為一個常數。

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

2.5 小生境操作

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

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

(2)

2)當個體Xi和Xj的海明距離小于L時，對個體Xi和Xj中適應度較低的個體施加一個罰函數Penalty。

3)對種群按適應度大小進行降序排列，保留排名在前n位的個體，組成新的群體。

3 混合遺傳算法構成框架

在線性能指標(遺傳算法性能的評價指標之一)指

(3)

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

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

圖1 改進的小生境遺傳算法流程圖

圖1中的P(0

4 多峰值函數應用

為了測試經改進的小生境混合遺傳算法的性能，本文選用了Shubert多峰值函數，并與經典小生境遺傳算法對Shubert函數的優(yōu)化結果進行了比較。

4.1Shubert函數

Shubert函數可描述為

(4)

這是一個二元多峰值函數，如圖2所示，其定義域內共有760個局部最小點，其中18個點為全局最小點，全局最小值為f=-186.731。

用小生境遺傳算法求解函數時，需用式(5)進行目標函數值到個體適應度的變換處理

(5)

圖2 Shubert多峰值函數圖像

4.2 參數設置

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

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

4.3 實驗結果

圖3為兩種算法各實驗50次所繪制的平均進化圖。算法1為經典小生境遺傳算法，算法2為改進的小生境混合遺傳算法。

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

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

圖3 兩種算法進化結果比較

5 結 論

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

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

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

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

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

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

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

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

[8] 姜封國.結構系統(tǒng)基于可靠性的優(yōu)化設計研究[D].哈爾濱:哈爾濱工程大學，2009.

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

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

[11] 劉 楠.改進的小生境遺傳算法在多目標車間調度中的應用研究[D].大連:計算機應用技術，2010.

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

[13] 程紹清.自適應微型遺傳算法在動態(tài)本構參數反演中的應用[D].長沙:湖南大學，2010.

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

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

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

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

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

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

[20] 李 兵.瑞雷波技術在巨粒土路基檢測中的應用[D].重慶:重慶交通大學，2011.

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

[22] 周洪偉.遺傳算法“早熟”現象和改進策略研究[D].鄭州:解放軍信息工程大學，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- )，男，碩士，研究方向為遺傳算法，嵌入式工程。

胡燕海(1965- )，男，通訊作者，博士，教授，從事機電液產品開發(fā)，生產計劃與控制領域研究工作，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

國家自然科學基金資助項目(51408323)； 寧波市重大科技專項資助項目(2015C110033)

TP 18

A

1000—9787(2017)05—0153—04