基于遺傳算法收斂特性的停機(jī)準(zhǔn)則＊

王 輝 徐曉英

（武漢理工大學(xué)理學(xué)院 武漢 430070）

0 引 言

作為一類模擬進(jìn)化計(jì)算方法，遺傳算法的基本框架、構(gòu)成要素及操作策略已經(jīng)形成，其搜索機(jī)理及收斂性理論也得到了深入的探索研究．目前，關(guān)于遺傳算法的基礎(chǔ)理論，較為完善的有Schema理論、遺傳算法的馬氏鏈分析及遺傳算法的收斂理論［1］．

與收斂理論緊密相關(guān)的另一基本理論問題是遺傳算法的收斂速度該如何表達(dá)．針對(duì)這一基本問題，文獻(xiàn)［2］中Aytug和Koehlen利用馬氏鏈中的首次訪問時(shí)間概念，估計(jì)出遺傳算法在一定的置信水平下訪問到所有種群狀態(tài)所需要的進(jìn)化代數(shù)；文獻(xiàn)［3］從轉(zhuǎn)移矩陣的第二大特征值出發(fā)研究了標(biāo)準(zhǔn)遺傳算法的停時(shí)準(zhǔn)則；文獻(xiàn)［4］中基于鞅理論研究了保留精英策略遺傳算法的收斂速度，并給出了最大收斂代數(shù)的估算公式．

從目前多種估算方式和判斷準(zhǔn)則的研究中可以發(fā)現(xiàn)：（1）在判斷遺傳算法是否達(dá)到最優(yōu)解時(shí)很少甚至并未考慮前代的信息，過于拘泥于概率意義上的計(jì)算；（2）在推導(dǎo)遺傳算法最大收斂代數(shù)的估算公式中利用到全局最優(yōu)解或最優(yōu)解域的信息，而如何判斷種群已達(dá)到最優(yōu)解并未給出．

本文從遺傳算法收斂性的定義出發(fā)，分析遺傳算法的收斂特點(diǎn)，利用不同種群中最優(yōu)個(gè)體適應(yīng)值的一致性、種群的多樣性分布，提出判斷算法自動(dòng)停止迭代的方法．為建立合適的停機(jī)準(zhǔn)則及統(tǒng)一的遺傳算法收斂速度度量方法提供參考．

1 遺傳算法收斂定義及特點(diǎn)

設(shè)S為個(gè)體空間，SN為種群空間，P為SN上的概率分布，｛（n）｝是遺傳算法所生成的第n代種群序列，f：s→R＋為適應(yīng)值函數(shù)，記全體最優(yōu)解集為M＝｛X；?Y∈S有f（X）≥f（Y）｝．

定義2 （幾乎必然收斂）稱種群序列｛Xˉ（n）｝幾乎處處弱收斂到全局最優(yōu)解集M，若

從上述的定義可以看出，如果遺傳算法收斂，不管是依概率收斂還是幾乎必然收斂，不管是強(qiáng)收斂還是弱收斂，必定存在種群序列｛ˉX（i）｝，該序列與最優(yōu)解集的交集不為空集，并且，這樣的種群序列不止一組［5－8］．

在計(jì)算過程中，如何判斷種群序列｛ˉX（i）｝與最優(yōu)解集的關(guān)系是判斷是否停止迭代的重要依據(jù)．而如何確定問題的最優(yōu)解集或者最優(yōu)解又是分析上述關(guān)系的關(guān)鍵．

2 停機(jī)準(zhǔn)則研究

2.1 不同種群最優(yōu)個(gè)體適應(yīng)值的一致性

通過對(duì)遺傳算法種群序列收斂的定義及其特點(diǎn)的分析，可以看出收斂的遺傳算法能夠到達(dá)最優(yōu)解集．如果種群序列｛ˉX（i）｝到達(dá)最優(yōu)解集，并且該算法采用最優(yōu)個(gè)體保留策略，對(duì)于序列｛ˉX（k）；k＞i｝，則必含最優(yōu)解集的值，即使不采用最優(yōu)個(gè)體保留策略，在第i代以后的種群中，必然還將存在能夠到達(dá)最優(yōu)解集的序列．將第i代種群序列的最優(yōu)個(gè)體適應(yīng)值記為fmax，i，并將其存放在集合B中．

