改進的快速遺傳算法在函數(shù)優(yōu)化中的應(yīng)用

周勇 胡中功

摘 要： 遺傳算法作為一種模仿生物自然進化過程的全局隨機優(yōu)化算法，在工程中已得到廣泛應(yīng)用。但普通遺傳算法易存在早熟及收斂速度慢等缺點。提出一種快速收斂的改進遺傳算法，該算法從全局出發(fā)，對初始群體生成、遺傳選擇、交叉和變異算子操作等幾個方面做出改進，其中重點對交叉率和變異率進行優(yōu)化，實現(xiàn)交叉率和變異率按個體適應(yīng)度以S曲線和高斯分布曲線形式進行非線性自適應(yīng)調(diào)整。通過案例仿真分析，證明了該方法的可行性和有效性，且具有更快的收斂速度和更可靠的穩(wěn)定性。

關(guān)鍵詞： 遺傳算法； 高斯分布； 自適應(yīng)； 收斂； 性能仿真； 函數(shù)優(yōu)化

中圖分類號： TN911.1?34； TP18 文獻標識碼： A 文章編號： 1004?373X（2018）17?0153?05

Abstract： Genetic algorithm （GA）， as a global stochastic optimization algorithm to simulate the natural evolution process of biology， has been widely used in engineering field， but the common GA has slow convergence speed and is easy to fall into premature convergence. Therefore， an improved fast?convergence GA is proposed to improve the items of initial population generation， genetic selection， operators crossover and operators mutation proceeding from the overall situation. The crossover rate and mutation rate are optimized emphatically to realize the nonlinear adaptive adjustment in the forms of the S curve and Gaussian distribution curve according to individual fitness. The analysis results of case simulation show that the method is feasible and effective， and has fast convergence speed and high stability.

Keywords： genetic algorithm； Gaussian distribution； adaptation； convergence； performance simulation； function optimization

0 引 言

遺傳算法（Genetic Algorithm，GA）是美國Holland教授于1975年首先提出來的一種借鑒生物進化理論和門德爾基因遺傳理論的高度并行、隨機的優(yōu)化方法[1]。它模擬自然界生物“優(yōu)勝劣汰，適者生存”的自然進化過程，將研究的解空間映射為遺傳空間[2]，主要特點是整體搜索策略和優(yōu)化搜索方法在計算時不依賴于梯度信息或其他輔助知識，也不依賴于問題的具體領(lǐng)域[3]。近年來，從簡單的PID控制，到復(fù)雜的最優(yōu)控制、自適應(yīng)控制等遺傳算法在各種工程控制問題中都有成功的應(yīng)用案例。特別是目前人工智能的蓬勃發(fā)展，因而極具潛力的遺傳算法一直是研究的熱點。遺傳算法雖然應(yīng)用廣泛，但在解決復(fù)雜問題時，由于其自身的隨機搜索特點也帶來了收斂速度慢和算法局部收斂（早熟）等問題[4]。遺傳算法的交叉率[Pc]和變異率[Pm]反映了算法交叉和變異操作的概率，直接影響算法的收斂性能。標準（基本）遺傳算法（SGA）的交叉率和變異率這兩個參數(shù)是固定的，導(dǎo)致收斂能力和穩(wěn)定性較差。文獻[5?8]對遺傳算法做了一些改進。文獻[5]提出一種根據(jù)適應(yīng)度調(diào)整交叉率和變異率的自適應(yīng)遺傳算法（AGA），但在該算法中，個體適應(yīng)度越高，平均適應(yīng)度和最大適應(yīng)度越接近，交叉率和變異率不斷變小并接近于0，導(dǎo)致在進化初期，種群中的優(yōu)良個體幾乎不會改變，使算法搜索性能下降。文獻[6]中的改進遺傳算法（線性自適應(yīng)遺傳算法LAGA）解決了算法初期交叉率和變異率為零的不足，但在算法后期，當(dāng)種群平均適應(yīng)度和最大適應(yīng)度接近時，交叉率和變異率自適應(yīng)調(diào)整曲線變化比較陡峭，產(chǎn)生較大差異，使進化停滯不前，產(chǎn)生局部收斂的可能。文獻[7]把交叉和變異率按個體適應(yīng)度以Sigmoid函數(shù)曲線非線性自適應(yīng)調(diào)整，但進化初期變異率過大，雖能增加種群多樣性，但可能使算法收斂速度變慢。文獻[8]提出一種新的交叉和變異算子，但算法交叉率和變異率是固定的，增加了產(chǎn)生早熟的概率。針對遺傳算法存在的不足，本文提出一種改進的快速遺傳算法（IFGA），該算法從全局出發(fā)，分別對初始化分配、選擇、交叉和變異等幾個方面進行改進，其中著重從交叉和變異改進的方向出發(fā)，自適應(yīng)地以非線性曲線模式優(yōu)化交叉概率和變異概率，滿足算法對不同階段的側(cè)重，以增加種群多樣性，提高算法搜索能力和收斂速度。復(fù)雜函數(shù)的仿真實驗結(jié)果表明，改進的遺傳算法能較好地解決傳統(tǒng)遺傳算法存在的不足，改善收斂性質(zhì)。

