Genetic Engineering Algorithm (GEA): An Efficient Metaheuristic Algorithm for Solving Combinatorial Optimization Problems

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

Генетические алгоритмы (ГА) известны своей эффективностью в решении задач комбинаторной оптимизации благодаря их способности исследовать разнообразные пространства решений, обрабатывать различные представления, использовать параллелизм, сохранять хорошие решения, адаптироваться к изменяющимся условиям, управлять комбинаторным разнообразием и проводить эвристический поиск. Тем не менее такие ограничения, как преждевременная сходимость, неспецифичность и стохастичность операторов кроссовера и мутации, делают ГА не всегда эффективными при нахождении глобального оптимума. Чтобы преодолеть эти недостатки, в данной статье предлагается новый метаэвристический алгоритм, названный алгоритмом генетической инженерии (GEA), вдохновленный концепциями генной инженерии. GEA модифицирует традиционный ГА, включая новые методы поиска для выделения, коррекции, вставки и экспрессии новых генов на основе существующих, что способствует появлению желаемых признаков и производству хромосом на основе выбранных генов. Сравнение с результатами работы других алгоритмов на стандартных примерах демонстрирует эффективность GEA.

About the authors

Majid Sohrabi

Национальный исследовательский университет “Высшая школа экономики”

Email: msohrabi@hse.ru
Москва

Amir M. Fathollahi-Fard

Университет Квебека в Монреале

Email: fathollahifard.amirmohammad@courrier.uqam.ca
Канада

V. A Gromov

Национальный исследовательский университет “Высшая школа экономики”

Email: stroller@rambler.ru
Москва