通常情況下，某個(gè)體在多代種群中被作為最佳個(gè)體而被保存下來，則說明該個(gè)體具有優(yōu)良的基因，其適應(yīng)自然的能力極強(qiáng)而不致被淘汰，其個(gè)體最接近或者就是問題的最優(yōu)解．反映到算法中，設(shè)集合B大小為m，將第一代種群序列｛ˉX（1）｝的最優(yōu)個(gè)體適應(yīng)值fmax，1存入集合B中，然后進(jìn)行遺傳操作，得到的下一代種群序列｛ˉX（2）｝的最優(yōu)個(gè)體適應(yīng)值記為fmax，2，存入集合B中，依次進(jìn)行下去，直到將集合B存滿為止．將集合B中不同種群最優(yōu)個(gè)體適應(yīng)值的一致性記為R．

如果B已經(jīng)存滿而所得R值不能滿足要求，則繼續(xù)進(jìn)行遺傳操作運(yùn)算，如果獲得的fmax，m＋1比B中較差個(gè)體適應(yīng)值更優(yōu)，則將fmax，m＋1取代B中的最小值，依次進(jìn)行下去，直到所得結(jié)果滿足要求為止．

R值在一定程度上反映了種群最優(yōu)個(gè)體適應(yīng)值作為最優(yōu)解的可信度，當(dāng)m取較大的值并且R值趨于1時(shí)，說明不同種群最優(yōu)個(gè)體的適應(yīng)值一致性較強(qiáng)，取B中的最大值作為問題的最優(yōu)解的可信度比較的大．在實(shí)際應(yīng)用中，m值依具體情況而定．

然而，僅采用不同種群最優(yōu)個(gè)體適應(yīng)值的一致性判斷算法達(dá)到最優(yōu)解容易使算法陷入局部極值而停止迭代，故需考慮種群的多樣性．

2.2 種群的多樣性

遺傳算法在計(jì)算過程中對(duì)包含可能解的種群反復(fù)使用遺傳學(xué)的基本操作，不斷地生成新的種群，并以全局并行搜索技術(shù)來搜索問題域中的最優(yōu)個(gè)體，以求得滿足要求的最優(yōu)解或準(zhǔn)最優(yōu)解．遺傳算法在運(yùn)行的過程中可能會(huì)暫時(shí)停留在某些非最優(yōu)點(diǎn)上，直到變異發(fā)生使其躍遷到另一個(gè)最優(yōu)點(diǎn)上．由此可以斷定，隨著種群多樣性的增加，在上述不同種群個(gè)體最優(yōu)值的一致性為1的情況下所得的最優(yōu)解作為全局最優(yōu)解的可信度更大．

種群的多樣性不是指一代種群，而是指到停時(shí)為止所有種群個(gè)體的多樣性．設(shè)當(dāng)代種群中包含不同個(gè)體數(shù)目記為其中k為種群中個(gè)體所在的位置，N為種群規(guī)模．當(dāng)遺傳算法迭代n次后，所有種群所包含的不同個(gè)體的數(shù)目為所有種群的多樣性記為V．

V值一定程度上反映了算法搜索域在整個(gè)問題的可行解域中所占的比例，當(dāng)V值趨于1時(shí)，說明遺傳算法搜索了所有的可行解，這樣，所得到的最優(yōu)個(gè)體必然是問題的最優(yōu)解．

在實(shí)際的計(jì)算中，采用式（2）會(huì)使算法的復(fù)雜度大大增加．對(duì)實(shí)際問題，可以考慮將個(gè)體空間進(jìn)行 劃 分 h 塊，令 S記 δi＝如此，則V可簡(jiǎn)化為

2.3 停機(jī)準(zhǔn)則

設(shè)遺傳算法的停機(jī)判斷因子為η，η表達(dá)式如下

當(dāng)η→1時(shí)，算法停止迭代，所得的計(jì)算結(jié)果可作為問題的最優(yōu)解．上式中沒有用到具體的編碼方式，僅從不同種群最優(yōu)個(gè)體適應(yīng)值、種群的多樣性出發(fā)研究停機(jī)準(zhǔn)則，故該式的適用范圍較廣．在實(shí)際的應(yīng)用中，B中所包含元素的個(gè)數(shù)以及可行域的劃分影響所得結(jié)果的可信度，需著重考慮．

對(duì)于標(biāo)準(zhǔn)遺傳算法，通過馬氏鏈模型可以看出，該算法不能保證得到全局最優(yōu)解，然而可以達(dá)到種群空間中任何狀態(tài)無限多次，如此，從上述停機(jī)判斷角度分析，標(biāo)準(zhǔn)遺傳算法的停機(jī)判別因子η能夠無限接近于1，故從實(shí)用的角度來講，標(biāo)準(zhǔn)遺傳算法是有效的．

2.4 數(shù)值實(shí)驗(yàn)