1 改進的遺傳算法基本原理

1.1 初始群體生成

初始群體的分布對算法的收斂有較大影響。初始群體分布不合理會導(dǎo)致算法收斂速度變慢，特別當(dāng)遺傳算子選擇不當(dāng)時，甚至早熟不收斂?；荆藴剩┻z傳算法和大部分遺傳算法的初始群體在搜索空間都是隨機產(chǎn)生的，這種方法可能使解空間個體都集中在某一局部區(qū)域內(nèi)，這對搜索全局最優(yōu)點極為不利。本文針對常規(guī)初始群體存在的問題，借鑒文獻[9]提出的小區(qū)間初始群體生產(chǎn)法，將規(guī)模為[n]的群體[E]以待求參數(shù)的取值范圍分成群體總數(shù)個小區(qū)間，并在各小區(qū)間中分別隨機產(chǎn)生一個初始個體，從而保證初始個體能均勻地分布在整個解空間范圍內(nèi)，增強初始群體的活力。

1.2 選擇操作的改進

選擇操作反映了“優(yōu)勝劣汰，適者生存”的自然界規(guī)律，它以個體的適應(yīng)度作為衡量標準，適應(yīng)度高的個體作為父代被選擇繁衍進入下一代進化；反之，則被淘汰。選擇策略比較多，經(jīng)典遺傳算法常采用輪盤賭選擇方式。輪盤賭選擇方式根據(jù)個體適應(yīng)度值在群體適應(yīng)度總和中所占的比例來表示其被選中的概率，適應(yīng)度越高的個體，被選中的幾率越大。但這種選擇方式的選擇誤差較大，對收斂速度有較大影響。為了豐富種群模式，優(yōu)化算法收斂性質(zhì)，本文中選擇算子采用輪盤賭方式和遺傳代數(shù)相結(jié)合自適應(yīng)調(diào)整選擇概率。改進后的選擇算子為：

式中：[fE（1，i）i=1nfE（1，i）]為輪盤賭方式的初代選擇算子；[T]為最大進化代數(shù)；[k]為實數(shù)，一般為8～10。

從式（2）可知，算法在進化初期根據(jù)輪盤賭方式進行遺傳操作，使子代群體模式豐富，降低了早熟的可能性。在進化后期，隨著進化代數(shù)的增加，加大了選擇算子的概率，可極大地促進種群中適應(yīng)度較高的個體進行進化操作，能夠較好地提高算法的收斂速度。

1.3 自適應(yīng)交叉率和變異率的改進

