遺傳算法的改進(jìn)與參數(shù)特性研究

劉帥+彭業(yè)飛+馮智鑫+張維繼

摘要：先敘述了遺傳算法的基本原理和操作流程，并結(jié)合實(shí)際問(wèn)題具體分析其特點(diǎn)，針對(duì)遺傳算法易早熟、局部搜索能力弱以及易受參數(shù)影響等缺陷，從適應(yīng)值函數(shù)、變異概率和自適應(yīng)調(diào)節(jié)三個(gè)方面對(duì)算法進(jìn)行了改進(jìn)研究，并通過(guò)實(shí)例進(jìn)行仿真驗(yàn)證，結(jié)果表明改進(jìn)的算法有較好的尋優(yōu)性能。參數(shù)間的不同組合將影響算法的尋優(yōu)性能，尤其是收斂性，研究交叉概率和變異概率之間的交互作用，得出交叉概率和變異概率的建議取值區(qū)間。

關(guān)鍵詞： 遺傳算法；早熟；局部搜索；交叉概率；變異概率

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）04-0182-04

Genetic Algorithm Optimizations Improve And Parameter Features Research

LIU Shuai ，PENG Ye-fei， FENG Zhi-xin，ZHANG Wei-ji

（Naval University of Engineering， Wuhan 430033， China）

Abstract：First describes the basic idea of genetic algorithm， mathematics principle and operation process， and analysis their characteristic combine with the actual problem. In view of the weak of local searching ability of the genetic algorithm is easy to premature and wait for blemish. From the fitness function 、mutation probability and adaptive control algorithm is improved in the aspect of research，and through the example to simulation， the results show that the improved algorithm has better optimization performance. parameters between different combination would have a great influence on the performance of genetic algorithm， particularly affect the convergence of the algorithm， by studying the interaction between the crossover probability and mutation probability， and concluded that the advice of the crossover probability and mutation probability values range.

Key words：Genetic Algorithm； precocious； local searching；crossover probability；mutation probability

1 概述

遺傳算法（Genetic Algorithm，GA）是群智能算法的一個(gè)重要的組成部分，是基于對(duì)達(dá)爾文學(xué)說(shuō)的論證的有關(guān)于生命進(jìn)化機(jī)制的一種新學(xué)科，也是仿生算法的鼻祖 [1]。遺傳算法根據(jù)生命遺傳過(guò)程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，利用遺傳算子（選擇、交叉和變異）按照某一特定的標(biāo)準(zhǔn)進(jìn)行迭代從而逐漸逼近而找出最優(yōu)值。遺傳算法經(jīng)過(guò)幾十年的發(fā)展對(duì)于解決優(yōu)化問(wèn)題有了質(zhì)的飛躍。本文針對(duì)遺傳算法易早熟、局部搜索能力弱和易受參數(shù)影響的缺陷，從三個(gè)不同的方面對(duì)算法進(jìn)行改進(jìn)研究，并分析交叉概率和變異概率之間的交互作用。

2 遺傳算法原理

2.1 基本原理

在GA算法中，生命進(jìn)化的原理轉(zhuǎn)變?yōu)閰?shù)所形成的編碼串，把染色體視為個(gè)體，而染色體又是由很多基因組成。通過(guò)基因型與表現(xiàn)型之間的關(guān)系，按遺傳操作對(duì)種群和個(gè)體進(jìn)行篩選[2]。從初始群體開(kāi)始，重復(fù)進(jìn)行選擇、交叉和變異等操作，保留適值函數(shù)值高的個(gè)體，形成新群體，新群體在保留前代信息的同時(shí)，加入了新的更優(yōu)個(gè)體，使得整個(gè)群體越來(lái)越接近最優(yōu)結(jié)果。通過(guò)迭代，群體適應(yīng)值不斷提高，直至達(dá)到要求的極限條件。適應(yīng)值最高的個(gè)體即為問(wèn)題所求最優(yōu)解。

2.2基本操作和流程

GA算法具有以下三個(gè)基本操作。

