一種含全交叉算子的改進遺傳算法

張宏偉， 張向鋒， 文傳博

(上海電機學院 電氣學院， 上海 201306)

一種含全交叉算子的改進遺傳算法

張宏偉， 張向鋒， 文傳博

(上海電機學院 電氣學院， 上海 201306)

提出一種含全交叉算子的遺傳算法。與傳統的基于點的交叉不同，全交叉算子選擇與、或、異或3種方式中的一種作為染色體之間的交叉方式。為了提高算法進化速度，從種群中選擇優秀個體組成精英集，每輪更新精英集，種群中染色體進行交叉操作時會先選擇一種交叉方式，再從精英集中隨機選擇精英個體作為交叉染色體進行交配。在同樣情況下，與單點交叉、兩點、多點交叉進行比較，仿真實驗結果表明，含全交叉的改進遺傳算法有較好的優化效果。

遺傳算法; 全交叉算子; 交叉方式; 精英集

遺傳算法(Genetic Algorithm，GA)由美國Holland教授于1975年首次提出。該算法通過模擬自然界生物進化過程來搜索問題的最優解，具有較強的全局優化能力和魯棒性，不需要已知太多條件，即可得到較優的結果，受到學者們的廣泛關注。目前已在函數優化[1]、數據處理[2]、神經網絡優化[3]、設備控制[4]、系統辨識[5]等多方面得到廣泛應用,但在優化一些高維復雜問題時，GA存在著早熟、收斂緩慢及收斂精度低的問題。

為了克服GA存在的上述問題，學者們研究了不少改進措施：文獻[6]中將交叉算子引入引向因子并加強群體信息共享，使得GA進化具有一定的方向性；文獻[7-8]中將個體相似度引入到GA中，來調整算法交叉操作，改善種群多樣性；文獻[9]中將子代中適應度最差的個體用父代中適應度最好的個體替換，使父代中優良的基因得以延續；文獻[10]中提出一種基于種群算法投資組合的策略；文獻[11]中通過最小生成樹聚類將種群劃分為若干個子種群, 子種群內及不同子種群間同時進行遺傳操作,保證了收斂速度和多樣性；文獻[12-13]中將GA與模擬退火算法相結合，提高了全局尋優能力；文獻[14]中綜合GA和粒子群算法的優點提出了混合優化算法。

GA已問世多年，其主要步驟是選擇、交叉、變異，其中在交叉運算中，人們還是采用以某一點或某幾點為界交換兩條染色體前后的部分，這里統稱之為基于點的交叉。本文研究了一種含全交叉算子的改進遺傳算法(Genetic Algorithm with Total Crossover Operator, GATCO), 全交叉算子與目前的基于點的交叉不同，選擇與、或、異或3種方式中一種作為染色體之間的交叉方式。為提升算法的進化速度，改變以往GA從種群中選擇隨機的或相鄰的兩個個體進行交叉的策略，而是從種群中選擇優秀染色體組成精英集，每個染色體的交叉對象均來自精英集，每輪迭代結束后會更新精英集。GATCO算法中，每個染色體進行交叉操作時，先取隨機數與交叉概率進行比較,若小于交叉概率，再從精英集中隨機選擇精英個體作為交叉染色體,采用全交叉方式進行交配。與單點交叉、兩點、多點交叉進行實比較，結果表明其具有較好的優化效果。

1 含全交叉算子的改進遺傳算法

1.1全交叉算子

GA是模仿自然界生物進化的一種算法，其主要通過選擇、交叉、變異來實現染色體種群的進化。目前，GA的交叉操作主要有單點交叉、兩點交叉和多點交叉，但交叉后的效果不理想或編程過于復雜。針對這一問題，本文提出一種全交叉算子，它在2條染色體之間進行與、或、異或等位運算作為交叉操作。全交叉算子具有以下優勢：① 采用數學中位運算中常用的與、或、異或作為交叉方式，可視每一點都能交叉；② 相比目前主要的單點、兩點和多點交叉3種交叉方式，豐富了交叉形式；③ 目前很多編程語言或工具都自帶位運算函數，如算法仿真中常用的軟件Matlab就自帶與、或、異或等位運算函數(在Matlab中分別為bitand、bitor和bitxor函數)，方便了研究人員進行GA編程。

1.2精英集

GA的交叉操作，一般是選擇種群內相鄰或隨機的兩個染色體進行交叉[15-16]，這樣無法保證交叉對象的優劣，將影響交叉操作的效果，影響算法進化速度。而在GATCO算法中，為了提升交叉速度，將種群中的染色體與精英集中選擇的一條精英染色體進行交叉。精英集中由種群歷史中優秀個體組成，設其規模為e(e小于整個染色體種群規模p)。初始化時，可從種群中選擇e條染色體組成初始的精英集，以后每輪染色體種群更新完畢后，對精英集也進行更新。