遺傳算法中，交叉和變異算子是算法進化的核心，對算法收斂性和穩(wěn)定性有重要作用。交叉算子通過基因重組獲取優(yōu)良個體，決定了遺傳算法的全局搜索能力[10]。變異算子通過改變?nèi)后w個體基因，保證算法能搜索到解空間中的任何角落，能夠較好地維持群體的多樣性，克服早熟，使算法具有全局收斂性。遺傳算法的交叉率和變異率是算法收斂、穩(wěn)定的關(guān)鍵參數(shù)。交叉率越大，算法搜索空間越大，種群越豐富，產(chǎn)生新個體的速度越快，但是優(yōu)良個體破壞的可能性越大；交叉率過小，不易產(chǎn)生新個體，使得搜索過程緩慢。變異概率是全局最優(yōu)解的關(guān)鍵，變異率越小，不容易產(chǎn)生新的個體結(jié)構(gòu)，種群多樣性變差；變異率過大，又會使遺傳算法變成純粹的隨機搜索算法[6]。

本文基于Sigmoid函數(shù)和高斯分布函數(shù)對交叉率和變異率進行改進，設(shè)計自適應(yīng)非線性調(diào)整交叉率和變異率的調(diào)節(jié)公式。改進算法解決以下幾個問題：

1） 在進化初期，要提高搜索速度和個體多樣性，而且保證種群中最優(yōu)個體的交叉率和變異率不應(yīng)為零；

2） 當(dāng)平均適應(yīng)度和最大適應(yīng)度相差較大時，不會出現(xiàn)線性調(diào)整，避免進化停滯不前；

3） 算法后期，在滿足精度的情況下，使接近最大適應(yīng)度處曲線更光滑，緩慢減小交叉率和變異率，使交叉率和變異率的差異減小，較好地保留優(yōu)良個體。

由圖3和改進的式（5），式（6）可知，[Pc]按照個體適應(yīng)度在[favg]和[fmax]之間隨S曲線進行非線性調(diào)整，[Pm]按照個體適應(yīng)度以[favg]為中心隨高斯分布曲線進行非線性調(diào)節(jié)。在種群進化初期，保證了當(dāng)前種群優(yōu)良個體[Pc]和[Pm]不為零，而且防止變異率過大破壞種群優(yōu)良個體，使算法收斂速度變慢和進入局部最優(yōu)的可能。同時，當(dāng)大多數(shù)個體適應(yīng)度與[favg]接近時，使個體[Pc]和[Pm]接近最大，避免了算法停滯不前。在個體適應(yīng)度接近[fmax]時，盡可能緩慢地減小個體[Pc]和[Pm]，減少它們之間的差異，使[Pc]和[Pm]最小，最大限度地保留[fmax]處的優(yōu)良個體，克服算法早熟和局部收斂，滿足算法在進化過程中對不同階段的要求。

2 改進遺傳算法的實現(xiàn)

改進遺傳算法實現(xiàn)步驟如下：

1） 對求解參數(shù)進行二進制編碼，采用小區(qū)間生產(chǎn)法初始化種群，進化代數(shù)為[T]，種群規(guī)模為[n]；

2） 解碼，計算種群個體適應(yīng)度，確定適應(yīng)度函數(shù)[F]，評價是否滿足收斂條件。目標函數(shù)求最大值，則[F=f（x）]，否則，[F=1f（x）]。同時，對個體適應(yīng)度按從小到大進行排序，選出最大個體適應(yīng)度。

3） 如果滿足要求（精度10-5或進化代數(shù)[T]），輸出結(jié)果；否則繼續(xù)步驟4）；

4） 按輪盤賭和遺傳代數(shù)確定選擇復(fù)制，生產(chǎn)匹配池；

5） 根據(jù)[favg]和個體適應(yīng)度，結(jié)合自適應(yīng)調(diào)節(jié)公式進行交叉和變異操作；

