И.Н. Синицын1, Ю.П. Титов2

1,2 ФИЦ «Информатика и управление» РАН (Москва, Россия)
1,2 Московский авиационный институт (Москва, Россия)
 

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

Цель. Рассмотреть различные подходы к обработке агентов, нашедших уже рассмотренное решение, для метода муравьиных колоний, примененного для задачи направленного перебора гиперпараметров.

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

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

Синицын И.Н., Титов Ю.П. Исследование алгоритмов циклического поиска дополнительных решений при оптимизации порядка следования гиперпараметров методом муравьиных колоний // Системы высокой доступности. 2023. Т. 19. № 1. С. 59–73. DOI: https://doi.org/ 10.18127/j20729472-202301-05

1. Colorni A., Dorigo M., Maniezzo V. Distributed Optimization by Ant Colonies // Proc. First Eur. Conf. on Artific. Life, Paris, France, F.Varela and P.Bourgine (Eds.), Elsevier Publishing. 1992. Р. 134–142.
2. Dorigo M., St¨ utzle, T. Ant Colony Optimization // MIT Press. 2004. p. 321.
3. Joseph M. Pasia, Richard F. Hartl, Karl F. Doerner. Solving a Bi-objective Flowshop Scheduling Problem by Pareto-Ant Colony Optimization  M. Dorigo et al. (Eds.) // ANTS 2006, LNCS 4150. 2006. Р. 294–305.
4. Torry Tufteland(B), Guro Ødesneltvedt(B), and Morten Goodwin Optimizing PolyACO Training with GPU-Based Parallelization M. Dorigo et al. (Eds.) // ANTS 2016, LNCS 9882. 2016. Р. 233–240. DOI: 10.1007/978-3-319-44427-7 20
5. Parpinelli R., Lopes H., Freitas A. Data mining with an ant colony optimization algorithm // IEEE Trans. Evol. Comput. 2002. 6(4). Р. 321–332.
6. Bremer Jörg and Sebastian Lehnhoff. Constrained Scheduling of Step-Controlled Buffering Energy Resources with Ant Colony Optimization // ANTS Conference. 2020.
7. A. Coates and A.Y. Ng. The importance of encoding versus training with sparse coding and vector quantization // ICML'11: Proceedings of the 28th International Conference on International Conference on Machine LearningJune 2011. P. 921–928.
8. Feurer M., Hutter F. Hyperparameter Optimization. In: Hutter, F., Kotthoff, L., Vanschoren, J. (eds) Automated Machine Learning // The Springer Series on Challenges in Machine Learning. Springer, Cham. 2019. https://doi.org/10.1007/978-3-030-05318-5_1
9. Koehrsen Will. A conceptual explanation of bayesian hyperparameter optimization for machine learning. 2018 (Открытый доступ 23.12.2022: https://towardsdatascience.com/a-conceptual-explanation-of-bayesian-model-based-hyperparameter-optimization-for-machine-learning-b8172278050f)
10. Bergstra James S., Rémi Bardenet, Yoshua Bengio and Balázs Kégl. Algorithms for hyper-parameter optimization // In Advances in neural information processing systems. 2011. Р. 2546–2554.
11. Akiba, Takuya, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-generation hyperparameter optimization framework // In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019. Р. 2623–2631. https://doi.org/10.48550/arXiv.1907.10902
12. https://krasserm.github.io/2018/03/21/bayesian-optimization (Открытый доступ 23.12.2022)
13. https://krasserm.github.io/2018/03/19/gaussian-processes (Открытый доступ 23.12.2022)
14. https://towardsdatascience.com/a-conceptual-explanation-of-bayesian-model-based-hyperparameter-optimization-for-machine-learning-b8172278050f (Открытый доступ 23.12.2022)
15. Ian Dewancker, Michael McCourt, Scott Clark Bayesian Optimization Primer (Открытый доступ 23.12.2022: https://static.sigopt.com/b/20a144d208ef255d3b981ce419667ec25d8412e2/static/pdf/SigOpt_Bayesian_Optimization_Primer.pdf)
16. IBM Bayesian Optimization Accelerator 1.1 helps identify optimal product designs faster with breakthrough performance for scientific discovery and high-performance computing simulation (Открытый доступ 23.12.2022: https://www.ibm.com/ common/ssi/ShowDoc.wss?docURL=/common/ssi/rep_ca/6/877/ENUSZP20-0186/index.html&request_locale=en)
17. Martens D., De Backer M., Haesen R., Vanthienen J., Snoeck M., Baesens B. Classification with ant colony optimization // IEEE Trans. Evol. Comput. 2007. 11(5). Р. 651–665.
18. Синицын И.Н., Титов Ю.П. Оптимизация порядка следования гиперпараметров вычислительного кластера методом муравьиных колоний // Системы высокой доступности. 2022. Т. 18. № 3. С. 23–37. DOI 10.18127/j20729472-202203-02
19. Карпенко А.П., Синицын И.Н. Бионика и системы высокой доступности // Системы высокой доступности. 2022. Т. 18. № 2. С. 25−41. DOI: https://doi.org/ 10.18127/j20729472-202202-02
20. Синицын И.Н., Титов Ю.П. Развитие стохастических алгоритмов муравьиной организации // Бионика – 60 лет. Итоги и перспективы // Сб. статей Первой Междунар. научно-практ. конф. 17–19 декабря 2021 г., Москва / Под ред. А.П. Карпенко. М.: Ассоциация технических университетов. 2022. С. 210–220. DOI: 10.53677/9785919160496_210_220
21. Хахулин Г.Ф. Титов, Ю.П. Система поддержки решений поставок запасных частей летательных аппаратов военного назначения // Известия Самарского научного центра Российской академии наук. 2014. Т. 16. № 1-5. С. 1619–1623.
22. Титов Ю.П. Модификации метода муравьиных колоний для разработки программного обеспечения решения задач многокритериального управления поставками // Современные информационные технологии и ИТ-образование. 2017. Т. 13. № 2. С. 64–74. DOI 10.25559/SITITO.2017.2.222
23. Судаков В.А., Батьковский А.М., Титов Ю.П. Алгоритмы ускорения работы модификации метода муравьиных колоний для поиска рационального назначения сотрудников на задачи с нечетким временем выполнения // Современные информационные технологии и ИТ-образование. 2020. Т. 16. № 2. С. 338–350. doi: 10.25559/SITITO.16.202002.338-350
24. Синицын И.Н., Титов Ю.П. Инструментальное программное обеспечение анализа и синтеза стохастических систем высокой доступности (XV) // Системы высокой доступности. 2021. Т. 17. № 4. С. 24–33. DOI 10.18127/j20729472-202104-02. – EDN YEGVMR.