Genetic Engineering Algorithm (GEA): An Efficient Metaheuristic Algorithm for Solving Combinatorial Optimization Problems
- Authors: Sohrabi M.1, Fathollahi-Fard A.M.1, Gromov V.A1
-
Affiliations:
- Issue: No 3 (2024)
- Pages: 23–37
- Section: Articles
- URL: https://journals.rcsi.science/0005-2310/article/view/256151
- DOI: https://doi.org/10.31857/S0005231024030027
- EDN: https://elibrary.ru/UAGNKK
- ID: 256151
Cite item
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
- Holland J. Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press, 1975.
- 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.
- 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.
- Yang X.S., Deb S. Engineering optimisation by cuckoo search // Int. J. Math. Modell. Numer. Optim. 2010. V. 1. No. 4. P. 330–343.
- Mirjalili S., Lewis A. The whale optimization algorithm // Advanc. Engin. Software. 2016. V. 95. P. 51–67.
- Mirjalili S. SCA: a sine cosine algorithm for solving optimization problems // Knowledge-Based Syst. 2016. V. 96. P. 120–133.
- 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.
- 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.
- 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.
- 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.
- 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.
- Abualigah L., Yousri D., Abd Elaziz M., et al. Aquila optimizer: a novel metaheuristic optimization algorithm // Comput. Indust. Engin. 2021. V. 157. P. 107250.
- Braik M.S. Chameleon Swarm Algorithm: A bio-inspired optimizer for solving engineering design problems // Expert Syst. Appl. 2021. V. 174. P. 114685.
- Yang Z., Deng L., Wang Y., et al. Aptenodytes forsteri optimization: Algorithm and applications // Knowledge-Based Syst. 2021. V. 232. P. 107483.
- 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.
- Zhong C., Li G., Meng Z. Beluga whale optimization: A novel nature-inspired metaheuristic algorithm // Knowledge-Based Syst. 2022. V. 251. P. 109215.
- 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.
- 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.
- 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.
- 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.
- Raposo V.L. The first Chinese edited babies: a leap of faith in science // JBRA Assist. Reproduct. 2019. V. 23. No. 3. P. 197.
- Li C. Breeding crops by design for future agriculture // J. Zhejiang Univer. Sci. B. 2020. V. 21. No. 6. P. 423.
- Dubock A. Golden rice: to combat vitamin A deficiency for public health. Vitamin A. 2019. V. 1.
- 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.
- 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.
- 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.
- 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
- Gero J.S., Kazakov V. A genetic engineering approach to genetic algorithms // Evoluti. Comput. 2001. V. 9. No. 1. P. 71–92.
- Kameya Y., Prayoonsri C. Pattern-based preservation of building blocks in genetic algorithms // IEEE Congre. Evolut. Comput. (CEC). 2011. P. 2578–2585.
- 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.
- 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.
- 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.
- 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.
- Peng B., Li L. An improved localization algorithm based on genetic algorithm in wireless sensor networks // Cognitive Neurodynam. 2015. V. 9. P. 249–256.
- 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.
- 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.
- 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.
- 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.
- 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.
- Du D., Pardalos P.M. Handbook of combinatorial optimization. Springer Science & Business Media. 1998. V. 4.
- Mart R., Pardalos P.M., Resende M.G. Handbook of heuristics. Springer Publishing Company, Incorporated. 2018.