一種新型自適應遺傳算法在多峰函數優化中的應用

張大科 錢謙

摘 要：為解決傳統遺傳算法在一維多峰函數優化中容易陷入局部極值、收斂概率低、穩定性不理想等問題，提出了一種新型的自適應遺傳算法。結合自適應差分進化算法流程，提出了一種基于種群適應度變化程度而變化的非線性交叉算子和變異算子，使算法跳出局部極值，尋找到全局最優解，提升最優值迭代效率。函數測試實驗表明，在一維多峰函數優化中，該算法在函數收斂概率、最優值迭代效率以及穩定性上比已有算法均有提高。

關鍵詞：遺傳算法；自適應；函數優化；變異概率；交叉概率

DOI：10.11907/rjdk.173028

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2018）006-0085-03

Abstract：Traditional genetic algorithm is easy to fall into the local extremum， its convergence probability and stability in one-dimensional multi-peak function optimization are also low. This paper presents an improved adaptive genetic algorithm. This algorithm uses a nonlinear crossover operator and mutation operator， which are based on the variation degree of population fitness values. Furthermore， the algorithm combines the process of the adaptive differential evolution algorithm. Two modifications can make the algorithm escape from the local extremum， find the global optimal solution and increase the iterative efficiency of the optimal value. Compared with other existing algorithms， the results of experiments show that the improved algorithm has good performance in improving the probability of convergence ， iterative efficiency of optimal value and algorithm stability .

Key Words：genetic algorithm； adaptive； function optimization； mutation probability； crossover probability

0 引言

遺傳算法是美國Michigan大學的Holland提出，后來經過DeJong、Goldberg等人歸納總結形成的一類模擬進化算法[1-3]，它來源于達爾文進化理論和孟德爾的遺傳變異理論[4]，作為一種自適應啟發式全局意義上的搜索算法，具有很強的魯棒性和通用的優化能力[5]。傳統遺傳算法擁有一個可以代表問題潛在解的種群，種群中的每個個體在選擇、交叉、變異的作用下不斷進化，以找到問題最優解。但傳統遺傳算法在解決函數優化問題上仍存在一些缺陷，故Srinivas[6]等人提出了自適應遺傳算法（Adaptive Genetic Algorithms 以下簡稱AGA）。

在遺傳算法中，交叉和變異兩個控制參數是影響遺傳算法性能的關鍵因素。具有自適應調節功能的交叉和變異算子，在種群演化過程中能隨著種群的集中、分散而調節交叉和變異概率的大小。交叉概率的大小決定了種群的豐富度，交叉概率值越大，種群的豐富度就越高，種群中的優秀個體就越容易被破環。變異概率決定了產生新個體數量的多少，變異概率越高，產生的新個體就越多，就越容易跳出局部極值尋找到全局最優解。但是如果變異概率過大，很容易使遺傳算法變成隨機搜索算法[7]，所以自適應遺傳算法通過對遺傳參數的自適應調整，能夠有效提高遺傳算法的收斂精度和收斂速度。自適應遺傳算法在保持種群多樣性的同時，保證了算法的收斂性，有利于尋找到最優解[8]。

在自適應遺傳算法發展初期，人們一直從交叉算子和變異算子基于種群個體適應度的線性變化進行分析優化。如Srinivas等人提出的AGA就是根據交叉概率和變異概率隨著種群個體適應度中的平均適應度和最大適應度進行線性變換分析，如式（1）、式（2）所示。

在式（1）、 式（2）中， f-max表示種群中最大適應度，f-avg表示種群平均適應度。f-1表示參與交叉的兩個個體中的較大適應度， f-2表示變異個體的適應度。

由式（1）、式（2）可知，交叉概率及變異概率隨著種群適應度的分散和集中程度動態調整，當種群適應度較分散時，降低交叉概率和變異概率，當種群適應度較集中時，增大交叉概率和變異概率。在當前個體適應度和種群最大適應度無限接近時，交叉概率和變異概率的值也將無限趨近于零，這就導致在遺傳算法進化初期，優秀的個體都處于一種穩定狀態，所以此時的群體在進行全局尋優時很可能陷入局部極值，尋找不到全局最優解。由此可知，AGA的演化并不是非常理想[9]。

