基于遺傳算法收斂特性的停機準則＊

王 輝 徐曉英

（武漢理工大學理學院 武漢 430070）

0 引 言

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

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

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

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

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

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

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

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

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

2 停機準則研究

2.1 不同種群最優個體適應值的一致性

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

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

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

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

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

2.2 種群的多樣性

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

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

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

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

2.3 停機準則

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

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

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

2.4 數值實驗

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

1）De Jong測試函數

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

表1 設定的迭代次數與函數最小值

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

2）Shubert測試函數

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

表3 設定的迭代次數與函數最小值

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

從該實驗中，可以看出，利用停機準則設置算法停止迭代的條件，實現了目標函數達到最優解后自動停機的目的．

3 結束語

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

［1］田雨波，錢 鑒．計算智能與計算電磁學［M］．北京：科學出版社，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］鄺溯瓊．遺傳算法參數自適應控制及收斂性研究［D］．長沙：中南大學，2009．

［5］張文修，梁 怡．遺傳算法的數學基礎［M］．西安：西安交通大學出版社，2003．

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

［7］朱葛俊．基于差分進化和粗糙集理論的多目標優化算法的研究［J］．科技通報，2012，28（2）：80－84．

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