Везде

ОЭММПУИзвестия Российской академии наук. Теория и системы управления Journal of Computer and System Sciences International

  • ISSN (Print) 0002-3388
  • ISSN (Online) 3034-6444

Модификации метода муравьиных колоний для перебора вариантов решения дискретнозначной параметрической задачи

Вы можете
Код статьи
S0002338825010067-1
DOI
10.31857/S0002338825010067
Тип публикации
Статья
Статус публикации
Опубликовано
Авторы
Давыдкина Е. А.
  • Аффилиация: МАИ (Национальный исследовательский университет)
Нестеров В. А.
  • Аффилиация: МАИ (Национальный исследовательский университет)
Судаков В. А.
  • Аффилиация:
    МАИ (Национальный исследовательский университет)
    ИПМ им. М.В. Келдыша РАН
Сыпало К. И.
  • Аффилиация: Центральный аэрогидродинамический институт им. проф. Н.Е. Жуковского
Титов Ю. П.
  • Аффилиация: МАИ (Национальный исследовательский университет)
Том/ Выпуск
Том / Номер выпуска 1
Страницы
73-89
Аннотация
Рассматривается задача поиска рациональных решений многоэкстремальной параметрической задачи методом муравьиных колоний. Рациональные решения – это решения, близкие по значению целевой функции к оптимальному, но не обязательно являющиеся таковыми. Для решения многоэкстремальной задачи предложена модификация метода муравьиных колоний, которая не сходится к одному решению, а продолжает его поиск. Отсутствие сходимости к одному решению преодолевает проблему стагнации предложенного в работе алгоритма метода муравьиных колоний. Найденные решения сохраняются в хэш-таблице, что позволяет избежать повторного вычисления значения целевой функции для уже вычисленного решения на вычислителе и осуществить поиск нового решения для каждого агента. Описана новая формула определения вероятности перехода муравья (агента) к новому параметру. Задачей данной формулы является решение проблемы стагнации алгоритма на ранних итерациях путем увеличения вероятности посещения агентом еще нерассмотренных компонентов решений. Алгоритм данной модификации метода муравьиных колоний позволяет решать дискретные параметрические задачи, определять рациональные значения параметров из дискретного множества. Изучается зависимость эффективности работы метода от параметров предложенной модификации метода муравьиных колоний. Исследование на тестовых задачах и задачах большой размерности показало зависимость от параметров аддитивной свертки и коэффициента испарения, отвечающего за уменьшение весов, которые получены на прошлых итерациях.
Ключевые слова
параметрическая задача метод муравьиных колоний целевая функция гиперпараметры хэш-таблица
Дата публикации
11.11.2025
Год выхода
2025
Всего подписок
0
Всего просмотров
73