References

  1. Holland J. Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press, 1975.
  2. Elshaer R., Awad H. A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants // Computers Indust. Engin. 2020. V. 140.P. 106242.
  3. Katoch S., Chauhan S.S., Kumar V. A review on genetic algorithm: past, present, and future // Multimedia Tools Appli. 2021. V. 80. P. 8091–8126.
  4. Yang X.S., Deb S. Engineering optimisation by cuckoo search // Int. J. Math. Modell. Numer. Optim. 2010. V. 1. No. 4. P. 330–343.
  5. Mirjalili S., Lewis A. The whale optimization algorithm // Advanc. Engin. Software. 2016. V. 95. P. 51–67.
  6. Mirjalili S. SCA: a sine cosine algorithm for solving optimization problems // Knowledge-Based Syst. 2016. V. 96. P. 120–133.
  7. Heidari A.A., Mirjalili S., Faris H., et al. Harris hawks optimization: Algorithm and applications // Future Generat. Comput. Syst. 2019. V. 97. P. 849–872.
  8. Jain M., Singh V., Rani A. A novel nature-inspired algorithm for optimization: Squirrel search algorithm // Swarm Evoluti. Comput. 2019. V. 44. P. 148–175.
  9. Fathollahi-Fard A.M., Hajiaghaei-Keshteli M., Tavakkoli-Moghaddam R. Red deer algorithm (RDA): a new nature-inspired meta-heuristic // Soft Comput. 2020. V. 24. P. 14637–14665.
  10. Xue J., Shen B. A novel swarm intelligence optimization approach: sparrow search algorithm // Syst. Sci. Control Engine. 2020. V. 8. No. 1. P. 22–34.
  11. Braik M., Sheta A., Al-Hiary H. A novel meta-heuristic search algorithm for solving optimization problems: capuchin search algorithm // Neural Comput. Appli. 2021. V. 33. P. 2515–2547.
  12. Abualigah L., Yousri D., Abd Elaziz M., et al. Aquila optimizer: a novel metaheuristic optimization algorithm // Comput. Indust. Engin. 2021. V. 157. P. 107250.
  13. Braik M.S. Chameleon Swarm Algorithm: A bio-inspired optimizer for solving engineering design problems // Expert Syst. Appl. 2021. V. 174. P. 114685.
  14. Yang Z., Deng L., Wang Y., et al. Aptenodytes forsteri optimization: Algorithm and applications // Knowledge-Based Syst. 2021. V. 232. P. 107483.
  15. Xue J., Shen B. Dung beetle optimizer: A new meta-heuristic algorithm for global optimization // J. Supercomput. 2023. V. 79. No. 7. P. 7305–7336.
  16. Zhong C., Li G., Meng Z. Beluga whale optimization: A novel nature-inspired metaheuristic algorithm // Knowledge-Based Syst. 2022. V. 251. P. 109215.
  17. Wolpert D.H., Macready W.G. No free lunch theorems for optimization // IEEE Transactions on Evoluti. Comput. 1997. V. 1. No. 1. P. 67–82.
  18. Fathollahi-Fard A.M., Hajiaghaei-Keshteli M., Tavakkoli-Moghaddam R. The social engineering optimizer (SEO) // Engin. Appli. Artific. Intellig. 2018. V. 72. P. 267– 293.
  19. Li D., Li X., Zhou W.L., et al. Genetically engineered T cells for cancer immunotherapy // Signal Transduct. Targeted Therapy. 2019. V. 4. No. 1. P. 35.
  20. Xiao Q., Guo D., Chen S. Application of CRISPR/Cas9-based gene editing in HIV1/AIDS therapy // Frontiers Cellul. Infect. Microbiol. 2019. V. 9. P. 69.
  21. Raposo V.L. The first Chinese edited babies: a leap of faith in science // JBRA Assist. Reproduct. 2019. V. 23. No. 3. P. 197.
  22. Li C. Breeding crops by design for future agriculture // J. Zhejiang Univer. Sci. B. 2020. V. 21. No. 6. P. 423.
  23. Dubock A. Golden rice: to combat vitamin A deficiency for public health. Vitamin A. 2019. V. 1.
  24. Huang T.K., Puchta H. Novel CRISPR/Cas applications in plants: from prime editing to chromosome engineering // Transgen. Res. 2021. V. 30. P. 529–549.
  25. Shahryari A., Saghaeian Jazi M., Mohammadi S., et al. Development and clinical translation of approved gene therapy products for genetic disorders // Front. Genet. 2019. V. 10. P. 868.
  26. Zhuo C., Zhang J., Lee J.H., et al. Spatiotemporal control of CRISPR/Cas9 gene editing // Signal Transduct. and Targeted Therapy. 2021. V. 6. No. 1. P. 238.
  27. Kostenetskiy P.S., Chulkevich R.A., Kozyrev V.I. HPC Resources of the Higher School of Economics // J. Phys. Conf. Seri. 2021. V. 1740. No. 1. P. 012050. https://doi.org/10.1088/1742-6596/1740/1/012050
  28. Gero J.S., Kazakov V. A genetic engineering approach to genetic algorithms // Evoluti. Comput. 2001. V. 9. No. 1. P. 71–92.
  29. Kameya Y., Prayoonsri C. Pattern-based preservation of building blocks in genetic algorithms // IEEE Congre. Evolut. Comput. (CEC). 2011. P. 2578–2585.
  30. Ding S., Su C., Yu J. An optimizing BP neural network algorithm based on genetic algorithm // Artific. Intellig. Rev. 2011. V. 36. P. 153–162.
  31. Liang Y., Leung K.S. Genetic algorithm with adaptive elitist-population strategies for multimodal function optimization // Appl. Soft Comput. 2011. V. 11. No. 2. P. 2017–2034.
  32. Dasgupta K., Mandal B., Dutta P., et al. A genetic algorithm (ga) based load balancing strategy for cloud computing // Procedia Techn. 2013. V. 10. P. 340–347.
  33. Elsayed S.M., Sarker R.A., Essam D.L. A new genetic algorithm for solving optimization problems // Engin. Appli. of Artific. Intellig. 2014. V. 27. P. 57–69.
  34. Peng B., Li L. An improved localization algorithm based on genetic algorithm in wireless sensor networks // Cognitive Neurodynam. 2015. V. 9. P. 249–256.
  35. Askarzadeh A. A memory-based genetic algorithm for optimization of power generation in a microgrid // IEEE Transact. Sustainable Energy. 2017. V. 9. No. 3. P. 1081–1089.
  36. Reddy G.T., Reddy M.P.K., Lakshmanna, et al. Hybrid genetic algorithm and a fuzzy logic classifier for heart disease diagnosis // Evolut. Intellig. 2020. V. 13. P. 185–196.
  37. Fathollahi-Fard A.M., Dulebenets M.A., Hajiaghaei-Keshteli M., et al. Two hybrid meta-heuristic algorithms for a dual-channel closed-loop supply chain network design problem in the tire industry under uncertainty // Adv. Engin. Inform. 2021. V. 50. P. 101418.
  38. Fathollahi-Fard A.M., Tian G., Ke H., et al. Efficient Multi-objective Metaheuristic Algorithm for Sustainable Harvest Planning Problem // Comput. Oper. Res. 2023. V. 158. P. 106304.
  39. Kolaee M.H., Mirzapour Al-e-Hashem S.M.J, Jabbarzadeh A. A local search-based non-dominated sorting genetic algorithm for solving a multi-objective medical tourism trip design problem considering the attractiveness of trips // Engin. Appl. Artific. Intellig. 2023. V. 124. P. 106630.
  40. Du D., Pardalos P.M. Handbook of combinatorial optimization. Springer Science & Business Media. 1998. V. 4.
  41. Mart R., Pardalos P.M., Resende M.G. Handbook of heuristics. Springer Publishing Company, Incorporated. 2018.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2024 The Russian Academy of Sciences