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

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

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

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

Результаты. Предложен подход разделения информации, с которой взаимодействует метод муравьиных колоний, на отдельные слои. В вероятностной формуле производится свертка значений (мультипликативная в оригинальном алгоритме и аддитивная в новой предложенной модификации). Таким образом, легко формализуется задача многокритериальной оптимизации путем добавления новых слоев для параметрического графа. Предложены варианты изменения вероятностной формулы: оптимизация по одному из критериев, результатам линейной свертки критериев, с переключением критерия для каждого агента. За счет применения модификации метода муравьиных колоний ACOCCyI, которая позволяет продолжить поиск рациональных решений после нахождения оптимального значения, при любом из подходов к изменению вероятностной формулы происходит нахождение всех элементов итогового множества Парето менее чем за 35% от всех возможных решений. Модификация с переключением целевой функции для каждого агента быстрее находит все решения из множества Парето, но требует больше времени из-за увеличения количества дополнительных итераций для агентов.

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

Синицын И.Н., Титов Ю.П. Исследование применения метода муравьиных колоний в многокритериальных параметрических задачах // Системы высокой доступности. 2024. Т. 20. № 4. С. 52−63. DOI: https://doi.org/10.18127/ j20729472-202404-06

1. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. 2-е изд. М.: Изд-во МГТУ им. Баумана. 2017. 446 с.
2. Саймон Д. Алгоритмы эволюционной оптимизации: практическое руководство. М.: ДМК Пресс. 2020. 1002 с.
3. 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.
4. Titov Y.P. Modifications of the ant colony method for aviation routing // Automation and Remote Control. 2015. V. 76. № 3. P. 458–471. https://doi.org/10.1134/S0005117915030091
5. Dorigo M., St¨utzle T. Ant Colony Optimization // MIT Press. 2004. P. 321.
6. Pasia J.M., Hartl R.F., Doerner K.F. Solving a Bi-objective Flowshop Scheduling Problem by Pareto-Ant Colony Optimization // ANTS 2006, LNCS 4150. 2006. P. 294–305.
7. Bremer Jörg and Lehnhoff S. Constrained Scheduling of Step-Controlled Buffering Energy Resources with Ant Colony Optimization // ANTS Conference. 2020.
8. Parpinelli R., Lopes H., Freitas A. Data mining with an ant colony optimization algorithm // IEEE Trans. Evol. Comput. 2002. 6(4). P. 321–332.
9. 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.
10. Socha K., Dorigo M. Ant colony optimization for continuous domains // European Journal of Operational Research. 2008. V. 185. Iss. 3. Р. 1155–1173. DOI: 10.1016/j.ejor.2006.06.046
11. Mohamad M., Tokhi M., Omar O.M. Continuous Ant Colony Optimization for Active Vibration Control of Flexible Beam Struc­tures // IEEE International Conference on Mechatronics (ICM). Apr. 2011. P. 803–808.
12. Карпенко А.П., Синицын И.Н. Бионика и системы высокой доступности // Системы высокой доступности. 2022. Т. 18. № 2. С. 25–41. DOI: 10.18127/j20729472-202202-02
13. Судаков В.А., Кильмишкин Н.В., Титов Ю.П. Применение модификации метода муравьиных колоний для классификации авиатранспортных маршрутов // Современные наукоемкие технологии. 2024. С. 63–70. DOI: 10.17513/snt.40065
14. Синицын И.Н., Титов Ю.П. Управление наборами значений параметров системы методом муравьиных колоний // Автоматика и телемеханика. 2023. № 8. С. 153–168. DOI: 10.31857/S000523102308010X
15. Синицын И.Н., Титов Ю.П. Оптимизация параметрических задач с отрицательным значением целевой функции методом муравьиных колоний // Системы высокой доступности. 2024. Т. 20. № 1. С. 30–37. DOI: 10.18127/j20729472-202401-03
16. Mora A.M., García-Sánchez P., Merelo J.J. et al. Pareto-based multi-colony multi-objective ant colony optimization algorithms: an island model proposal. Soft Comput 17. 2013. Р. 1175–1207. https://doi.org/10.1007/s00500-013-0993-y
17. Hou J., Mi W., & Sun J. Optimal spatial allocation of water resources based on Pareto ant colony algorithm. International Journal of Geographical Information Science. 2013. 28(2). 213–233. https://doi.org/10.1080/13658816.2013.849809
18. Ning X. and Wang L.-g. Construction Quality-Cost Trade-Off Using the Pareto-Based Ant Colony Optimization Algorithm. 2009 International Conference on Management and Service Science, Beijing, China. 2009. Р. 1–4. doi: 10.1109/ICMSS.2009.5302127
19. Pratiwi A., Nasution M., & Herawati E. Pareto Frontier Approach to Determining the Optimal Path on Multi-Objectives. Sinkron. Jurnal Dan Penelitian Teknik Informatika. 2023. 7(3). 1379–1388. https://doi.org/10.33395/sinkron.v8i3.12465
20. Титов Ю.П. Модификации метода муравьиных колоний для разработки программного обеспечения решения задач многокритериального управления поставками // Современные информационные технологии и ИТ-образование. 2017. Т. 13. № 2. С. 64–74. DOI: 10.25559/SITITO.2017.2.222
21. Титов Ю.П. Опыт моделирования планирования поставок с применением модификаций метода муравьиных колоний в системах высокой доступности // Системы высокой доступности. 2018. Т. 1. № 1. С. 27–42.