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

doi:10.11772/j.issn.1001-9081.2017.07.1972

计算机应用 ›› 2017, Vol. 37 ›› Issue (7): 1972-1976.DOI: 10.11772/j.issn.1001-9081.2017.07.1972

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

朱春媚¹, 莫鸿强²

1. 电子科技大学中山学院机电工程学院, 广东中山 528400;
2. 华南理工大学自动化科学与工程学院, 广州 510641

收稿日期:2017-01-05 修回日期:2017-03-04 出版日期:2017-07-10 发布日期:2017-07-18
通讯作者: 朱春媚
作者简介:朱春媚(1981-),女,广东河源人,讲师,博士研究生,主要研究方向:智能控制、模式识别;莫鸿强(1976-),男,广东茂名人,教授,博士,主要研究方向:进化计算。
基金资助:
国家自然科学基金资助项目（61105062）。

Encoding of genetic algorithm for a class of fitness functions

ZHU Chunmei¹, MO Hongqiang²

1. College of Mechanical and Electrical Engineering, Zhongshan Institute, University of Electronic Science and Technology of China, Zhongshan Guangdong 528400, China;
2. College of Automation Science and Engineering, South China University of Technology, Guangzhou Guangdong 510641, China

Received:2017-01-05 Revised:2017-03-04 Online:2017-07-10 Published:2017-07-18
Supported by:
This work is partially supported by National Natural Science Foundation of China (61105062).

摘要/Abstract

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

关键词: 编码, 性能评价, 遗传算法, 周期性适应度函数, 累积逃脱概率

Abstract: 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 integer m, research on encoding was carried out. Firstly, the general form of the fitness function was given, and the concept of base-m encoding 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 integer m, a base-m encoding could achieve higher AEP than encodings with bases other than m. The simulation results show that, the optimization performance and the rise time of the average fitness of the population under a base-m encoding are significantly better than those of the other encodings.

Key words: encoding, performance evaluation, Genetic Algorithm (GA), periodic fitness function, Accumulated Escape Probability (AEP)

中图分类号:

TP301.6
TP18

朱春媚, 莫鸿强. 一类适应度函数的遗传算法编码[J]. 计算机应用, 2017, 37(7): 1972-1976.

ZHU Chunmei, MO Hongqiang. Encoding of genetic algorithm for a class of fitness functions[J]. Journal of Computer Applications, 2017, 37(7): 1972-1976.

参考文献

[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.

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

Encoding of genetic algorithm for a class of fitness functions

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	王周恺, 张炯, 马维纲, 王怀军. 面向高速列车监测数据的并行解压缩算法[J]. 计算机应用, 2021, 41(9): 2586-2593.
[2]	李康康, 张静. 基于注意力机制的多层次编码和解码的图像描述模型[J]. 计算机应用, 2021, 41(9): 2504-2509.
[3]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[4]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[5]	杨震, 马健霄, 王宝杰. 设置待行区条件下双环相位信号配时优化模型[J]. 计算机应用, 2021, 41(7): 2108-2112.
[6]	张元钧, 张曦煌. 基于图卷积与长短期记忆网络的动态网络表示学习模型[J]. 计算机应用, 2021, 41(7): 1857-1864.
[7]	李进, 王凤, 杨沈宇. 换电模式下电动车货运路径优化模型与算法[J]. 计算机应用, 2021, 41(6): 1792-1798.
[8]	蒋林, 施佳琪, 李远成. 可重构结构下合成视点失真变化算法并行设计与实现[J]. 计算机应用, 2021, 41(6): 1734-1740.
[9]	杨盼盼, 赵继春. 基于状态视图的流媒体图像信息置乱隐藏算法[J]. 计算机应用, 2021, 41(6): 1729-1733.
[10]	徐国保, 陈媛晓, 王骥. 基于图卷积网络的药物靶标关联预测算法[J]. 计算机应用, 2021, 41(5): 1522-1526.
[11]	李舒仪, 韩晓龙. 海铁联运港口混合作业模式下轨道吊与集卡协同调度[J]. 计算机应用, 2021, 41(5): 1506-1513.
[12]	刘紫燕, 马珊珊, 白鹤. 基于改进智能水滴的正交匹配追踪混合预编码算法[J]. 计算机应用, 2021, 41(5): 1419-1424.
[13]	孙鹤立, 孙玉柱, 张晓云. 基于生成对抗网络的事件描述生成[J]. 计算机应用, 2021, 41(5): 1256-1261.
[14]	李旭娟, 皮建勇, 黄飞翔, 贾海朋. 基于自生成深度神经网络的4D航迹预测[J]. 计算机应用, 2021, 41(5): 1492-1499.
[15]	樊玮, 王慧敏, 邢艳. 基于自编码器的多视图属性网络表示学习模型[J]. 计算机应用, 2021, 41(4): 1064-1070.