一類適應度函數的遺傳算法編碼

朱春媚，莫鴻強

(1.電子科技大學中山學院 機電工程學院，廣東 中山 528400； 2.華南理工大學 自動化科學與工程學院，廣州 510641) (*通信作者電子郵箱cmzhu@zsc.edu.cn)

一類適應度函數的遺傳算法編碼

朱春媚1*，莫鴻強2

(1.電子科技大學中山學院 機電工程學院，廣東 中山 528400； 2.華南理工大學 自動化科學與工程學院，廣州 510641) (*通信作者電子郵箱cmzhu@zsc.edu.cn)

針對在探討適應度函數的周期性特點與整數編碼元數之間的關聯(lián)特性時，一階積木塊數量對編碼性能的評價不一定成立的問題，提出以累積逃脫概率(AEP)作為遺傳算法(GA)編碼性能的評價指標，對以頻率為正整數m的整數次冪的正弦函數為基函數線性組合構成的適應度函數編碼展開研究。首先給出了該類適應度函數的一般形式和m進制整數編碼的含義；然后介紹了AEP的定義，并根據函數特點制定了AEP的計算方法；最后分析比較了該類適應度函數在不同整數編碼下的AEP，指出其采用m元整數編碼時更容易進化。仿真結果表明，該類適應度函數采用m元整數編碼時，其最終優(yōu)化結果和群體適應度均值的上升時間皆明顯優(yōu)于其他編碼，反映了AEP能有效評價編碼的性能，并再次驗證了對于該類適應度函數m元整數編碼優(yōu)于非m元整數編碼的結論。

編碼；性能評價；遺傳算法；周期性適應度函數；累積逃脫概率

0 引言

編碼作為遺傳算法(Genetic Algorithm, GA)設計中的首要環(huán)節(jié)，決定著遺傳算法的精度和效率，是算法能否解決問題的前提。隨著GA研究和應用的日益深入，編碼方法也在不斷地改進，目前已有多種編碼方式，常用的有二進制編碼、實數編碼、矩陣編碼、樹型編碼和量子編碼等[1-3]。自Holland[4]提出GA以來，二進制編碼成為應用最早和最廣的編碼方式，具有簡單、符合最小符號集編碼原則和模式定理的優(yōu)點，但對于一些多維、高精度連續(xù)函數優(yōu)化問題，二進編碼又存在不能直接反映問題的固有結構和個體編碼長度大等不足。針對二進制編碼的缺陷，Michalewicz等[5]提出了實數編碼，實數編碼精度高，適合復雜大空間搜索，對多參數連續(xù)函數優(yōu)化問題具有更好的性能。矩陣編碼尤其適用于求解大規(guī)模復雜問題、高維數值優(yōu)化問題和多目標優(yōu)化問題，例如文獻[6]和[7]分別采用矩陣編碼的遺傳算法實現(xiàn)試題庫自動組卷和模擬集成電路模塊布局。樹型編碼也是一種有效的編碼方式，主要適用于求解能用樹或圖表示的優(yōu)化問題，如Web服務選擇[8]、配電網優(yōu)化規(guī)劃[9]等。量子編碼是將染色體用量子的態(tài)矢量表示，使算法能夠在較小的種群規(guī)模下求得最優(yōu)解，被廣泛應用于組合優(yōu)化、信號處理和自動控制等方面[10]。

