劉立民,潘 偉,龐彥軍,李法朝

(1.河北工程大學 理學院,河北邯鄲 056038;2.河北科技大學 經(jīng)濟管理學院,河北石家莊050018)

遺傳算法[1]是由美國控制論專家Holland提出的一種基于生物進化論及孟代爾基因遺傳理論的搜索型優(yōu)化算法,是近年來在數(shù)據(jù)挖掘、優(yōu)化控制、人工智能、專家系統(tǒng)等領(lǐng)域的一個熱點研究內(nèi)容[2-4],并且在函數(shù)優(yōu)化、機器學習、人工神經(jīng)網(wǎng)絡(luò)、分子生物學和優(yōu)化調(diào)度等領(lǐng)域得到了廣泛應(yīng)用。

盡管遺傳算法思路直觀、操作簡單,但卻常常存在“未成熟”收斂以及收斂精度不高等方面的不足,尤其對大范圍、高精度的優(yōu)化問題往往不能收斂到全局最優(yōu)解。近年來,人們提出許多改進的遺傳算法,但大多是集中在選擇、交叉和變異概率及適應(yīng)度函數(shù)的選取上[5-6],且均具有較強的針對性,沒有從根本上解決上述算法的不足。針對上述不足,結(jié)合遺傳算法的求解機理,提出了多階段復(fù)合型遺傳算法,并利用Markov鏈理論和仿真技術(shù)進行算法的收斂性能分析,為復(fù)雜系統(tǒng)數(shù)值優(yōu)化等方面的優(yōu)化問題提供了依據(jù)。

1 MSC-GA的結(jié)構(gòu)

1.1 問題的提出

現(xiàn)實生活中無論是復(fù)雜優(yōu)化系統(tǒng)還是其他領(lǐng)域的優(yōu)化問題,對精度的研究具有很高的應(yīng)用價值。理論上,當所考慮的優(yōu)化問題存在最優(yōu)解時便一定能夠求出精確的值,但在實際問題中,由于模型的提煉過程存在理論誤差、數(shù)據(jù)的欠缺存在信息誤差、認知觀念的不同存在認識偏差等等,因而常?？紤]的是優(yōu)化問題的滿意解。從直觀的角度來看,優(yōu)化問題變量變化范圍與解的精度具有密切的聯(lián)系,當優(yōu)化變量的變化范圍較大時,便很難求出精度較高的滿意解,而當變化范圍很小時,則易于求出精度較高的滿意解。因此,對尋優(yōu)范圍大、精度要求高的優(yōu)化問題,若能夠按照某種策略,在不損失最優(yōu)解的情況下逐步縮小問題的尋優(yōu)范圍,那么對求得精度較高的滿意解顯然是有利的。

基于以上觀點,提出了多階段復(fù)合型遺傳算法(簡記為MSC-GA),過程分為最優(yōu)預(yù)判和最優(yōu)搜索兩個階段。最優(yōu)預(yù)判階段由幾段相互獨立的遺傳搜索構(gòu)成,其目的是以各次所得的相對滿意解為基礎(chǔ),通過某種策略確定問題最優(yōu)解或滿意解的基本特征,進而結(jié)合某種方法(比如統(tǒng)計規(guī)律、網(wǎng)格理論等)縮小尋優(yōu)范圍;最優(yōu)搜索階段是以最優(yōu)預(yù)判的結(jié)果(即縮小后的尋優(yōu)范圍)為基礎(chǔ),繼續(xù)進行精度更高的遺傳搜索。為了更形象和直觀地體現(xiàn)MSC-GA的結(jié)構(gòu),將之記為(K⊕1)-GA,其中k表示最優(yōu)預(yù)判部分重復(fù)執(zhí)行的次數(shù),1表示最優(yōu)搜索部分。顯然,k=0時,(K⊕1)-GA即為現(xiàn)行的基本遺傳算法SGA,這表明(K⊕1)-GA是SGA的推廣和完善。下面給出(K⊕1)-GA的具體實施策略。

1.2 實施步驟

按照上面的分析和討論,我們可以遵循下面的步驟來設(shè)計(K⊕1)-GA。

Step1選擇個體的編碼形式。

Step2(最優(yōu)預(yù)判)獨立地重復(fù)k次如下操作:隨機產(chǎn)生N個個體構(gòu)成初始種群,并對其進行指定代數(shù)的遺傳進化操作,記錄各次進化結(jié)果中的個體及其對應(yīng)的適應(yīng)度。

