遺傳算法變異算子的改進(jìn)

王春陽(yáng),趙玉慶,謝金興,蘇本堂

遺傳算法變異算子的改進(jìn)

王春陽(yáng),趙玉慶,謝金興,蘇本堂*

山東農(nóng)業(yè)大學(xué)信息科學(xué)與工程學(xué)院, 山東泰安 271018

為了提高遺傳算法的全局尋優(yōu)能力，本文提出變異算子的一種新的構(gòu)造機(jī)制。在種群進(jìn)化的初始階段，使變異點(diǎn)發(fā)生在二進(jìn)制染色體的高位區(qū)，以保證種群的多樣性；在進(jìn)化的中期階段，使變異點(diǎn)發(fā)生在染色體的中位區(qū)，以保持種群持續(xù)大范圍尋優(yōu)；在收斂階段，使變異點(diǎn)發(fā)生在染色體的低位區(qū)，以提高最優(yōu)個(gè)體的精度。數(shù)值試驗(yàn)表明，在不增加算法整體計(jì)算量的前提下，這樣構(gòu)造的變異算子，對(duì)避免遺傳算法出現(xiàn)早熟具有明顯的積極作用。

遺傳算法; 變異算子; 二進(jìn)制

其中表示決策變量個(gè)數(shù)，()為多峰函數(shù)。記(1,2,…,l)，=(1,2,…,u)，[,]為可行解空間。

多峰函數(shù)全局最優(yōu)化問(wèn)題的求解方法有兩類(lèi)，第一類(lèi)是確定性算法，譬如填充函數(shù)法[1]、隧道法[2]、積分-水平集法[3]、割峰函數(shù)法[4]等；另一類(lèi)是智能算法，典型的有遺傳算法[5]、模擬退火算法[6]、粒子群算法[7]等。確定性算法計(jì)算效率高，但對(duì)目標(biāo)函數(shù)的性態(tài)要求苛刻；智能算法雖然計(jì)算量較大，但可以并行計(jì)算，并且對(duì)目標(biāo)函數(shù)的性態(tài)要求低。

作為一種應(yīng)用廣泛的智能算法，遺傳算法的改進(jìn)一直受到學(xué)術(shù)界的重視。這些改進(jìn)工作主要圍繞提高算法的計(jì)算效率、克服早熟現(xiàn)象展開(kāi)。譬如，江中央等提出了一種自適應(yīng)正交交叉算子的方法，并引入了基于種群分割和單形搜索的局部搜索策略[8]；曾三友[9]等把正交實(shí)驗(yàn)方法和統(tǒng)計(jì)優(yōu)化方法相結(jié)合，提出了一種基于正交設(shè)計(jì)的多目標(biāo)最優(yōu)化算法；謝燕麗[10]等給出一種基于黃金分割法的變異算子構(gòu)造。

本文給出一種控制變異算子變異點(diǎn)的策略，在種群進(jìn)化的不同階段，選擇不同的位置進(jìn)行變異。將該變異算子與文[8]的遺傳算法相結(jié)合，對(duì)提高算法的計(jì)算效率和健壯性有較為明顯的作用。

1 遺傳算法及其變異算子

遺傳算法的核心內(nèi)容由參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作設(shè)計(jì)、控制參數(shù)設(shè)定等五個(gè)要素組成，其中遺傳操作分交叉、選擇和變異三個(gè)環(huán)節(jié)。

變異是對(duì)基因鏈上的某個(gè)基因按較小概率改變，以此保持個(gè)體的多樣性，克服早熟現(xiàn)象。變異算子是遺傳算法產(chǎn)生新個(gè)體的重要操作，是影響算法收斂性能的關(guān)鍵。變異操作主要有四種形式：

（1）基本位變異。對(duì)個(gè)體編碼串以一定的變異概率隨機(jī)指定某一位或某幾位基因進(jìn)行變異操作。

（2）均勻變異。分別用符合某一范圍內(nèi)均勻分布的隨機(jī)數(shù)，以某一較小的概率來(lái)替換個(gè)體編碼串中各個(gè)基因上的原有基因值。