由此可見，不同編碼方式有其自身的優(yōu)缺點和適用場合，事實上，關于該如何設計編碼策略長期以來存在許多爭議。傳統(tǒng)的觀點認為，進化的本質主要在于交叉而非變異，從最大化隱并行性的角度出發(fā)，建議采用最小字符集編碼，例如二進制編碼，以便獲得盡可能多的模式[11]，但該原則未能得到一致認同，一方面由于對于相當多的搜索和優(yōu)化問題，二進制編碼不符合問題本身的結構特點，實現(xiàn)起來并不方便[12]；另一方面，有的研究結果也表明，最小字符集的編碼原則并不一定合理。例如，Antonisse等[13]發(fā)現(xiàn)，即使是為了最大化算法的隱并行性，只要從不同的角度解釋無關符的作用，就可得到完全相反的結論，即應采用大的編碼字符集而非小字符集。而以Fogel等[14]為代表的研究者對進化的本質持相反的觀點，認為其主要在于變異而非交叉，因而置疑隱并行性的意義和最小字符集的編碼原則。Fogel等[15]指出，僅需滿足一些一般性的假設條件，即可對任意兩種編碼字符集設計出功能等效的兩類進化算法。此外，即使不考慮最小字符原則，對應該采用二進制編碼還是格雷碼同樣存在爭議[16]。這些爭議以及近年來對NFL(No Free Lunch)定理[17]等關于優(yōu)化算法的一般性定理的研究[18-19]表明：通用又高效的編碼方式是不存在的，不同類型的適應度函數應采用不同的編碼。解決編碼策略選擇問題的一個可行出路是將通用編碼方式的研究轉為探尋編碼與適應度函數特性之間的通用依賴關系。

在前期研究中，為揭示適應度函數的周期性特點與編碼元數之間的關聯(lián)特性，以可展開為分立周期的正弦函數分量線性組合而成的適應度函數為研究對象，采用一階積木塊數量作為編碼性能的評價方法，發(fā)現(xiàn)對頻率為正整數m的整數次冪的正弦函數為基函數線性組合構成的適應度函數，采用m元整數編碼時性能優(yōu)于其他編碼[20-21]。

然而，一階積木塊是以模式定理為依據的，即認為較優(yōu)的模式在遺傳算法的迭代過程中將按指數規(guī)律增長，如果在多個基因座上存在一階積木塊，則在這些基因座上，全局最優(yōu)串的搜索可以轉化為在這些基因座上的并行搜索，故而GA可較快找到較優(yōu)值，但事實上模式定理在某些情況下不一定成立，GA欺騙、超平面不一致性和同步等現(xiàn)象可能會導致GA向錯誤的方向搜索[22]，這時將不能保證積木塊數量與優(yōu)化性能之間的正相關關系。

基于此，本文希望找到一種更合理的編碼性能評價方法來進一步驗證適應度函數的周期性特點與編碼元數之間的關聯(lián)特性。編碼方式影響到GA的很多方面，如積木塊數量、連鎖[23]和適應度分布[24]等，所有這些因素又最終影響到GA進化的難易程度，在其他參數相同的情況下，不同編碼下GA進化的難易程度是編碼性能最直觀的體現(xiàn)。在判斷進化算法的難易程度時，運行時間是使用最廣泛、最可靠的性能指標[25-26]，文獻[27]指出，逃脫概率(Escape Probability， EP)反映了當前個體進化到更優(yōu)個體的概率，其大小與期望運行時間成反相關，因此，EP可以有效反映進化算法的難易程度；在EP基礎上得到的累積逃脫概率(Accumulated Escape Probability， AEP)實現(xiàn)了進化難易程度數值化，可用于比較不同算法之間的性能。本文提出以AEP作為編碼性能的評價指標。

1 研究對象

1.1 適應度函數

1.2 廣義整數編碼

2 基于逃脫概率的編碼選擇方法

2.1 AEP定義

