王春陽,趙玉慶,謝金興,蘇本堂

遺傳算法變異算子的改進

王春陽,趙玉慶,謝金興,蘇本堂*

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

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

遺傳算法; 變異算子; 二進制

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

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

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

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

1 遺傳算法及其變異算子

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

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

（1）基本位變異。對個體編碼串以一定的變異概率隨機指定某一位或某幾位基因進行變異操作。

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

（3）二元變異。對于選取的兩條染色體，通過二元變異操作生成兩條新個體中的各個基因分別取原染色體對應基因值的同或/異或。

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

2 變異算子的改進

2.1 變異算子的改進思路

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

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

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

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

2.2 改進變異算子的偽代碼

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

Step2分割二進制段

對每一個存儲在數(shù)組（下標從0開始）中的長度為BitLength二進制染色體進行以下劃分，使其染色體的表示變?yōu)椋篬高位，中位，低位] BitLength1=[BitLength-BitLength/3]；BitLength2=[BitLength1-BitLength/3]。

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

Step3進行變異

判斷：如果為1~1代，則在染色體的“高位”，隨機選取一個位點進行取反。

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

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

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

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

3.1 自適應正交交叉算子(簡稱SOC)

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

3.2 聚類局部搜索

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

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

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

Step2生成臨時種群?：每代種群的每一個個體以一定的概率被選擇進臨時種群中。

若臨時種群個體數(shù)為奇數(shù)，則再從進化種群中隨機選擇一個個體加入到臨時種群中。

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

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

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

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

Step7終止判斷：達到滿意結果，結束并輸出結果，否則轉Step2。

4 數(shù)值試驗

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

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

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

表1 兩種算法（本文算法，HSOGA[8]）對14個測試函數(shù)的實驗結果比較

5 結語

隨著計算機技術的不斷進步和超級計算的廣泛應用，遺傳算法作為求解復雜優(yōu)化問題全局最優(yōu)解的有效算法之一，構造健壯性更好的算法是有意義的。本文在前人的基礎上給出遺傳算子設計的新思路，使算法的全局搜索能力有所提高，對克服早熟現(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].應用數(shù)學和力學,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].北京:科學出版社,1994

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

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

[9] 曾三友,魏巍,康立三,等.基于正交設計的多目標演化算法[J].計算機學報,2005,28(7):1153-1162

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

[11] 蔡自興,江中央,王勇,等.一種新的基于正交實驗設計的約束優(yōu)化進化算法[J].計算機學報,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

國家大學生科技訓練計劃項目(201710434312)

王春陽(1995-),男,本科生,研究方向:計算科學. E-mail:15726569335@163.com

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