一类适应度函数的遗传算法编码

朱春媚，莫鸿强

(1.电子科技大学中山学院 机电工程学院，广东 中山 528400； 2.华南理工大学 自动化科学与工程学院，广州 510641) (*通信作者电子邮箱cmzhu@zsc.edu.cn)

一类适应度函数的遗传算法编码

朱春媚1*，莫鸿强2

(1.电子科技大学中山学院 机电工程学院，广东 中山 528400； 2.华南理工大学 自动化科学与工程学院，广州 510641) (*通信作者电子邮箱cmzhu@zsc.edu.cn)

针对在探讨适应度函数的周期性特点与整数编码元数之间的关联特性时，一阶积木块数量对编码性能的评价不一定成立的问题，提出以累积逃脱概率(AEP)作为遗传算法(GA)编码性能的评价指标，对以频率为正整数m的整数次幂的正弦函数为基函数线性组合构成的适应度函数编码展开研究。首先给出了该类适应度函数的一般形式和m进制整数编码的含义；然后介绍了AEP的定义，并根据函数特点制定了AEP的计算方法；最后分析比较了该类适应度函数在不同整数编码下的AEP，指出其采用m元整数编码时更容易进化。仿真结果表明，该类适应度函数采用m元整数编码时，其最终优化结果和群体适应度均值的上升时间皆明显优于其他编码，反映了AEP能有效评价编码的性能，并再次验证了对于该类适应度函数m元整数编码优于非m元整数编码的结论。

编码；性能评价；遗传算法；周期性适应度函数；累积逃脱概率

0 引言

编码作为遗传算法(Genetic Algorithm, GA)设计中的首要环节，决定着遗传算法的精度和效率，是算法能否解决问题的前提。随着GA研究和应用的日益深入，编码方法也在不断地改进，目前已有多种编码方式，常用的有二进制编码、实数编码、矩阵编码、树型编码和量子编码等[1-3]。自Holland[4]提出GA以来，二进制编码成为应用最早和最广的编码方式，具有简单、符合最小符号集编码原则和模式定理的优点，但对于一些多维、高精度连续函数优化问题，二进编码又存在不能直接反映问题的固有结构和个体编码长度大等不足。针对二进制编码的缺陷，Michalewicz等[5]提出了实数编码，实数编码精度高，适合复杂大空间搜索，对多参数连续函数优化问题具有更好的性能。矩阵编码尤其适用于求解大规模复杂问题、高维数值优化问题和多目标优化问题，例如文献[6]和[7]分别采用矩阵编码的遗传算法实现试题库自动组卷和模拟集成电路模块布局。树型编码也是一种有效的编码方式，主要适用于求解能用树或图表示的优化问题，如Web服务选择[8]、配电网优化规划[9]等。量子编码是将染色体用量子的态矢量表示，使算法能够在较小的种群规模下求得最优解，被广泛应用于组合优化、信号处理和自动控制等方面[10]。

由此可见，不同编码方式有其自身的优缺点和适用场合，事实上，关于该如何设计编码策略长期以来存在许多争议。传统的观点认为，进化的本质主要在于交叉而非变异，从最大化隐并行性的角度出发，建议采用最小字符集编码，例如二进制编码，以便获得尽可能多的模式[11]，但该原则未能得到一致认同，一方面由于对于相当多的搜索和优化问题，二进制编码不符合问题本身的结构特点，实现起来并不方便[12]；另一方面，有的研究结果也表明，最小字符集的编码原则并不一定合理。例如，Antonisse等[13]发现，即使是为了最大化算法的隐并行性，只要从不同的角度解释无关符的作用，就可得到完全相反的结论，即应采用大的编码字符集而非小字符集。而以Fogel等[14]为代表的研究者对进化的本质持相反的观点，认为其主要在于变异而非交叉，因而置疑隐并行性的意义和最小字符集的编码原则。Fogel等[15]指出，仅需满足一些一般性的假设条件，即可对任意两种编码字符集设计出功能等效的两类进化算法。此外，即使不考虑最小字符原则，对应该采用二进制编码还是格雷码同样存在争议[16]。这些争议以及近年来对NFL(No Free Lunch)定理[17]等关于优化算法的一般性定理的研究[18-19]表明：通用又高效的编码方式是不存在的，不同类型的适应度函数应采用不同的编码。解决编码策略选择问题的一个可行出路是将通用编码方式的研究转为探寻编码与适应度函数特性之间的通用依赖关系。

在前期研究中，为揭示适应度函数的周期性特点与编码元数之间的关联特性，以可展开为分立周期的正弦函数分量线性组合而成的适应度函数为研究对象，采用一阶积木块数量作为编码性能的评价方法，发现对频率为正整数m的整数次幂的正弦函数为基函数线性组合构成的适应度函数，采用m元整数编码时性能优于其他编码[20-21]。

然而，一阶积木块是以模式定理为依据的，即认为较优的模式在遗传算法的迭代过程中将按指数规律增长，如果在多个基因座上存在一阶积木块，则在这些基因座上，全局最优串的搜索可以转化为在这些基因座上的并行搜索，故而GA可较快找到较优值，但事实上模式定理在某些情况下不一定成立，GA欺骗、超平面不一致性和同步等现象可能会导致GA向错误的方向搜索[22]，这时将不能保证积木块数量与优化性能之间的正相关关系。