精英集更新策略如下：將種群中每條染色體一次與精英集中每條染色體進行比較，若種群染色體比精英集中染色體適應度值更優，則該精英染色體被該種群染色體替換掉，同時該條染色體不會與后面的精英染色體比較，防止精英染色體中有重復。這樣，算法優化過程中出現的優秀染色體，被保存下來。GATCO中，種群個體只與精英集中個體進行交叉，而不會與種群中其他個體進行交叉，以促使算法向好的方向不斷優化。

1.3GATCO的步驟

(1) 初始化染色體種群P(用二進制編碼)，并隨機從染色體種群中選e條染色體組成初始的精英集E;

(2) 對染色體種群P進行選擇操作;

(3) 對染色體種群P進行改進的交叉操作，即取(0，1)間的一個隨機數m與交叉概率Pc比較，若m

(4) 對染色體種群P進行變異操作;

(5) 更新染色體種群P和精英集E;

(6) 本輪迭代完畢，返回到步驟(2)，直到達到迭代次數。

GATCO算法流程如圖1所示。

圖1 GATCO算法流程圖

2 仿真實驗

2.1算法參數設置與測試函數

為檢驗GATCO的性能，本文選用3個標準測試函數(見表1)來測試。這些函數的理論最小值均為 0，全局最優解通常分布在狹小的空間范圍內，常規的優化算法很難得到最優解，且優化難度隨著變量維數的增加而急劇上升。實驗中,算法參數設置如下:染色體種群規模p=20，Pc=0.7，變異概率Pm=0.05，維數D=20，每一維變量二進制編碼時精確到0.01以下，為方便編程統一為18位編碼，即染色體總長為360，迭代次數W=2 000。算法均采用輪盤賭算子，e=3。本文實驗環境如下：Intel i5 CPU 2.3 GHz，RAM 8.00 GB，Window 2007操作系統，Matlab 2010b。

2.2最優全交叉方式或組合的選擇

在算法的整個迭代過程中，所有個體都可采用單一一種全交叉方式，也可以2種或3種全交叉方式組成一個全交叉組合，且每一輪迭代種群中的每個個體隨機從全交叉組合中選擇一種全交叉方式進行全交叉操作，因此，進行以下實驗比較它們的策略優劣。本文分別采用與、或、異或3種單一全交叉方式，以及與+或、與+異或、或+異或、與+或+異或4種的全交叉組合，利用GATCO算法對表1中的測試函數進行優化實驗。其中，在GAT-CO采用全交叉組合的情況下，當對種群中每個染色體進行交叉操作時，會先產生一個不大于全交叉組合內全交叉方式數量的隨機整數，根據該隨機整數在組合中選擇一種全交叉方式。實驗各進行20次。表2給出了不同全交叉方式下GATCO對測試函數的平均適應度。

由表2可見，在單一全交叉方式或全交叉組合下，與+或的全交叉組合方式對3個測試函數的優化結果都是最優，與交叉對3個測試函數優化結果最差(在函數Rastigrin和Griewank上與交叉所得結果最差，而在函數Schwefel上，與交叉所得結果也僅僅只是稍優于或交叉)，因此,應選擇與+或的全交叉組合作為GATCO的全交叉算子，故以下仿真實驗的全交叉均采用與+或的全交叉組合的方式。

表1 標準測試函數

表2 不同全交叉方式下GATCO對測試函數的平均適應度

2.3GATCO與基于點交叉的GA的比較

分別利用GATCO與基于點交叉的GA對表1中的測試函數進行優化。其中，基于點交叉的GA選擇單點交叉、2點交叉和3點交叉3種形式。GATCO的交叉算子采用與+或的全交叉組合作為控制變量，兩種算法的交叉對象均來自精英集，參數設置不變,每組實驗進行20次，表3給出了含不同交叉算子的GA對測試函數的優化結果。

表3 含不同交叉算子的GA對測試函數的優化結果

注：MB為最優適應度值；Mavg為10次適應度值的平均值；Mstd為適應度值的標準差

由表3可見，① GATCO對函數Griewank和Schwefel的優化結果均明顯優于基于點交叉的GA；而對于函數Rastigrin，與基于點交叉的GA相比較，GATCO在MB和Mavg這兩項指標上表現最好，由此可知，對函數Rastigrin的優化仍是GATCO效果最好。② 在基于點交叉的GA中，采用單點交叉GA對函數Rastigrin和Schwefel的優化效果最好，采用三點交叉的GA對函數Griewank的優化效果最好，采用兩點交叉GA對測試函數優化結果最差。

圖2給出了GATCO和基于點交叉GA對不同測試函數的迭代優化比較。由圖2可見，GATCO在迭代到600次時最優適應度值已明顯優于基于點交叉的GA，而且此后GATCO仍然有迭代優化的能力；而在基于點交叉的GA中，相較于2點交叉和3點交叉，單點交叉的GA優化效果更佳。

