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

王 輝 徐曉英

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

0 引 言

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

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

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

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

1 遺傳算法收斂定義及特點

設(shè)S為個體空間，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，若

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

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

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

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

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

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

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

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

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

2.2 種群的多樣性

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

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

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

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

2.3 停機準(zhǔn)則

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

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

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

2.4 數(shù)值實驗

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

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

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

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

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

2）Shubert測試函數(shù)

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

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

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

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

3 結(jié)束語

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

［1］田雨波，錢 鑒．計算智能與計算電磁學(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］．長沙：中南大學(xué)，2009．

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

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

［7］朱葛?。诓罘诌M化和粗糙集理論的多目標(biāo)優(yōu)化算法的研究［J］．科技通報，2012，28（2）：80－84．

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