基于自適應遺傳算法的改進及實現*

楊森 劉新平 李克文

（中國石油大學（華東）計算機科學與技術學院 青島 266580）

1 引言

遺傳算法［1］（Genetic Algorithm，GA）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型。將生物自然選擇、基因突變等生物學理論，作為算法中交叉率、變異率、選擇因子等進行全局概率搜索。該算法具有很強的穩定性和易用性，且搜索效果好，目前在很多領域得到了廣泛應用，比如最短路徑、神經網絡、圖像處理等。

標準GA中交叉率、變異率兩個參數是固定的，這就導致了其早熟、收斂速度慢的缺點，且為每個優化問題設置不同的交叉率和變異率，都需進行多次實驗。Srinvas 等［8］將算法自適應調整交叉率和變異率融入到了GA 算法中，提出了自適應遺傳算法（Adaptive GA，AGA），提高了GA 的收斂速度，但是也隨之產生了新的問題，即AGA 在算法進化的早期會出現一定的停滯現象。因此，如何改進交叉率和變異率的自適應調整，來解決出現的這一停滯現象并提高收斂速度，這依舊具有極大的挑戰性并廣泛地引起了學者們的關注。

該文提出了自適應遺傳算法（Improved Adaptive GA，IAGA）的一種改進方法，對AGA 自適應交叉率和變異率調整曲線進行非線性優化，將個體適應度與當代種群的平均適應度、最大適應度進行比較，計算得出進化下一代染色體所需的交叉率和變異率。通過這一改進，提高了優良個體保留概率、劣質個體變異能力，使算法不趨向于停留在局部最優解，從而更好避免了過早收斂及停滯現象。與AGA 相比，該算法實現簡單，舊個體可以根據周圍個體的適應度自適應地調整其交叉率和突變率。實驗表明，新算法收斂速度快，穩定性好。

2 自適應遺傳算法

任何一種遺傳算法［4］中，交叉率和變異率都會直接對算法收斂速度造成影響。交叉率過高，優良個體基因很難進行迭代；反之就會造成新個體產生速度較慢，兩者都會造成算法產生停止、過早收斂現象。變異率越大，則算法就會成為完全隨機搜索算法，最終是否會尋找到全局最優，將不再受選擇、交叉和變異等操作的影響；反之則不容易產生新的優良個體。因此，如果采用標準GA，則需針對每個優化問題，都需要通過循環反復的試驗，來尋找針對性的交叉率和變異率，這幾乎是不可能完成的，且最終難以尋找到最優參數值。

Srinvas 等［10］提出的AGA 算法中，根據個體適應值與群體的平均適應值、最大適應值接近情況，對交叉率和變異率進行線性調整。具體調整方式見式（1）、（2）：

AGA 在進化早期階段并不理想，因為早期階段優良個體傾向于不改變自身狀態，但優良個體可能并不是全局最優解，這使算法容易收斂于局部最優解，而進化后期，算法趨于穩定，交叉率、變異率降低，算法無法跳出局部最優解，只能取得局部最優解，而非全局最優解。

3 改進的自適應遺傳算法

3.1 改進策略

針對SGA 及AGA 的弊端，本文采用種群最大適應值Fitmax、最小適應值Fitmin、平均適應值Fitave三個參數，衡量種群個體的集中度，自適應計算得到種群個體交叉率和變異率［7］。

首先使用Fitave與Fitmax，分別表示種群內部適應度分布情況，二者越接近，算法越趨于收斂。判定方法為當Fitave/Fitmax＞a 時，則該代個體集中，其中參數0.5＜a＜1。a 越接近于0.5，越容易判斷為“集中”。其次使用Fitmin與Fitmax，分別表示種群個體集中程度，二者越靠近，遺傳算法收斂于局部最優解的可能性越大，即適應度更集中，反之則更分散。Fitmix/Fitmax＞b 時，認為個體集中，其中參數0＜b＜1。b越接近于0，越容易判斷“集中”。當Fitave/Fitmax＞a且Fitmix/Fitmax＞b 時，判斷群體為集中，此時交叉率Pc和變異率Pm根據群體集中程度進行自適應變化，使算法自行調整自然選擇機制；不滿足該條件時，判斷為群體分散，交叉率Pc和變異率Pm則保持較小原始值。