6） 返回步驟2），如達到指定要求，算法結(jié)束，否則繼續(xù)執(zhí)行操作。

3 改進遺傳算法的實驗及結(jié)果分析

3.1 測試函數(shù)的選擇及優(yōu)化目標的確定

為研究改進的快速遺傳算法（IFGA）的性能及解決多模態(tài)復(fù)雜問題的能力，選用3個不同的空間函數(shù)，通過對比IFGA、基本遺傳算法（SGA）、文獻[6]的LAGA線性自適應(yīng)遺傳算法的的仿真結(jié)果，測試IFGA的收斂速度（平均收斂代數(shù)）和穩(wěn)定性（收斂次數(shù)）。在3個函數(shù)中，[f1]函數(shù)側(cè)重于測試克服早熟，[f2]函數(shù)側(cè)重于測試收斂速度。

3.2 算法參數(shù)的選擇及仿真結(jié)果分析

各遺傳算法參數(shù)見表1。

選擇[f1，f3]的最大進化代數(shù)為200代，[f2]的最大進化代數(shù)為100代。3種遺傳算法均采用二進制編碼，交叉操作采用單點交叉，變異操作采用基本位變異，SGA和LAGA采用經(jīng)典輪盤賭選擇策略。

由于遺傳算法中存在大量隨機操作，因此對每種算法各運行20次，統(tǒng)計最優(yōu)解的收斂次數(shù)和平均收斂代數(shù)。各算法測試結(jié)果見表2和表3，以及圖4～圖6。

從表2和表3看出，對[f1]函數(shù)，SGA的平均收斂代數(shù)是本文算法的10.18倍，LAGA平均收斂代數(shù)是本文算法的8.2倍，同時，SGA未收斂5次，LAGA未收斂4次，IFGA無未收斂情況。對[f2]函數(shù)，SGA和LAGA的平均收斂代數(shù)比本文算法多1.02次和5.22次。而對[f3]函數(shù)，SGA和LAGA的平均收斂代數(shù)比本文算法多19.3次和20.4次?？梢姡琁FGA無論在收斂性還是穩(wěn)定性上均極大地改善了遺傳算法的性能。

圖4～圖6為在3個測試函數(shù)下IFGA，SGA和LAGA搜索最大適應(yīng)度值的對比曲線。從圖4～圖6可看出，SGA和LAGA在進化初期容易出現(xiàn)停滯現(xiàn)象。當(dāng)種群大部分個體接近平均適應(yīng)度時，由于SGA采用固定的[Pc]和[Pm]，很難跳出局部收斂，雖然LAGA采用了線性自適應(yīng)調(diào)節(jié)[Pc]和[Pm]，可以跳出局部收斂的不利狀態(tài)，但是拖慢了其收斂速度。相比之下，本文提出的改進遺傳算法能較好地適應(yīng)外部環(huán)境，當(dāng)SGA和LAGA在進化初期處于停滯階段時，IFGA將接近平均適應(yīng)度的相近個體進行大交叉和變異操作，呈階梯上升趨勢，以最快速度擺脫局部收斂，具有較好的收斂速度和穩(wěn)定性。

4 結(jié) 語

本文針對傳統(tǒng)和改進遺傳算法在收斂性和穩(wěn)定性上的不足，提出一種改進的遺傳算法。算法從全局出發(fā)，對初始化分配、選擇、交叉和變異等幾個方面進行改進。其中，結(jié)合S型曲線和高斯分布曲線，著重對交叉率和變異率的自適應(yīng)調(diào)節(jié)進行設(shè)計。在求解函數(shù)優(yōu)化問題時，改進的遺傳算法無論在收斂速度還是穩(wěn)定性上，都比SGA和LAGA等遺傳算法有較明顯的優(yōu)勢，克服了遺傳算法易陷入早熟和收斂速度慢等問題。因此，本文提出的改進遺傳算法是有效的，為實際工程應(yīng)用提供了理論支持。

參考文獻