1）選擇：這個(gè)方法是根據(jù)生物界自然選擇的現(xiàn)象中優(yōu)勝劣汰的原則，從現(xiàn)有的種群中選擇出優(yōu)良的個(gè)體，為個(gè)體的交叉操作和變異操作準(zhǔn)備。一般來(lái)說(shuō)，適應(yīng)值越高的個(gè)體選擇的幾率就越大，則基因被遺傳到下一代的幾率也就越大。下面介紹幾種比較常用的選擇操作算子[3]。

① 適應(yīng)度比例選擇法

這個(gè)選擇方法又被稱為輪盤(pán)賭選擇方法。選擇的概率通過(guò)個(gè)體適應(yīng)值所占的比例決定，適應(yīng)值越大，則選擇的概率越大，相反若個(gè)體適應(yīng)值越小，則越容易被淘汰。

② 錦標(biāo)賽選擇法

這個(gè)選擇法的方法是：選取若干個(gè)遺傳個(gè)體，在這個(gè)群體中，選取適應(yīng)值高的個(gè)體遺傳到下一代，進(jìn)而重復(fù)上面的過(guò)程，最終形成一個(gè)群體。

③ 最優(yōu)保存策略

也稱精英保留策略[4]，通過(guò)保留最優(yōu)個(gè)體進(jìn)行最優(yōu)選擇，是學(xué)者們比較喜歡采用的一種方法。通過(guò)比較當(dāng)代最優(yōu)個(gè)體和前代最優(yōu)個(gè)體的適應(yīng)值，保留最優(yōu)的個(gè)體。這種選擇方法可避免種群的最優(yōu)個(gè)體不會(huì)被遺傳操作破壞。

2）交叉：模擬生物進(jìn)化的繁殖現(xiàn)象，通過(guò)兩個(gè)個(gè)體基因的交換與組合，把前一代的個(gè)體特征隨機(jī)搭配成對(duì)，來(lái)創(chuàng)造出新的優(yōu)良個(gè)體。主要有單點(diǎn)交叉和多點(diǎn)交叉兩種方式。

3）變異：這個(gè)操作就是在某個(gè)基因編碼串中隨機(jī)改變某一位的值，即把1變?yōu)?。這種操作為提供新個(gè)體提供條件，一般變異概率取值都比較小，大約為0.005-0.01之間，一定程度上，平衡了生命遺傳的多樣性和穩(wěn)定性。

GA算法的操作步驟為：

Step 1 對(duì)參數(shù)進(jìn)行編碼。針對(duì)具體問(wèn)題選擇適當(dāng)?shù)木幋a方式，把參數(shù)集合X轉(zhuǎn)換為相應(yīng)編碼空間S；

Step 2 初始化種群，計(jì)算機(jī)隨機(jī)產(chǎn)生N個(gè)個(gè)體的初始群體，并以這N個(gè)群作為算法計(jì)算的開(kāi)始點(diǎn)；

Step 3 進(jìn)行個(gè)體評(píng)價(jià)。計(jì)算個(gè)體的適應(yīng)值，適應(yīng)值的設(shè)定從求解問(wèn)題的實(shí)際出發(fā)考慮，按一定的概率選擇相應(yīng)的個(gè)體作為父代依照選擇算子進(jìn)行操作；

Step 4 進(jìn)行交叉操作；

Step 5 進(jìn)行變異操作；

Step 6 若滿足終止條件，則執(zhí)行執(zhí)行Step7；否則執(zhí)行Step 2；

Step 7 輸出最優(yōu)解。

2.3算法特點(diǎn)

1）通用性和魯棒性較強(qiáng)。GA算法與常規(guī)傳統(tǒng)尋優(yōu)方法不同的是，它直接利用目標(biāo)函數(shù)作為信息進(jìn)行處理，不需要非常準(zhǔn)確地描述整個(gè)問(wèn)題的特征，也不需要所求問(wèn)題的先驗(yàn)知識(shí)，因此對(duì)知識(shí)的依賴性低[2]。

