一種改進(jìn)的自適應(yīng)遺傳算法?

劉萍 俞煥

（陸軍炮兵防空兵學(xué)院 合肥 230031）

1 引言

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

2 遺傳算法

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

2.1 遺傳算法的原理

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

圖1 遺傳算法的具體流程

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

2.2 遺傳算法的特點

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

1）遺傳算法是一種隨機(jī)優(yōu)化算法，對于所求解的優(yōu)化問題沒有過多的數(shù)學(xué)要求，鑒于其進(jìn)化特性，搜索過程中不需要考慮問題的內(nèi)在屬性，無論是線性的還是非線性的，離散的還是連續(xù)的，都可以直接對結(jié)構(gòu)對象進(jìn)行操作，應(yīng)用的場景及范圍比較廣泛。

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

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

4）遺傳算法是針對參數(shù)的編碼進(jìn)行操作，而非針對參數(shù)本身，其尋優(yōu)規(guī)則取決于相應(yīng)的概率，而非確定性的。它本質(zhì)上不僅僅只是一種優(yōu)化算法，更是提供了一種求解系統(tǒng)優(yōu)化問題的通用框架，具有巨大的發(fā)展?jié)摿Α?/p>

3 遺傳算法的自適應(yīng)優(yōu)化

3.1 遺傳算法存在的不足

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

3.2 自適應(yīng)遺傳算法

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

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

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

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

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

經(jīng)過上述兩個方面的改進(jìn)后，本文所采用的改進(jìn)后遺傳算法具體實現(xiàn)步驟如下：

1）對待求解問題進(jìn)行編碼，生成初始群體，設(shè)定群體數(shù)量與最大迭代次數(shù)。

2）選取適應(yīng)度函數(shù)來評估群體中個體的適應(yīng)度。

3）依據(jù)輪盤賭法進(jìn)行個體選取，進(jìn)入下一步的交叉操作，大概率地保留高適應(yīng)度個體。

4）依據(jù)自適應(yīng)交叉概率，對選中的個體進(jìn)行交叉操作。

5）依據(jù)自適應(yīng)變異概率，對新生成的個體進(jìn)行變異操作，產(chǎn)生新的群體。

6）重復(fù)2～5步，直到算法到達(dá)一定的迭代次數(shù)或個體適應(yīng)度達(dá)到設(shè)定的標(biāo)準(zhǔn)。

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

4 實例

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

圖2 TSP問題仿真結(jié)果

通過Matlab仿真得到的結(jié)果可以發(fā)現(xiàn)，經(jīng)過優(yōu)化后的遺傳算法在收斂速度上取得了較好的效果，可以有效提升了整個算法的運算效率，算法具有一定的實用價值。

5 結(jié)語

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