遺傳算法在數值優化問題的分析及改進

摘要：本文首先對遺傳算法進行簡單的描述，系統地介紹了標準遺傳算法理論方法， 提出了一種基于共軛梯度法的混合遺傳算法。

關鍵詞：共扼梯度法 遺傳算法 函數優化

一、引言

遺傳算法(Genetic Algorithms，GA)是20世紀60年代由美國J．Holland教授提出的一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法，其主要特點是群體搜索策略和群體中個體之間的信息交換，在整個搜索過程中，對梯度信息的依賴程度將到了最低，而得到了較為理想的結果，尤其在較難解決的搜索方面，傳統的搜索方法無法實現，以及在非線性問題上，遺傳算法顯示出了強大的功能性。

二、標準遺傳算法介紹

（一）流程介紹

遺傳算法實質上是一個迭代過程，在每次迭代中都將保留一個候選群體，并對候選群體中的個體進行評價，首先按照適應度的大小進行選擇何時的樣本個體，然后通過對這些個體進行交叉和變異等遺傳操作，進而產生了新一代群體樣本。重復此過程直到滿足收斂條件。在整個遺傳算法的運算過程中，需要重點把握以下5個方面：1)對參數進行編碼處理；2)設定群體的初始參數；3) 設計適應度函數；4)遺傳設計操作；5) 設定控制參數 (主要是指群體大小以及使用遺傳操作的概率等)。五種要素構成了遺傳算法的主要結構。

（二）算子介紹

標準的遺傳算法的操作算子一般包括選擇(selection)、交叉(crossover)、變異(mutation)三種基本形式。[5]

（1）選擇算子

選擇算子(或稱復制算子)是對群體中的個體按照優勝劣汰的方式進行操作，同時將父代特征遺傳到下一代的過程。其基礎是對群體中的每個個體根據適應值對適應度進行評價，其中具有較高適應度的個體通過遺傳并將特征轉到下一代的概率較為明顯。而適應度較低的個體由于沒有對環境進行很好的適應，因此其特點被遺傳的概率較小，進而被剔除。一般來說，常用的個體選擇的算法算子有以下適應度比例方法、最佳個體保存方法、期望值方法、排序選擇方法幾種形式。

（2）交叉算子

交叉算子(crossover)是指依據交叉概率Pc，對兩個相互交配的染色體進行部分基因的交換，整個過程按照特定的方式有序進行，并最終有兩個新的個體出現。其中Pc是一個系統參數。在遺傳算法中，使用交叉算子產生后代個體來模仿兩個同源染色體通過交配重組形成新染色體的生物進化過程。在遺傳算法中，交叉算子的作用至關重要。一方面，它使在原來的群體中具有優良特性的個體以某種方式進行了保留，同時也開辟了新的基因空間和運算空間。進行保證了群體中的個體具有多樣性的特點。

（3）變異算子

變異操作模仿自然界生物體進化中染色體上某位基因發生的突變現象，從而改變染色體的結構和物理性狀。在遺傳算法中，用變異算子來產生出新的個體，其基本原理是改變在個體編碼串中特定位置的基因值。一般來說，編碼串多由二進制表示，其中是轉換基因位置的基因值，并通過變異概率Pm進行。以最簡單的0-1為例，通過變異操作，變為1-0等。還有一種情況是在被編碼的個體中存在浮點數，對于這種情況，首先需要確定變異點的取值范圍，即為[Umin，Umax]。并根據這一范圍中的某一特點進行實際的變異操作，整個過程需要規范化和標準化。[6]

三、基于共軛梯度的遺傳算法設計

（一）設計思想

共軛梯度法是無約束優化算法中比較常用的算法之一，在運用過程中，具有存儲量小、高效和計算公式簡單等優點，廣泛適用于非線性優化等問題。然而在運算過程中，盡管局部搜索能力較強，而在群居搜索能力上，卻比較差，需要與其他算法進行聯合使用。本文主要對共軛梯度法與遺傳算法進行結合使用，并提出了一種混合遺傳算法，這種算法其過程中首先以GA對群體進行搜索，并確定最優解鎖可能存在的空間領域，以此為基礎進行微調。同時，本文發現共軛梯度法很好地解決了具有狹長山谷的優化問題，并以此為切入點，提出了基于共軛梯度法的改進GA算法的混合遺傳優化算法。

（二）具體設計

1、傳統遺傳算法

1)首先對個體的參數執行初始化處理，在這一基礎上產生了隨機初始群體用于計算；對每個個體的適應值進行計算，進而了解個體特征。

2)根據個體染色體適應值的比例等信息，合理選取具有計算信息的父代。在這一過程中，具有最大適應值的個體可強行將遺傳代碼遺傳到下一代，以便提高運算收斂速度。

3)具體運算中，對固定Pc和自適應Pc進行結合，并交換兩個隨機個體，其原理是結合一點交換法和兩點交換法的運算優點。

4)在對每一個個體的變異運算過程中，可綜合應用普通變異法和大變異相法；使固定Pm和自適應Pm相結合。

5)直到運算過程滿足運算法則，才能夠停止運算準則，此時所得到的結果可認為是全局最優解，運算過程也具有算法收斂性。

6）若運算結果不滿足，轉至步驟2)重新進行運算。

2、共軛梯度法

1)在s內取初值x(0)及精度ε>0。

2)計算方程go=▽f(x(0))，同時設s(0)=-g0，k=0。

3)x(k+1)= x(k)+ λs(k)，g(k+1)= ▽f(x(x+1))，式中λk=argmin f(x(k)+λs(k))。

4)若‖g(k+1)‖≤ε，則迭代結束。否則轉(5)。

5)若k

3、混合算法

1)對群體進行參數初始化操作；

2)運用遺傳算法對運算過程進行迭代處理，在這一過程中，對最優個體進行x*搜索，若在經歷若干迭代過程仍然無法尋找更好的個體，停止搜索，轉至3）

3）應用共扼梯度法搜索，在進行若干代后，如果仍然找不到比個體x*更好的點，則視x*為最優，結束進程。若找到假定點y，其函數值較x*相比較優，則產生同時確定包含y的群體，返回操作2）執行。

四、小結

本文所提出的基于共軛梯度法的混合遺傳算法，通過實驗證明，對于促進遺傳算法跳出擺脫“早熟收斂”狀態，同時以概率1收斂到全局最優值，具有較好的效果。混合遺傳算法的求解結果在精度和用時兩個方面都有了一定程度的提高。

參考文獻:

[1]惲為民， 席裕庚. 遺傳算法的運行機理分析[J]. 控制理論與應用， 1996， 13( 3)

[2] 牛向陽，高成修.基于混合編碼的混合遺傳算法[J].數學雜志，2008，28(4)

[3] 季力，王曉棟，楊旭曙，劉樹深，王連生.遺傳算法結合共轆梯度法改進BP算法人工神經網絡用于環境雌激素的QSAR研究[J].科學通報，2007，52(18)