改進(jìn)的混合遺傳算法及其應(yīng)用

劉克浩 肖飛龍

(湖北省疾病預(yù)防控制中心，湖北武漢 430079)

?

改進(jìn)的混合遺傳算法及其應(yīng)用

劉克浩 肖飛龍

(湖北省疾病預(yù)防控制中心，湖北武漢 430079)

本文針對簡單遺傳算法的缺陷，設(shè)計(jì)了一種混合型搜索策略對算法進(jìn)行改進(jìn)。這種改進(jìn)的算法歸一化處理了復(fù)雜的約束條件，利用精英策略和輪盤賭策略選擇最優(yōu)個(gè)體，多點(diǎn)交叉和動(dòng)態(tài)的變異操作使得種群保持多樣性。通過改進(jìn)，使得算法更小幾率陷入局部最優(yōu)，仿真實(shí)驗(yàn)表明，這種算法在穩(wěn)定性、收斂精度上得到了較好的效果。

簡單遺傳算法；混合遺傳算法；測試函數(shù)

遺傳算法是一類起源于自然的智能啟發(fā)式搜索算法。由 Holland[1]在 1975 年提出了這種智能優(yōu)化算法，緊接著他的學(xué)生 Goldberg[2]在Genetic algorithms in search, optimization, and machine learning書中對簡單遺傳算法(SGA)做了完整的描述，這本書涉及到遺傳算法的所有重要的參數(shù)討論，包括交叉算子，變異算子，適應(yīng)度計(jì)算等等，而且將遺傳算法用到現(xiàn)實(shí)生活當(dāng)中。遺傳算法的主要特點(diǎn)是群體搜索策略和群體中個(gè)體之間的信息交換和搜索不依賴于梯度信息。作為啟發(fā)式概率搜索的代表,遺傳算法簡潔明了，適應(yīng)性強(qiáng)，而且可以易于并行化編程設(shè)計(jì)，在生物科學(xué)，數(shù)據(jù)挖掘，機(jī)械控制，智能優(yōu)化等諸多領(lǐng)域有廣泛的應(yīng)用,成為本世紀(jì)關(guān)于智能計(jì)算非常重要的關(guān)鍵詞。

區(qū)別于傳統(tǒng)的優(yōu)化方法，例如梯度下降法[3](gradient descent)、共軛梯度法[4](Conjugate Gradient)、牛頓法[5](Newton-Raphson method)等，這些數(shù)學(xué)優(yōu)化算法理論往往需要對所求問題進(jìn)行求導(dǎo)數(shù)或者偏導(dǎo)數(shù)，因此對于簡單的問題也許能取得好的效果，但是對于那些維數(shù)高而又帶有復(fù)雜苛刻約束條件的問題，不但需要目標(biāo)函數(shù)具有良好的連續(xù)性，很容易陷入局部最優(yōu)。在遺傳算法當(dāng)中，基因染色體的組成往往是首先進(jìn)行編碼，取代原有的數(shù)學(xué)表達(dá)方式，因此算法無論是離散、連續(xù)變量都能輕松解決。目標(biāo)函數(shù)主導(dǎo)這個(gè)算法搜索過程的，不依靠其他輔助外界信息，這樣沒有必要需求設(shè)計(jì)函數(shù)或者解空間的平滑性和連續(xù)性，方便處理許多實(shí)際數(shù)學(xué)模型；另一方面，遺傳演化算法在科學(xué)研究中有很多不同的研究方向，可以對算法的算法參數(shù)、搜索策略進(jìn)行有效地改進(jìn)，也可以與其他啟發(fā)式算法進(jìn)行融合，構(gòu)成混合遺傳算法。

1 混合遺傳算法及其改進(jìn)

啟發(fā)式搜索算法的代表——遺傳算法，為求解優(yōu)化問題提供了一個(gè)模式，它不依賴具體問題，具有極強(qiáng)的魯棒性。算法的基本單位為基因染色體，由眾多染色體組成了種群。種群個(gè)體實(shí)際上是基因染色體編碼組成，在整個(gè)可行域中不斷進(jìn)行進(jìn)化搜索。種群中每個(gè)個(gè)體都被人為給予一個(gè)代表其搜索能力的值，稱為適應(yīng)度值(Fitness)，表示種群個(gè)體適應(yīng)環(huán)境的能力，適應(yīng)度越高，適應(yīng)能力越強(qiáng)。

