淺談遺傳算法的研究與改進

【摘 要】遺傳算法是模擬自然界生物進化機制的概率性搜索算法，可以處理傳統搜索方法難以解決的非線性問題。但是經典遺傳算法存在局部收斂、收斂速度慢等缺點，這使得經典遺傳算法有時很難找到全局最優解。本文針對經典遺傳算法中所存在的缺點，采用階段式的適應度函數、基于競爭機制的交叉方式和仿粒子群變異操作，使遺傳算法的收斂速率、全局收斂概率都得到了較大的提高。

【關鍵詞】遺傳算法 適應度 交叉操作 仿粒子群變異

【中圖分類號】TP18 【文獻標識碼】A 【文章編號】1674－4810（2011）11－0012－04

一 遺傳算法

遺傳算法（Genetic Algorithm，簡稱GA）是Holland在研究自然遺傳現象與人工系統的自適應行為時，模擬生物進化現象，并采用自然進化機制來表現復雜現象的一種全局群體搜索算法。遺傳算法的基本思想起源于Darwin進化論和Mendel的遺傳學說。作為一類智能計算工具和學習算法，由于其實現簡單、對目標函數要求不高等特性，遺傳算法已廣泛應用于如人工智能、組合優化等研究領域。

1．遺傳算法的優越性

遺傳算法（Genetic Algorithm）利用某種編碼技術作用在稱為染色體的二進制串上，模擬由這些串組成的個體的進化過程。通過有組織的、隨機的信息交換來重新結合那些適應性好的串，在每一代中，利用上一代串結構中適應性好的位和段來形成一個新的串的群體，同時在串結構中嘗試用新的位和段來代替原來的部分以形成新的個體，以增加種群的多樣性。遺傳算法的最大優點是能夠通過群體間的相互作用，保存已經搜索到的信息，這是基于單次搜索過程的優化方法所無法比擬的。但是，遺傳算法也存在著計算速度較慢，并且容易陷入局部最優解的問題中。

遺傳算法的優越性歸功于它與傳統搜索方法不同的特定結構。

第一，遺傳算法的操作對象是編碼，對問題的限制極少，對函數的一些約束條件如連續性、可導性等不做要求，減少了要解決問題的復雜性。

第二，遺傳算法同時搜索解空間內的許多點，因而可以有效地防止搜索過程中收斂到局部最優解，并獲得全局最優解，與其他單點搜索的方法相比，在計算時間上也有較大的優勢。

第三，遺傳算法使用遺傳操作時是按概率在解空間進行搜索，因而既不同于隨機搜索，也不同于枚舉法那樣盲目地舉例，而是一種有目標、有方向的啟發式搜索。

2．遺傳算法的基本步驟

遺傳算法的實現中包括復制、交叉、變異三個算子，需要確定關鍵的幾個參數與標準包括：種群規模、基因編碼、適值函數、選擇概率、遺傳算子以及停機準則。下面分別對其進行說明：

第一，表示法與適應度計算。標準遺傳算法（二進制編碼）作用于確定長度的二進制位串上，即I＝{0，1}l。假設需要

解決如下函數優化問題 ，一般

是將位串分為n段，每段長度為lx，即l＝n#8226;lx，每段表示分量

xi∈［ui，vi］的二進制代碼。位段譯碼函數 的常見形式為：

…（1）

其中 … 記為個體 … 的第

i段。把位段譯碼函數 組合成一個個體的譯碼函數 … ，則適應度函數可設置為 ，其中δ為比例變換函數，作用之一是確保適應值為正值，并且最好使個體的適應度值最大。常見的比例變換有線性比例、冪比例和指數比例等。

第二，交叉。交叉操作是將已有個體組合出新個體，使兩個個體的有效信息得以遺傳到下一代，并可能得到新的個體信息。在遺傳算法中，交叉操作是主要的遺傳操作，它把兩個不同個體上的有用段組合在一起，GA的性能在很大的程度上依賴所使用的交叉算子。交叉操作算子r'∶I μ→I也是作用在位串上，以概率pc對兩個個體進行交叉，pc的作用范圍一般為［0.6，1.0］。兩個父輩個體s＝（s1，…，sl），v＝（v1，…，vl）被隨機地從群體中選擇而進行交叉，產生了兩個子代個體：

s'＝（s1，…，sh－1，sh，vh－1，…，vl，） （2）

v'＝（v1，…，vh－1，vh，sh－1，…，sl，） （3）

其中交叉點h為1到l之間的一個隨機整數。這種交叉即為一點交叉，通過選擇更多的交叉點并交替地變換交叉點之間的位段，就可以把一點交叉擴展到m點交叉算子。另外還有一些其他形式的交叉算子，如一致交叉算子等。不過目前還沒有明確的理論或可靠的實驗證據來決定哪一種交叉算子是最適合的。

