一種新型自適應(yīng)遺傳算法在多峰函數(shù)優(yōu)化中的應(yīng)用

張大科 錢謙

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

關(guān)鍵詞：遺傳算法；自適應(yīng)；函數(shù)優(yōu)化；變異概率；交叉概率

DOI：10.11907/rjdk.173028

中圖分類號：TP312

文獻標(biāo)識碼：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大學(xué)的Holland提出，后來經(jīng)過DeJong、Goldberg等人歸納總結(jié)形成的一類模擬進化算法[1-3]，它來源于達爾文進化理論和孟德爾的遺傳變異理論[4]，作為一種自適應(yīng)啟發(fā)式全局意義上的搜索算法，具有很強的魯棒性和通用的優(yōu)化能力[5]。傳統(tǒng)遺傳算法擁有一個可以代表問題潛在解的種群，種群中的每個個體在選擇、交叉、變異的作用下不斷進化，以找到問題最優(yōu)解。但傳統(tǒng)遺傳算法在解決函數(shù)優(yōu)化問題上仍存在一些缺陷，故Srinivas[6]等人提出了自適應(yīng)遺傳算法（Adaptive Genetic Algorithms 以下簡稱AGA）。

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

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

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

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

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

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

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

1 改進的自適應(yīng)遺傳算法

1.1 算法基本步驟

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

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

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

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

在式（4）、式（5）中，f-max表示種群中最大適應(yīng)度，f-avg表示種群平均適應(yīng)度，f表示當(dāng)前個體適應(yīng)度，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）可知，改進后的交叉概率和變異概率無論當(dāng)前適應(yīng)度變大還是變小，交叉概率和變異概率都不會等于零，不會出現(xiàn)AGA在演化初期結(jié)果不理想的狀況，避免在演化初期走向局部最優(yōu)解。在當(dāng)前個體遠離最優(yōu)個體時，交叉概率和變異概率的值漸漸提高，便于盡快尋找到最優(yōu)解。在當(dāng)前個體比較接近最優(yōu)個體時，交叉概率和變異概率值漸漸減小，以避免當(dāng)前個體進入局部最優(yōu)解。

1.3 精英保留策略

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

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

2 改進算法實驗結(jié)果及分析

2.1 測試函數(shù)

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

2.2 算法性能指標(biāo)評價

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

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

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

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

3 結(jié)語

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

參考文獻：

[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].控制理論與應(yīng)用，1996，13（6）：697-708.

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

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

[5] 歐陽森，王建華.一種新的改進的遺傳算法及其應(yīng)用[J].系統(tǒng)仿真學(xué)報，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] 王思艷.自適應(yīng)遺傳算法的研究[D].北京：華北電力大學(xué)，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] 金晶，蘇勇.一種改進的自適應(yīng)遺傳算法[J].計算機工程與應(yīng)用，2005（18）：64-69.

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

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

（責(zé)任編輯：杜能鋼）