I.N. Sinitsyn1, Yu.P. Titov2

1, 2 FIC «Informatics and Management» RAS (Moscow, Russia)
1,2 Moscow Aviation Institute (National Research University) (Moscow, Russia)
1 sinitsin@dol.ru, 2 kalengul@mail.ru

A modification of the ant colony method is considered, which makes it possible to search for a rational (optimal) solution to a parametric problem with the possibility of obtaining a negative value of the objective function. The objective function in the original algorithm that calculates the traveling salesman's path is determined by the total length of the path and cannot be negative. But when solving parametric problems of optimization of difference values for high availability systems, negative values of the objective function may arise. Such values lead to a negative value of the weights (pheromone), which leads to incorrect operation of the probabilistic arc/vertex selection formula. A formula has been derived for recalculating the positive shift of the objective function and pheromone to obtain a positive value of the pheromone, which is used when the sum of the value of the objective function and the shift is negative. The approaches are compared: initial shift, single shift, calculation of the module of the objective function, and a gradual iterative shift algorithm is proposed. The proposed approach allows us to equate the minimum value of the objective function to 0 and mathematically recalculate the weights (pheromone) for the parametric problem taking into account the resulting shift. By applying relative values of the weights, such a shift does not affect the probability distribution, but takes into account new values for previous calculations of the objective function. The studies were carried out on various benchmarks with optimal values in the negative region. Statistically, the proposed algorithm is not inferior in performance to shift and modular algorithms for converting the value of the objective function to the positive semi-axis.

Sinitsyn I.N., Titov Yu.P. Optimization of parametric problems with a negative value of the objective function using the ant colony method. Highly Available Systems. 2024. V. 20. № 1. P. 30−37. DOI: https://doi.org/ 10.18127/j20729472-202401-03 (in Russian)

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. Sinicyn I.N., Shalamov A.S. Lekcii po teorii sistem integrirovannoj logisticheskoj podderzhki. Izd. 2-e. M.: TORUS PRESS. 2019. 1072 s. (in Russian).
11. Sinicyn I.N., Titov Yu.P. Optimizaciya poryadka sledovaniya giperparametrov vychislitel'nogo klastera metodom murav'inyh kolonij. Sistemy vysokoj dostupnosti. 2022. T. 18. № 3. S. 23–37. DOI 10.18127/j20729472-202203-02 (in Russian).
12. Sudakov V.A., Titov Yu.P., Sivakova T.V., Ivanova P.M. Primenenie metoda murav'inyh kolonij dlya poiska racional'nyh znachenij parametrov tekhnicheskoj sistemy. Preprint IPM. 2023. № 38. S. 1–15. DOI: 10.20948/prepr-2023-38 (in Russian).
13. Sinicyn I.N., Titov Yu.P. Issledovanie vozmozhnosti polucheniya vsekh reshenij metodom murav'inyh kolonij dlya zadachi. Sistemy vysokoj dostupnosti. 2023. T. 20. № 2. S. 55–69. DOI: 10.31857/S000523102308010X (in Russian).
14. Sinicyn I.N., Titov Yu.P. Upravlenie naborami znachenij parametrov sistemy metodom murav'inyh kolonij. Avtomatika i telemekhanika. 2023. № 8. S. 153–168. DOI 10.31857/S000523102308010X (in Russian).
15. Sinicyn I.N., Titov Yu.P. Issledovanie algoritmov ciklicheskogo poiska dopolnitel'nyh reshenij pri optimizacii poryadka sledovaniya giperparametrov metodom murav'inyh kolonij. Sistemy vysokoj dostupnosti. 2023. T. 19. № 1. S. 59–73. DOI: 10.18127/j20729472-202301-05 (in Russian).
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.