I.N. Sinitsyn1, Yu.P. Titov2 

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

The problem of parameter optimization, particularly in the context of high-availability technical systems, is critical when analyzing and synthesizing complex systems. Multi-criteria optimization tasks necessitate the identification of all solutions that belong to the Pareto set, which consists of non-dominated alternatives. While the Ant Colony Optimization (ACO) method effectively converges to optimal solutions in single-objective optimization scenarios, it struggles with achieving convergence to a single solution when tasked with computing the Pareto set. This limitation underscores the need for innovative approaches to enhance the ACO method for multi-criteria optimization challenges.

The primary objective of this study is to explore modifications of the ACO algorithm that enable it to address multi-criteria optimization problems and determine all solutions within the Pareto set. We propose and test various modifications of the ACO method that can effectively handle multiple criteria. One significant approach introduced is the separation of the information with which the ACO interacts into distinct layers, allowing for a more structured representation of the multi-criteria optimization problem by incorporating additional layers into the parametric graph.

Our results indicate that by altering the probabilistic formula used in the ACO algorithm–shifting from a multiplicative approach in the original algorithm to an additive one in our proposed modification—we can better formalize multi-criteria optimization tasks. We present different variations of this probabilistic formula, including optimization based on individual criteria, linear combinations of criteria, and switching criteria for each agent. Notably, our modified ACO variant, ACOCCyI, continues to search for rational solutions even after reaching an optimal value, successfully identifying all elements of the final Pareto set in less than 35% of all possible solutions. The modification involving criterion switching for each agent demonstrates a faster convergence to all Pareto solutions, although it requires additional iterations, resulting in increased computational time.

The practical significance of these modifications is underscored by their performance on complex benchmarks, where multi-criteria analysis was evaluated for both bi-criteria and five-criteria problems. The developed algorithms and their modifications have proven effective in solving the Pareto set search problem and finding solutions based on linear combinations of criteria, thus contributing valuable methodologies to the field of multi-criteria optimization in technical systems.

Sinitsyn I.N., Titov Yu.P. Study of the application of the ant colony method in multicriterial parametric problems. Highly Available Systems. 2024. V. 20. № 4. P. 52−63. DOI: https://doi.org/10.18127/j20729472-202404-06 (in Russian)

1. Karpenko A.P. Sovremenny`e algoritmy` poiskovoj optimizacii. Algoritmy`, vdoxnovlenny`e prirodoj. 2-e izd. M.: Izd-vo MGTU im. Baumana. 2017. 446 s.
2. Sajmon D. Algoritmy` e`volyucionnoj optimizacii: prakticheskoe rukovodstvo. M.: DMK Press. 2020. 1002 s.
3. Colorni A., Dorigo M., Maniezzo V. Distributed Optimization by Ant Colonies. Proc. First Eur. Conf. on Artific. Life. Paris, France. F. Va­rela and P. Bourgine (Eds.). Elsevier Publishing. 1992. R. 134–142.
4. Titov Y.P. Modifications of the ant colony method for aviation routing. Automation and Remote Control. 2015. V. 76. № 3. P. 458–471. https://doi.org/10.1134/S0005117915030091.
5. Dorigo M., St¨utzle T.  Ant Colony Optimization. MIT Press. 2004. P. 321.
6. Pasia J.M., Hartl R.F., Doerner K.F. Solving a Bi-objective Flowshop Scheduling Problem by Pareto-Ant Colony Optimization. ANTS 2006, LNCS 4150. 2006. P. 294–305.
7. Bremer Jörg and Lehnhoff S. Constrained Scheduling of Step-Controlled Buffering Energy Resources with Ant Colony Optimization. ANTS Conference. 2020.
8. Parpinelli R., Lopes H., Freitas A. Data mining with an ant colony optimization algorithm. IEEE Trans. Evol. Comput. 2002. 6(4). P. 321–332.
9. 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). R. 651–665.
10. Socha K., Dorigo M. Ant colony optimization for continuous domains. European Journal of Operational Research. 2008. V. 185. Iss. 3. R. 1155–1173. DOI: 10.1016/j.ejor.2006.06.046
11. Mohamad M., Tokhi M., Omar O.M. Continuous Ant Colony Optimization for Active Vibration Control of Flexible Beam Structures. IEEE International Conference on Mechatronics (ICM). Apr. 2011. P. 803–808.
12. Karpenko A.P., Sinicyn I.N. Bionika i sistemy` vy`sokoj dostupnosti. Sistemy` vy`sokoj dostupnosti. 2022. T. 18. № 2. S. 25–41. DOI: 10.18127/j20729472-202202-02
13. Sudakov V.A., Kil`mishkin N.V., Titov Yu.P. Primenenie modifikacii metoda murav`iny`x kolonij dlya klassifikacii aviatransportny`x marshrutov. Sovremenny`e naukoemkie texnologii. 2024. S. 63–70. DOI: 10.17513/snt.40065
14. Sinicyn I.N., Titov Yu.P. Upravlenie naborami znachenij parametrov sistemy` metodom murav`iny`x kolonij. Avtomatika i telemexa­nika. 2023. № 8. S. 153–168. DOI: 10.31857/S000523102308010X
15. Sinicyn I.N., Titov Yu.P. Optimizaciya parametricheskix zadach s otriczatel`ny`m znacheniem celevoj funkcii metodom murav`iny`x kolonij. Sistemy` vy`sokoj dostupnosti. 2024. T. 20. № 1. S. 30–37. DOI: 10.18127/j20729472-202401-03
16. Mora A.M., García-Sánchez P., Merelo J.J. et al. Pareto-based multi-colony multi-objective ant colony optimization algorithms: an island model proposal. Soft Comput 17. 2013. R. 1175–1207. https://doi.org/10.1007/s00500-013-0993-y
17. Hou J., Mi W., & Sun J. Optimal spatial allocation of water resources based on Pareto ant colony algorithm. International Journal of Geographical Information Science. 2013. 28(2). 213–233. https://doi.org/10.1080/13658816.2013.849809
18. Ning X. and Wang L.-g. Construction Quality-Cost Trade-Off Using the Pareto-Based Ant Colony Optimization Algorithm. 2009 International Conference on Management and Service Science, Beijing, China. 2009. R. 1–4. doi: 10.1109/ICMSS.2009.5302127
19. Pratiwi A., Nasution M., & Herawati E. Pareto Frontier Approach to Determining the Optimal Path on Multi-Objectives. Sinkron. Jurnal Dan Penelitian Teknik Informatika. 2023. 7(3). 1379–1388. https://doi.org/10.33395/sinkron.v8i3.12465
20. Titov Yu.P. Modifikacii metoda murav`iny`x kolonij dlya razrabotki programmnogo obespecheniya resheniya zadach mnogokriterial`nogo upravleniya postavkami. Sovremenny`e informacionny`e texnologii i IT-obrazovanie. 2017. T. 13. № 2. S. 64–74. DOI: 10.25559/SITITO.2017.2.222
21. Titov Yu.P. Opy`t modelirovaniya planirovaniya postavok s primeneniem modifikacij metoda murav`iny`x kolonij v sistemax vy`sokoj dostupnosti. Sistemy` vy`sokoj dostupnosti. 2018. T. 1. № 1. S. 27–42.