Step3(縮小搜索范圍)利用Step2所得的結(jié)果,按照某種原則確定相對滿意解集合,并結(jié)合解的編碼形式縮小尋優(yōu)范圍。

Step4(最優(yōu)搜索)以Step3所得的范圍為基礎(chǔ),進行最后階段的遺傳搜索。

Step5(終止條件檢測)若滿足終止條件,則輸出當前解;若不滿足,則以Step4搜索后所得的范圍為基礎(chǔ),轉(zhuǎn)到Step2。

2 縮小搜索范圍的策略

縮小搜索范圍是(K⊕1)-GA的核心環(huán)節(jié),在實際實施過程中,應(yīng)結(jié)合優(yōu)化問題的性質(zhì)以及編碼的形式來確定具體的方法。就一般情形而言,可以概括為下面的兩種方法:

方法I.對于二進制和符號形式的編碼,可通過確定重要或非重要基因位的策略縮小尋優(yōu)范圍。

方法II.對于實數(shù)編碼,可通過縮短區(qū)位的途徑縮小搜索區(qū)域。

針對(K⊕1)-GA在最優(yōu)預(yù)判階段所得到的K?N個個體,采用如下流程圖來縮小搜索范圍:

下面給出幾種具體的縮小搜索范圍的方法。

2.1 基于統(tǒng)計規(guī)律的縮小范圍方法

利用統(tǒng)計理論可知,只有當數(shù)據(jù)充分多的時候,所得的統(tǒng)計規(guī)律才具有可靠性,因而,當最優(yōu)預(yù)判階段的重復(fù)循環(huán)次數(shù)K較大且所得到的K?N個個體具備一定的共性特征時,可以按照如下策略來縮小尋優(yōu)范圍:

1)確定相對滿意解集C

方法1按一定的比例α(0＜α≤1)確定,即選擇int(K?N)個適應(yīng)度較大的個體作為相對滿意解集C。

方法2以K?N個個體的最大適應(yīng)度W為標準,通過相對最優(yōu)滿意度 β(0＜β＜1)來確定相對滿意解集,即選擇K?N個個體中的適應(yīng)度w滿足(W-w)／W≤β的個體構(gòu)成相對滿意解集C。

2)給出最優(yōu)解的預(yù)判范圍

方法1通過基因位穩(wěn)定率來確定重要基因位,即選擇滿意解集C中個體的基因穩(wěn)定率超過β(0＜β≤1)的基因位作為重要基因位。該方法適應(yīng)于非實數(shù)編碼的情形。

方法2利用對稱分位的方式確定預(yù)判范圍,即以滿意解集的概率分布(直方圖)為基礎(chǔ),通過分布的雙側(cè) β(0＜β≤1)分位點來確定最優(yōu)解的預(yù)判范圍。

2.2 (K⊕1)-GA的實施步驟

當預(yù)判階段所得到的K?N個個體不存在不明顯的共性特征時,利用統(tǒng)計規(guī)律便不能得到可靠程度較高的縮小范圍,為了盡可能地不損失最優(yōu)解的信息,且達到縮小尋優(yōu)范圍的目的,我們按如下步驟,采用Min-Max策略來縮小尋優(yōu)范圍:

步驟1按照某種規(guī)則(如:按一定的比例去掉較差的個體;按照相對滿意度去掉較差的個體,等)得到相對滿意解集C。

步驟2以相對滿意解集C為基礎(chǔ),取其中適應(yīng)度最小的個體及適應(yīng)度最大的個體作為最優(yōu)預(yù)判范圍的下限和上限。

2.3 幾點注明

1)最優(yōu)預(yù)判是為了在不損失最優(yōu)解的前提下逐步的縮小優(yōu)化問題的尋優(yōu)范圍,因此,為了獲得盡可能多的最優(yōu)解的信息,在遺傳操作過程中應(yīng)采用最優(yōu)個體保留策略。

2)K的選擇直接影響到(K⊕1)-GA性能,若太大,則可能導致計算的時效性差,若太小,則可能導致最優(yōu)預(yù)判結(jié)果失真。因而,在具體問題中應(yīng)結(jié)合解的編碼形式、預(yù)判階段的種群規(guī)模以及所選用的縮小范圍的策略來系統(tǒng)地確定K的取值,一般而言,對于基于統(tǒng)計規(guī)律的范圍縮小方法,K的取值不易太小,應(yīng)在4-10之間為好;而對于基于Min-Max的范圍縮小方法,K的取值不易太大,在3-6之間為好。

