劉克浩 肖飛龍

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

?

改進的混合遺傳算法及其應用

劉克浩 肖飛龍

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

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

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

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

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

1 混合遺傳算法及其改進

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

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

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

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

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

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

1.1 選擇策略

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

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

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

1.2 交叉和變異策略

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

1.3 算法描述

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

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

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

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

Step5.遍歷每個個體，對符合變異條件的個體進行變異操作；

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

圖1 程序框圖

2 仿真實驗及分析

2.1 測試環(huán)境

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

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

2.2 測試函數(shù)

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

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)值實際最優(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 結果分析

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

3 結 語

本文提出了一種混合遺傳算法，這種算法歸一化處理了復雜的約束條件，利用精英策略和輪盤賭策略選擇最優(yōu)個體，多點交叉和動態(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

(責任編輯：譚銀元)

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

劉克浩，主要從事計算機應用方面的科研工作。

R394

A

1671-8100(2015)03-0034-04