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

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

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