周勇 胡中功

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

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

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

1 改進(jìn)的遺傳算法基本原理

1.1 初始群體生成

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

1.2 選擇操作的改進(jìn)

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

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

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

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

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

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

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

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

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

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

2 改進(jìn)遺傳算法的實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

[1] 余有明，劉玉樹(shù)，閻光偉.遺傳算法的編碼理論與應(yīng)用[J].計(jì)算機(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] 程敏，宋宇博，孫剛，等.改進(jìn)的自適應(yīng)遺傳算法及其性能研究[J].計(jì)算機(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)遺傳算法的改進(jìn)及在系統(tǒng)辨識(shí)中應(yīng)用研究[J].系統(tǒng)仿真學(xué)報(bào)，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] 金立兵，胡穎，祁繼鵬.改進(jìn)的自適應(yīng)遺傳算法在結(jié)構(gòu)優(yōu)化設(shè)計(jì)中的應(yīng)用[J].信陽(yáng)師范學(xué)院學(xué)報(bào)（自然科學(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ìn)的遺傳算法研究[J].計(jì)算機(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ìn)的快速遺傳算法及其性能研究[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] 楊從銳，錢謙，王鋒，等.改進(jìn)的自適應(yīng)遺傳算法在函數(shù)優(yōu)化中的應(yīng)用[J].計(jì)算機(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ù)表征超低滲透儲(chǔ)層的非達(dá)西滲流特征[J].西安石油大學(xué)學(xué)報(bào)（自然科學(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.