基于此，本文希望找到一种更合理的编码性能评价方法来进一步验证适应度函数的周期性特点与编码元数之间的关联特性。编码方式影响到GA的很多方面，如积木块数量、连锁[23]和适应度分布[24]等，所有这些因素又最终影响到GA进化的难易程度，在其他参数相同的情况下，不同编码下GA进化的难易程度是编码性能最直观的体现。在判断进化算法的难易程度时，运行时间是使用最广泛、最可靠的性能指标[25-26]，文献[27]指出，逃脱概率(Escape Probability， EP)反映了当前个体进化到更优个体的概率，其大小与期望运行时间成反相关，因此，EP可以有效反映进化算法的难易程度；在EP基础上得到的累积逃脱概率(Accumulated Escape Probability， AEP)实现了进化难易程度数值化，可用于比较不同算法之间的性能。本文提出以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的定义，本文实现AEP的计算步骤如下：

1)采样。本文研究对象为连续适应度函数，为了得到离散的适应度集合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)。

由于采样点没有现成的个体与之进行交叉，本文通过以下步骤近似实现交叉操作：按交叉率决定是否需要进行交叉，若是，则随机选择样本个体串上一个点，分别对该点之前的所有位和之后的所有位按一定概率变异，得到两个新的个体，取适应度较大的个体作为交叉的结果。

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

红山的阳坡，二丫的新坟还氤氲着黄土的气息，坟头的纸幡在夜风中上下翻飞。我婆婆坟前，当年植下的两株柏苗，已有几人高了。月光垂照下来，柏树披上白纱，静穆地肃立着。我跟她们说，狼剩儿我找到了。婆婆说，你带来让我瞅瞅！我不敢直视婆婆的眼睛，低头小声说，我带不回……婆婆厉声责备我，看你这个娘是么样当的，这点能耐都冇得！

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编码将期望获得优于另外两种编码的性能。

3 GA仿真

为了验证AEP的结论，采用两种方式对不同编码的性能进行比较，第一种是最终优化结果比较，第二种是群体平均适应度的上升时间比较，适应度的最终优化结果越大、群体适应度均值上升到一定值时所需的进化代数越小则表示编码的性能越好。

采用传统GA对表1中的5组适应度函数共5 000个样本进行优化仿真。仿真参数设置如表2所示。每个函数重复运算20次，取这20个最优值的均值得到平均适应度作为最终的优化结果。为了方便比较，对不同编码下的优化结果取差值。5组函数在不同编码下的优化结果差分别如图2所示。

图2 5组适应度函数在不同编码下的优化结果差

由图2可见，当m=2时,1 000个G1(x)样本采用base- 2编码与base- 3和base- 5的优化结果差的均值分别为0.626和0.662，base- 2的优化结果明显优于其他两种编码；当m为3，4，5和6时，分别是base- 3、base- 4、base- 5和base- 6编码对应的优化结果最优。由此可见，对G(x)，base-m编码的性能明显优于码元非m的整数编码，与AEP的结论一致。

表2 GA仿真参数设置

3.2 群体平均适应度上升时间比较

对表1中的5组适应度函数，以10-6为步长，通过穷举搜索法得到每个样本函数适应度的全局极大值，然后计算不同编码下每个样本函数群体适应度的均值上升到全局极大值70%时所需要的进化代数，最大进化代数设500，其他参数与表2相同。将所需进化代数划分为(0～15)、(16～30)和(>30)3组，统计每组进化代数的样本函数比例，结果如图3所示。由图3可见，对5组适应度函数，当采用base-m编码时，最少83.8%以上的样本函数在15代以内群体平均适应度上升到全局极大值的70%，所需进化代数的均值和方差都明显小于其他两种编码，反映了该类适应度函数采用base-m编码更容易进化，与AEP的结论一致。

4 结语

本文以频率为正整数m的整数次幂的正弦函数为基函数线性组合构成的适应度函数为研究对象，采用AEP作为编码性能指标，分析比较了该类适应度函数在不同码元整数编码下的AEP，发现该类适应度函数采用base-m编码时进化难度小于其他码元非m编码。5 000个适应度函数样本的仿真结果表明，该类函数采用base-m编码时，最终优化结果和群体平均适应度的上升速度明显优于其他非m码元编码，验证了AEP对编码性能评价的有效性。

本文结果再次确认了对于该类适应度函数m元整数编码优于非m元整数编码的结论，可为GA的编码设计提供借鉴。另外，AEP反映了进化的难易程度，可推广应用于适应度函数的设计和操作算子的选择，如设计不同的适应度函数通过AEP选择较容易进化的一个，以及选择有利于进化的选择算子、交叉率和变异率等。

图3 不同编码下群体适应度均值上升至全局极大值70%所需的进化代数统计

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] 张理洪,谢长生,张玉萍,等.基于位矩阵编码实现模拟集成电路模块布局的遗传算法[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] 章文俊,程浩忠,王一,等.基于树形结构编码单亲遗传算法的配电网优化规划[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