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

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

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

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

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

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

Синицын И.Н., Титов Ю.П. Оптимизация параметрических задач с отрицательным значением целевой функции методом муравьиных колоний // Системы высокой доступности. 2024. Т. 20. № 1. С. 30−37. DOI: https:// doi.org/10.18127/j20729472-202401-03

1. Dorigo, M., Stutzle, T. Ant Colony Optimization. MIT Press. 2004. P. 321.
2. 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. P. 134–142
3. Pasia J.M., Hartl R.F., Doerner K.F. Solving a Bi-objective Flowshop Scheduling Problem by Pareto-Ant Colony Optimization. Dorigo M. et al. (Eds.). ANTS 2006, LNCS 4150. 2006. P. 294–305.
4. Parpinelli R., Lopes H., Freitas A. Data mining with an ant colony optimization algorithm. IEEE Trans. Evol. Comput. 2002. № 6(4). P. 321–332.
5. 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). P. 651–665.
6. Bergstra J. S., Rémi Bardenet, Bengio Yo., Balázs Kégl. Algorithms for hyper-parameter optimization. In Advances in neural information processing systems 2011. P. 2546–2554.
7. Menéndez H.D., Otero F.E.B., Camacho D. MACOC: A Medoid-Based ACO Clustering Algorithm. ANTS 2014: Swarm Intelligence. 2014. P. 122–133.
8. Jafar O.M., Sivakumar R. Ant-based clustering algorithms: A brief survey. International Journal of Computer Theory and Engineering. 2010. № 2. P. 787–796.
9. Kao Y., Cheng K. An aco-based clustering algorithm. In: Ant Colony Optimization and Swarm Intelligence, Lecture Notes in Computer Science. 2006. V. 4150. P. 340–347. Springer Berlin Heidelberg, http://dx.doi.org/10.1007/11839088_31.
10. Синицын И.Н., Шаламов А.С. Лекции по теории систем интегрированной логистической поддержки. Изд. 2-е. М.: ТОРУС ПРЕСС. 2019. 1072 с.
11. Синицын И.Н., Титов Ю.П. Оптимизация порядка следования гиперпараметров вычислительного кластера методом муравьиных колоний // Системы высокой доступности. 2022. Т. 18. № 3. С. 23–37. DOI 10.18127/j20729472-202203-02.
12. Судаков В.А., Титов Ю.П., Сивакова Т.В., Иванова П.М. Применение метода муравьиных колоний для поиска рациональных значений параметров технической системы. Препринт ИПМ. 2023. № 38. С. 1–15. DOI: 10.20948/prepr-2023-38.
13. Синицын И.Н., Титов Ю.П. Исследование возможности получения всех решений методом муравьиных колоний для задачи // Системы высокой доступности. 2023. Т. 20. № 2. С. 55–69. DOI: 10.31857/S000523102308010X.
14. Синицын И.Н., Титов Ю.П. Управление наборами значений параметров системы методом муравьиных колоний. Автоматика и телемеханика. 2023. № 8. С. 153–168. DOI 10.31857/S000523102308010X.
15. Синицын И.Н., Титов Ю.П. Исследование алгоритмов циклического поиска дополнительных решений при оптимизации порядка следования гиперпараметров методом муравьиных колоний // Системы высокой доступности. 2023. Т. 19. № 1. С. 59–73. DOI: 10.18127/j20729472-202301-05.
16. 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. DOI: 10.2139/ssrn.926132.
17. Layeb Abdesslem. New hard benchmark functions for global optimization. 2022. DOI: 10.48550/arXiv.2202.04606.