(a) Rastigrin函數

圖2GATCO和基于點交叉GA對不同測試函數的迭代優化比較

Fig.2 Iterative optimization comparison of GATCO and GA based on point cross over different test functions

3.4精英集規模對GATCO影響

表4 不同e值下GA TCO的對測試函數的優化結果

4 結 語

為了改善GA算法交叉運算時效果不好或編程較復雜的問題，本文提出了一種含全交叉算子的改進遺傳算法。該算法使用一種新的交叉方式,即采用數學位運算中常用的與、或、異或作為交叉方式。該交叉方式可視為每一點都能交叉，交叉形式更加豐富，且易于研究人員編程。為使交叉產生的子代更優良，從種群中選擇優秀染色體組成精英集，每輪對其更新，交叉操作時限定只能與精英集中個體交叉。仿真結果表明，與基于點交叉(單點交叉、兩點交叉或多點交叉)的GA相對，所提出的GATCO能夠有效改善GA交叉效果，得到更好的最優解。

[1] 張晨，譚小球，楊林峰. 改進量子遺傳算法在函數尋優中的應用 [J].微型機與應用，2016,35(11):83-86.

[2] 潘國榮，谷川. 改進的遺傳算法用于工業測量數據處理 [J].大地測量與地球動力學，2008,28(1):55-58．

[3] 武彤，程輝. 用遺傳算法改進的BP神經網絡剪枝算法來優化決策樹模型 [J].計算機科學，2013,40(S2):278-281.

[4] 甘屹，郭家忠，王子健，等. 基于遺傳算法改進的太陽能跟蹤控制 [J].控制工程，2015,22(1):157-163.

[5] 任子武，傘治．自適應遺傳算法的改進及在系統辨識中應用研究 [J]．系統仿真學報，2006,18(1) : 41-43，66.

[6] 瞿顏，袁建濤，郭陳江，等. 一種基于引向因子和反向搜索的改進遺傳算法 [J].計算機仿真，2015,32(1):301-305.

[7] 湯可宗，張彤，羅立明. 基于個體相似性評價策略的改進遺傳算法 [J].計算機應用與軟件，2016,33(3):236-239.

[8] 文藝，潘大志. 用于求解TSP問題的改進遺傳算法 [J].計算機科學，2016,43(S1):90-92.

[9] 徐傳敬，趙敏，李天明. 一種改進遺傳算法的PID參數整定研究 [J].計算機技術與發展，2016,26(9):12-15.

[10] PENG Fei，TANG Ke，CHEN Guoliang, et al．Population-based algorithm portfolios for numerical optimization [J]．IEEE Transactions on Evolutionary Computation，2010,14(5): 782-800．

[11] 楊新武，楊麗軍. 基于交叉模型的改進遺傳算法 [J].控制與決策，2016,31(10):1837-1844.

[12] 曹恒智，余先川．單親遺傳模擬退火及在組合優化問題中的應用 [J]．北京郵電大學學報，2008,31(3): 38-41．[13] 郭曉剛，蔡金玲，朱莉. 改進遺傳算法在圖像分割中的應用 [J].儀表技術，2016(2):23-25.

[14] 馬超，鄧超，熊堯，等．一種基于混合遺傳和粒子群的智能優化算法 [J]．計算機研究與發展，2013,50(11):2278-2286．

[15] 劉浩然，趙翠香，李軒，等. 一種基于改進遺傳算法的神經網絡優化算法研究 [J].儀器儀表學報，2016,37(7):1573-1580.

[16] 周生偉，蔣同海，張榮輝. 改進遺傳算法求解VRP問題 [J].計算機仿真，2013,30(12):140-143.

An Improved Genetic Algorithm with Total Crossover Operator

ZHANGHongwei,ZHANGXiangfeng,WENChuanbo

(School of Electrical Engineering, Shanghai Dianji University, Shanghai 201306, China)

Differing from the traditional crossover operator, a genetic algorithm containing a total crossover operator is proposed in this paper, which uses AND, OR, XOR operators as a cross method. To improve evolution speed of the algorithm, the algorithm selects elite individuals from the population to form an elite set, and the elite set updates per round. A cross method and an elite individual from the elite set are selected when chromosomes conduct crossover. Simulations show that the improved genetic algorithm with total crossover has better optimization effect as compared with single point crossing, two-point and multi-point algorithms.

genetic algorithm (GA); total crossover operator; cross method; elite set

張向鋒(1977-)，女，副教授，博士，主要研究方向為智能控制、智能優化算法等，E-mail:zhangxfasdju.edu.cn

TP 18

A

2017 -05 -31

國家自然科學基金項目資助(61374136)；上海市人才發展基金項目資助(201511)

張宏偉(1993-)，男，碩士生，主要研究方向為微電網優化配置, E-mail:zhw_jeff93@126.com

2095 - 0020(2017)04 -0196 - 05