文獻[27]在逃脫概率的基礎上給出了AEP的定義。給定G(x)，在其搜索空間進行采樣，并將所得結果按適應度大小分為L級，得適應度集合為F={f0,f1,…,fL|f0

P(fi)=1/Si

(1)

對于特定的fi，逃脫概率越大表示越容易獲得比當前值更高的適應度。將逃脫概率的定義擴展到適應度集合，Pi表示所有大于等于fi的適應度的逃脫概率平均值，定義如下：

(2)

其中Ci={fj|j>i}。進一步定義適應度概率云(Fitness-Probability Cloud， FPC)為：

FPC={(f0,P0),(f1,P1),…,(fL,PL)}

(3)

由FPC，得到累積逃脫概率AEP為:

(4)

AEP實際上是集合F中Pi的平均值。由逃脫概率P(fi)和Pi的定義可知，AEP越大，則表示適應度函數進化難度越小。

2.2 AEP計算方法

根據AEP的定義，本文實現(xiàn)AEP的計算步驟如下：

1)采樣。本文研究對象為連續(xù)適應度函數，為了得到離散的適應度集合F={f0,f1,…,fL|f0

開始 隨機生成個體s1fori:=2tondo1)隨機生成個體α; 2)在(0, 1)范圍等概率隨機生成一實數k; 3)若(k≤φ(f(si-1),f(α))) 則sk:=α否則跳轉至1) 4)i:=i+1

end for

結束

2)計算每個樣本點的適應度函數，按從小到大排序(根據適應度的取值范圍，本文中若兩個樣本點適應度之差小10-6，則認為這兩個樣本點適應度位于同一級)。計算所有適應度處于第i級的個體的適應度均值作為fi)，得到適應度集合F={f0,f1,…,fL|f0

圖1 5組適應度函數在不同編碼下的AEP

3)計算每個樣本點的逃脫概率。對每個采樣點，采用交叉和位變異操作獲得若干個鄰域點，以大于該樣本適應度的鄰域點數與總鄰域點數的比值近似計算逃脫概率P(fi)。

由于采樣點沒有現(xiàn)成的個體與之進行交叉，本文通過以下步驟近似實現(xiàn)交叉操作：按交叉率決定是否需要進行交叉，若是，則隨機選擇樣本個體串上一個點，分別對該點之前的所有位和之后的所有位按一定概率變異，得到兩個新的個體，取適應度較大的個體作為交叉的結果。

4)由式(3)計算得到FPC。

紅山的陽坡，二丫的新墳還氤氳著黃土的氣息，墳頭的紙幡在夜風中上下翻飛。我婆婆墳前，當年植下的兩株柏苗，已有幾人高了。月光垂照下來，柏樹披上白紗，靜穆地肅立著。我跟她們說，狼剩兒我找到了。婆婆說，你帶來讓我瞅瞅！我不敢直視婆婆的眼睛，低頭小聲說，我?guī)Р换亍牌艆柭曍焸湮遥茨氵@個娘是么樣當的，這點能耐都冇得！

5)由式(4)計算得到AEP。

為了提高準確率，對每個適應度函數樣本重復計算AEP 10次，取10次結果的均值作為最終的AEP值。

2.3 不同編碼的AEP比較

表1 適應度函數樣本

按以上步驟計算AEP，其中樣本點數、鄰域點數和變異率分別取10 000，50和0.3，每組適應度函數的1 000個函數樣本在不同編碼下的AEP分別如圖1所示。

由圖1可見，當m=2時，1 000個G1(x)樣本在base- 2編碼下AEP的均值為0.322，base- 3和base- 5編碼對應AEP均值分別為0.261和0.269，base- 2對應的AEP明顯大于base- 3和base- 5編碼；當m為3，4，5和6時，分別是base- 3，base- 4，base- 5和base- 6編碼對應的AEP值最大。圖1的結果表明，對于適應度函數G(x)，base-m編碼對應的AEP明顯大于另外兩種編碼，反映了base-m編碼的GA進化難度較小，即在相同條件下，base-m編碼將期望獲得優(yōu)于另外兩種編碼的性能。

3 GA仿真

為了驗證AEP的結論，采用兩種方式對不同編碼的性能進行比較，第一種是最終優(yōu)化結果比較，第二種是群體平均適應度的上升時間比較，適應度的最終優(yōu)化結果越大、群體適應度均值上升到一定值時所需的進化代數越小則表示編碼的性能越好。