2）具有全局搜索能力。遺傳算法的群體搜索策略和遺傳算子使遺傳算法得以突破領(lǐng)域搜索的限制，可以實(shí)現(xiàn)動(dòng)態(tài)調(diào)整整個(gè)解空間上的信息和采集、探索相應(yīng)的信息，而變異算子更是有助于跳出局部最優(yōu)值。此外，遺傳算法處理多個(gè)個(gè)體，即是對(duì)多個(gè)個(gè)體進(jìn)行評(píng)估，可以應(yīng)用在多峰分布的搜索空間中，避免陷入局部最優(yōu)值，實(shí)現(xiàn)可遺傳算法的全局搜索能力。

3）具有良好的擴(kuò)展性。遺傳算法是一個(gè)基礎(chǔ)的算法，易于和其他的算法相結(jié)合。

4）易早熟。因算法的局部搜索能力較弱，在求解優(yōu)化問(wèn)題時(shí)，GA算法容易過(guò)早收斂，即便增大迭代次數(shù)，也無(wú)法提高解的質(zhì)量。

5）處理約束問(wèn)題缺乏良好的手段。編碼的不規(guī)范和編碼的表示不準(zhǔn)確，難以把約束問(wèn)題表示出來(lái)。

3遺傳算法的改進(jìn)

3.1 適應(yīng)值函數(shù)遺傳算法

一般情況下，直接把目函數(shù)作為適應(yīng)值的函數(shù)[5]，這樣比較個(gè)體的優(yōu)劣十分便捷。但目標(biāo)函數(shù)值之間往往差別很小，使個(gè)體的選擇概率也很相近，這樣就會(huì)使得遺傳算法的選擇功能被弱化，此時(shí)需要對(duì)目標(biāo)函數(shù)所得到的適應(yīng)值進(jìn)行相對(duì)衡量。結(jié)合動(dòng)態(tài)線性衡量的方法，本文提出適應(yīng)值函數(shù)改進(jìn)型遺傳算法（Modified Fitness GA，MFGA）。

求解最小值時(shí)的公式為：

[F=f-fkmax+ξk]

上式中為適應(yīng)值函數(shù)，為目標(biāo)函數(shù)，為第k代個(gè)體的最小目標(biāo)函數(shù)值， 為選擇壓力調(diào)節(jié)值，它是一個(gè)較小的數(shù)，隨著k的增大而減小，一般采用如下方法設(shè)置：

[ξ0=MξK=K?ξK-1，K∈0.9，0.999] [（2）]

其中M，K為常數(shù)。

算法步驟基本與遺傳算法相同，但Step 2做如下改進(jìn)： 對(duì)目標(biāo)函數(shù)值作為變換，計(jì)算個(gè)體適應(yīng)值，并判斷是否滿足優(yōu)化準(zhǔn)則，若滿足，則輸出最優(yōu)解；否則繼續(xù)下一步。

3.2 大概率變異遺傳算法

為改善算法的穩(wěn)定性，變異概率的取值一般很小，但當(dāng)算法出現(xiàn)“早熟”時(shí)，就要變異很多代才能得出一個(gè)新個(gè)體。因此，針對(duì)這一情況，提出大概率變異遺傳算法（Big probability Mutation GA，BPMGA ） [6]。每一次變異操作的概率都取得很大，使得群體能夠隨機(jī)、獨(dú)立地產(chǎn)生更多新個(gè)體，避免“早熟”。

具體操作過(guò)程：當(dāng)某一代的最大適應(yīng)度[fmax]與平均適應(yīng)度[favg]滿足

[β?][fmax][<][favg] [（3）]

其中，[0.5<β<1]為密集因子，表征個(gè)體的集中程度。

密集因子和變異大概率是BPMGA算法的兩個(gè)重要參數(shù)：

1）密集因子決定變異操作在整個(gè)算法搜索過(guò)程中所占的比重，數(shù)值越接近0.5，則被調(diào)用越頻繁。

2）變異概率越大，穩(wěn)定性就越好，但降低了收斂速度。

