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

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Рассматривается задача поиска рациональных решений многоэкстремальной параметрической задачи методом муравьиных колоний. Рациональные решения – это решения, близкие по значению целевой функции к оптимальному, но не обязательно являющиеся таковыми. Для решения многоэкстремальной задачи предложена модификация метода муравьиных колоний, которая не сходится к одному решению, а продолжает его поиск. Отсутствие сходимости к одному решению преодолевает проблему стагнации предложенного в работе алгоритма метода муравьиных колоний. Найденные решения сохраняются в хэш-таблице, что позволяет избежать повторного вычисления значения целевой функции для уже вычисленного решения на вычислителе и осуществить поиск нового решения для каждого агента. Описана новая формула определения вероятности перехода муравья (агента) к новому параметру. Задачей данной формулы является решение проблемы стагнации алгоритма на ранних итерациях путем увеличения вероятности посещения агентом еще нерассмотренных компонентов решений. Алгоритм данной модификации метода муравьиных колоний позволяет решать дискретные параметрические задачи, определять рациональные значения параметров из дискретного множества. Изучается зависимость эффективности работы метода от параметров предложенной модификации метода муравьиных колоний. Исследование на тестовых задачах и задачах большой размерности показало зависимость от параметров аддитивной свертки и коэффициента испарения, отвечающего за уменьшение весов, которые получены на прошлых итерациях.

Полный текст

Доступ закрыт

Об авторах

Е. А. Давыдкина

МАИ (Национальный исследовательский университет)

Автор, ответственный за переписку.
Email: davydkinaelena@yandex.ru
Россия, Москва

В. А. Нестеров

МАИ (Национальный исследовательский университет)

Email: nesterov46@inbox.ru
Россия, Москва

В. А. Судаков

МАИ (Национальный исследовательский университет); ИПМ им. М.В. Келдыша РАН

Email: sudakov@ws-dss.com
Россия, Москва; Москва

К. И. Сыпало

Центральный аэрогидродинамический институт им. проф. Н.Е. Жуковского

Email: ksypalo@tsagi.ru
Россия, Жуковский

Ю. П. Титов

МАИ (Национальный исследовательский университет)

Email: kalengul@mail.ru
Россия, Москва

