Modifications of the ant colonies method for solving a discrete-valued parametric problem

Мұқаба

Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Тек жазылушылар үшін

Аннотация

The problem of finding rational solutions to a multi-extremal parametric problem using the ant colony method is considered. Rational solutions are solutions that are close to the optimal one in terms of the value of the objective function, but are not necessarily such. To solve for a multi-extreme problem, a modification of the ant colony method is proposed, which does not converge to a single solution, but continues to search for a solution. The ant colony method underlying the modification allows one to consider all rational solutions at the earliest iterations. The lack of convergence to a single solution solves the problem of stagnation of the proposed algorithm of the ant colony method. The solutions considered are stored in a hash table, which allows avoiding recalculation of the value of the objective function for a given solution on the computer and searching for a new solution for each agent. A new formula for determining the probability of the ant’s (agent’s) transition to a new parameter. The purpose of this formula is to solve the problem of algorithm stagnation in early iterations by increasing the probability of the agent visiting components of solutions that have not yet been considered. The algorithm of this modification of the ant colony method allows solving discrete parametric problems, determining rational values of parameters from discrete set. The paper investigates the dependence of the efficiency of the method on the parameters of the proposed modification of the ant colony method. The study on test problems and large-scale problems showed the dependence on the parameters of the additive convolution and the evaporation coefficient, which is responsible for reducing the weights obtained in previous iterations.

Толық мәтін

Рұқсат жабық

Авторлар туралы

E. Davydkina

MAI (national research university)

Хат алмасуға жауапты Автор.
Email: davydkinaelena@yandex.ru
Ресей, Moscow

V. Nesterov

MAI (national research university)

Email: nesterov46@inbox.ru
Ресей, Moscow

V. Sudakov

MAI (national research university); Keldysh Institute of Applied Mathematics of RAS

Email: sudakov@ws-dss.com
Ресей, Moscow; Moscow

K. Sypalo

Central Central Aerohydrodynamic Institute

Email: ksypalo@tsagi.ru
Ресей, Zhukovsky

Yu. Titov

MAI (national research university)

Email: kalengul@mail.ru
Ресей, Moscow

Әдебиет тізімі

  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. Fig. 1. Algorithm of the modified ant colony method (ACOCCyI).

Жүктеу (475KB)
Метадеректер
3. Fig. 2. Graph of the “Carrom table function” (top), “Multifunction” (middle) and “Scheffel” function (bottom).

Жүктеу (446KB)
Метадеректер
4. Fig. 3. Estimates of statistical parameters when changing parameters 1, 2, 3 and restrictions on the maximum number of iterations: a, b – estimate of the mathematical expectation of the number of additional iterations per agent, c – estimate of the mathematical expectation of the solution number on which the optimal values ​​of the parameters were found, d – estimate of the probability of finding the optimal solution.

Жүктеу (411KB)
Метадеректер
5. Fig. 4. Estimates of statistical criteria of the algorithm’s efficiency when changing the values ​​of the Q parameter and the limit on the number of iterations: a – estimate of the mathematical expectation of the solution number, on which the optimal values ​​of the parameters for a low-dimensional graph were found (benchmark); b – estimate of the probability of finding the optimal solution for a high-dimensional graph; c – estimate of the mathematical expectation of the solution number, on which the optimal values ​​of the parameters for a high-dimensional graph were found.

Жүктеу (465KB)
Метадеректер
6. Fig. 5. Estimates of statistical criteria for the efficiency of the algorithm when changing the values ​​of the parameter  and the limit on the number of iterations: a – estimate of the probability of finding the optimal solution for a low-dimensional graph (benchmark), b – estimate of the probability of finding the optimal solution for a high-dimensional graph.

Жүктеу (241KB)
Метадеректер
7. Fig. 6. Estimates of statistical criteria for the efficiency of the algorithm when changing the number of agents at iteration K and the limit on the number of iterations: a – estimate of the probability of finding an optimal solution for a large-scale graph, b – estimate of the mathematical expectation of the number of additional iterations per agent for a large-scale graph.

Жүктеу (222KB)
Метадеректер
8. Fig. 7. Estimates of statistical criteria for the efficiency of the algorithm when changing the degrees , ,  and the coefficients 1, 2, 3: a – the influence of the degree parameters , ,  on the estimate of the probability of finding an optimal solution for a large-dimensional graph, b – the influence of the coefficients 1, 2, 3 on the estimate of the probability of finding an optimal solution for a large-dimensional graph.

Жүктеу (279KB)
Метадеректер

© Russian Academy of Sciences, 2025

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».