Библиография

  1. 1. Bergstra J.S., Bardenet R., Bengio Y., Kégl B. Algorithms for Hyper-parameter Optimization // Adv. Neural Inform. Proc. Systems. 2011. V. 24. P. 2546–2554.
  2. 2. Akiba T., Shotaro S., Toshihiko Y., Takeru O., Masanori K. Optuna: A Next-generation Hyperparameter Optimization Framework // 25th ACM SIGKDD Intern. Conf. on Knowledge Discovery & Data Mining. N.Y., USA, 2019. P. 2623–2631; https://doi.org/10.48550/arXiv.1907.10902
  3. 3. Koehrsen W. A Conceptual Explanation of Bayesian Hyperparameter Optimization for Machine Learning. 2018 (открытый доступ 23.10.2022). https://towardsdatascience.com/a-conceptual-explanation-of-bayesian-model-based-hyperparameter-optimization-for-machine-learning-b8172278050f)
  4. 4. Dewancker I., McCourt M., Scott C. Bayesian Optimization Primer (открытый доступ 23. 23.10.2022). https://static.sigopt.com/b/20a144d208ef255d3b981ce419667ec25d8412e2/static/pdf/SigOpt_Bayesian_Optimization_Primer.pdf
  5. 5. IBM Bayesian Optimization Accelerator 1.1 Helps Identify Optimal Product Designs Faster with Breakthrough Performance for Scientific Discovery and High-performance Computing Simulation (открытый доступ 23.10.2022). https://www.ibm.com/common/ssi/ShowDoc.wss?docURL=/common/ssi/rep_ca/6/877/ENUSZP20-0186/index.html&request_locale=en
  6. 6. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. 2-е изд. М.: Изд-во МГТУ им. Баумана, 2017. 446 с.
  7. 7. Colorni A., Dorigo M., Maniezzo V. Distributed Optimization by Ant Colonies // Proc. First Eur. Conf. on Artific. Life / Eds F. Varela, P. Bourgine. Paris, France: Elsevier Publishing. 1992. P. 134–142.
  8. 8. Dorigo M., Stützle T. Ant Colony Optimization. Cambridge, Massachusetts: MIT Press, 2004. 321 p.
  9. 9. Юхименко Б.И., Титов Н.А., Ушаков В.О. Разработка и исследование алгоритмов муравьиной колонии для решения некоторых задач комбинаторной оптимизации // Актуальные научные исследования в современном мире. 2020. № 11-2 (67). С. 101–115.
  10. 10. Семенкина О.Е., Семенкин Е.С. О сравнении эффективности муравьиного и генетического алгоритмов при решении задач комбинаторной оптимизации // Актуальные проблемы авиации и космонавтики. 2011. Т. 1. № 7. С. 338–339.
  11. 11. Semenkina O.E., Popov E. Adaptive Ant Colony Optimization Algorithm for Hierarchical Scheduling Problem. Proc. Intern. Conf. on Information Technologies, Constantine and Elena. Varna, Bulgaria, 2019. P. 8860897; https://doi.org/10.1109/InfoTech.2019.8860897
  12. 12. Хахулин Г.Ф. Титов Ю.П. Система поддержки решений поставок запасных частей летательных аппаратов военного назначения // Изв. Самарского научного центра Российской академии наук. 2014. Т. 16. № 1–5. С. 1619–1623.
  13. 13. Судаков В.А., Батьковский А.М., Титов Ю.П. Алгоритмы ускорения работы модификации метода муравьиных колоний для поиска рационального назначения сотрудников на задачи с нечетким временем выполнения // Современные информационные технологии и ИТ-образование. 2020. Т. 16. № 2. C. 338–350; https://doi.org/10.25559/SITITO.16.202002.338-350
  14. 14. Martens D., De Backer M., Haesen R., Vanthienen J., Snoeck M., Baesens B. Classification with Ant Colony Optimization // IEEE Trans. Evol. Comput. 2007. V. 11. № 5. P. 651–665.
  15. 15. Синицын И.Н., Титов Ю.П. Оптимизация порядка следования гиперпараметров вычислительного кластера методом муравьиных колоний // Системы высокой доступности. 2022. Т. 18. № 3. С. 23–37; https://doi.org/10.18127/j20729472-202203-02
  16. 16. Судаков В.А., Титов Ю.П., Сивакова Т.В., Иванова П.М. Применение метода муравьиных колоний для поиска рациональных значений параметров технической системы: Препринт № 38. М.: ИПМ, 2023. С. 1–15; https://doi.org/10.20948/prepr-2023-38
  17. 17. Krzysztof S. Christian B. An Ant Colony Optimization Algorithm for Continuous Optimization: Application to Feed-Forward Neural Network Training // Neural Comput. Appl. 2007. V. 3. № 16. P. 235–247; https://doi.org/10.1007/s00521-007-0084-z
  18. 18. Пантелеев А.В., Алёшина Е.А. Применение непрерывной модификации метода муравьиных колоний к задаче поиска оптимального управления дискретными детерминированными системами // Научный вестник МГТУ ГА. 2013. № 8 (194).
  19. 19. Пантелеев А.В., Пановский В.Н. Применение гибридного меметического алгоритма в задачах оптимального управления нелинейными стохастическими системами с неполной обратной связью // Научный вестник МГТУ ГА. 2018. Т. 21, № 2. С. 59–70; https://doi.org/10.26467/2079-0619-2018-21-2-59-70
  20. 20. Саймон Д. Алгоритмы эволюционной оптимизации / Пер. с англ. А.В. Логунова. М.: ДМК Пресс, 2020. 1002 с.
  21. 21. Socha K., Dorigo M. Ant Colony Optimization for Continuous Domains // Europ. J. of Oper. Res. 2008. V. 185. № 3. P. 1155–1173; https://doi.org/10.1016/j.ejor.2006.06.046
  22. 22. Mohamad M., Tokhi M., Omar O.M. Continuous Ant Colony Optimization for Active Vibration Control of Flexible Beam Structures // IEEE Intern. Conf. on Mechatronics (ICM). Istanbul, Turkey, 2011. P. 803–808.
  23. 23. Карпенко А.П., Чернобривченко К.А. Эффективность оптимизации методом непрерывно взаимодействующей колонии муравьев (CIAC) // Наука и образование: научное издание МГТУ им. Н.Э. Баумана. 2011. № 2; https://doi.org/10.7463/0211.0165551
  24. 24. Abdelbar A.M., Salama K.M., Falcón-Cardona J.G., Coello C.A.C. An Adaptive Recombination-Based Extension of the iMOACOR Algorithm // IEEE Sympos. Series on Computational Intelligence (SSCI). Bangalore, India. 2018. P. 735–742; https://doi.org/10.1109/SSCI.2018.8628657
  25. 25. Abdelbar A.M., Humphries T., Falcón-Cardona J.G., Coello C.A. An Extension of the iMOACO Algorithm Based on Layer-Set Selection // Swarm Intelligence. ANTS 2022. Lecture Notes in Computer Science. 2022. V. 13491; https://doi.org/10.1007/978-3-031-20176-9_22
  26. 26. Карпенко А.П., Чернобривченко К.А. Мультимемеевая модификация гибридного муравьиного алгоритма непрерывной оптимизации HCIAC // Наука и образование: научное издание МГТУ им. Н.Э. Баумана. 2012. № 9; https://doi.org/10.7463/0912.0470529
  27. 27. Синицын И.Н., Титов Ю.П. Исследование возможности получения всех решений методом муравьиных колоний для задачи // Системы высокой доступности. 2023. Т. 20. № 2. С. 55–69; https://doi.org/10.31857/S000523102308010X
  28. 28. Russell S.J., Norvig P. Artificial Intelligence: A Modern Approach: Pearson Series In Artificial Intelligence. Fourth Edition. Hoboken: Pearson, 2021. 1245 с.
  29. 29. Синицын И.Н., Титов Ю.П. Управление наборами значений параметров системы методом муравьиных колоний // АиТ. 2023. № 8. С. 153–168; https://doi.org/10.31857/S000523102308010X
  30. 30. Синицын И.Н., Титов Ю.П. Оптимизация параметрических задач с отрицательным значением целевой функции методом муравьиных колоний // Системы высокой доступности. 2024. Т. 20. № 1. С. 30−37; https://doi.org/10.18127/j20729472-202401-03
  31. 31. Синицын И.Н., Титов Ю.П. Исследование алгоритмов циклического поиска дополнительных решений при оптимизации порядка следования гиперпараметров методом муравьиных колоний // Системы высокой доступности. 2023. Т. 19. № 1. С. 59–73; https://doi.org/10.18127/j20729472-202301-05
  32. 32. Mishra Sudhanshu K. Some New Test Functions for Global Optimization and Performance of Repulsive Particle Swarm Method. University Library of Munich, Germany: MPRA Paper, 2006; https://doi.org/10.2139/ssrn.926132
  33. 33. Abdesslem L. New Hard Benchmark Functions for Global Optimization. N.Y.: Cornell Tech, 2022; https://doi.org/10.48550/arXiv.2202.04606
  34. 34. Википедия. Тестовые функции для оптимизации (открытый доступ 23.10.2022) https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82%D0%BE%D0%B2%D1%8B%D0%B5_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8_%D0%B4%D0%BB%D1%8F_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8
  35. 35. Реализация модификаций алгоритма ACO (открытый доступ 23.10.2022). https://github.com/kalengul/ACO_Cluster/tree/master/Rezul
QR
Перевести

Индексирование

Scopus

Scopus

Scopus

Crossref

Scopus

Высшая аттестационная комиссия

При Министерстве образования и науки Российской Федерации

Scopus

Научная электронная библиотека