第三，變異。變異操作的目的是通過隨機改變染色體的某些基因來引入新個體，增加種群多樣性，并在一定程序上進行局部搜索。相對于交叉操作，變異操作的設計和實現更為簡單和靈活。在標準遺傳算法中，變異一般被看作為輔助算子，它作用在位串上，以較小的概率pm隨機地改變串上的每一位（即相應位上的0變為1，或者1變為0）。變異概率pm的值一般為0.001到0.01之間，它不依賴目標變量的維數

和位串的總長。個體（s1，…，sl）經變異算子 作用后

變為（ … ），其中：

…（4）

這里θi是0與1之間的一致隨機數，對串上的每一位都要重新采樣。常用的變異操作包括：（1）互換：隨機變換若干不同位置上的不同基因。（2）逆序：將某兩隨機位置間的基因串逆序。（3）插入：即將某一位置上的基因（或某一段位置上的基因串）插入到另一位置之前或之后，若兩位置相鄰，則該操作也稱為漂移。

第四，選擇。標準遺傳算法采用的是一種依據概率復制的選擇算子s∶I μ→I μ，個體ai的復制概率由它的相對適應度給出：

…（5）

按照這個概率分布選取μ個個體產生下一代父輩群體。顯然該選擇算子不適于出現負適應度值和最小化任務的情況，此時需采用適應度值比例轉換。綜上所述，標準遺傳算法的主要步驟可描述如下：

二 遺傳算法的改進

1．一般自適應遺傳算法

經典遺傳算法（CGA）采用的都是固定參數，由于遺傳算法從本質上說是一種動態自適應的進化過程，因此固定的參數設置則是對遺傳算法性能的一種局限和束縛。經典遺傳算法在進化過程中，各遺傳算子的參數保持不變。由于在進化后期，種群內個體的多樣性大幅度減小，適應值接近，因此選擇操作的選擇壓力可能不夠，致使算法接近隨機搜索狀態。

針對CGA存在的這些問題，Srinvivas等人提出自適應遺傳算法（Adaptive GA，AGA），即交叉概率Pc和變異概率Pm能夠隨適應度自動改變，遺傳算法的參數中交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關鍵所在，直接影響算法的收斂性，Pc越大，新個體產生的速度就越快。然而，Pc過大時遺傳模式被破壞的可能性也越大，使得具有高適應度的個體結構很快就會被破壞；但是如果Pc過小，會使搜索過程緩慢，以至停滯不前。對于變異概率Pm，如果Pm過小，就不易產生新的個體結構；如果Pm取值過大，那么遺傳算法就變成了純粹的隨機搜索算法。

當種群中每個個體的適應度趨于一致或趨于局部最優時，使二者增加，而當種群適應度比較分散時，使二者減小，同時對適應度高于群體平均適應度的個體，采用較低的交叉和變異概率，使性能優良的個體進入下一代，而低于平均適應度的個體，采用較高的交叉和變異概率，使性能較差的個體被淘汰。因此，自適應的Pc和Pm能夠提供相對某個解的最佳Pc和Pm。自適應遺傳算法在保持群體多樣性的同時，保證遺傳算法的收斂性。自適應遺傳算法由于改進了各遺傳算子的參數，使算法能夠適應于種群進化各個階段的特征，使算法的優化效率和解的質量得到提高。

2．改進的遺傳算法

經典遺傳算法的局部搜索能力較差，一般對經典遺傳算法進行適當的改進或將遺傳算法與傳統的基于問題的啟發式搜索技術相結合形成混合遺傳算法來解決這個問題。設計混合遺傳算法有三條指導性原則：（1）采用原有算法中的編碼技術；（2）吸收原有算法的優點；（3）改造遺傳算子。

根據這三個指導原則本文在保留一般自適應算法的編碼方式、變異和交叉概率設定的基礎上，對一般的自適應算法的適應度函數、交叉方式、變異方式做出改進，提出了改進的混合遺傳算法（Hybrid GA， HGA）。最后，通過實驗說明了改進算法的優越性。（1）適應度函數的改進。適應度函數是評價個體適應環境的能力，是選擇操作的依據，它的好壞能直接影響遺傳算法的性能。適應度函數是由目標函數轉換而成的。（2）交叉方式的改進。GA交叉算子是模仿自然界有性繁殖的基因重組過程，在該過程中群體的個體品質得以提高。直觀來講，選擇算子將原有的優良基因遺傳給下一代個體，而交叉算子則可以生成包含更多優良基因的新個體。交叉方式的設計，一般與所求問題的特征有關。通常需要考慮如下因素：第一，必須保證優良基因能夠在下一代中有一定的遺傳和繼承的機會；第二，必須保證通過交叉操作存在一定的生成優良基因的機會；第三，交叉方式的設計與問題編碼緊密相關，必須結合編碼的結構來設計高效的交叉算子。（3）變異方式的改進。變異即對群體中個體的某些基因作出變動。變異的目的有兩個：一個是使遺傳算法具有局部的隨機搜索能力；另一個是保持群體的多樣性。變異在GA中的作用是第二位，與交叉算子相比，當變異概率較小時，在進化初期模式存活概率比較高；在進化穩定期，與交叉算子下的模式存活概率基本相同；當變異概率比較大時，變異算子作用下模式的存活概率比交叉算子下要小得多。