[1] 余有明，劉玉樹，閻光偉.遺傳算法的編碼理論與應(yīng)用[J].計算機工程與應(yīng)用，2006，42（3）：86?89.

YU Youming， LIU Yushu， YAN Guangwei. Encoding theory and application of genetic algorithm [J]. Computer engineering and applications， 2006， 42（3）： 86?89.

[2] 程敏，宋宇博，孫剛，等.改進的自適應(yīng)遺傳算法及其性能研究[J].計算機與數(shù)字工程，2014，42（3）：355?358.

CHENG Min， SONG Yubo， SUN Gang， et al. An improved self?adaption genetic algorithm and its performances [J]. Computer and digital engineering， 2014， 42（3）： 355?358.

[3] LINDA M M， NAIR N E. A new?fangled adaptive mutation breeder genetic optimization of global multi?machine power system stabilize [J]. International journal of electrical power and energy systems， 2013， 44（1）： 249?258.

[4] XU Haiyan. Research for new modified adaptive genetic algorithm [C]// 2012 IEEE World Automation Congress. Puerto Vallarta： IEEE， 2012： 146?147.

[5] SRINVAS M， PATNAIK L M. Adaptive probabilities of crossover and， mutation in genetic algorithms [J]. IEEE transactions on system man and cybernetics， 2002， 24（4）： 656?667.

[6] 任子武，傘冶.自適應(yīng)遺傳算法的改進及在系統(tǒng)辨識中應(yīng)用研究[J].系統(tǒng)仿真學(xué)報，2006，18（1）：41?43.

REN Ziwu， SAN Ye. Improved adaptive genetic algorithm and its application research in parameter identification [J]. Journal of system simulation， 2006， 18（1）： 41?43.

[7] 金立兵，胡穎，祁繼鵬.改進的自適應(yīng)遺傳算法在結(jié)構(gòu)優(yōu)化設(shè)計中的應(yīng)用[J].信陽師范學(xué)院學(xué)報（自然科學(xué)版），2016，29（4）：621?624.

JIN Libing， HU Ying， QI Jipeng. Application of improved adaptive genetic algorithm in structural optimization design [J]. Journal of Xinyang Teachers College （natural science edition）， 2016， 29（4）： 621?624.

[8] 謝燕麗，許青林，姜文超.一種基于交叉和變異算子改進的遺傳算法研究[J].計算機技術(shù)與發(fā)展，2014，24（4）：80?83.

XIE Yanli， XU Qinglin， JIANG Wenchao. An improved genetic algorithm based on crossover and mutation operators [J]. Computer technology and development， 2014， 24（4）： 80?83.

[9] 高瑋.改進的快速遺傳算法及其性能研究[J].系統(tǒng)工程與電子技術(shù)，2003，25（11）：1427?1430.

GAO Wei. An improved fast?convergent genetic algorithm and its performance study [J]. Systems engineering and electronics， 2003， 25（11）： 1427?1430.

[10] 楊從銳，錢謙，王鋒，等.改進的自適應(yīng)遺傳算法在函數(shù)優(yōu)化中的應(yīng)用[J].計算機應(yīng)用研究，2018，35（4）：1042?1045.

YANG Congrui， QIAN Qian， WANG Feng， et al. Application of improved adaptive genetic algorithm in function optimization [J]. Application research of computers， 2018， 35（4）： 1042?1045.

[11] 梅俊偉，彭仕宓，李雄炎，等.利用Sigmoid函數(shù)表征超低滲透儲層的非達西滲流特征[J].西安石油大學(xué)學(xué)報（自然科學(xué)版），2011，26（2）：64?67.

MEI Junwei， PENG Shimi， LI Xiongyan， et al. Characterization of the non?darcy seepage flow in ultra?low permeability reservoir based on Sigmoid function [J]. Journal of Xian Shiyou University （natural science edition）， 2011， 26（2）： 64?67.