改進后的交叉率Pc和變異率Pm的值的自適應計算公式，見式（3）、（4）：

改進自適應遺傳算法初期，個體比較分散，變異概率較低，可以保證種群向全局最優解收斂；當種群個體趨于集中時，采用較大變異率，使得算法在增大種群多樣性、保證種群進化的同時仍然保留了算法的局部搜索能力。

3.2 最優保存策略

自適應遺傳算法存在一個實際問題，雖然算法自適應調整交叉率和變異率，但二者可能會不斷變大，這樣就會造成優良個體被淘汰，本文采用最優保存策略來避免這一現象。

基本思想為將當代群體中的最高適應值個體與上一代群體最高適應值個體相比較，如果上一代群體最高適應值較高，則隨機淘汰掉當代群體中的一個個體，然后將上一代最高適應值個體加到當代中來。通過這種最優保存策略，即使有較高交叉率、變異率，當前最優個體也不會被破壞，這種策略保證了改進后自適應遺傳算法可以很好的收斂。

4 仿真實驗與性能分析

為了綜合比較SGA、AGA、IAGA 的尋優性能，我們選取了四個具有一定復雜度的經典測試函數進行測試［2，9］。其中三種算法均采用二進制編碼和相同選擇策略，由于最優個體保留策略對該文算法的全局收斂性能影響不大，因此在IAGA 中可以用之。測試函數如下：

Schaffer 函數，如圖1 所示。其理論最大值為1，收斂值為0.9999。

圖1 Schaffer函數

Griewank 函數，如圖2 所示。其理論最大值為2.5，收斂值為2.4993。

圖2 Griewank函數

Rosenbrock 函數，如圖3 所示。其理論最小值為0，收斂值為0.0852。

圖3 Rosenbrock函數

Ackley 函數，如圖4 所示。其理論最小值為0，收斂值為0.0055。

圖4 Ackley函數

實驗中參數設置為：f1，f2，f3，f4 種群規模皆取30，最大進化代數都設為100 代。對四個測試函數各運行100次后所得實驗結果如下。

表1 三種算法各運行100次的平均收斂結果

表2 三種算法各運行100次的平均收斂代數

從表中結果可知，AGA 雖收斂速度快，但其進化能力較差，往往過早陷入局部最優解；SGA 平均收斂結果要稍高于AGA，但其收斂速度明顯不如AGA、IAGA；而本文提出的IAGA 尋找全局最優解的能力明顯強于前兩種算法，且同時具有較快的收斂速度。

圖5 為SGA、AGA、IAGA 在四種經典測試函數下搜索最大適應度的性能比較。

圖5 SGA、AGA、IAGA檢索最大適應度性能

由圖可見，SGA 和AGA 在收斂過程中，初期容易出現停滯現象，而SGA采用固定的交叉率和變異率，所以當種群中出現較多集中程度較高個體時，SGA 很難讓這些個體進行交叉、變異，就無法跳出局部最優解。AGA 通過自適應調整交叉率和變異率，在收斂效果上得到了很大提升，但沒有避免在進化初期容易陷入局部最優解的問題。而本文提出的改進自適應遺傳算法IAGA，剛好解決了算法初期容易陷入局部最優解的問題。通過比較平均適應度與最大適應度的接近度，調整交叉率、變異率，使算法能夠很好地收斂和避免局部最優解。

5 結語

針對遺傳算法穩定性差、過早收斂的弊端，本文提出了一種針對交叉率和變異率的新的自適應方法，其基本思想是：當種群在趨向于尋得局部最優值時，交叉率、變異率的值得到增加，并且在解空間中種群趨于發散時，以較小的初始值初始化兩種概率的值。這樣可以使算法收斂速度得到增加，同時又可以避免算法進入局部最優解而無法跳出。最后采用四個復雜經典測試函數，對SGA、AGA、IAGA分別進行了測試及實現結果對比。結果表明本文提出的改進自適應遺傳算法收斂速度更快且不會陷入局部最優。