張大科 錢謙

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

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

DOI：10.11907/rjdk.173028

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

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

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

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

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

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

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

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

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

1.1 算法基本步驟

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

1.2 改進(jìn)算法的交叉算子和變異算子

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

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

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

1.3 精英保留策略

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

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

2 改進(jìn)算法實(shí)驗(yàn)結(jié)果及分析

2.1 測(cè)試函數(shù)

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

2.2 算法性能指標(biāo)評(píng)價(jià)

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

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

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[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].計(jì)算機(jī)應(yīng)用與軟件，2004，21（2）：69-73.

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

[5] 歐陽(yáng)森，王建華.一種新的改進(jìn)的遺傳算法及其應(yīng)用[J].系統(tǒng)仿真學(xué)報(bào)，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] 金晶，蘇勇.一種改進(jìn)的自適應(yīng)遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，2005（18）：64-69.

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

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

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