с 01.01.2024 по настоящее время
Россия
АО "Научно-исследовательский институт электронной техники"
Россия
УДК 004.023 Эвристические методы
Статья посвящена исследованию и сравнению различных эвристических алгоритмов оптимизации, применяемых для решения задач, где отсутствуют строгие аналитические решения. Рассмотрены три алгоритма: генетические алгоритмы, алгоритм имитации отжига и алгоритм оптимизации роем светлячков. Каждый из этих методов основан на принципах случайного поиска и вдохновлён природными процессами и идеей ролевого интеллекта, где поведение отдельных особей в соответствии с простыми правилами позволяет найти квазиоптимальное решение. Генетические алгоритмы используют механизмы селекции, кроссинговера и мутации для поиска оптимальных решений. Алгоритм имитации отжига вдохновляется процессом охлаждения твёрдого кристаллического тела, позволяет системе переходить в менее выгодные состояния с определённой вероятностью. Алгоритм оптимизации роем светлячков основан на поведении светлячков, где агенты перемещаются в направлении более ярких особей, что означает лучшее значение целевой функции, либо перемещаются в случайном направлении. В статье проведён вычислительный эксперимент, который позволяет сравнить эффективность алгоритмов по двум критериям: близость к глобальному минимуму и количество вычислений целевой функции. Результаты показали, что алгоритм имитации отжига является наиболее простым и эффективным для оптимизации двумерных многомодальных функций, тогда как генетические алгоритмы и алгоритм светлячков требуют более сложной настройки параметров.
генетические алгоритмы, роевой интеллект, алгоритмы оптимизации, эвристические алгоритмы, имитация отжига, рой светлячков
1. Трушин, С.М. Применение эволюционного моделирования и генетических алгоритмов для решения задач оптимизации / С.М.Трушин, А.К. Титлянов // Научный аспект. – 2024. – Т. 46, №4. – С.6138-6149.
2. Aarts E., Korst J., Michiels W. Simulated annealing // Operations Research. 1992. N 40(1). P. 113-125.
3. Костенко, В.А. Алгоритмы комбинаторной оптимизации, сочетающие жадные стратегии и ограниченный перебор / В.А. Костенко // Известия Российской академии наук. Теория и системы управления. – 2017. - №2. – С. 48-56. DOI:https://doi.org/10.7868/S0002338817020135
4. Костенко, В.А. Алгоритмы комбинаторной оптимизации, сочетающие жадные стратегии и ограниченный перебор / В.А. Костенко // Известия Российской академии наук. Теория и системы управления. – 2017. - №2. – С. 48-56. DOI:https://doi.org/10.7868/S0002338817020135
5. Гладков Л. А., Курейчик В. В., Курейчик В.М. Генетические алгоритмы / Под ред. В.М. Курейчика. — 2-е изд., исправл. и доп. — М.: ФИЗМАТЛИТ, 2010. — 368 с. — ISBN 978-5-9221-0510-1.
6. Жабин Д.А. Автоматизированный синтез принципиальных схем и топологии малошумящих СВЧ-усилителей на основе генетического алгоритма / Д.А. Жабин [и др.] // Доклады ТУСУР. – 2017. – Т.20, №3. – С.132-143
7. Кныш, Д.С. Генетический алгоритм трассировки коммутационных блоков / Д.С.Кныш, В.М. Курейчик //Известия высших учебных заведений. Электроника. – 2009 - №5(79). – С.28-34
8. Holland J.N. Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan: Univ. of Michigan Press, 1975.
9. Golberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning. 61 Addison-Wesley, Reading, Mass., 1989.
10. D. Kovalenko, V. Kostenko A Genetic Algorithm for Construction of Recognizers of Anomalies in Behaviour of Dynamical Systems// Proceedings of the IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications, IEEE Press, China. 2010. - pp.258-263.
11. Программная реализация метода имитации отжига и анализ его эффективности /А. В. Землянский, Г. А. Штыков // Вестник Пензенского государственного университета. – 2017. – № 4 (20). – С. 76–81
12. Костенко В.А., Калашников А.В. Исследование различных модификаций алгоритмов имитации отжига для решения задачи построения многопроцессорных расписаний// Дискретные модели в теории управляющих систем. Труды VII Международной конференции. М.: МАКС Пресс, 2006. - С.179- 184.
13. Зорин, Д. А. Оценка сходимости алгоритма имитации отжига для задачи построения многопроцессорных расписаний / Д. А. Зорин // Вестник Московского университета. Серия 15: Вычислительная математика и кибернетика. – 2014. – № 2. – С. 53-59. – EDN SATXOZ.
14. Van Laarhoven P.J., Aarts E.H., Lenstra J.K. Job shop scheduling by simulated annealing // Operations Research. 1992. N 40(1) P. 113-125.
15. Hongxia Liu, Shiliang Chen, Yongquan Zhou. A novel hybrid optimization algorithm based on glowworm swarm and fish school, Journal of Computational Information Systems, 2010, No. 6 (13), pp. 4533-4542
16. Piotr and Oramus. Improvements to glowworm swarm optimization algorithm, Computer Science, 2010, No. 11, pp. 7-20.
17. Karpenko A.P. Populyatsionnye algoritmy global'noy poiskovoy optimizatsii. Obzor novykh i maloizvestnykh algoritmov [Population Algorithms for Global Continuous Optimization. Review of New and Little-Known Algorithms], Informatsionnye tekhnologii [Information Technologies], 2012, No. 7, pp. 1-32.
18. Karpenko A.P. Gibridnye populyatsionnye algoritmy parametricheskoy optimizatsii proektnykh resheniy [Hybrid population-based algorithms for parametric optimization of design solutions], Informatsionnye tekhnologii [Information Technologies], 2013, No. 12, pp. 6-15.
19. Курейчик, В.В. алгоритм параметрической оптимизации на основе модели поведения роя светлячков / В.В. Курейчик, Д.В. Заруба, Д.Ю. Запорожец // Известия ЮФУ. Технические науки. – 2015. - №6(167). – С. 6-15
20. Карпенко, А. П. Популяционные алгоритмы глобальной поисковой оптимизации. Обзор новых и малоизвестных алгоритмов / А. П. Карпенко // Информационные технологии. – 2012. – № S7. – С. 1-32. – EDN PBMPVF.
21. Bulavchuk A., Semenova D. Genetic algorithm based on idempotent algebra methods for RCPSP // 2021 IEEE 15th International Conference on Application of Information and Communication Technologies (AICT). — 2021. — P. 1–4.
22. Bulavchuk A., Semenova D. Genetic algorithm based on idempotent algebra methods for RCPSP // 2021 IEEE 15th International Conference on Application of Information and Communication Technologies (AICT). — 2021. — P. 1–4.
23. Bulavchuk A., Semenova D. Application of idempotent algebra methods in genetic algorithm for solving the scheduling problem // Prikl. Diskr. Mat. — 2022. — № 58. — P. 112–124. (in Russian)
24. Bulavchuk A., Semenova D. Features of risk analysis in solving RCPSP using the GASPIA algorithm // 2022 IEEE International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON). — 2022. — P. 970–973.
25. Pan N.-H., Hsiang T.-C., Chen W.-T. Using hybrid simulated annealing algorithm in resource-constrained project scheduling problem // The International Journal of Organizational Innovation. — 2020. — Vol. 12. — P. 25–46.
26. Bulavchuk A., Semenova D. Application of idempotent algebra methods in genetic algorithm for solving the scheduling problem // Prikladnaya Diskretnaya Matematika. — 2023. — P. 112–124.
27. Козлов А., Кондратенко Ю. Поиск оптимальных функций принадлежности нечетких систем на основе биоинспирированных эволюционных алгоритмов. Часть 1. Пошаговый метод // International Scientific Technical Journal Problems of Control and Informatics. — 2020. — № 66. — P. 55–75.
28. Жирнова О.В., Тулеушова Р.Ж. Интеллектуальные системы управления полётом на основе искусственного интеллекта // Вестник Академии гражданской авиации. — 2024.
29. Swamy E.N. Automatic timetable generation using genetic algorithm // Journal of Information Studies & Technology (JIS&T). — 2025. — Vol. 33.
30. Naaman D., Ahmed B., Ibrahim I. Optimization by nature: A review of genetic algorithm techniques // The Indonesian Journal of Computer Science. — 2025.
31. Tang W. Optimization of urban terminal delivery routes using fuzzy genetic algorithm and its practical application // Journal of Computational Methods in Sciences and Engineering. — 2025.
32. Slowik A., Ezugwu A., Wagdy A. Swarm intelligence algorithms and their engineering applications. — 2024.
33. Козлов А., Кондратенко Ю. Поиск оптимальных функций принадлежности нечетких систем на основе биоинспирированных эволюционных алгоритмов. Часть 1. Пошаговый метод // International Scientific Technical Journal Problems of Control and Informatics. — 2020. — № 66. — P. 55–75.