簡單遺傳算法(SGA)操作簡單，適用于普通的優(yōu)化問題，而針對多約束而且參數(shù)關(guān)系緊密的工程優(yōu)化問題，其收斂速度和搜索精度會(huì)由于問題規(guī)模增加而下降，因此為了在一定程度上避免上述問題，提出相應(yīng)的改進(jìn)策略。

(1)遺傳算法中的諸多參數(shù)會(huì)直接關(guān)聯(lián)到最終的搜索效率和結(jié)果，通過實(shí)驗(yàn)效果修改相應(yīng)的參數(shù)可以提高收斂效果。

(2)隨迭代次數(shù)的遞增, 演化得到的最優(yōu)解在整個(gè)種群的百分比接近100%，意味著搜索結(jié)果在逐漸收斂，可以考慮將上一代的優(yōu)良個(gè)體直接保存至下一代，加快收斂。

(3)在整個(gè)可行域的范圍內(nèi)不斷迭代搜索的過程,根本上是由于在每次迭代過后增加了當(dāng)前較好個(gè)體的存活概率，通過設(shè)計(jì)變異操作，刻意改變個(gè)體的搜索廣度和搜索深度，以達(dá)到搜索整個(gè)解空間的效果。

在改進(jìn)當(dāng)中，值得注意的是，沒有任何一種優(yōu)化算法是能適應(yīng)于所有的問題模型。Wolpert 和Macready在其論文當(dāng)中提出了“No free lunch”理論[6]。

1.1 選擇策略

當(dāng)完成個(gè)體評價(jià)工作后，進(jìn)入選擇操作，這里采用混合策略，一方面保留部分種群中的精英個(gè)體，直接進(jìn)入下一代的個(gè)體當(dāng)中；另一方面利用罰函數(shù)的比例大小進(jìn)行選擇操作，在剩下的個(gè)體中選取產(chǎn)生余下的部分，兩方面綜合形成新的下一代個(gè)體。

Step1.對所有個(gè)體進(jìn)行排序，選取前個(gè)個(gè)體作為精英(也就是說種群數(shù)目越大，精英個(gè)體的數(shù)目雖然增加，但所占比例減少，仍然保留了最優(yōu)個(gè)體)

Step2.對剩余個(gè)體的罰函數(shù)值進(jìn)行歸一化處理，采用輪盤賭法選擇個(gè)個(gè)體

1.2 交叉和變異策略

交叉操作的設(shè)置根據(jù)具體問題而定，如果問題的參數(shù)變量較多，通過約束條件看出變量之間的關(guān)聯(lián)較多，建議采用多點(diǎn)交叉，交叉的段數(shù)范圍在中隨機(jī)取整生成,n代表變量的個(gè)數(shù)。關(guān)于變異操作，這里采取的策略是，能讓種群在進(jìn)化的早期盡可能的進(jìn)行大規(guī)模搜索，在進(jìn)化的晚期盡量在當(dāng)前解集附近搜索，隨著代數(shù)的增加，收斂速度由慢變快。根據(jù)以往的經(jīng)驗(yàn)認(rèn)為，如果變異概率大往往會(huì)丟失一些好的解，相反變異概率小會(huì)讓種群早熟。

1.3 算法描述

Step1.確定算法的初始參數(shù)，初始化種群；

Step2.評估種群，計(jì)算適應(yīng)度值函數(shù)和違約值，得到罰函數(shù)值；

Step3.對所有個(gè)體排序，先采用精英策略選擇子代，剩余子代由輪盤賭生成；

Step4.遍歷每個(gè)個(gè)體，確定每個(gè)個(gè)體的交叉位數(shù)，進(jìn)行交叉操作；

Step5.遍歷每個(gè)個(gè)體，對符合變異條件的個(gè)體進(jìn)行變異操作；

Step6.檢查算法是否結(jié)束，如是則結(jié)束輸出結(jié)果；如否則返回step2，見圖1。

圖1 程序框圖

2 仿真實(shí)驗(yàn)及分析

2.1 測試環(huán)境

硬件環(huán)境：Intel(R) Core(TM)2 Duo CPUT5750 2GHz RAM2GB

軟件環(huán)境：Windows8 VS2012

2.2 測試函數(shù)

我們對混合遺傳算法、普通遺傳算法進(jìn)行基本測試，使用一組標(biāo)準(zhǔn)的benchmark測試集函數(shù)。對不同算法，使用相同的種群規(guī)模和演化代數(shù)以及相同的算法參數(shù)(交叉率、變異率)，通過收斂速率、精度等相關(guān)系數(shù)進(jìn)行比較。這組測試函數(shù)有的是單峰函數(shù)，有的是多峰函數(shù)，搜索空間的區(qū)分度比較大，包含不少局部最優(yōu)點(diǎn)。

