一種改進的自適應遺傳算法?

劉萍 俞煥

（陸軍炮兵防空兵學院 合肥 230031）

1 引言

遺傳算法（Genetic Algorithm，GA），是自然啟發式算法（heuristic algorithm）中較為經典的一種算法，最早于二十世紀六十年代由密歇根大學的John Holland提出［1］。顧名思義，遺傳算法就是依據自然界中生物遺傳與進化的過程來設計實現的算法［2］。隨著時代的進步與科技的發展，計算機的性能得到質的提升，遺傳算法也開始從理論層面逐漸進入實際應用領域。作為一個可以有效解決復雜優化問題的框架式算法，遺傳算法在學者的深入研究下變得越來越豐富，并被廣泛地適用于計算科學、商業、農業等多個領域。

2 遺傳算法

遺傳算法借鑒自然界生物的進化方式，將生物進化的過程算法化，并在計算機上進行模擬實現，從而用來解決實際領域中的優化問題，是一種可以避免限于局部最值的全局搜索算法。它會隨機生成不同種類的問題解決方案，并依據適者生存的原則，選擇更有利于解決問題的方案，通過遺傳與變異進一步進行方案的迭代與優化，類似于自然界中的生物進化。正是其初始選擇方案的隨機化，加上遺傳中不斷進行的變異，使得其可以跳出局部最優的困境，適合用于進行全局的搜索與優化。

2.1 遺傳算法的原理

遺傳算法是一種建立在達爾文進化論基礎上的算法，適合用來解決復雜問題的優化，具備自我學習、自我適應、自我優化的優點［3］。遺傳算法的基本原理為［4］：它是把求解問題的方案抽象編碼到染色體，一個染色體對應一個解決方案。而后利用一個評價標準來對每個染色體進行評價，依據個體的適應度大小來進行排序，適應度高的個體有更高的概率被選中，通過選擇、交叉、變異等方式，進行下一代種群的遺傳與繁殖，如此循環直到出現的個體適應度滿足算法的需求，最終得到的個體便是我們要尋求問題的最優解。其具體流程如圖1所示。

圖1 遺傳算法的具體流程

遺傳算法中主要存在三種具體的步驟，依次為選擇操作、交叉操作和變異操作。只有科學合理地銜接這些操作步驟，根據具體的待解決問題來設計相應的操作方案，才可以最大程度提升算法的性能，快速準確地得到最優解。選擇操作是指在當前的種群中選擇適應度高的個體，來進行下一步的遺傳與變異，個體被選中的概率與適應度值成正比，即適應度值越高，被選中的概率則越大；交叉操作是指將上述選擇操作中選出的親本進行隨機配對，使得每個被選中個體的染色體以一定的概率進行對換，交換染色體相對應的基因組［5］。交叉過程為從群體中任選兩個染色體，隨機選擇一點或者多點染色體位置來進行交換，其一般經驗取值在0.01～0.99之間；變異操作是指從種群中任選一個個體，選擇其染色體中的一點或者多點進行變異以產生更加優秀的個體，是產生新個體的一種實現手段。變異算子的使用，保證了種群在繁衍中的多樣性，不僅可以進一步優化遺傳算法的效率，還可以強制算法搜索當前焦點以外的區域，從而避免算法出現過早收斂的現象，其一般經驗取值為0.0001～0.1之間。

2.2 遺傳算法的特點

針對各個領域的不同性質的優化問題，學者們提出不同種類的智能優化算法，例如模擬退火算法（Simulated Annealing）、粒子群算法（Particle Swarm Optimization）等，這些算法建立在不同的理論基礎上，適用的具體領域各不相同，各有其優缺點。作為一種適用于解決復雜問題優化的算法，遺產算法具有以下的特點。

1）遺傳算法是一種隨機優化算法，對于所求解的優化問題沒有過多的數學要求，鑒于其進化特性，搜索過程中不需要考慮問題的內在屬性，無論是線性的還是非線性的，離散的還是連續的，都可以直接對結構對象進行操作，應用的場景及范圍比較廣泛。

2）遺傳算法直接以目標函數作為搜索信息，僅用適應度函數來評估個體［5］，而不需要其他復雜的推導和附加信息，并在此基礎上進行遺傳操作，來實現種群中個體之間的信息交換，從而對于求解問題的依賴性較小，具有很好的靈活性。

3）遺傳算法采用多點并行的搜索方式，并非僅僅局限于一點，因此可以有效地防止搜索過程收斂于局部最優解。同時，正是憑借遺傳算法具有并行結算的特點，我們可以通過大規模的并行計算來提升算法的運算速度，使得快速實時尋優切實可行［7］。

4）遺傳算法是針對參數的編碼進行操作，而非針對參數本身，其尋優規則取決于相應的概率，而非確定性的。它本質上不僅僅只是一種優化算法，更是提供了一種求解系統優化問題的通用框架，具有巨大的發展潛力。

3 遺傳算法的自適應優化

3.1 遺傳算法存在的不足

遺傳算法模擬自然環境中生物進化方式來實現全局最優解，雖然一定程度上可以避免陷入局部尋優的困境，但是在面對一些復雜問題時，遺傳算法仍具有一定的局限性，很難準確收斂到全局最優解［8］。因為傳統的遺傳算法在進化尋優的過程中，算法的相關參數都是固定不變的，在群體隨著外界因素不斷調整的背景下，固定的參數不能滿足個體在不同進程下的動態需求，從而影響了算法的性能與效率［9］。

