Modification of the asynchronous ant colony method for searching for rational solutions to a parametric problem


Аuthors

Titov Y. 1*, Sudakov V. 2**

1. Moscow Aviation Institute (National Research University), 4, Volokolamskoe shosse, Moscow, А-80, GSP-3, 125993, Russia
2. Keldysh Institute of Applied Mathematics, KIAM, Moscow, Russia

*e-mail: kalengul@mail.ru
**e-mail: sudakov@ws-dss.com

Abstract

The article considers the ant colony method modifications for application in the problems of searching for optimal values of system parameters. The parameters optimality is being determined by the values of the objective function computed as the result of complex computations of a mathematical or simulation model running on a separate computing cluster with the ability for parallel computing of the objective function values. To save the computing cluster resources, the already considered parameter values and the value of the objective function are stored in hash tables. Modifications of the ant colony method are being developed to solve the problem of stagnation, convergence to one rational solution, and allow the method to be applied to find the optimal solution without using the multi-start procedure. This is achieved by modifying the behavior of the agent ant; the ants continue to search for a new set of parameter values that have not yet been considered on the cluster. Thus, each ant agent searches for its own unique route. As the result, the modification of the ant colony method does not converge to one solution, but continues to search for other solutions, avoiding stagnation and ensuring a complete directed search of all solutions (values of system parameters). This modification determines optimal and rational solutions in the early (estimate of mathematical expectation) iterations of the method. The authors proposed an asynchronous modification of the ant colony method for the effective work with a remote multi-threaded computer. Each ant agent searches for its unique set of parameter values in a separate thread and, after finding it, sends a new task to the computing cluster via TCP sockets. The tasks received on the computer are buffered and sent to the dispatcher for uniform and constant loading of the computational threads. of The ant agents blocking associated with the addition and evaporation of pheromone is solved by the blocking-free RCU (read, copy, update) algorithm. A separate thread controls creation of a new graph with an updated pheromone, and all new agent ants will look for paths in the already new graph.

Keywords:

ant colony method, metaheuristic optimization, directed search, parametric problem, computing cluster, algorithms that do not use locks

References

  1. Panteleev A.V., Dmitrakov A.V. Trudy MAI. 2010, no. 37. URL: https://trudymai.ru/eng/published.php?ID=13428
  2. Panteleev A.V., Letova T.A., Pomazueva E.A. Trudy MAI, 2015, no. 79. URL: https://trudymai.ru/eng/published.php?ID=55635
  3. Panteleev A.V., Karane M.S. Trudy MAI, 2021, no. 117. URL: https://trudymai.ru/eng/published.php?ID=156249. DOI: 10.34759/trd-2021-117-10
  4. Panteleev A.V., Aleshina E.A. Trudy MAI, 2010, no. 37. URL: https://trudymai.ru/eng/published.php?ID=13427
  5. Takha Kh. Vvedenie v issledovanie operatsii (Introduction to Operations Research), Moscow, Izdatel'skii dom "Vil'yams", 2005, 912 p.
  6. Khakhulin G.F. Postanovki i metody resheniya zadach diskretnogo programmirovaniya (Statements and methods for solving discrete programming problems), Moscow, Izd-vo MAI, 1992, 59 p.
  7. Papadimitriu Kh., Staiglits K. Kombinatornaya optimizatsiya. Algoritmy i slozhnost' (Combinatorial optimization. Algorithms and complexity), Moscow, Mir, 1985, 512 p.
  8. Khakhulin G.F., Krasovskaya M.A., Bulygin V.S. Teoreticheskie osnovy avtomatizirovannogo upravleniya. Zadachi, metody, algoritmy teorii optimal'nogo planirovaniya i upravleniya. (Theoretical foundations of automated control. Tasks, methods, algorithms of the theory of optimal planning and control), Moscow, Izd-vo MAI, 2005, 396 p.
  9. Karpenko A.P. Sovremennye algoritmy poiskovoi optimizatsii. Algoritmy, vdokhnovlennye prirodoi (Modern search engine optimization algorithms. Algorithms inspired by nature), Moscow, Izd-vo MGTU im. Baumana, 2017, 446 p.
  10. Saimon D. Algoritmy evolyutsionnoi optimizatsii: prakticheskoe rukovodstvo (Evolutionary optimization algorithms: a practical guide), Moscow, DMK Press, 2020, 1002 p.
  11. Yukhimenko B.I., Titov N.A., Ushakov V.O. Aktual'nye nauchnye issledovaniya v sovremennom mire, 2020, no. 11-2 (67), pp. 101-115.
  12. Dorigo M., Stutzle T. Ant Colony Optimization, MIT Press, 2004, 321 p.
  13. Bergstra James S., Rémi Bardenet, Yoshua Bengio, Balázs Kégl. Algorithms for hyper-parameter optimization, In Advances in neural information processing systems, 2011, pp. 2546-2554.
  14. Joseph M. Pasia, Richard F. Hartl, Karl F. Doerner. Solving a Bi-objective Flowshop Scheduling Problem by Pareto-Ant Colony Optimization, Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics, International Workshop, 2006, pp. 294–305. DOI: 10.1007/978-3-540-74446-7_15
  15. Parpinelli R., Lopes H., Freitas A. Data mining with an ant colony optimization algorithm, IEEE Transactions on Evolutionary Computation, 2002, vol. 6 (4), pp. 321–332. DOI: 10.1109/TEVC.2002.802452
  16. Martens D., De Backer M., Haesen R., Vanthienen J., Snoeck M., Baesens B. Classification with ant colony optimization, IEEE Transactions on Evolutionary Computation, 2007, vol. 11 (5), pp 651–665. DOI: 10.1109/TEVC.2006.890229
  17. Mishra Sudhanshu K. Some New Test Functions for Global Optimization and Performance of Repulsive Particle Swarm Method, SSRN Electronic Journal, 2006. DOI: 10.2139/ssrn.926132
  18. Layeb Abdesslem. New hard benchmark functions for global optimization, 2022. DOI: 10.48550/arXiv.2202.04606
  19. Sinitsyn I.N., Titov Y.P. Control of Set of System Parameter Values by the Ant Colony Method, Automation and Remote Control, 2023, vol. 84, pp. 893–903. DOI: 10.1134/S0005117923080106
  20. Sudakov V.A., Titov Yu.P., Sivakova T.V., Ivanova P.M. Preprint IPM, 2023, no. 38, pp. 1-15. DOI: 10.20948/prepr-2023-38
  21. Sinitsyn I.N., Titov Yu.P. Sistemy vysokoi dostupnosti, 2023, vol. 19, no. 1, pp. 59-73. DOI: 10.18127/j20729472-202301-05
  22. Sinitsyn I.N., Titov Yu.P. Sistemy vysokoi dostupnosti, 2023, vol. 20, no. 2, pp. 55-69. DOI: 10.31857/S000523102308010X
  23. Paul E. McKenney. Comparing performance of read-copy update and other locking primitives, Sequent TR-SQNT-98-PEM-1, 1998

Download

mai.ru — informational site MAI

Copyright © 2000-2024 by MAI

 Вход