上位效应对遗传算法可靠性的影响（英文）
|
摘要
目的:探讨遗传算法的局限性和实用性,并分析基于相互作用产生的上位效应对遗传算法可靠性的影响。创新点:1.指出遗传算法缺陷的根源;2.基于测试样本函数定义目标函数,以判断遗传算法的适用性。方法:1.基于非上位效应函数(表1)和上位效应函数(表2),以及非上位效应函数F4和上位效应函数F6的结构图来验证遗传算法可靠性;2.通过计算样本函数(公式(1))和遗传算法流程(图3)表达遗传算法的工作原理。3.利用克洛弗函数(公式(2))和计算不同结构角下的函数分布(图4),进一步判断匹配度(表3)和计算效率(表4);定义新的目标函数(公式(9))和一组新的变量(公式(10))来实现变量相关性解离。结论:1.对当前遗传算法存在的不足给出了独到见解,并认为正定性的假设并非可以保证遗传算法实际的有效性和优化性。2.定义成本代价函数用以判断遗传算法可靠性,并分别考虑上位性和非上位性效应两种情形。当成本代价函数在非上位性效应下时,遗传算法是有效的;否则,可以把N维函数降级为N个一维函数,从而采用更简单的算法来判断。基于一些通用的基准,进一步设计三类样本函数来证实以上判断,且这些样本函数适合于上位性效应情形和非上位效应情形。3.遗传算法的瓶颈在于主算子和相干匹配性;可以通过破坏某些结构来实现变量关系的解离,从而抑制相干匹配性对遗传算法的影响。希望相关读者在处理实际优化问题时能验证作者关于上位效应的定性结论,并给出更可靠的方法来表征这种效应。
In the field of genetics, it is well known that a specific genetic behavior may be influenced by more than one gene. There is a similar concept in genetic algorithms(GAs), called epistasis, which is the interaction between genes. This study demonstrates that, in spite of what is generally assumed, GAs are not an efficient optimization tool. This is because the main operator, mating(crossover), cannot function properly in epistatic optimization problems. In non-epistatic problems, although a GA can possibly provide a correct solution, it is an inefficient and time-consuming algorithm. As proof, we used conventional test functions and introduced new ones and confirmed our claim with simulation results.
In the field of genetics, it is well known that a specific genetic behavior may be influenced by more than one gene. There is a similar concept in genetic algorithms(GAs), called epistasis, which is the interaction between genes. This study demonstrates that, in spite of what is generally assumed, GAs are not an efficient optimization tool. This is because the main operator, mating(crossover), cannot function properly in epistatic optimization problems. In non-epistatic problems, although a GA can possibly provide a correct solution, it is an inefficient and time-consuming algorithm. As proof, we used conventional test functions and introduced new ones and confirmed our claim with simulation results.
引文
Davis LD,de Jong K,Vose MD,et al.,2012.Evolutionary Algorithms.Springer,New York,USA.https://doi.org/10.1007/978-1-4612-1542-4
de Oliveira LL,Freitas AA,Tinós R,2018.Multi-objective genetic algorithms in the study of the genetic code’s adaptability.Information Sciences,425:48-61.https://doi.org/10.1016/j.ins.2017.10.022
di Francescomarino C,Dumas M,Federici M,et al.,2018.Genetic algorithms for hyperparameter optimization in predictive business process monitoring.Information Systems,74:67-83.https://doi.org/10.1016/j.is.2018.01.003
Dong HB,Li T,Ding R,et al.,2018.A novel hybrid genetic algorithm with granular information for feature selection and optimization.Applied Soft Computing,65:33-46.https://doi.org/10.1016/j.asoc.2017.12.048
Greco A,D’Urso D,Cannizzaro F,et al.,2018.Damage identification on spatial Timoshenko arches by means of genetic algorithms.Mechanical Systems and Signal Processing,105:51-67.https://doi.org/10.1016/j.ymssp.2017.11.040
Guo LH,Wang GG,Gandomi AH,et al.,2014.A new improved krill herd algorithm for global numerical optimization.Neurocomputing,138:392-402.https://doi.org/10.1016/j.neucom.2014.01.023
Haupt RL,Haupt SE,2004.Practical Genetic Algorithms.John Wiley&Sons,Hoboken,New Jersey,USA.
Jain A,Chaudhari NS,2017.An improved genetic algorithm for developing deterministic OTP key generator.Complexity,2017:7436709.https://doi.org/10.1155/2017/7436709
Karakati?S,Podgorelec V,2015.A survey of genetic algorithms for solving multi depot vehicle routing problem.Applied Soft Computing,27:519-532.https://doi.org/10.1016/j.asoc.2014.11.005
Qu BY,Liang JJ,Wang ZY,et al.,2016.Novel benchmark functions for continuous multimodal optimization with comparative results.Swarm and Evolutionary Computation,26:23-34.https://doi.org/10.1016/j.swevo.2015.07.003
Sivanandam SN,Deepa SN,2008.Introduction to Genetic Algorithms.Springer,Berlin,Heidelberg,Germany.https://doi.org/10.1007/978-3-540-73190-0
Steinberg ML,Cosloy SD,2009.Biotechnology and Genetic Engineering.Infobase Publishing,New York,USA.
Teimouri R,Baseri H,Rahmani B,et al.,2014.Modeling and optimization of spring-back in bending process using multiple regression analysis and neural computation.International Journal of Material Forming,7(2):167-178.https://doi.org/10.1007/s12289-012-1117-4
Tseng HE,Chang CC,Lee SC,et al.,2018.A block-based genetic algorithm for disassembly sequence planning.Expert Systems with Applications,96:492-505.https://doi.org/10.1016/j.eswa.2017.11.004
Wang H,Zhao ZZ,Guo ZW,et al.,2017.An improved clustering method for detection system of public security events based on genetic algorithm and semisupervised learning.Complexity,2017:8130961.https://doi.org/10.1155/2017/8130961
Zhou Y,Zhou LS,Wang Y,et al.,2017.Application of multiple-population genetic algorithm in optimizing the train-set circulation plan problem.Complexity,2017:3717654.https://doi.org/10.1155/2017/3717654
de Oliveira LL,Freitas AA,Tinós R,2018.Multi-objective genetic algorithms in the study of the genetic code’s adaptability.Information Sciences,425:48-61.https://doi.org/10.1016/j.ins.2017.10.022
di Francescomarino C,Dumas M,Federici M,et al.,2018.Genetic algorithms for hyperparameter optimization in predictive business process monitoring.Information Systems,74:67-83.https://doi.org/10.1016/j.is.2018.01.003
Dong HB,Li T,Ding R,et al.,2018.A novel hybrid genetic algorithm with granular information for feature selection and optimization.Applied Soft Computing,65:33-46.https://doi.org/10.1016/j.asoc.2017.12.048
Greco A,D’Urso D,Cannizzaro F,et al.,2018.Damage identification on spatial Timoshenko arches by means of genetic algorithms.Mechanical Systems and Signal Processing,105:51-67.https://doi.org/10.1016/j.ymssp.2017.11.040
Guo LH,Wang GG,Gandomi AH,et al.,2014.A new improved krill herd algorithm for global numerical optimization.Neurocomputing,138:392-402.https://doi.org/10.1016/j.neucom.2014.01.023
Haupt RL,Haupt SE,2004.Practical Genetic Algorithms.John Wiley&Sons,Hoboken,New Jersey,USA.
Jain A,Chaudhari NS,2017.An improved genetic algorithm for developing deterministic OTP key generator.Complexity,2017:7436709.https://doi.org/10.1155/2017/7436709
Karakati?S,Podgorelec V,2015.A survey of genetic algorithms for solving multi depot vehicle routing problem.Applied Soft Computing,27:519-532.https://doi.org/10.1016/j.asoc.2014.11.005
Qu BY,Liang JJ,Wang ZY,et al.,2016.Novel benchmark functions for continuous multimodal optimization with comparative results.Swarm and Evolutionary Computation,26:23-34.https://doi.org/10.1016/j.swevo.2015.07.003
Sivanandam SN,Deepa SN,2008.Introduction to Genetic Algorithms.Springer,Berlin,Heidelberg,Germany.https://doi.org/10.1007/978-3-540-73190-0
Steinberg ML,Cosloy SD,2009.Biotechnology and Genetic Engineering.Infobase Publishing,New York,USA.
Teimouri R,Baseri H,Rahmani B,et al.,2014.Modeling and optimization of spring-back in bending process using multiple regression analysis and neural computation.International Journal of Material Forming,7(2):167-178.https://doi.org/10.1007/s12289-012-1117-4
Tseng HE,Chang CC,Lee SC,et al.,2018.A block-based genetic algorithm for disassembly sequence planning.Expert Systems with Applications,96:492-505.https://doi.org/10.1016/j.eswa.2017.11.004
Wang H,Zhao ZZ,Guo ZW,et al.,2017.An improved clustering method for detection system of public security events based on genetic algorithm and semisupervised learning.Complexity,2017:8130961.https://doi.org/10.1155/2017/8130961
Zhou Y,Zhou LS,Wang Y,et al.,2017.Application of multiple-population genetic algorithm in optimizing the train-set circulation plan problem.Complexity,2017:3717654.https://doi.org/10.1155/2017/3717654