采用傳統(tǒng)GA對表1中的5組適應度函數共5 000個樣本進行優(yōu)化仿真。仿真參數設置如表2所示。每個函數重復運算20次，取這20個最優(yōu)值的均值得到平均適應度作為最終的優(yōu)化結果。為了方便比較，對不同編碼下的優(yōu)化結果取差值。5組函數在不同編碼下的優(yōu)化結果差分別如圖2所示。

圖2 5組適應度函數在不同編碼下的優(yōu)化結果差

由圖2可見，當m=2時,1 000個G1(x)樣本采用base- 2編碼與base- 3和base- 5的優(yōu)化結果差的均值分別為0.626和0.662，base- 2的優(yōu)化結果明顯優(yōu)于其他兩種編碼；當m為3，4，5和6時，分別是base- 3、base- 4、base- 5和base- 6編碼對應的優(yōu)化結果最優(yōu)。由此可見，對G(x)，base-m編碼的性能明顯優(yōu)于碼元非m的整數編碼，與AEP的結論一致。

表2 GA仿真參數設置

3.2 群體平均適應度上升時間比較

對表1中的5組適應度函數，以10-6為步長，通過窮舉搜索法得到每個樣本函數適應度的全局極大值，然后計算不同編碼下每個樣本函數群體適應度的均值上升到全局極大值70%時所需要的進化代數，最大進化代數設500，其他參數與表2相同。將所需進化代數劃分為(0～15)、(16～30)和(>30)3組，統(tǒng)計每組進化代數的樣本函數比例，結果如圖3所示。由圖3可見，對5組適應度函數，當采用base-m編碼時，最少83.8%以上的樣本函數在15代以內群體平均適應度上升到全局極大值的70%，所需進化代數的均值和方差都明顯小于其他兩種編碼，反映了該類適應度函數采用base-m編碼更容易進化，與AEP的結論一致。

4 結語

本文以頻率為正整數m的整數次冪的正弦函數為基函數線性組合構成的適應度函數為研究對象，采用AEP作為編碼性能指標，分析比較了該類適應度函數在不同碼元整數編碼下的AEP，發(fā)現(xiàn)該類適應度函數采用base-m編碼時進化難度小于其他碼元非m編碼。5 000個適應度函數樣本的仿真結果表明，該類函數采用base-m編碼時，最終優(yōu)化結果和群體平均適應度的上升速度明顯優(yōu)于其他非m碼元編碼，驗證了AEP對編碼性能評價的有效性。

本文結果再次確認了對于該類適應度函數m元整數編碼優(yōu)于非m元整數編碼的結論，可為GA的編碼設計提供借鑒。另外，AEP反映了進化的難易程度，可推廣應用于適應度函數的設計和操作算子的選擇，如設計不同的適應度函數通過AEP選擇較容易進化的一個，以及選擇有利于進化的選擇算子、交叉率和變異率等。

圖3 不同編碼下群體適應度均值上升至全局極大值70%所需的進化代數統(tǒng)計

References)

[1] 馬永杰,云文霞.遺傳算法研究進展[J].計算機應用研究,2012,29(4):1201-1206.(MA Y J, YUN W X. Research progress of genetic algorithm [J]. Application Research of Computers, 2012, 29(4): 1201-1206.)

[2] AGGARWAL S, GARG R, GOSWAMI P. A review paper on different encoding schemes used in genetic algorithms [J]. International Journal on Advanced Research in Computer Science and Software Engineering, 2014, 4(1): 596-600.

[3] 張超群,鄭建國,錢潔.遺傳算法編碼方案比較[J].計算機應用研究,2011,28(3):819-822.(ZHANG C Q, ZHENG J G, QIAN J. Comparison of coding schemes for genetic algorithms [J]. Application Research of Computers, 2011, 28(3): 819-822.)

[4] HOLLAND J H. Genetic algorithms and the optimal allocation of trials [J]. SIAM Journal on Computing, 1973, 2(2): 88-105.