3．算法步驟

Step1采用實數編碼產生初始種群，在函數定義域內按照均勻分布隨機產生μ個個體{xi}（i＝1，2，…，μ），設定最大進化代數設為T。

Step2計算每個個體的函數值，之后根據計算種群函數的平均值，最后按照本文設定的適應度函數計算當前種群中每個個體的適應度。

Step3最優保存策略，結合文獻本文將最優保存策略算法做如下修改：第一步計算每個個體的函數值，然后排序，找出最優解，最差解；第二步若上一代最優解的函數值比當前最優解的函數值大，則用上一代的最優解替換當前最優解；若上一代的最優解函數值小，則用上一代的最優解替換當前中的最差解。

Step4根據每個個體的適應度，采用比例選擇法。通過轉換，使得在進化前期原本函數值小的個體將有更大的概率被選擇，保持了種群的多樣性。

Step5計算交叉概率，然后在種群中按照交叉概率隨機選擇父代個體，然后應用本文改進的交叉操作進行交叉，最后通過競爭選取兩個最好的個體作為子代個體。

Step6計算變異概率，選定變異個體，將選定的個體依照本文采用的擬粒子群變異方法進行變異操作。

Step7滿足迭代次數即停止，否則代數加1，轉入Step2。

三 實驗分析

1．實驗參數設定

為了驗證改進遺傳算法的效果，選用以下三個典型函數進行測試：

（1）問題P1

g3是Schaffer函數，由函數圖像可以看出當（x1，x2）＝（0，0）時有全局最小值0。為方便編程將問題P3轉化為求全局最大值，得到問題P3'：

分別用經典遺傳算法（CGA）、一般自適應遺傳算法（AGA）和改進遺傳算法（HGA）對這些函數進行優化。為了方便編程，函數均設定為求其全局最大值，然后將三種算法運行的參數設置如下：

問題P1'算法運行的參數如表1所示：

采用上述參數用三種算法對每個函數各自獨立運行 50 次，當算法達到最大迭代次數，或者所得結果與函數全局最優解的誤差|e|≤10-2時算法終止。表4列出了三種算法的平均收斂代數，最小收斂代數和全局收斂概率。

三種算法運行收斂的代數，見圖1、圖2、圖3。

2．結果分析

通過表4可以看出，本文的改進算法HGA無論是收斂代數還是收斂概率都全面優于經典遺傳算法。與一般自適應算法相比，達到最優值的收斂代數減少，得到了令人滿意的效果。

四 小結

在本節中詳細介紹了本文改進的遺傳算法（HGA）流程，通過對幾組數據的測試結果分析得出本算法的優越性。雖然對個別函數在全局收斂概率方面略顯不足，但是對于大部分函數本文改進的算法在減少收斂代數和提高全局收斂概率方面都是優于經典遺傳算法（CGA）與一般自適應遺傳算法（AGA）的。

參考文獻

［1］馮紅娟.基于遺傳算法的車間作業調度問題研究［D］.長春理工大學，2008.3

［2］趙蕾.遺傳算法在通信網優化中的實現［D］.山東大學，2005.3

［3］Goldberg D E.Genetic Algorithms in Search. Optimization and Machine Learning.Reading， MA: Addison－Wesley， 1989

［4］譚丹丹等.一種基于配對的改進遺傳算法［J］.計算機應用，2007（27）：170～171

［5］鄺航宇、金晶、蘇勇.自適應遺傳算法交叉變異算子的改進［J］.計算機工程與應用，2006（12）：93～99

［6］向佐勇、劉正才.基于完全自適應策略的遺傳算法［J］.中南林業科技大學學報，2007（5）：136～139

［7］申元霞、曾傳華、張翠芳.一種自適應緊湊遺傳算法及其仿真研究［J］.系統仿真學報，2008（5）：1167～1169

［8］劉立平、牛熠.遺傳算法綜述［J］.東莞理工學院學報，2005（3）：48～52

［9］杜明、王江晴.遺傳算法在車輛路徑問題中的應用與實踐［J］.控制理論與應用，2007（6）：10～12

〔責任編輯：李錦雯〕

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文