Full Text:   <417>

Summary:  <149>

CLC number: O31

On-line Access: 2019-01-29

Received: 2018-05-28

Revision Accepted: 2018-09-11

Crosschecked: 2018-10-15

Cited: 0

Clicked: 1988

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Sajad Jafari

https://orcid.org/0000-0002-6845-7539

-   Go to

Article info.
Open peer comments

Journal of Zhejiang University SCIENCE A 2019 Vol.20 No.2 P.109-116

http://doi.org/10.1631/jzus.A1800399


Effect of epistasis on the performance of genetic algorithms


Author(s):  Sajad Jafari, Tomasz Kapitaniak, Karthikeyan Rajagopal, Viet-Thanh Pham, Fawaz E. Alsaadi

Affiliation(s):  Biomedical Engineering Department, Amirkabir University of Technology, Tehran 15875-4413, Iran; more

Corresponding email(s):   phamvietthanh@tdt.edu.vn

Key Words:  Genetic algorithm (GA), Epistasis, Crossover, Superposition, Optimization, Cost function


Sajad Jafari, Tomasz Kapitaniak, Karthikeyan Rajagopal, Viet-Thanh Pham, Fawaz E. Alsaadi. Effect of epistasis on the performance of genetic algorithms[J]. Journal of Zhejiang University Science A, 2019, 20(2): 109-116.

@article{title="Effect of epistasis on the performance of genetic algorithms",
author="Sajad Jafari, Tomasz Kapitaniak, Karthikeyan Rajagopal, Viet-Thanh Pham, Fawaz E. Alsaadi",
journal="Journal of Zhejiang University Science A",
volume="20",
number="2",
pages="109-116",
year="2019",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.A1800399"
}

%0 Journal Article
%T Effect of epistasis on the performance of genetic algorithms
%A Sajad Jafari
%A Tomasz Kapitaniak
%A Karthikeyan Rajagopal
%A Viet-Thanh Pham
%A Fawaz E. Alsaadi
%J Journal of Zhejiang University SCIENCE A
%V 20
%N 2
%P 109-116
%@ 1673-565X
%D 2019
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.A1800399

TY - JOUR
T1 - Effect of epistasis on the performance of genetic algorithms
A1 - Sajad Jafari
A1 - Tomasz Kapitaniak
A1 - Karthikeyan Rajagopal
A1 - Viet-Thanh Pham
A1 - Fawaz E. Alsaadi
J0 - Journal of Zhejiang University Science A
VL - 20
IS - 2
SP - 109
EP - 116
%@ 1673-565X
Y1 - 2019
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.A1800399


Abstract: 
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.

上位效应对遗传算法可靠性的影响

目的:探讨遗传算法的局限性和实用性,并分析基于相互作用产生的上位效应对遗传算法可靠性的影响.
创新点:1. 指出遗传算法缺陷的根源; 2. 基于测试样本函数定义目标函数,以判断遗传算法的适用性.
方法:1. 基于非上位效应函数(表1)和上位效应函数(表2),以及非上位效应函数F4和上位效应函数F6的结构图来验证遗传算法可靠性; 2. 通过计算样本函数(公式(1))和遗传算法流程(图3)表达遗传算法的工作原理. 3. 利用克洛弗函数(公式(2))和计算不同结构角下的函数分布(图4),进一步判断匹配度(表3)和计算效率(表4); 定义新的目标函数(公式(9))和一组新的变量(公式(10))来实现变量相关性解离.
结论:1. 对当前遗传算法存在的不足给出了独到见解,并认为正定性的假设并非可以保证遗传算法实际的有效性和优化性. 2. 定义成本代价函数用以判断遗传算法可靠性,并分别考虑上位性和非上位性效应两种情形. 当成本代价函数在非上位性效应下时,遗传算法是有效的; 否则,可以把N维函数降级为N个一维函数,从而采用更简单的算法来判断. 基于一些通用的基准,进一步设计三类样本函数来证实以上判断,且这些样本函数适合于上位性效应情形和非上位效应情形. 3. 遗传算法的瓶颈在于主算子和相干匹配性; 可以通过破坏某些结构来实现变量关系的解离,从而抑制相干匹配性对遗传算法的影响. 希望相关读者在处理实际优化问题时能验证作者关于上位效应的定性结论,并给出更可靠的方法来表征这种效应.

关键词:上位性效应; 遗传算法; 相干匹配性; 叠加性; 优化; 成本代价函数

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Davis LD, de Jong K, Vose MD, et al., 2012. Evolutionary Algorithms. Springer, New York, USA.

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

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

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

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

[6]Guo LH, Wang GG, Gandomi AH, et al., 2014. A new improved krill herd algorithm for global numerical optimization. Neurocomputing, 138:392-402.

[7]Haupt RL, Haupt SE, 2004. Practical Genetic Algorithms. John Wiley & Sons, Hoboken, New Jersey, USA.

[8]Jain A, Chaudhari NS, 2017. An improved genetic algorithm for developing deterministic OTP key generator. Complexity, 2017:7436709.

[9]Karakatič S, Podgorelec V, 2015. A survey of genetic algorithms for solving multi depot vehicle routing problem. Applied Soft Computing, 27:519-532.

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

[11]Sivanandam SN, Deepa SN, 2008. Introduction to Genetic Algorithms. Springer, Berlin, Heidelberg, Germany.

[12]Steinberg ML, Cosloy SD, 2009. Biotechnology and Genetic Engineering. Infobase Publishing, New York, USA.

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

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

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

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

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE