Abstract
Epigenetics’ flexibility in terms of finer manipulation of genes renders unprecedented levels of refined and diverse evolutionary mechanisms possible. From the epigenetic perspective, the main limitations to improving the stability and accuracy of genetic algorithms are as follows: (1) the unchangeable nature of the external environment, which leads to excessive disorders in the changed phenotype after mutation and crossover; (2) the premature convergence due to the limited types of epigenetic operators. In this paper, a probabilistic environmental gradient-driven genetic algorithm (PEGA) considering epigenetic traits is proposed. To enhance the local convergence efficiency and acquire stable local search, a probabilistic environmental gradient (PEG) descent strategy together with a multi-dimensional heterogeneous exponential environmental vector tendentiously generates more offsprings along the gradient in the solution space. Moreover, to balance exploration and exploitation at different evolutionary stages, a variable nucleosome reorganization (VNR) operator is realized by dynamically adjusting the number of genes involved in mutation and crossover. Based on the above-mentioned operators, three epigenetic operators are further introduced to weaken the possible premature problem by enriching genetic diversity. The experimental results on the open Congress on Evolutionary Computation-2017 (CEC’ 17) benchmark over 10-, 30-, 50-, and 100-dimensional tests indicate that the proposed method outperforms 10 state-of-the-art evolutionary and swarm algorithms in terms of accuracy and stability on comprehensive performance. The ablation analysis demonstrates that for accuracy and stability, the fusion strategy of PEG and VNR are effective on 96.55% of the test functions and can improve the indicators by up to four orders of magnitude. Furthermore, the performance of PEGA on the real-world spacecraft trajectory optimization problem is the best in terms of quality of the solution.
摘要
表观遗传学的灵活性使进化机制更加精细和多样化. 从表观遗传的角度来看, 提升遗传算法的稳定性和准确性需要重点解决两个方面的问题: (1) 恒定外部环境导致突变或交叉后表型变化的过度无序性; (2) 表观遗传算子类型有限导致的过早收敛. 为此本文提出一种考虑表观遗传特征的概率环境梯度驱动遗传算法 (PEGA). 提出概率环境梯度下降策略 (PEG), 其基于多维异构指数环境向量在解空间中沿梯度方向生成更多后代, 以提高局部收敛效率并获得稳定的局部搜索能力. 为了在不同进化阶段平衡全局和局部搜索, 设计了可变核小体重组算子 (VNR) 以动态调整参与突变和交叉的基因数量. 在此基础上, 引入3个表观遗传算子, 通过丰富遗传多样性来减少过早收敛的可能. 在CEC’17基准函数集上10维, 30维, 50维和100维的实验结果表明, PEGA的准确性和稳定性均优于10种先进的进化和群体智能算法. 消融分析验证了PEG和VNR在96.55%的测试函数上的有效性, 并可将准确性提高至多4个数量级. 此外, PEGA在航天器轨迹优化问题上也表现出了最佳综合性能.
This is a preview of subscription content, log in via an institution to check access.
Data availability
The data that support the findings of this study are available from the corresponding author upon reasonable request.
References
Abualigah L, Shehab M, Alshinwan M, et al., 2021. Ant Lion Optimizer: a comprehensive survey of its variants and applications. Arch Comput Methods Eng, 28(3):1397–1416. https://doi.org/10.1007/s11831-020-09420-6
Baş E, Ülker E, 2020. A binary social spider algorithm for continuous optimization task. Soft Comput, 24(17):12953–12979. https://doi.org/10.1007/s00500-020-04718-w
Birogul S, 2016. Epigenetic algorithm for optimization: application to mobile network frequency planning. Arab J Sci Eng, 41(3):883–896. https://doi.org/10.1007/s13369-015-1869-5
Chen HC, Martinez JP, Zorita E, et al., 2017. Position effects influence HIV latency reversal. Nat Struct Mol Biol, 24(1):47–54. https://doi.org/10.1038/nsmb.3328
Chen HX, Fan DL, Fang L, et al., 2020. Particle swarm optimization algorithm with mutation operator for particle filter noise reduction in mechanical fault diagnosis. Int J Patt Recog Artif Intell, 34(10):2058012. https://doi.org/10.1142/S0218001420580124
Chromiński K, Boryczka M, 2016. Epigenetically inspired modification of genetic algorithm and his efficiency on biological sequence alignment. In: Czarnowski I, Caballero A, Howlett R, et al. (Eds.), Intelligent Decision Technologies 2016. Springer, Cham, p.95–105. https://doi.org/10.1007/978-3-319-39627-9_9
Coli GM, Boattini E, Filion L, et al., 2022. Inverse design of soft materials via a deep learning-based evolutionary strategy. Sci Adv, 8(3):eabj6731. https://doi.org/10.1126/sciadv.abj6731
Das S, Suganthan PN, 2010. Problem Definitions and Evaluation Criteria for CEC 2011 Competition on Testing Evolutionary Algorithms on Real World Optimization Problems. Technical Report, Jadavpur University, India, and Nanyang Technological University, Singapore, p.341–359.
Ezzarii M, El Ghazi H, El Ghazi H, et al., 2020. Epigenetic algorithm-based detection technique for network attacks. IEEE Access, 8:199482–199491. https://doi.org/10.1109/ACCESS.2020.3035250
Feng YH, Yi JH, Wang GG, 2019. Enhanced moth search algorithm for the set-union knapsack problems. IEEE Access, 7:173774–173785. https://doi.org/10.1109/ACCESS.2019.2956839
Gouil Q, Baulcombe DC, 2018. Paramutation-like features of multiple natural epialleles in tomato. BMC Genomics, 19(1):203. https://doi.org/10.1186/s12864-018-4590-4
Katoch S, Chauhan SS, Kumar V, 2021. A review on genetic algorithm: past, present, and future. Multim Tools Appl, 80(5):8091–8126. https://doi.org/10.1007/s11042-020-10139-6
Khalid QS, Azim S, Abas M, et al., 2021. Modified particle swarm algorithm for scheduling agricultural products. Eng Sci Technol Int J, 24(3):818–828. https://doi.org/10.1016/J.JESTCH.2020.12.019
Li Y, Lin XX, Liu JS, 2021. An improved gray wolf optimization algorithm to solve engineering problems. Sustainability, 13(6):3208. https://doi.org/10.3390/su13063208
Lin J, Zhu L, Gao KZ, 2020. A genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem. Expert Syst Appl, 140:112915. https://doi.org/10.1016/j.eswa.2019.112915
Makino H, Feng XA, Kita E, 2020. Stochastic schemata exploiter-based optimization of convolutional neural network. IEEE Int Conf on Systems, Man, and Cybernetics, p.4365–4371. https://doi.org/10.1109/SMC42975.2020.9283473
Mayanagi K, Saikusa K, Miyazaki N, et al., 2019. Structural visualization of key steps in nucleosome reorganization by human fact. Sci Rep, 9(1):10183. https://doi.org/10.1038/s41598-019-46617-7
Miikkulainen R, Forrest S, 2021. A biological perspective on evolutionary computation. Nat Mach Intell, 3(1):9–15. https://doi.org/10.1038/s42256-020-00278-8
Mirjalili S, Dong JS, Sadiq AS, et al., 2020. Genetic Algorithm: Theory, Literature Review, and Application in Image Reconstruction. In: Mirjalili S, Dong JS, Lewis A, (Eds.), Nature-Inspired Optimizers. Studies in Computational Intelligence. Springer, Cham, p.69–85. https://doi.org/10.1007/978-3-030-12127-3_5
Mohamed AW, Hadi AA, Mohamed AK, 2020. Gaining-sharing knowledge based algorithm for solving optimization problems: a novel nature-inspired algorithm. Int J Mach Learn Cybern, 11(7):1501–1529. https://doi.org/10.1007/s13042-019-01053-x
Monroe JG, Srikant T, Carbonell-Bejerano P, et al., 2022. Mutation bias reflects natural selection in Arabidopsis thaliana. Nature, 602(7895):101–105. https://doi.org/10.1038/s41586-021-04269-6
Nguyen TT, 2019. A high performance social spider optimization algorithm for optimal power flow solution with single objective optimization. Energy, 171:218–240. https://doi.org/10.1016/j.energy.2019.01.021
Owens NDL, Gonzalez I, Artus J, et al., 2020. Mitotic bookmarking by transcription factors and the preservation of pluripotency. In: Meshorer E, Testa G (Eds.), Stem Cell Epigenetics. Academic Press, Amsterdam, the Netherlands, p.131–153. https://doi.org/10.1016/B978-0-12-814085-7.00006-4
Pereira AGC, Campos VSM, de Pinho ALS, et al., 2020. On the convergence rate of the elitist genetic algorithm based on mutation probability. Commun Stat-Theory Methods, 49(4):769–780. https://doi.org/10.1080/03610926.2018.1528361
Periyasamy S, Gray A, Kille P, 2008. The epigenetic algorithm. IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), p.3228–3236. https://doi.org/10.1109/CEC.2008.4631235
Slowik A, Kwasnicka H, 2020. Evolutionary algorithms and their applications to engineering problems. Neur Comput Appl, 32:12363–12379.
Song YJ, Cai X, Zhou XB, et al., 2023. Dynamic hybrid mechanism-based differential evolution algorithm and its application. Expert Syst Appl, 213:118834. https://doi.org/10.1016/j.eswa.2022.118834
Stolfi DH, Alba E, 2018. Epigenetic algorithms: a new way of building gas based on epigenetics. Inform Sci, 424:250–272. https://doi.org/10.1016/j.ins.2017.10.005
Sun P, Liu H, Zhang Y, et al., 2021. An intensify atom search optimization for engineering design problems. Appl Math Model, 89:837–859. https://doi.org/10.1016/j.apm.2020.07.052
Tanev I, Yuta K, 2003. Epigenetic programming: an approach of embedding epigenetic learning via modification of histones in genetic programming. The 2003 Congress on Evolutionary Computation, p.2580–2587. https://doi.org/10.1109/CEC.2003.1299413
Thamban T, Agarwaal V, Khosla S, 2020. Role of genomic imprinting in mammalian development. J Biosci, 45(1):20. https://doi.org/10.1007/s12038-019-9984-1
Więckowski J, Kizielewicz B, Kołodziejczyk J, 2020. Finding an approximate global optimum of characteristic objects preferences by using simulated annealing. Proc 12th KES Int Conf on Intelligent Decision Technologies, p.365–375. https://doi.org/10.1007/978-981-15-5925-9_31
Yue CT, Price KV, Suganthan PN, et al., 2017. Problem Definitions and Evaluation Criteria for the CEC 2017 Special Session and Competition on Single Objective Bound Constrained Numerical Optimization. Technical Report, No. 201911 (2016).
Author information
Authors and Affiliations
Contributions
Zhiyu DUAN and Shunkun YANG designed the research and drafted the paper. Qi SHAO and Minghao YANG helped organize the paper. Zhiyu DUAN and Qi SHAO revised and finalized the paper.
Corresponding author
Ethics declarations
All the authors declare that they have no conflict of interest.
Additional information
Project supported by the National Natural Science Foundation of China (No. 61672080)
List of supplementary materials
1 The pseudocode of three types of epigenetic operators: position effect operator (PEO), gene imprinting operator (GIO), and paramutation operator (PMO)
2 The ablation experimental results of the probabilistic environmental gradient (PEG) and variable nucleosome reorganization (VNR) strategies
3 The complete results of performance experiments of the probabilistic environmental gradient-driven epigenetic algorithm (PEGA) (D=100, 50, 30, and 10)
Table S1 PEG, VNR, and PEG+VNR strategy comparison on the accuracy
Table S2 PEG, VNR, and PEG+VNR strategy comparison on the stability
Table S3 Comparison results of two unimodal and seven multimodal benchmark functions for PEGA and other algorithms
Table S4 Comparison results of 10 hybrid functions for PEGA and other algorithms
Table S5 Comparison results of 10 composition benchmark functions for PEGA and other algorithms
Algorithm S1 Position effect
Algorithm S2 Gene imprinting
Algorithm S3 Paramutation
Supplementary materials for
11714_2024_2014_MOESM1_ESM.pdf
PEGA: probabilistic environmental gradient-driven genetic algorithm considering epigenetic traits to balance global and local optimizations
Rights and permissions
About this article
Cite this article
Duan, Z., Yang, S., Shao, Q. et al. PEGA: probabilistic environmental gradient-driven genetic algorithm considering epigenetic traits to balance global and local optimizations. Front Inform Technol Electron Eng 25, 839–855 (2024). https://doi.org/10.1631/FITEE.2300170
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1631/FITEE.2300170
Key words
- Evolutionary algorithm
- Epigenetics
- Epigenetic algorithm
- Probabilistic environmental vector
- Variable nucleosome reorganization