（3）二元變異。對(duì)于選取的兩條染色體，通過(guò)二元變異操作生成兩條新個(gè)體中的各個(gè)基因分別取原染色體對(duì)應(yīng)基因值的同或/異或。

（4）高斯變異。用正態(tài)分布的一個(gè)隨機(jī)數(shù)來(lái)替換原有基因值。其操作過(guò)程與均勻變異類(lèi)似。

2 變異算子的改進(jìn)

2.1 變異算子的改進(jìn)思路

本文采用二進(jìn)制編碼，在種群進(jìn)化的不同階段，對(duì)變異基因的位置采取不同的控制策略。

高位變異：指在遺傳進(jìn)化的初始階段（第1~1代，其中0<1<(/2)，代表種群進(jìn)化的代數(shù)）時(shí)，控制變異發(fā)生在染色體的高位區(qū)，使變異產(chǎn)生的新個(gè)體能夠均勻的分布在整個(gè)解空間中，從而使個(gè)體的分布具有多樣性，提高了種群基因庫(kù)的多樣性，避免了早熟現(xiàn)象的發(fā)生。

中位變異：指在遺傳進(jìn)化的中期階段（第(1+1)~2代，其中1<2<）時(shí)，通過(guò)控制變異發(fā)生在染色體的中位區(qū)，使種群的個(gè)體在可行解空間持續(xù)大范圍尋優(yōu)，加快算法收斂的速度。

低位變異：指在遺傳進(jìn)化的收斂階段（第2+1~代）時(shí)，即在種群進(jìn)化末期，整個(gè)種群基本上收斂在全局最優(yōu)解的附近，通過(guò)控制變異發(fā)生在染色體的低位區(qū)，有利于提高最優(yōu)個(gè)體的精度。

2.2 改進(jìn)變異算子的偽代碼

Step1 根據(jù)解空間和精度，將實(shí)數(shù)值個(gè)體轉(zhuǎn)化為二進(jìn)制表示的個(gè)體

Step2分割二進(jìn)制段

對(duì)每一個(gè)存儲(chǔ)在數(shù)組（下標(biāo)從0開(kāi)始）中的長(zhǎng)度為BitLength二進(jìn)制染色體進(jìn)行以下劃分，使其染色體的表示變?yōu)椋篬高位，中位，低位] BitLength1=[BitLength-BitLength/3]；BitLength2=[BitLength1-BitLength/3]。

將每一個(gè)二進(jìn)制染色體均勻地分割為三部分，分別為：“高位”：[0, BitLength2]；“中位”：(BitLength2, BitLength1]；“低位”：(BitLength1, BitLength]

Step3進(jìn)行變異

判斷：如果為1~1代，則在染色體的“高位”，隨機(jī)選取一個(gè)位點(diǎn)進(jìn)行取反。

判斷：如果為(1+1)~2代，則在染色體的“中位”，隨機(jī)選取一個(gè)位點(diǎn)進(jìn)行取反。

判斷：如果為(2+1)~代，則在染色體的“低位”，隨機(jī)選取一個(gè)位點(diǎn)進(jìn)行取反。

3 遺傳算法的實(shí)現(xiàn)

除了上述給出的變異算子，本文采納了文[8]算法中的自適應(yīng)正交交叉算子和聚類(lèi)局部搜索技術(shù)，以增強(qiáng)算法的局部尋優(yōu)能力，簡(jiǎn)述如下。

3.1 自適應(yīng)正交交叉算子(簡(jiǎn)稱(chēng)SOC)

自適應(yīng)正交交叉算子是選取兩個(gè)父代個(gè)體，指定正交設(shè)計(jì)的水平Q，對(duì)超長(zhǎng)方體的每一維按選定的水平數(shù)進(jìn)行離散化。正交設(shè)計(jì)的因素F依據(jù)兩個(gè)父代個(gè)體數(shù)值接近的分量個(gè)數(shù)動(dòng)態(tài)確定，并通過(guò)正交設(shè)計(jì)產(chǎn)生子代個(gè)體。

3.2 聚類(lèi)局部搜索

聚類(lèi)局部搜索策略是先對(duì)群體進(jìn)行聚類(lèi)，將種群分割為互不相交的局部鄰域，使每個(gè)子種群僅覆蓋搜索空間一個(gè)較小的鄰域。對(duì)每個(gè)子種群，利用單形交叉算子[11]進(jìn)行局部搜索，以提高單形搜索的局部收斂速度；同時(shí)對(duì)不相交的局部鄰域進(jìn)行并行搜索,以實(shí)現(xiàn)快速的全局搜索。

3.3 遺傳算法實(shí)現(xiàn)的主要步驟

Step1種群初始化：正交設(shè)計(jì)產(chǎn)生初始種群。

Step2生成臨時(shí)種群?：每代種群的每一個(gè)個(gè)體以一定的概率被選擇進(jìn)臨時(shí)種群中。

若臨時(shí)種群個(gè)體數(shù)為奇數(shù)，則再?gòu)倪M(jìn)化種群中隨機(jī)選擇一個(gè)個(gè)體加入到臨時(shí)種群中。

Step3交叉操作：對(duì)臨時(shí)種群中的個(gè)體進(jìn)行隨機(jī)配對(duì)，對(duì)其中的每一個(gè)個(gè)體都以概率p進(jìn)行SOC，將交叉后產(chǎn)生的新一代個(gè)體加入到群體集合C中。

Step4局部搜索：臨時(shí)種群?經(jīng)過(guò)最近原則局部搜索后生成新種群L。

Step5變異：種群?的任一個(gè)體p=(p,1,p,2,…,p,N)，?{1,2,…}（其中，代表種群個(gè)體數(shù)），以概率p參與變異操作，選擇出要變異的個(gè)體后，按照2.2中改進(jìn)的變異算法進(jìn)行變異，群體經(jīng)變異后生成的新種群記G。

Step6選擇：最優(yōu)選擇策略，從種群(P+C+L+G)中選擇適應(yīng)度值最好的初始種群個(gè)數(shù)的70%進(jìn)入下一代種群，再?gòu)姆N群(P+C+L+G)剩余的個(gè)體中，隨機(jī)選擇至種群最初個(gè)數(shù)。

Step7終止判斷：達(dá)到滿意結(jié)果，結(jié)束并輸出結(jié)果，否則轉(zhuǎn)Step2。

4 數(shù)值試驗(yàn)

為了測(cè)試本文提出的改進(jìn)的變異算子的性能，我們采用文[8]中的14個(gè)高維的Benchmark函數(shù)作為測(cè)試集，并將求解效果與文[8]的結(jié)果進(jìn)行了比較。對(duì)于函數(shù)1~6及函數(shù)10~14，=30；對(duì)函數(shù)7~9，=100。函數(shù)1~8屬于多峰函數(shù)，每一個(gè)函數(shù)具有多個(gè)局部極值點(diǎn)，其中函數(shù)7具有100!=9.33×10157個(gè)局部極值點(diǎn)。

對(duì)所有的測(cè)試函數(shù)，參數(shù)的選取與文[8]是一致的。種群的規(guī)模=200，同時(shí)取p=0.6，p=0.1。當(dāng)程序運(yùn)行達(dá)到=120代或找到最優(yōu)解時(shí)，就終止運(yùn)行，其中變異算子的1=20，2=70。對(duì)每一個(gè)函數(shù)，在相同的條件下獨(dú)立運(yùn)行30次，記錄其平均函數(shù)評(píng)價(jià)次數(shù)(M-num-fun)，最優(yōu)平均值(M-best)和標(biāo)準(zhǔn)差(St.dev)。

由表1可見(jiàn)，函數(shù)1~4、10~14得到全局最優(yōu)解，而5~9得到近似最優(yōu)解。與[8]的結(jié)果相比較，函數(shù)3，5，7，9在精確度與穩(wěn)定性方面均有了明顯的提高，函數(shù)1，8在穩(wěn)定性方面有較大的提升，函數(shù)6在精確度與穩(wěn)定性方面有所提高，其余函數(shù)在精確度與穩(wěn)定性方面均與文[8]的結(jié)果相同。