3)最優(yōu)預(yù)判階段和最優(yōu)搜索階段的的目標和作用是不同的,因而,相應(yīng)的遺傳參數(shù)設(shè)置可以是不同的。一般來說,最優(yōu)預(yù)判階段的變異概率應(yīng)適當大于最優(yōu)搜索階段的變異概率,而最優(yōu)預(yù)判階段的進化代數(shù)要小于最優(yōu)搜索階段的進化代數(shù)。

3 (K⊕1)-GA的收斂性分析

在遺傳算法的搜索過程中,由于第t+1代種群X(t+1)只與第t代種群X(t)有關(guān),且各種群之間的轉(zhuǎn)移概率與時間的起點無關(guān),因而遺傳算法的遺傳序列是一個齊次的Markov鏈。本部分的主要工作是利用Markov鏈理論來分析(K⊕1)-GA的收斂性[7]。

定義1[8]設(shè) X(t)={X1(t),X2(t),…,XN(t)}為遺傳算法的第t代種群(t))表示種群X(t)的最優(yōu)適應(yīng)值,f*=max{f(X)｜X∈S}表示全局最優(yōu)值。若則稱遺傳序列是收斂的。

定義2[9]設(shè)為Markov鏈從狀態(tài)i出發(fā)經(jīng)過n步首次到達狀態(tài)j的概率:1)若對任意狀態(tài) i,j,均存在自然數(shù)m使得則稱是不可約的;2)若對任意狀態(tài)i,j,D={n:n≥0}非空且D的最大公約數(shù)為1,則稱{X(t)}是為非周期的;3)對于狀態(tài)j,若=1,則稱狀態(tài) j是常返的;若稱狀態(tài)j是非常返的。

定義3[9]對于Markov鏈{X(t)的常返狀態(tài),若則稱 i為正常返的;若狀態(tài)空間中任何狀態(tài)都是正常返且非周期的,則稱為遍歷的。

定理1(K⊕1)-GA收斂到最優(yōu)解的概率小于1。

定理2采用最優(yōu)個體保留策略的(K⊕1)-GA的遺傳序列{X(t)依概率1收斂于全局最優(yōu)解。

4 實例仿真

為了進一步分析(K⊕1)-GA的特點和收斂性能,本部分結(jié)合一個具有相當復(fù)雜度且最常用的測試算法性能的函數(shù)進行分析和討論。

例考慮Shaffer函數(shù)[10-11]:

該函數(shù)在定義域內(nèi)只有一個全局最大值點(0,0),最大值為f(0,0)=1。

下面采用二進制編碼和實數(shù)編碼,利用SGA和(K⊕1)-GA分別對問題進行尋優(yōu)處理。其中,各參數(shù)設(shè)置如下:

1)采用二進制編碼

基本遺傳算法:種群大小80,進化最大代數(shù)100,交叉概率pc=0.6,變異概率 pm=0.002,迭代結(jié)果如圖2所示。

(K⊕1)-GA:①最優(yōu)預(yù)判階段:種群大小40,進化最大代數(shù)100,交叉概率pc=0.6,變異概率pm=0.002;預(yù)判次數(shù) k=5,②最優(yōu)搜索階段:種群大小80,進化最大代數(shù)100,交叉概率 pc=0.6,變異概率pm=0.001;③縮小搜索范圍的策略采用尋找重要基因位,以預(yù)判階段所得滿意解集為依據(jù)縮小尋優(yōu)范圍,迭代結(jié)果如圖3、圖4、圖5所示。

2)采用實數(shù)編碼

基本遺傳算法:種群大小80,進化最大代數(shù)100,交叉概率 pc=0.6,變異概率pm=0.002,迭代結(jié)果如圖6所示。

(K⊕1)-GA:①最優(yōu)預(yù)判階段:種群大小80,進化最大代數(shù)100,交叉概率pc=0.6,變異概率pm=0.002;預(yù)判次數(shù)K=5;②最優(yōu)搜索階段:種群大小80,進化最大代數(shù)100,交叉概率pc=0.6,變異概率pm=0.001;③縮小搜索范圍的策略是以預(yù)判滿意解集的概率分布(直方圖)為依據(jù),通過分布的雙側(cè)β(β=0.1)分位點來縮小尋優(yōu)范圍,其迭代結(jié)果如圖7、圖8和圖9所示。

圖2和圖3、圖6和圖7分別表示采用二進制編碼和實數(shù)編碼的SGA和(5⊕1)-GA的100代進化曲線圖(其中橫坐標表示迭代次數(shù),縱坐標表示目標函數(shù)值);圖4和圖5、圖8和圖9為采用二進制編碼和實數(shù)編碼的(5⊕1)-GA在預(yù)判階段所得滿意解的分布直方圖。