Srinivas等人提出的AGA主要是基于交叉算子和變異算子的線性變化進行演化，但線性變化并不能很好地解決在群體中尋找到全局最優個體。石山、勵慶孚等[10]提出了余弦型自適應遺傳算法（Cosine Adaptive Genetic Algorithms以下簡稱CAGA），通過交叉概率和變異概率隨著種群個體適應度中的平均適應度和最大適應度進行非線性變換，處理函數優化問題。

改進后的交叉概率和變異概率隨著適應值的增大而增大，隨適應值的減小而減小。當前適應度和平均適應度無限接近時，余弦值接近于1，交叉概率和變異概率的值為最大。當前適應度值和平均適應度值無限遠離時，余弦值接近于0但始終不等于0。所以CAGA相對AGA等算法的線性變化而言，在種群的前期提高了種群的交叉概率和變異概率，在種群的后期又降低了種群的交叉概率和變異概率，這樣便將優良個體保存在種群中。但當種群中的平均適應度和最大適應度相差較大時，CAGA與AGA等基于線性調整的算法相比性能相差不大[11]。無論是普通的遺傳算法還是自適應遺傳算法，如何確定交叉算子和變異算子便成為提高算法性能的重要因素之一。

本文提出一種新型的自適應遺傳算法（Improved Adaptive Genetic Algorithms以下簡稱IAGA）。從遺傳算法的交叉、變異算子入手，結合自適應差分進化算法，先執行變異操作，再執行交叉操作，最后執行選擇操作，使該算法在一維多峰函數的優化中能夠兼顧全局搜索性和收斂穩定性。實驗結果表明，改進后的自適應遺傳算法在函數優化中比AGA和CAGA的收斂度更高，最優值的迭代效果更明顯，基本達到了預期目的。

1 改進的自適應遺傳算法

1.1 算法基本步驟

改進的自適應遺體算法步驟如下：①確定編碼策略，采用二進制編碼，建立從自變量的實際值到二進制編碼之間的一一映射關系；②初始化種群，選定種群規模、染色體規模，確定收斂條件；③適應度分析。計算種群中每個個體的適應度，按照適應度大小排序；④判斷tanf-avgf-max≤0.5是否成立，如果成立，說明此種群的平均適應度和最大適應度比較接近，若小于0.5則說明此時種群的適應度比較集中在某個區域內。此時進入步驟⑤操作，如果不成立，說明此種群的平均適應度和最大適應度相差較遠，大于0.5則說明此種群的適應度呈現一種較分散狀態，此時進入步驟⑥的操作；⑤按照自適應差分進化算法流程，即先執行變異操作，再執行交叉操作，最后執行選擇操作；⑥按照傳統遺傳算法流程，即先執行選擇操作，再執行交叉操作，最后執行變異操作；⑦將得到的種群采取精英保留策略；⑧判斷是否滿足收斂條件，如果滿足條件就進行下一步操作，否則進行步驟③；⑨以此循環往復操作，直到找到最優解，輸出最優解。

1.2 改進算法的交叉算子和變異算子

在自適應差分進化算法中經常構造如式（3）這樣的變異算子。該算子能夠在種群初期保持個體的多樣性。隨著種群的發展，到種群后期又能夠保留優良信息，避免了優良個體被破壞。

此算子在規定的區間內前期變化平緩，中間變化逐漸加快，后期又逐漸減慢速度。本文基于自適應差分進化算法的變異算子，設計出解決一維多峰函數優化問題的IAGA算子，如式（4）、式（5）所示。

在式（4）、式（5）中，f-max表示種群中最大適應度，f-avg表示種群平均適應度，f表示當前個體適應度，P-C1表示交叉概率中的較大概率，本文選取P-C1=0.9。P-C2表示交叉概率中的較小概率，本文選取P-C2=0.1。P-m1表示變異概率中的較大概率，本文選取P-m1=0.2。P-m2表示變異概率中的最小概率，本文選取P-m2=0.001。

由式（4）、式（5）可知，改進后的交叉概率和變異概率無論當前適應度變大還是變小，交叉概率和變異概率都不會等于零，不會出現AGA在演化初期結果不理想的狀況，避免在演化初期走向局部最優解。在當前個體遠離最優個體時，交叉概率和變異概率的值漸漸提高，便于盡快尋找到最優解。在當前個體比較接近最優個體時，交叉概率和變異概率值漸漸減小，以避免當前個體進入局部最優解。

1.3 精英保留策略