[5] MICHALEWICZ Z, JANIKOW C Z, KRAWCZYK J B. A modified genetic algorithm for optimal control problems [J]. Computers & Mathematics with Applications, 1992, 23(12): 83-94.

[6] 馬德良,陸昌輝,王小樂.基于改進遺傳算法的智能組卷方法[J].計算機應用,2009,29(7):1884-1886.(MA D L, LU C H, WANG X L. Intelligent test paper generation based on improved genetic algorithm [J]. Journal of Computer Applications, 2009, 29(7): 1884-1886.)

[7] 張理洪,謝長生,張玉萍,等.基于位矩陣編碼實現(xiàn)模擬集成電路模塊布局的遺傳算法[J].計算機學報,2003,26(9):1157-1164.(ZHANG L H, XIE C S, ZHANG Y P, et al. A bit-matrix genetic approach to analog module placement [J]. Chinese Journal of Computers, 2003, 26(9): 1157-1164.)

[8] 蔡美玲,陳榮平,陳明.基于樹型編碼遺傳算法的Web服務組合[J].計算機應用與軟件,2008,25(11):60-62.(CAI M L, CHEN R P, CHEN M. Web service composition based on tree-coding genetic algorithm [J]. Application Research of Computers, 2008, 25(11): 60-62.)

[9] 章文俊,程浩忠,王一,等.基于樹形結構編碼單親遺傳算法的配電網優(yōu)化規(guī)劃[J].電工技術學報,2009,24(5):154-160.(ZHANG W J, CHENG H Z, WANG Y, et al. Distribution network optimal planning based on tree structure encoding partheno-genetic algorithm [J]. Transactions of China Electrotechnical Society, 2009, 24(5): 154-160.)

[10] 梁昌勇,柏樺,蔡美菊,等.量子遺傳算法研究進展[J].計算機應用研究,2012,29(7):2401-2405.(LIANG C Y, BAI H, CAI M J, et al. Advances in quantum genetic algorithm [J]. Application Research of Computers, 2012, 29(7): 2401-2405.)

[11] GOLDBERG D E, HOLLAND J H. Genetic algorithms and machine learning [J]. Machine Learning, 1988, 3(2): 95-99.

[12] MICHALEWICZ Z. Genetic Algorithm+Data Structures=Evolution Programs [M]. 3rd ed. Berlin: Springer, 1996: 31-62.

[13] ANTONISSE H J, RAWLINS G J E. A grammar-based genetic algorithm [M]// Foundations of Genetic Algorithms. San Francisco, CA: Morgan Kaufmann, 1990: 193-204.

[14] CHELLAPILLA K, FOGEL D B. Fitness distributions in evolutionary computation: motivation and examples in the continuous domain [J]. BioSystems, 1999, 54(1/2): 15-29.

[15] FOGEL D, GHOZEIL A. A note on representations and variation operators [J]. IEEE Transactions on Evolutionary Computation, 1997, 1(2): 159-161.

[16] CHAKRABORTY U K, JANIKOW C Z. An analysis of gray versus binary encoding in genetic search [J]. Information Sciences, 2003, 156(3/4): 253-269.

