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


Авторы

Титов Ю. П.1*, Судаков В. А.2**

1. Московский авиационный институт (национальный исследовательский университет), Волоколамское шоссе, 4, Москва, A-80, ГСП-3, 125993, Россия
2. Институт прикладной математики имени М.В. Келдыша РАН, Москва, Россия

*e-mail: kalengul@mail.ru
**e-mail: sudakov@ws-dss.com

Аннотация

Рассматриваются модификации бионической оптимизации методом муравьиных колоний для решения параметрических задач, в частности определения рационального расположения блоков на космическом корабле. Предложены модификации метода, позволяющие производить направленный перебор параметров с целью поиска всех рациональных решений без применения мультистарта. Полный направленный перебор гарантирует нахождение всех оптимальных и рациональных решений, а применение переупорядочивания рассматриваемых решений с помощью модификации метода муравьиных колоний позволяет рассмотреть лучшие решения на ранних этапах. Для практической реализации на кластерной системе в работе рассматриваются асинхронные методы муравьиных колоний, позволяющие обеспечить параллельное рассмотрение решений на многопоточном кластере. Предложена структура программного обеспечения, позволяющая избежать блокировок кластера, тем самым увеличить эффективность использования процессорного времени.

Ключевые слова:

метод муравьиных колоний, метаэвристическая оптимизация, направленный перебор, параметрическая задача, вычислительный кластер, алгоритмы, не использующие блокировки

Библиографический список

  1. Пантелеев А.В., Дмитраков А.В. Применение метода дифференциальной эволюции для оптимизации параметров аэрокосмических систем // Труды МАИ. 2010. № 37. URL: https://trudymai.ru/published.php?ID=13428
  2. Пантелеев А.В., Летова Т.А., Помазуева Е.А. Применение методов глобальной оптимизации для параметрического синтеза обобщенного пропорционально-интегрально-дифференциального регулятора в задаче управления полетом // Труды МАИ. 2015. № 79. URL: https://trudymai.ru/published.php?ID=55635
  3. Пантелеев А.В., Каранэ М.С. Применение гибридного мультиагентного метода интерполяционного поиска в задаче о стабилизации спутника // Труды МАИ. 2021. № 117. URL: https://trudymai.ru/published.php?ID=156249. DOI: 10.34759/trd-2021-117-10. 
  4. Пантелеев А.В., Алешина Е.А. Применение метода частиц в стае к задаче поиска оптимального управления дискретными детерминированными системами // Труды МАИ. 2010. № 37. URL: https://trudymai.ru/published.php?ID=13427
  5. Таха Х. Введение в исследование операций. - М.: Издательский дом "Вильямс", 2005. – 912 с.
  6. Хахулин Г.Ф. Постановки и методы решения задач дискретного программирования. - М.: Изд-во МАИ, 1992 – 59 с.
  7. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985. – 512 с.
  8. Хахулин Г.Ф., Красовская М.А., Булыгин В.С. Теоретические основы автоматизированного управления (Задачи, методы, алгоритмы теории оптимального планирования и управления). - М.: Изд-во МАИ, 2005. – 396 с.
  9. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. - М.: Изд-во МГТУ им. Баумана, 2017. - 446 с.
  10. Саймон Д. Алгоритмы эволюционной оптимизации: практическое руководство. - М.: ДМК Пресс, 2020. - 1002 с.
  11. Юхименко Б.И., Титов Н.А., Ушаков В.О. Разработка и исследование алгоритмов муравьиной колонии для решения некоторых задач комбинаторной оптимизации // Актуальные научные исследования в современном мире. 2020. № 11-2 (67). С. 101-115.
  12. Dorigo M., Stutzle T. Ant Colony Optimization, MIT Press, 2004, 321 р.
  13. Bergstra James S., Rémi Bardenet, Yoshua Bengio, Balázs Kégl. Algorithms for hyper-parameter optimization // In Advances in neural information processing systems, 2011, pp. 2546-2554.
  14. Joseph M. Pasia, Richard F. Hartl, Karl F. Doerner. Solving a Bi-objective Flowshop Scheduling Problem by Pareto-Ant Colony Optimization // Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics, International Workshop, 2006, pp. 294–305. DOI: 10.1007/978-3-540-74446-7_15
  15. Parpinelli R., Lopes H., Freitas A. Data mining with an ant colony optimization algorithm // IEEE Transactions on Evolutionary Computation, 2002, vol. 6 (4), pp. 321–332. DOI: 10.1109/TEVC.2002.802452
  16. Martens D., De Backer M., Haesen R., Vanthienen J., Snoeck M., Baesens B. Classification with ant colony optimization // IEEE Transactions on Evolutionary Computation, 2007, vol. 11 (5), pp 651–665. DOI: 10.1109/TEVC.2006.890229
  17. Mishra Sudhanshu K. Some New Test Functions for Global Optimization and Performance of Repulsive Particle Swarm Method // SSRN Electronic Journal, 2006. DOI: 10.2139/ssrn.926132
  18. Layeb Abdesslem. New hard benchmark functions for global optimization, 2022. DOI: 10.48550/arXiv.2202.04606
  19. Sinitsyn I.N., Titov Y.P. Control of Set of System Parameter Values by the Ant Colony Method // Automation and Remote Control, 2023, vol. 84, pp. 893–903. DOI: 10.1134/S0005117923080106
  20. Судаков В.А., Титов Ю.П., Сивакова Т.В., Иванова П.М. Применение метода муравьиных колоний для поиска рациональных значений параметров технической системы // Препринт ИПМ. 2023. № 38. C. 1-15. DOI: 10.20948/prepr-2023-38
  21. Синицын И.Н., Титов Ю.П. Исследование алгоритмов циклического поиска дополнительных решений при оптимизации порядка следования гиперпараметров методом муравьиных колоний // Системы высокой доступности. 2023. Т. 19. № 1. С. 59-73. DOI: 10.18127/j20729472-202301-05
  22. Синицын И.Н., Титов Ю.П. Исследование возможности получения всех решений методом муравьиных колоний для задачи оптимизации порядка следования гиперпараметров // Системы высокой доступности. 2023. Т. 20. № 2. С. 55-69. DOI: 10.31857/S000523102308010X
  23. Paul E. McKenney. Comparing performance of read-copy update and other locking primitives // Sequent TR-SQNT-98-PEM-1, 1998.


Скачать статью

mai.ru — информационный портал Московского авиационного института

© МАИ, 2000—2024

 Вход