3.2 自適應遺傳算法

遺傳算法中尋求全局最優解的基礎是通過適應度函數的選擇使得群體中優秀的個體得以保存，而得到優秀個體的前提條件就是確保群體中個體的多樣性，實現算法在保證較快收斂速度的同時有效的避免陷入局部最優解［10］。因此，交叉概率與變異概率的選擇對于遺傳算法準確地搜索全局最優解中占據著很大的比重，科學合理的概率參數可以有效防止算法出現早熟的現象，提升遺傳算法的全局搜索性能。針對以上問題，本文對傳統的遺傳算法作出一些優化，主要是優化算法中的交叉概率與變異概率，將種群中個體的適應度值作為交叉、變異概率取值的重要參考指標，使得算法更貼近群體的實際情況，從而更好地篩選出優秀的個體，高效地實現全局最優解的搜索［11］。本文對遺傳算法進行以下兩點改進。

1）自適應性交叉概率。交叉操作是遺傳算法中最為核心的部分，扮演著個體基因重新組合的角色，通過交叉操作不斷產生更加優秀的新個體，來擴大算法在整個空間中的搜索范圍，確保遺傳算法優秀的搜索性能。交叉概率作為交叉操作強度的唯一指標，其取值的選擇至關重要，如果交叉概率取值過大，雖然算法的搜索強度會進一步增大，但是算法的整體效率會被影響；如果交叉概率取值過小，那么算法極有可能會變得遲緩低效，全局搜索性能大大降低。為了克服上述問題，本文采用一種自適應的交叉概率，依據群體中個體的適應度值高低來不斷調整交叉概率，對于適應度最大和最小的個體，相對應的不是零交叉操作或者完全交叉操作，而是進行特定概率的交叉操作，可以有效提升交叉操作保持算法中個體多樣性的作用，調整后的算法為

式中PC是交叉概率，fc是交叉操作前兩個父代中適應度較高者，fmax，fmin是群體中適應度最大值與最小值，k1，k2，k3是0～1之間的常數，k2>k3。

2）自適應性變異概率。變異操作也是遺傳算法中不可或缺的一部分，通過對新生成的個體依據一定的變異概率進行變異，從而確保群體中個體基因的多樣性。變異操作通常和交叉操作銜接使用，提升算法的全局搜索性能，在算法即將接近最優解的時候，可以通過適當的變異操作有效加快算法的收斂速度。變異操作中以變異概率來表示變異操作的強度，變異概率的取值對于整個算法影響重大，變異概率通常取值較小，可以防止群體中優秀基因的流失，如果取值過大，算法易趨向于隨機搜索，失去原本的特性。相關的研究表明，在單峰函數中，變異概率的選擇一般依據個體編碼串的維度數確定，并且隨著迭代次數的累計增加，變異概率的取值逐漸減小以提高算法的收斂效率。而面對多峰值函數時，自適應的變異概率則更加貼近實際問題，更具有高度的適應性，其具體公示如下所示：

式中Pm是交叉概率，fc是交叉操作前兩個父代中適應度較高者，fmax，fmin是群體中適應度最大值與最小值，k4，k5，k6是0～1之間的常數，k5>k6。

經過上述兩個方面的改進后，本文所采用的改進后遺傳算法具體實現步驟如下：

1）對待求解問題進行編碼，生成初始群體，設定群體數量與最大迭代次數。

2）選取適應度函數來評估群體中個體的適應度。

3）依據輪盤賭法進行個體選取，進入下一步的交叉操作，大概率地保留高適應度個體。

4）依據自適應交叉概率，對選中的個體進行交叉操作。

5）依據自適應變異概率，對新生成的個體進行變異操作，產生新的群體。

6）重復2～5步，直到算法到達一定的迭代次數或個體適應度達到設定的標準。

7）輸出最終結果，還原編碼得到實際問題的解。

4 實例

旅行商問題（TSP）是指單一的旅行商需要到n個城市去推銷商品，要求從某一城市出發，經過n-1個城市，旅行商在途徑的n-1個城市能且僅能經過一次，再回到出發城市，使得旅行商的路程最短。TSP屬于運籌學中比較經典的優化問題，具有較為廣泛的工程應用背景，例如飛機航線的規劃、公路路網的建設、快遞物流的配送等，這些實際應用問題均可以轉變為TSP問題來解決［12］。在Mat?lab環境中進行測試，設定城市的個數為20，目標函數為旅行商總路徑和最短，且除出發城市外，其余城市必須經過且只能經過1次，將本文的自適應遺傳算法與傳統固定交叉與變異概率的遺傳算法進行比較，測試結果如圖2所示。

圖2 TSP問題仿真結果

通過Matlab仿真得到的結果可以發現，經過優化后的遺傳算法在收斂速度上取得了較好的效果，可以有效提升了整個算法的運算效率，算法具有一定的實用價值。

5 結語

本文針對傳統遺傳算法存在的不足，對算法中的交叉概率和變異概率進行自適應改進，進一步增強算法的全局尋優能力，并且通過對于TSP問題進行Matlab仿真來實現驗證。實驗數據表明，優化后的遺傳算法有著更好的收斂速度與運算效率。