[17] WOLPERT D, MACREADY W. No free lunch theorems for optimization [J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 67-82.

[18] IGEL C. No free lunch theorems: limitations and perspectives of metaheuristics [M]// Theory and Principled Methods for the Design of Metaheuristics. Berlin: Springer, 2014: 1-23.

[19] ALABERT A, BERTI A, CABALLERO R, et al. No-free-lunch theorems in the continuum [J]. Theoretical Computer Science, 2015, 600: 98-106.

[20] MO H, LI Z, TIAN L, et al. Selection of encoding cardinality for a class of fitness functions to obtain order- 1 building blocks [J]. International Journal of Computational Intelligence Systems, 2015, 8(1): 62-74.

[21] MO H, LI Z, PARK J B, et al. On the supply of superior order- 1 building blocks for a class of periodical fitness functions [J]. International Journal of Computational Intelligence Systems, 2009, 2(1): 91-98.

[22] WHITLEY D. An overview of evolutionary algorithms: practical is-sues and common pitfalls [J]. Information and Software Technology, 2001, 43(14): 817-831.

[23] GOLDBERG D E. The Design of Innovation: Lessons from and for Competent Genetic Algorithms [M]. Rotterdam: Springer Science & Business Media, 2013: 59-93.

[24] LU G. Characterising fitness landscapes with fitness-probability cloud and its applications to algorithm configuration [D]. Birmingham: University of Birmingham, 2014: 133-149.

[25] PAPADIMITRIOU C H, STEIGLITZ K. Combinatorial Optimization: Algorithms and Complexity [M]. Massachusetts: Courier Corporation, 2013: 156-182.

[26] MERZ P. Advanced fitness landscape analysis and the performance of memetic algorithms [J]. Evolutionary Computation, 2004, 12(3): 303-325.

[27] LU G, LI J, YAO X. Fitness landscapes and problem difficulty in evolutionary algorithms: from theory to applications [M]// Recent Advances in the Theory and Application of Fitness Landscapes. Berlin: Springer, 2014: 133-152.

[28] VANNESCHI L, CLERGUE M, COLLARD P, et al. Fitness clouds and problem hardness in genetic programming [C]// GECCO 2004: Proceedings of the 2004 Genetic and Evolutionary Computation Conference, LNCS 3103. Berlin: Springer, 2004: 690-701.

This work is partially supported by National Natural Science Foundation of China (61105062).

ZHUChunmei, born in 1981, Ph. D. candidate. Her research interests include intelligent control, pattern recognition.

MOHongqiang, born in 1976, Ph. D., professor. His research interests include evolutionary computation.

Encodingofgeneticalgorithmforaclassoffitnessfunctions

ZHU Chunmei1*, MO Hongqiang2

(1.CollegeofMechanicalandElectricalEngineering,ZhongshanInstitute,UniversityofElectronicScienceandTechnologyofChina,ZhongshanGuangdong528400,China;2.CollegeofAutomationScienceandEngineering,SouthChinaUniversityofTechnology,GuangzhouGuangdong510641,China)

In the investigation of relationship between the periodicity of fitness function and encoding cardinality, the evaluation of encoding performance using the number of order- 1 building blocks is not necessarily established. Focused on this issue, evaluating method of encoding performance of Genetic Algorithm (GA) using Accumulated Escape Probability (AEP) was proposed, and for a class of fitness functions linearly combined of sinusoidal functions whose frequencies are exponential to a positive integerm, research on encoding was carried out. Firstly, the general form of the fitness function was given, and the concept of base-mencoding was explained. Secondly, the definition of AEP was introduced, and a method was proposed to figure out AEPs. Then the AEPs of the above-mentioned fitness functions under encodings with different encoding bases were compared, and the results showed that, for a fitness function which was linearly combined of sinusoidal functions with frequencies exponential to a positive integerm, a base-mencoding could achieve higher AEP than encodings with bases other thanm. The simulation results show that, the optimization performance and the rise time of the average fitness of the population under a base-mencoding are significantly better than those of the other encodings.

encoding; performance evaluation; Genetic Algorithm (GA); periodic fitness function; Accumulated Escape Probability (AEP)

TP301.6; TP18

:A

2017- 01- 05;

:2017- 03- 04。

國家自然科學基金資助項目(61105062)。

朱春媚(1981—)，女，廣東河源人，講師，博士研究生，主要研究方向：智能控制、模式識別； 莫鴻強(1976—)，男，廣東茂名人，教授，博士，主要研究方向：進化計算。

1001- 9081(2017)07- 1972- 05

10.11772/j.issn.1001- 9081.2017.07.1972