自圖2和圖6可以看出,無論采用二進制編碼還是實數(shù)編碼,基本遺傳算法始終不能收斂到精度較高的滿意解;而自圖3和圖7可知,無論采用哪種編碼,(5⊕1)-GA算法均能很好地收斂到全局滿意解。這表明-GA在收斂精度上較基本算法有很大提高。自圖4和圖5,圖8和圖9可以看出,采用二進制編碼和實數(shù)編碼時在預(yù)判階段所得的滿意解以較大的概率落在優(yōu)化變量的全局最優(yōu)解附近,這表明第2部分提出的縮小尋優(yōu)范圍的策略是可行的。

為了進一步分析(K⊕1)-GA的收斂性能,針對上述參數(shù)設(shè)置,分別就二進制編碼和實數(shù)編碼進行了10次獨立的求解試驗,結(jié)果如表1,其中所采用的縮小范圍的策略分別為:

二進制編碼:利用預(yù)判滿意解集,通過尋找重要基因位來縮小尋優(yōu)范圍。

實數(shù)編碼:以預(yù)判滿意解集的概率分布(直方圖)為依據(jù),通過分布的雙側(cè)β(β=0.1)分位點來縮小尋優(yōu)范圍。

表1 二進制編碼和實數(shù)編碼的收斂結(jié)果對比表Tab.1 The comparison of convergence results between binary coding and real coding

由表1可知以看出:1)無論是采用二進制編碼還是實數(shù)編碼,(5⊕1)-GA均具有穩(wěn)定的全局收斂性能;2)采用實數(shù)編碼的(5⊕1)-GA在收斂代數(shù)、收斂時間上明顯比采用二進制編碼的(5⊕1)-GA要低。因而,對于多變量、大范圍的、高精度的連續(xù)型優(yōu)化問題,采用(5⊕1)-GA以及實數(shù)編碼可以達到較好的優(yōu)化效果。

5 結(jié)論

針對基本遺傳算法在進化過程中存在的“早熟”現(xiàn)象以及收斂解精度低等方面的缺點,提出了一種改進的遺傳算法-多階段復(fù)合型遺傳算法,該算法的基本思想是首先尋找問題的滿意解群體,然后以得到的滿意解群體為基準,按照某種策略縮小尋優(yōu)范圍,并繼續(xù)搜索精度更高的全局最優(yōu)解或滿意解。理論分析和仿真技術(shù)表明,該算法不僅具有良好的結(jié)構(gòu)和可操作性,而且在計算效率和收斂穩(wěn)定性方面均明顯優(yōu)于常規(guī)的遺傳算法,為進一步構(gòu)建復(fù)合優(yōu)化方法奠定了基礎(chǔ),在一定程度上推廣和豐富了現(xiàn)有的智能優(yōu)化理論和方法。

[1]SRINIVAS M,PATNAIK M.Genetic algorithm:A survey[J].IEEE Computer,1994,27(6):17-26.

[2]FOGE D B.An introduction to simulatedevolutionary optimization[J].IEEE Trans,on SMC,1999,24(1):3-14.

[3]ATMAR W.Noteson the simulation of evolution[J].IEEE Trans,on SMC,1994,24(1):130-147.

[4]HOLLAND J H.Adaptation in nature and artificial systems[M].USA:Univ.of Michigan,1975.

[5]鞏敦衛(wèi),孫小燕,郭西進.一種新的優(yōu)勝劣態(tài)遺傳算法[J].控制與決策,2002(6):908-912.

[6]韓萬林.遺傳算法的改進[J].中國礦業(yè)大學學報,2001(1):102-105.

[7]劉立民,馬麗濤,龐彥軍,等.基于多保留策略的復(fù)合型遺傳算法及其收效性分析[J].河北工程大學學報(自然科學版),2010,27(1):103-108.

[8]夏道行,吳卓人,嚴紹宗,等.實變函數(shù)與泛函分析[M].北京:高等教育出版社,1979.

[9]方兆本,繆柏其.隨機過程[M].合肥:中國科學技術(shù)大學出版社,1993.

[10]盛驟.概率論與數(shù)理統(tǒng)計[M].北京:高等教育出版社,1989.

[11]王小平,曹立明.遺傳算法理論、應(yīng)用與軟件實現(xiàn)[M].西安:西安交通大學出版社,2002.