表1 兩種算法（本文算法，HSOGA[8]）對(duì)14個(gè)測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果比較

5 結(jié)語(yǔ)

隨著計(jì)算機(jī)技術(shù)的不斷進(jìn)步和超級(jí)計(jì)算的廣泛應(yīng)用，遺傳算法作為求解復(fù)雜優(yōu)化問(wèn)題全局最優(yōu)解的有效算法之一，構(gòu)造健壯性更好的算法是有意義的。本文在前人的基礎(chǔ)上給出遺傳算子設(shè)計(jì)的新思路，使算法的全局搜索能力有所提高，對(duì)克服早熟現(xiàn)象、提高收斂速度具有比較明顯的作用。

[1] Ge R: A filled function method for finding a global minimizer of a function of severalvariables[J]. Math. Prog,1990,46:191-204

[2] Levy AV, Montalvo A.The tunneling algorithm for the global minimization of functions[J]. SIAM J. Sci. Stat. Comput,1985,6:15-29

[3] 田蔚文,鄔冬華,張連生,等.一種修正的求約束總極值的積分-水平集方法[J].應(yīng)用數(shù)學(xué)和力學(xué),2004,25(2):181-188

[4] Wang Y, Fang W, Wu T. A cut-peak function method for global optimization [J].Comput. Appl. Math, 2009,230:135–142

[5] Holland JH. Adaptation in Natural and Artificial Systems[M].Cambridge: MIT Press, 1992

[6] 康立山.非數(shù)值并行算法-模擬退火算法[M].北京:科學(xué)出版社,1994

[7] Kennedy J, Eberhart R. Particle Swarm Optimization [M].New York: IEEE, 1995

[8] 江中央,蔡自興,王勇.求解全局優(yōu)化問(wèn)題的混合自適應(yīng)正交遺傳算法[J].軟件學(xué)報(bào),2010,21(6):1296-1307

[9] 曾三友,魏巍,康立三,等.基于正交設(shè)計(jì)的多目標(biāo)演化算法[J].計(jì)算機(jī)學(xué)報(bào),2005,28(7):1153-1162

[10] 謝燕麗,許青林,姜文超.一種基于交叉和變異算子改進(jìn)的遺傳算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014,24(4):80-83

[11] 蔡自興,江中央,王勇,等.一種新的基于正交實(shí)驗(yàn)設(shè)計(jì)的約束優(yōu)化進(jìn)化算法[J].計(jì)算機(jī)學(xué)報(bào),2010,33(5):855-864

An Improved Genetic Algorithm Variation Operator

WANG Chun-yang, ZHAO Yu-qing, XIE Jin-xing, SU Ben-tang*

271018,

In order to improve the global optimization ability of genetic algorithm, this paper proposes a new construction mechanism of the mutation operator. In the initial stage of population evolution, we select the mutation point in the high region of the binary chromosome to ensure the diversity of the population; in the middle stage of evolution, we make the mutation point occur in the middle region of the chromosome to maintain a large range of population optimization, while in the convergence phase, the mutation point occurred in the lower region of the chromosome to improve the accuracy of the optimal individual. Numerical experiments show that the mutation operator constructed in this way has obvious positive effects on avoiding the premature development of the genetic algorithm without increasing the overall calculation of the algorithm.

Genetic algorithm; mutation operator; binary system

TP301.6

A

1000-2324(2019)05-0898-04

10.3969/j.issn.1000-2324.2019.05.036

2018-06-12

2018-10-26

國(guó)家大學(xué)生科技訓(xùn)練計(jì)劃項(xiàng)目(201710434312)

王春陽(yáng)(1995-),男,本科生,研究方向:計(jì)算科學(xué). E-mail:15726569335@163.com

Author for correspondence.E-mail:sbtmath@sdau.edu.cn