多階段復(fù)合型遺傳算法的結(jié)構(gòu)及性能研究

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

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

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

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

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

1.1 問(wèn)題的提出

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

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

1.2 實(shí)施步驟

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

Step1選擇個(gè)體的編碼形式。

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

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

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

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

2 縮小搜索范圍的策略

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

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

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

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

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

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

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

1)確定相對(duì)滿意解集C

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

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

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

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

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

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

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

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

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

2.3 幾點(diǎn)注明

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

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

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

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

在遺傳算法的搜索過(guò)程中,由于第t+1代種群X(t+1)只與第t代種群X(t)有關(guān),且各種群之間的轉(zhuǎn)移概率與時(shí)間的起點(diǎn)無(wú)關(guān),因而遺傳算法的遺傳序列是一個(gè)齊次的Markov鏈。本部分的主要工作是利用Markov鏈理論來(lái)分析(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)過(guò)n步首次到達(dá)狀態(tài)j的概率:1)若對(duì)任意狀態(tài) i,j,均存在自然數(shù)m使得則稱是不可約的;2)若對(duì)任意狀態(tài)i,j,D={n:n≥0}非空且D的最大公約數(shù)為1,則稱{X(t)}是為非周期的;3)對(duì)于狀態(tài)j,若=1,則稱狀態(tài) j是常返的;若稱狀態(tài)j是非常返的。

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

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

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

4 實(shí)例仿真

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

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

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

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

1)采用二進(jìn)制編碼

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

針對(duì)基本遺傳算法在進(jìn)化過(guò)程中存在的“早熟”現(xiàn)象以及收斂解精度低等方面的缺點(diǎn),提出了一種改進(jìn)的遺傳算法-多階段復(fù)合型遺傳算法,該算法的基本思想是首先尋找問(wèn)題的滿意解群體,然后以得到的滿意解群體為基準(zhǔn),按照某種策略縮小尋優(yōu)范圍,并繼續(xù)搜索精度更高的全局最優(yōu)解或滿意解。理論分析和仿真技術(shù)表明,該算法不僅具有良好的結(jié)構(gòu)和可操作性,而且在計(jì)算效率和收斂穩(wěn)定性方面均明顯優(yōu)于常規(guī)的遺傳算法,為進(jìn)一步構(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),孫小燕,郭西進(jìn).一種新的優(yōu)勝劣態(tài)遺傳算法[J].控制與決策,2002(6):908-912.

[6]韓萬(wàn)林.遺傳算法的改進(jìn)[J].中國(guó)礦業(yè)大學(xué)學(xué)報(bào),2001(1):102-105.

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

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

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

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

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