F1：Schaffer function

-10≤xi≤10

圖2

F2:：Shubertfunction

圖3

F3:Hansenfunction

圖4

F4:Camelfunction

+xy+(-1+4y2)y2x,y∈[-100,100]

圖5

F5：

圖6

F6：

minf(x,y)=-[xsin(9πy)+ycos(25πx)+20]x,y∈[-10,10]

圖7

F7：

圖8

F8：

圖9

F9：

圖10

FunctionAlgorithmConvergeTimes理論最優(yōu)值實(shí)際最優(yōu)值f1SGA401．0000001．000003HGA671．0000001．000002f2SGA51-186．7309-186．7306HGA74-186．7309-186．7308f3SGA15-176．541793-176．541788HGA23-176．541793-176．541791f4SGA16-1．031628-1．031610HGA37-1．031628-1．031625f5SGA133．0000003．000003HGA383．0000003．000001f6SGA10-39．944506-15．548687HGA23-39．944506-36．687486f7SGA830．0000000．000000HGA950．0000000．000000f8SGA900．0000000．000000HGA990．0000000．000000F9SGA920．0000000．000000HGA990．0000000．000000

2.3 結(jié)果分析

對上述benchmark函數(shù)，兩個(gè)算法均運(yùn)行一百次，統(tǒng)計(jì)最終的結(jié)果。ConvergeTimes表示算法收斂到最優(yōu)值的次數(shù)，次數(shù)越高，算法的穩(wěn)定性越好。理論最優(yōu)值表示該函數(shù)的最小值，實(shí)際最優(yōu)值表示算法能達(dá)到的最優(yōu)值，通過改進(jìn)算法，混合遺傳算法在收斂速度和收斂精度上都得到了一定的提高。對于F2，F(xiàn)3，F(xiàn)5，F(xiàn)6這種解空間中存在多個(gè)局部最優(yōu)值的函數(shù)，改進(jìn)遺傳算法比SGA更加穩(wěn)定，特別是F6，它的局部最優(yōu)值非常多，SGA對處理這種欺騙性很大的函數(shù)非常困難，但混合遺傳算法在跳出局部最優(yōu)解這個(gè)問題上做的比SGA要好很多。

3 結(jié) 語

本文提出了一種混合遺傳算法，這種算法歸一化處理了復(fù)雜的約束條件，利用精英策略和輪盤賭策略選擇最優(yōu)個(gè)體，多點(diǎn)交叉和動(dòng)態(tài)的變異操作使得種群保持多樣性。通過一組benchmark函數(shù)的測試，表明混合遺傳算法比普通遺傳算法在收斂精度和穩(wěn)定性等方面有很大的提高。

1HollandJH.Adaptationinnaturalandartificialsystems1sted.MITPress,1975

2GoldbergDE.Geneticalgorithmsinsearch,optimization,andmachinelearning[M].ReadingMenloPark:Addison-wesley, 1989

3MordecaiAvriel(2003).NonlinearProgramming:AnalysisandMethods.DoverPublishing

4MagnusR.HestenesandEduardStiefel(1952),Methodsofconjugategradientsforsolvinglinearsystems,J.ResearchNat.Bur.Standards49, 409-436.

5 Tjalling J. Ypma Historical Development of the Newton-Raphson Method SIAM Rev.37(4), 531-551

6 D. H. Wolpert and W. G. Macready, “No free lunch theorems for optimization”, IEEE Transactions on Evolutionary Computation, 1(1), 1997, pp.67-82

(責(zé)任編輯：譚銀元)

The Improved Hybrid Genetic Algorithm and its Application Research

LIU Ke-hao,XIAO Fei-long

(Hubei Center for Disease Control and Prevention, Wuhan 430079, China)

In this paper, aiming at the defects of simple genetic algorithm, we design a hybrid search strategy to improve the algorithm. Normalization of this improved algorithm to deal with the complex constraints, using the elite strategy and roulette strategy choice the best individual, multipoint cross and dynamic mutation makes to keep population diversity. Through improvement, makes the algorithm more small chance to fall into local optimum, the simulation experiments show that this algorithm on the stability and convergence accuracy obtained better effect.

Genetic algorithm; Hybrid genetic algorithm; Benchmarks

2015-02-11

劉克浩，主要從事計(jì)算機(jī)應(yīng)用方面的科研工作。

R394

A

1671-8100(2015)03-0034-04