Обзор программных средств для работы с эволюционными и роевыми методами оптимизации
Аннотация
Настоящая статья посвящена обзору программных средств, позволяющих применять, разрабатывать и исследовать эволюционные и роевые методы оптимизации для решения сложных задач дискретной и непрерывной оптимизации. В статье рассматриваются различные виды и типы оптимизационных задач, возникающих в прикладных задачах, включая задачи многокритериальной оптимизации. Формализуется понятие популяционного алгоритма оптимизации и рассматриваются основные классы алгоритмов данного типа, в том числе эволюционные алгоритмы, роевые алгоритмы и многочастичные алгоритмы. Приводятся результаты детального анализа тринадцати современных наиболее популярных фреймворков для работы с эволюционными и роевыми алгоритмами оптимизации. Основной целью анализа является исследование предоставляемых данными программными средствами возможностей по созданию, настройке и применению популяционных алгоритмов оптимизации для решения прикладных оптимизационных задач. В том числе анализируются типы поддерживаемых рассматриваемыми программными средствами задач оптимизации, а также наличие встроенных средств тестирования и наборов тестовых задач оптимизации. Отдельный пункт исследования посвящен анализу поддержки рассматриваемыми фреймворками параллельных вычислений, так как известно, что применение популяционных алгоритмов с одной стороны является вычислительно затратным, а с другой стороны такие алгоритмы обладают значительным потенциалом к распараллеливанию. На основании результатов проведенного обзора даются рекомендации по применению рассмотренных программных средств в различных сценариях их практического использования.
Литература
2. Kennedy J., Eberhart R. Particle swarm optimization. In: Proceedings of the International Conference on Neural Networks (ICNN'95). Perth, WA, Australia: IEEE Press; 1995. Vol. 4. p. 1942-1948. https://doi.org/10.1109/ICNN.1995.488968
3. Passino K.M. Biomimicry of bacterial foraging for distributed optimization and control. IEEE control systems magazine. 2002;22(3):52-67. https://doi.org/10.1109/MCS.2002.1004010
4. Corana A., et al. Minimizing multimodal functions of continuous variables with the "simulated annealing" algorithm. ACM Transactions on Mathematical Software. 1987;13(3):262-280. https://doi.org/10.1145/29380.29864
5. Chen W.N., Tan D.Z. Set-based discrete particle swarm optimization and its applications: a survey. Frontiers of Computer Science. 2018;12:203-216. https://doi.org/10.1007/s11704-018-7155-4
6. Khuri S., Bäck T., Heitkötter J. An Evolutionary Approach to Combinatorial Optimization Problems. ACM Conference on Computer Science. 1994:66-73. https://doi.org/10.1145/197530.197558
7. Bianchi L., et al. A survey on metaheuristics for stochastic combinatorial optimization. Natural Computing. 2009;8:239-287. https://doi.org/10.1007/s11047-008-9098-4
8. Janecek A., Tan Y. Using Population Based Algorithms for Initializing Nonnegative Matrix Factorization. In: Tan Y., Shi Y., Chai Y., Wang G. (eds.) Advances in Swarm Intelligence. ICSI 2011. Lecture Notes in Computer Science. Vol. 6729. Berlin, Heidelberg: 2011. p. 307-316. https://doi.org/10.1007/978-3-642-21524-7_37
9. Chen X.Y., Chau K.W., Busari A.O. A comparative study of population-based optimization algorithms for downstream river flow forecasting by a hybrid neural network model. Engineering Applications of Artificial Intelligence. 2015;46:258-268. https://doi.org/10.1016/j.engappai.2015.09.010
10. Arnold D.V., Beyer H.G. Noisy Optimization with Evolution Strategies. Universität Dortmund; 2002. 20 p. http://dx.doi.org/10.17877/DE290R-14966
11. Patle B.K., et al. Path planning in uncertain environment by using firefly algorithm. Defence technology. 2018;14(6):691-701. https://doi.org/10.1016/j.dt.2018.06.004
12. Askarzadeh A. A novel metaheuristic method for solving constrained engineering optimization problems: crow search algorithm. Computers & structures. 2016;169:1-12. https://doi.org/10.1016/j.compstruc.2016.03.001
13. Kaboli S.H.A., Selvaraj J., Rahim N.A. Rain-fall optimization algorithm: A population based algorithm for solving constrained optimization problems. Journal of Computational Science. 2017;19:31-42. https://doi.org/10.1016/j.jocs.2016.12.010
14. Deb K. Multi-objective optimisation using evolutionary algorithms: an introduction // Multi-objective evolutionary optimisation for product design and manufacturing. London: Springer London, 2011. https://doi.org/10.1007/978-0-85729-652-8_1
15. Rajpurohit J., et al. Glossary of metaheuristic algorithms. International Journal of Computer Information Systems and Industrial Management Applications. 2017;9:25-25. Available at: https://cspub-ijcisim.org/index.php/ijcisim/article/view/353 (accessed 17.01.2025).
16. Cantu-Paz E., Goldberg D.E. On the scalability of parallel genetic algorithms. Evolutionary computation. 1999;7(4):429-449. https://doi.org/10.1162/evco.1999.7.4.429
17. Essaid M., et al. GPU parallelization strategies for metaheuristics: a survey. International Journal of Parallel, Emergent and Distributed Systems. 2019;34(5):497-522. https://doi.org/10.1080/17445760.2018.1428969
18. Parejo J.A., Ruiz-Cortés A., Lozano S., Fernandez P. Metaheuristic optimization frameworks: a survey and benchmarking. Soft Computing. 2012;16(3):527-561. https://doi.org/10.1007/s00500-011-0754-8
19. Ramírez A., Barbudo R., Romero J.R. An experimental comparison of metaheuristic frameworks for multi‐objective optimization. Expert Systems. 2023;40(4):e12672. https://doi.org/10.1111/exsy.12672
20. Talbi E. G. Automated design of deep neural networks: A survey and unified taxonomy. ACM Computing Surveys. 2021;54(2):1-37. https://doi.org/10.1145/3439730
21. Huang H.Z., Zhang X. Design optimization with discrete and continuous variables of aleatory and epistemic uncertainties. Journal of Mechanical Design. 2009;131(3):031006. https://doi.org/10.1115/1.3066712
22. Kokkolaras M., Audet C., Dennis J. E. Mixed variable optimization of the number and composition of heat intercepts in a thermal insulation system. Optimization and Engineering. 2001;2:5-29. https://doi.org/10.1023/A:1011860702585
23. Gutjahr W.J., Strauss C., Wagner E. A stochastic branch-and-bound approach to activity crashing in project management. INFORMS journal on computing. 2000;12(2):125-135. https://doi.org/10.1287/ijoc.12.2.125.11894
24. Patle B.K., et al. Path planning in uncertain environment by using firefly algorithm. Defence technology. 2018;14(6):691-701. https://doi.org/10.1016/j.dt.2018.06.004
25. Mahanta B.K., Chakraborti N. Tri-objective optimization of noisy dataset in blast furnace iron-making process using evolutionary algorithms. Materials and Manufacturing Processes. 2020;35(6):677-686. https://doi.org/10.1080/10426914.2019.1643472
26. Emmerich M.T.M., Deutz A.H. A tutorial on multiobjective optimization: fundamentals and evolutionary methods. Natural computing. 2018.17:585-609. https://doi.org/10.1007/s11047-018-9685-y
27. De Castro L.N., Von Zuben F.J. Learning and optimization using the clonal selection principle. IEEE transactions on evolutionary computation. 2002;6(3):239-251. https://doi.org/10.1109/TEVC.2002.1011539
28. Reynolds C.W. Flocks, herds and schools: A distributed behavioral model. In: Proceedings of the 14th annual conference on Computer graphics and interactive techniques. (SIGGRAPH '87). New York, NY, USA: Association for Computing Machinery; 1987. p. 25-34. https://doi.org/10.1145/37401.37406
29. Dorigo M., Birattari M., Stutzle T. Ant colony optimization. IEEE computational intelligence magazine. 2006;1(4):28-39. https://doi.org/10.1109/MCI.2006.329691
30. Pham D.T., et al. The Bees Algorithm A Novel Tool for Complex Optimisation Problems. Intelligent production machines and systems. 2nd I*PROMS Virtual International Conference 3-14 July 2006. Elsevier Science Ltd; 2006. p. 454-459. https://doi.org/10.1016/B978-008045157-2/50081-X
31. Krishnanand K.N., Ghose D. Glowworm swarm optimisation: a new method for optimising multi-modal functions. International Journal of Computational Intelligence Studies. 2009;1(1):93-119. https://doi.org/10.1504/IJCISTUDIES.2009.025340
32. Cheng R., Jin Y. A competitive swarm optimizer for large scale optimization. IEEE transactions on cybernetics. 2014;45(2):191-204. https://doi.org/10.1109/TCYB.2014.2322602
33. Rashedi E., Nezamabadi-Pour H., Saryazdi S. GSA: a gravitational search algorithm. Information sciences. 2009;179(13):2232-2248. https://doi.org/10.1016/j.ins.2009.03.004
34. Rabanal P., Rodríguez I., Rubio F. Using River Formation Dynamics to Design Heuristic Algorithms. In: Akl S.G., Calude C.S., Dinneen M.J., Rozenberg G., Wareham H.T. (eds.) Unconventional Computation. UC 2007. Lecture Notes in Computer Science. Vol. 4618. Berlin, Heidelberg: Springer; 2007. p. 163-177. https://doi.org/10.1007/978-3-540-73554-0_16
35. Miranda L.J. PySwarms: a research toolkit for Particle Swarm Optimization in Python. Journal of Open Source Software. 2018;3(21):433. https://doi.org/10.21105/joss.00433
36. Biscani F., Izzo D. A parallel global multiobjective framework for optimization: pagmo. Journal of Open Source Software. 2020;5(53):2338. https://doi.org/10.21105/joss.02338
37. Fortin F.A., et al. DEAP: Evolutionary algorithms made easy. The Journal of Machine Learning Research. 2012;13(1):2171-2175. Available at: https://dl.acm.org/doi/10.5555/2503308.2503311 (accessed 17.01.2025).
38. Blank J., Deb K. Pymoo: Multi-objective optimization in python. IEEE Access. 2020;8:89497-89509. https://doi.org/10.1109/ACCESS.2020.2990567
39. Durillo J.J., Nebro A.J. jMetal: A Java framework for multi-objective optimization. Advances in engineering software. 2011;42(10):760-771. https://doi.org/10.1016/j.advengsoft.2011.05.014
40. Coletti M.A., Scott E.O., Bassett J.K. Library for evolutionary algorithms in Python (LEAP). In: Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion (GECCO '20). New York, NY, USA: Association for Computing Machinery; 2020. p. 1571-1579. https://doi.org/10.1145/3377929.3398147
41. Dreo J., et al. Paradiseo: from a modular framework for evolutionary computation to the automated design of metaheuristics: 22 years of Paradiseo. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '21). New York, NY, USA: Association for Computing Machinery; 2021. p. 1522-1530. https://doi.org/10.1145/3449726.3463276
42. Collet P., Lutton E., Schoenauer M., Louchet J. Take It EASEA. In: Schoenauer, M., et al. Parallel Problem Solving from Nature PPSN VI. PPSN 2000. Lecture Notes in Computer Science. Vol. 1917. Berlin, Heidelberg: Springer; 2000. p. 891-901. https://doi.org/10.1007/3-540-45356-3_87
43. Wagner S., et al. Architecture and Design of the HeuristicLab Optimization Environment. In: Klempous R., Nikodem J., Jacak W., Chaczko Z. (eds.) Advanced Methods and Applications in Computational Intelligence. Topics in Intelligent Engineering and Informatics. Vol. 6. Heidelberg: Springer; 2014. p. 197-261. https://doi.org/10.1007/978-3-319-01436-4_10
44. Lukasiewycz M., Glaß M., Reimann F., Teich J. Opt4J: a modular framework for meta-heuristic optimization. In: Proceedings of the 13th annual conference on Genetic and evolutionary computation (GECCO '11). New York, NY, USA: Association for Computing Machinery; 2011. p. 1723-1730. https://doi.org/10.1145/2001576.2001808
45. Navarro R., Nápoles G. Classical niching methods for multimodal optimization: a brief review. Revista Cubana de Ciencias Informáticas. 2013;7(2):137-153. Available at: https://rcci.uci.cu/index.php/RCCI/article/view/430 (accessed 17.01.2025). (In Spain., abstract in Eng.)
46. Jiang S., Kaiser M., Wan S., Guo J., Yang S., Krasnogor N. An Empirical Study of Dynamic Triobjective Optimisation Problems. In: 2018 IEEE Congress on Evolutionary Computation (CEC). Rio de Janeiro, Brazil: IEEE Press; 2018. p. 1-8. https://doi.org/10.1109/CEC.2018.8477667
47. Zitzler E., Deb K., Thiele L. Comparison of multiobjective evolutionary algorithms: Empirical results. Evolutionary computation. 2000;8(2):173-195. https://doi.org/10.1162/106365600568202
48. Deb K., Thiele L., Laumanns M., Zitzler E. Scalable Test Problems for Evolutionary Multiobjective Optimization. In: Abraham A., Jain L., Goldberg R. (eds.) Evolutionary Multiobjective Optimization. Advanced Information and Knowledge Processing. London: Springer; 2005. p. 105-145. https://doi.org/10.1007/1-84628-137-7_6
49. Virtanen P., et al. SciPy 1.0: fundamental algorithms for scientific computing in Python. Nature methods. 2020;17(3):261-272. https://doi.org/10.1038/s41592-019-0686-2
50. de Nobel J., Ye F., Vermetten D., Wang H., Doerr C., Bäck T. IOHexperimenter: Benchmarking Platform for Iterative Optimization Heuristics. Evolutionary Computation. 2024;32(3):205-210. https://doi.org/10.1162/evco_a_00342
51. Telikani A., et al. Evolutionary machine learning: A survey. ACM Computing Surveys. 2021;54(8):1-35. https://doi.org/10.1145/3467477
52. Zhang Y., et al. Evolutionary Computation in bioinformatics: A survey. Neurocomputing. 2024;591:127758. https://doi.org/10.1016/j.neucom.2024.127758
53. Cantú-Paz E. Topologies, migration rates, and multi-population parallel genetic algorithms. In: Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation Vol. 1 (GECCO'99). San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.; 1999. p. 91-98. Available at: https://dl.acm.org/doi/10.5555/2933923.2933933 (accessed 17.01.2025).
54. Hold-Geoffroy Y., Gagnon O., Parizeau M. Once you SCOOP, no need to fork. In: Proceedings of the 2014 Annual Conference on Extreme Science and Engineering Discovery Environment (XSEDE '14). New York, NY, USA: Association for Computing Machinery; 2014. Article number: 60. https://doi.org/10.1145/2616498.2616565
55. Rocklin M. Dask: Parallel Computation with Blocked algorithms and Task Scheduling. In: Proceedings of the 14th Python in Science Conference (SciPy 2015). Austin, Texas July 6-12, 2015. p. 126-132. https://doi.org/10.25080/MAJORA-7B98E3ED-013
56. Dalcin L., Fang Y.L.L. mpi4py: Status Update After 12 Years of Development. Computing in Science & Engineering. 2021;23(4):47-54. https://doi.org/10.1109/MCSE.2021.3083216

Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.