Список литературы

  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. 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. 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. 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. 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. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. 2-е изд. М.: Изд-во МГТУ им. Баумана, 2017. 446 с.
  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. Dorigo M., Stützle T. Ant Colony Optimization. Cambridge, Massachusetts: MIT Press, 2004. 321 p.
  9. Юхименко Б.И., Титов Н.А., Ушаков В.О. Разработка и исследование алгоритмов муравьиной колонии для решения некоторых задач комбинаторной оптимизации // Актуальные научные исследования в современном мире. 2020. № 11-2 (67). С. 101–115.
  10. Семенкина О.Е., Семенкин Е.С. О сравнении эффективности муравьиного и генетического алгоритмов при решении задач комбинаторной оптимизации // Актуальные проблемы авиации и космонавтики. 2011. Т. 1. № 7. С. 338–339.
  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. Хахулин Г.Ф. Титов Ю.П. Система поддержки решений поставок запасных частей летательных аппаратов военного назначения // Изв. Самарского научного центра Российской академии наук. 2014. Т. 16. № 1–5. С. 1619–1623.
  13. Судаков В.А., Батьковский А.М., Титов Ю.П. Алгоритмы ускорения работы модификации метода муравьиных колоний для поиска рационального назначения сотрудников на задачи с нечетким временем выполнения // Современные информационные технологии и ИТ-образование. 2020. Т. 16. № 2. C. 338–350; https://doi.org/10.25559/SITITO.16.202002.338-350
  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. Синицын И.Н., Титов Ю.П. Оптимизация порядка следования гиперпараметров вычислительного кластера методом муравьиных колоний // Системы высокой доступности. 2022. Т. 18. № 3. С. 23–37; https://doi.org/10.18127/j20729472-202203-02
  16. Судаков В.А., Титов Ю.П., Сивакова Т.В., Иванова П.М. Применение метода муравьиных колоний для поиска рациональных значений параметров технической системы: Препринт № 38. М.: ИПМ, 2023. С. 1–15; https://doi.org/10.20948/prepr-2023-38
  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. Пантелеев А.В., Алёшина Е.А. Применение непрерывной модификации метода муравьиных колоний к задаче поиска оптимального управления дискретными детерминированными системами // Научный вестник МГТУ ГА. 2013. № 8 (194).
  19. Пантелеев А.В., Пановский В.Н. Применение гибридного меметического алгоритма в задачах оптимального управления нелинейными стохастическими системами с неполной обратной связью // Научный вестник МГТУ ГА. 2018. Т. 21, № 2. С. 59–70; https://doi.org/10.26467/2079-0619-2018-21-2-59-70
  20. Саймон Д. Алгоритмы эволюционной оптимизации / Пер. с англ. А.В. Логунова. М.: ДМК Пресс, 2020. 1002 с.
  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. 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. Карпенко А.П., Чернобривченко К.А. Эффективность оптимизации методом непрерывно взаимодействующей колонии муравьев (CIAC) // Наука и образование: научное издание МГТУ им. Н.Э. Баумана. 2011. № 2; https://doi.org/10.7463/0211.0165551
  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. 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. Карпенко А.П., Чернобривченко К.А. Мультимемеевая модификация гибридного муравьиного алгоритма непрерывной оптимизации HCIAC // Наука и образование: научное издание МГТУ им. Н.Э. Баумана. 2012. № 9; https://doi.org/10.7463/0912.0470529
  27. Синицын И.Н., Титов Ю.П. Исследование возможности получения всех решений методом муравьиных колоний для задачи // Системы высокой доступности. 2023. Т. 20. № 2. С. 55–69; https://doi.org/10.31857/S000523102308010X
  28. Russell S.J., Norvig P. Artificial Intelligence: A Modern Approach: Pearson Series In Artificial Intelligence. Fourth Edition. Hoboken: Pearson, 2021. 1245 с.
  29. Синицын И.Н., Титов Ю.П. Управление наборами значений параметров системы методом муравьиных колоний // АиТ. 2023. № 8. С. 153–168; https://doi.org/10.31857/S000523102308010X
  30. Синицын И.Н., Титов Ю.П. Оптимизация параметрических задач с отрицательным значением целевой функции методом муравьиных колоний // Системы высокой доступности. 2024. Т. 20. № 1. С. 30−37; https://doi.org/10.18127/j20729472-202401-03
  31. Синицын И.Н., Титов Ю.П. Исследование алгоритмов циклического поиска дополнительных решений при оптимизации порядка следования гиперпараметров методом муравьиных колоний // Системы высокой доступности. 2023. Т. 19. № 1. С. 59–73; https://doi.org/10.18127/j20729472-202301-05
  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. Abdesslem L. New Hard Benchmark Functions for Global Optimization. N.Y.: Cornell Tech, 2022; https://doi.org/10.48550/arXiv.2202.04606
  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. Реализация модификаций алгоритма ACO (открытый доступ 23.10.2022). https://github.com/kalengul/ACO_Cluster/tree/master/Rezul

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать
2. Рис 1. Алгоритм модифицированного метода муравьиных колоний (ACOCCyI).

Скачать (475KB)
Метаданные
3. Рис 2. График функции “Carrom table function” (сверху), “Мультифункции” (посередине) и функции “Шеффеля” (снизу).

Скачать (446KB)
Метаданные
4. Рис 3. Оценки статистических параметров при изменении параметров 1, 2, 3 и ограничения на максимальное количество итераций: а, б – оценка математического ожидания количества дополнительных итераций на одного агента, в – оценка математического ожидания номера решения, на которой были найдены оптимальные значения параметров, г – оценка вероятности найти оптимальное решение.

Скачать (411KB)
Метаданные
5. Рис. 4. Оценки статистических критериев эффективности работы алгоритма при изменении значений параметра Q и ограничения на количества итераций: а – оценка математического ожидания номера решения, на которой были найдены оптимальные значения параметров для графа малой размерности (бенчмарк); б – оценка вероятности найти оптимальное решение для графа большой размерности; в – оценка математического ожидания номера решения, на которой были найдены оптимальные значения параметров для графа большой размерности.

Скачать (465KB)
Метаданные
6. Рис. 5. Оценки статистических критериев эффективности работы алгоритма при изменении значений параметра  и ограничения на количества итераций: а – оценка вероятности найти оптимальное решение для графа малой размерности (бенчмарк), б – оценка вероятности найти оптимальное решение для графа большой размерности.

Скачать (241KB)
Метаданные
7. Рис. 6. Оценки статистических критериев эффективности работы алгоритма при изменении количества агентов на итерации K и ограничения на количества итераций: а – оценка вероятности найти оптимальное решение для графа большой размерности, б – оценка математического ожидания количества дополнительных итераций на одного агента для графа большой размерности.

Скачать (222KB)
Метаданные
8. Рис. 7. Оценки статистических критериев эффективности работы алгоритма при изменении степенней , ,  и коэффициентов 1, 2, 3: а – влияние параметров степени , ,  на оценку вероятности найти оптимальное решение для графа большой размерности, б – влияние коэффициентов 1, 2, 3 на оценку вероятности найти оптимальное решение для графа большой размерности.

Скачать (279KB)
Метаданные

© Российская академия наук, 2025