大變異遺傳算法步驟基本與遺傳算相同，Step 5稍作改變，內(nèi)容為：如果當(dāng)代最大適應(yīng)度[fmax]與平均適應(yīng)度[favg]滿足[β?][fmax][<][favg]時(shí)，進(jìn)行大概率變異，否則進(jìn)行普通變異操作。

3.3動(dòng)態(tài)調(diào)節(jié)遺傳算法

在GA算法中，交叉概率越大，產(chǎn)生新個(gè)體的速度就越快，但如果過(guò)大，遺傳模式將可能被破壞，而如果過(guò)小，則制約搜索過(guò)程。即對(duì)于過(guò)小變異概率不易產(chǎn)生新個(gè)體，而過(guò)大的變異概率將增加搜索的盲目性。因此針這個(gè)情況，提出動(dòng)態(tài)調(diào)節(jié)遺傳算法[7]（Adjust GA，AdjGA），交叉概率和變異概率能夠隨適應(yīng)度自動(dòng)改變，根據(jù)具體問(wèn)題來(lái)改善優(yōu)化。

動(dòng)態(tài)調(diào)節(jié)遺傳算法中交叉概率[Pc]和變異概率[Pm]為：

[Pc=k1（fmax-f）fmax-favg，f≥favgk2，f

[fmax]為種群體最大適應(yīng)值；[favg]為種群平均適應(yīng)值；[f]為進(jìn)行交叉的兩個(gè)個(gè)體中較大的適應(yīng)值；[f']為要變異個(gè)體的適應(yīng)度值；[k1，k2，k3，k4]為常數(shù)。

動(dòng)態(tài)調(diào)節(jié)遺傳算法步驟在基本遺傳算法Step 4和Step 5上運(yùn)用式來(lái)計(jì)算相應(yīng)的變異和交叉概率。

4 算法測(cè)試

本文選取典型的多峰值測(cè)試函數(shù)：

測(cè)試函數(shù)[maxf（x）=2x2cos（3x）+xsin（5x）+8，?x∈2，10]，理論上的最大值點(diǎn)為[（8.3885，141.1756）]，該函數(shù)形狀如圖1所示。采用一般的尋優(yōu)方法求解該函數(shù)時(shí)容易陷入局部極值。采用基本遺傳算法和上述三種改進(jìn)遺傳算法對(duì)測(cè)試函數(shù)進(jìn)行測(cè)試，參數(shù)設(shè)置如下：種群大小50，迭代次數(shù)100，交叉概率0.8.變異概率0.005，編碼長(zhǎng)度24。

結(jié)果如圖2和表1 所示：

從圖表中可以得出，雖然基本遺傳算法所耗時(shí)少但是改進(jìn)的遺傳函數(shù)迭代了500代后的平均適應(yīng)度值均比基本遺傳算法的精確。BPMGA采用大變異率增強(qiáng)了整個(gè)函數(shù)的全局搜索能力，因此方差相對(duì)來(lái)說(shuō)比較大，但是尋優(yōu)值是較好的。MFGA雖然耗時(shí)較長(zhǎng)，但是均值比較高，最小值也接近最優(yōu)值，說(shuō)明MFGA函數(shù)尋值優(yōu)化較強(qiáng)，每次運(yùn)行結(jié)果偏差小，高提穩(wěn)定性。AdjGA方差較小，說(shuō)明函數(shù)內(nèi)部結(jié)構(gòu)一直隨著外界因素變化自行自我調(diào)節(jié)，適合復(fù)雜問(wèn)題的優(yōu)化計(jì)算。

5 交叉概率Pc和變異概率Pm

遺傳算法應(yīng)用于函數(shù)優(yōu)化問(wèn)題時(shí)，一個(gè)非常重要、值得研究的問(wèn)題是遺傳算法中的控制參數(shù)如何設(shè)定.各個(gè)控制參數(shù)不同選擇，參數(shù)間的不同組合會(huì)對(duì)遺傳算法的性能產(chǎn)生較大的影響，尤其影響算法的收斂性。文獻(xiàn)[8]中對(duì)Pc和Pm交互作用進(jìn)行了研究，其圖像如圖3 所示：

由圖3可知，每條線的形狀大體相同，由此本文得出如下結(jié)論P(yáng)c和Pm的交互作用很小。再者，根據(jù)文獻(xiàn)[8]的實(shí)驗(yàn)結(jié)果，每組實(shí)驗(yàn)中都有一個(gè)Pc和Pm的最優(yōu)組合，共有 20 組實(shí)驗(yàn)數(shù)據(jù)，數(shù)據(jù)積累如表2所示：

根據(jù)相關(guān)性分析知識(shí)，利用 SPSS 計(jì)算出交叉概率Pc和變異概率Pm相關(guān)系數(shù)為0.112，由此亦能說(shuō)明Pc和Pm相關(guān)性不大，因此，在接下來(lái)的實(shí)驗(yàn)中本文采用固定Pc，研究Pm的最優(yōu)取值范圍，固定Pm，研究Pc的最優(yōu)取值范圍。

實(shí)驗(yàn)結(jié)果分析：

遺傳算法中，根據(jù)大量資料給出的Pc和Pm取值范圍，Pc的建議取值范圍是0.4 ～ 0.99，Pm的建議取值范圍是0.0001～ 0.1，本文經(jīng)過(guò)大量實(shí)驗(yàn)，并根據(jù)實(shí)驗(yàn)結(jié)果分析研究，給出[f（x）=x″]一類冪函數(shù)求得全局最優(yōu)解時(shí)所用最少遺傳代數(shù)的均值，Pm取值范圍是[0.009，0.03]，Pc的取值范圍是[0.6，0.99]。

6 結(jié)束語(yǔ)

遺傳算法是一種模擬自然生命進(jìn)化的算法，為復(fù)雜系統(tǒng)的優(yōu)化提供了一種新的方法，自提出以來(lái)，關(guān)注熱點(diǎn)高，經(jīng)過(guò)發(fā)展，如此理論、應(yīng)用都很成熟，對(duì)其他仿生算法的提出和改進(jìn)都具有借鑒性。本文介紹了遺傳算法的基本原理和操作流程，對(duì)三個(gè)重要的操作因子：選擇、交叉和變異分別做了闡述。引進(jìn)三種常見(jiàn)的改進(jìn)遺傳算法，并修改了適應(yīng)值函數(shù)遺傳算法的計(jì)算方式。對(duì)算法的交叉概率和變異概率進(jìn)行了研究，得出相應(yīng)結(jié)論。

參考文獻(xiàn)：

[1] 玄光男，程潤(rùn)偉. 遺傳算法與工程優(yōu)化[M].北京：清華大學(xué)出版社，2011 ：82-89.

[2] 李敏強(qiáng)，寇紀(jì)淞，林丹，等.遺傳算法的基本理論與應(yīng)[M].北京： 科學(xué)出版社，2012.

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

[4] 喻壽益，鄺溯瓊.保留精英遺傳算法收斂性和收斂速度的鞅方法分析[J].控制理論與應(yīng)用，2010，27（ 7） ：843-848.

[5] 馬永杰，馬義德，蔣兆遠(yuǎn)，等.一種快速遺傳算法及其收斂性[J].系統(tǒng)工程與電子技術(shù)，2009，31（3） ：714-718.

[6] ZHANG Jin-hua，ZHUANG Jian，DU Hai-feng，et al. Self-organizing genetic algorithm based tuning of PID controllers[J].Information Sciences，2009，179（ 7） ： 1007-1018.

[7] 申曉寧，郭毓，陳慶偉，等.一種保持群體多樣性的多目標(biāo)遺傳算法[J].控制與決策，2008，23（ 12） ：1435-1440.

[8] Eusuff M M，Lansey K E.Optimization of water distribution network design usingthe shuffled frog leaping algorithm[J].Water Resources Planning and Management，2013，129（3）：210-25.