為驗(yàn)證本文所提出的遺傳算法停機(jī)準(zhǔn)則的可行性，下面給出求De Jong函數(shù)和Shubert函數(shù)最小值的實(shí)驗(yàn)，并與不采用該停機(jī)準(zhǔn)則所計(jì)算的結(jié)果進(jìn)行比較．

1）De Jong測(cè)試函數(shù)

遺傳算法的主要參數(shù)：采用二進(jìn)制編碼，個(gè)體數(shù)量100，適應(yīng)度比例選擇算子，交叉概率0．7，變異概率0．035，停止迭代次數(shù)分別設(shè)置為100，200，300，400，各個(gè)迭代次數(shù)計(jì)算5次，取最小值．所得結(jié)果見表1．如果采用停機(jī)準(zhǔn)則，遺傳算法參數(shù)不變，最優(yōu)解｜B｜＝80，區(qū)間劃分為203個(gè)，η＝0．999 9，計(jì)算3次，結(jié)果見表2．

表1 設(shè)定的迭代次數(shù)與函數(shù)最小值

表2 滿足條件自動(dòng)停止的迭代次數(shù)與函數(shù)最小值

2）Shubert測(cè)試函數(shù)

遺傳算法的主要參數(shù)：采用二進(jìn)制編碼，個(gè)體數(shù)量50，適應(yīng)度比例選擇算子，交叉概率0．7，變異概率0．03，停止迭代次數(shù)分別設(shè)置為20，30，40，50，各個(gè)迭代次數(shù)計(jì)算5次，取最小值．所得結(jié)果見表3．如果采用停機(jī)準(zhǔn)則，遺傳算法參數(shù)不變，最優(yōu)解｜B｜＝10，區(qū)間劃分為100個(gè)，η＝0．999 9，計(jì)算4次，結(jié)果見表4．

表3 設(shè)定的迭代次數(shù)與函數(shù)最小值

表4 滿足條件自動(dòng)停止的迭代次數(shù)與函數(shù)最小值

從該實(shí)驗(yàn)中，可以看出，利用停機(jī)準(zhǔn)則設(shè)置算法停止迭代的條件，實(shí)現(xiàn)了目標(biāo)函數(shù)達(dá)到最優(yōu)解后自動(dòng)停機(jī)的目的．

3 結(jié)束語(yǔ)

從遺傳算法收斂性定義出發(fā)，研究了遺傳算法的自動(dòng)停機(jī)準(zhǔn)則，從式（4）中可以看出，該準(zhǔn)則只與不同種群最優(yōu)個(gè)體適應(yīng)值、種群多樣性有關(guān)，使得該公式有較廣的適用范圍．停機(jī)判斷因子反映了遺傳算法所求問題最優(yōu)解的可信度，η越接近于1，則所求最優(yōu)解的可信度越高．而在停機(jī)判別因子及各個(gè)參數(shù)的設(shè)置上，需根據(jù)具體需要加以適當(dāng)限定．同時(shí)，該停機(jī)準(zhǔn)則為建立恰當(dāng)?shù)亩攘繕?biāo)準(zhǔn)來客觀評(píng)價(jià)遺傳算法的各種執(zhí)行策略及時(shí)間復(fù)雜度提供參考．

［1］田雨波，錢 鑒．計(jì)算智能與計(jì)算電磁學(xué)［M］．北京：科學(xué)出版社，2008．

［2］AYTUG H，KOEHLER G J．Stopping criteria for finite length genetic algorithms［J］．INFORMS Journal on Computing，1996（8）：183－191．

［3］PARAG C P，GARY J K．A general steady state distribution based stopping criteria for finite length genetic algorithms［J］．European Journal of Operational Research，2007，176：1436－1451．

［4］鄺溯瓊．遺傳算法參數(shù)自適應(yīng)控制及收斂性研究［D］．長(zhǎng)沙：中南大學(xué)，2009．

［5］張文修，梁 怡．遺傳算法的數(shù)學(xué)基礎(chǔ)［M］．西安：西安交通大學(xué)出版社，2003．

［6］畢曉君，肖 婧．基于自適應(yīng)差分進(jìn)貨的多目標(biāo)進(jìn)化算法［J］．計(jì)算機(jī)集成制造系統(tǒng)，2011，17（12）：55－58．

［7］朱葛俊．基于差分進(jìn)化和粗糙集理論的多目標(biāo)優(yōu)化算法的研究［J］．科技通報(bào)，2012，28（2）：80－84．

［8］李 珂，鄭金華．一種改進(jìn)的基于差分進(jìn)化的多目標(biāo)進(jìn)化算法［J］．計(jì)算機(jī)工程與應(yīng)用，2008，44（29）：40－43．