為了保證每一代中的優良個體不被破壞，采取精英保留策略是非常必要的。精英保留策略即：如果下一代群體中的最佳個體適應度小于當前群體的最佳個體適應度，就將當前種群的最佳適應度或比下一代更優秀的個體保留下來，替代下一代中最差的個體。所以精英保留策略是群體收斂優化問題中群體尋優的一種保障。

為了體現出算子性能分析的準確性，本文采用最基本的選擇、交叉、變異方法。其中選擇操作選用經典的輪盤賭方法，交叉和變異操作選擇單點交叉和單點變異。下面通過不同的實驗論證本文優化算法。

2 改進算法實驗結果及分析

2.1 測試函數

由于遺傳算法中存在大量隨機操作，為了分析改進算法的搜索性能，通常采用一些典型的一維多峰函數檢驗算法的實際效率。本文選取2個具有代表性的測試函數對改進的算法進行性能測試。

2.2 算法性能指標評價

將上述兩個函數對IAGA、AGA和CAGA進行性能比較，然后將本文的IAGA和CAGA進行迭代結果比較，每個函數每種算法分別運算50次，群體規模100，進化代數500，交叉概率0.6，變異概率0.01，實驗結果見表1～表3。

綜合表1、表2、表3實驗數據可知，本文提出的IAGA在2個測試函數中分別運算50次，收斂次數最多，并且0每

個函數的收斂概率都達到0.8以上，尤其在f-1（x）測試函數下，函數的收斂概率達到了0.98，比AGA收斂概率高出0.2以上，比CAGA的收斂概率高出0.1以上。在迭代次數方面，本文的IAGA比AGA提前20代達到最優值，比CAGA提前100多代達到最優值。通過對比可以看出，本文的IAGA在全局收斂和迭代代數上均有提高，結果理想。

由圖1、圖2的函數迭代結果可知，圖1中的CAGA在達到最大值前進入了局部極值，而本文的IAGA則進行了正常的搜索，最后趨向最大值。圖2中的CAGA在迭代過程中一直趨向最大值，而且迭代過程不穩定，而本文的IAGA則依然維持在6 400左右的均值水平。由此可見，新算法在收斂概率和迭代次數方面有所提高，更具穩定性。

3 結語

本文通過對Srinivas等提出的AGA以及石山等提出的CAGA交叉算子和變異算子的分析，指出了AGA和CAGA在函數優化中存在的不足。結合自適應差分進化算法運算過程，同時基于自適應差分進化算法的變異算子，設計并改進出一種新型的自適應遺傳算法。算法實現方案簡單，種群適應度隨著基于改進的遺傳算法的交叉算子和變異算子進行非線性動態變化。IAGA與AGA和CAGA相比，本文的IAGA收斂概率更高，最優值的迭代次數也有所提升，具有更可靠的穩定性，所以本文的IAGA在一維多峰函數優化中是一種有效算法。

參考文獻：

[1] DEJONG K A. The analysis of the behavior of a class of genetic adaptive systems[D]. Ann Arbor： University of Michigan Press，1975.

[2] 席裕庚，柴天佑.遺傳算法綜述[J].控制理論與應用，1996，13（6）：697-708.

[3] 吉根林.遺傳算法研究綜述[J].計算機應用與軟件，2004，21（2）：69-73.

[4] 葛繼科，邱玉輝.遺傳算法研究綜述[J].計算機應用與研究，2008，25（10）：2911-2916.

[5] 歐陽森，王建華.一種新的改進的遺傳算法及其應用[J].系統仿真學報，2003，15（8）：1066-1068.

[6] SRINIVAS M ， PATNAIKL M . Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Trans on Systems， Man and Cybernetics，1994，24（4）：656-667.

[7] 王思艷.自適應遺傳算法的研究[D].北京：華北電力大學，2009.

[8] CONGRUI YANG， QIAN QIAN. An improved adaptive genetic algorithm for function optimization[C]. IEEE International Conference on Information and Automation，2017：675-680.

[9] 金晶，蘇勇.一種改進的自適應遺傳算法[J].計算機工程與應用，2005（18）：64-69.

[10] 石山，勵慶孚.基于自適應遺傳算法的無刷直流電機的優化設計[J].西南交通大學學報，2002，36（12）：1215-1218.

[11] 鄺航宇，金晶.自適應遺傳算法交叉變異算子的改進[J].計算機工程與應用，2006（12）：93-96.

（責任編輯：杜能鋼）