Development of Large Communication Networks
Optimization Problems and Heuristics
Abstract
This paper summarizes and continues the previous papers of the authors. We consider some models of optimization problems that arise when building large communication networks. The topology of the communication network is formalized by an undirected graph. The coordinates of the vertices of an undirected graph (nodes of the communication network) are usually set in advance in some way, and a set of edges must be constructed for this set of vertices. The main (and sometimes the only) goal, both of our previous articles and of this article, can be formulated as follows: for some special additional requirements, it is necessary to construct a set of edges of the graph that satisfies these requirements; these edges should have the minimum possible total length. Another important idea is to modify the standard algorithms for working with graphs in order to be able to consider dynamic models (when the input data changes slightly), and it should be possible to use the results of previous calculations when changing the input data.
From the point of view of graph theory, all these problems have long been solved, but in practice, the implementation of the corresponding algorithms is fraught with great difficulties: first, in real conditions, we consider graphs consisting of several thousand vertices; second, as we have already noted, the construction of large communication networks usually involves a dynamic change in requirements. The consequence of the two circumstances given is that often even algorithms of quadratic complexity often cannot be applied.
For each of our models of optimization problems, we present one or more possible algorithms (primarily heuristic ones) designed to solve it. Our proposed algorithms are usually iterative, and this fact fits well into the capabilities needed to build algorithms that work with dynamically changing data.
References
2.Melnikov B.F., Meshchanin V.Y., Terentyeva Y.Y. Implementation of optimality criteria in the design of communication networks. Journal of Physics: Conference Series. Engineering and Innovative Technologies. 2020; 1515:042093. (In Eng.) DOI: https://doi.org/10.1088/1742-6596/1515/4/042093
3.Bulynin A.G., Melnikov B.F., Meshchanin, V.Y., Terentyeva. Y.Y. Optimization problem, arising in the development of high-dimensional communication networks, and some heuristic methods for solving them. Informatization and Communication. 2020; (1):34-40.(In Russ., abstract in Eng.) DOI: https://doi.org/10.34219/2078-8320-2020-11-1-34-40
4.Bulynin A.G., Melnikov B.F., Meshchanin, V.Y. and Terentyeva. Y.Y. Algorithms for designing communication networks using greedy heuristics of different types.Proceedings of the International Conference on Information Technology and Nanotechnology (ITNT-2020). Samara University, Samara; 2020. p. 856-860. Available at: https://www.elibrary.ru/item.asp?id=43576630 (accessed 05.02.2021). (In Russ., abstract in Eng.)
5.Melnikov B.F., Terentyeva. Y.Y. Building communication networks: on the application of the Kruskal’s algorithm in the problems of large dimensions. International Journal of Open Information Technologies. 2021; 9(1):13-21. Available at: https://www.elibrary.ru/item.asp?id=44584129 (accessed 05.02.2021). (In Russ., abstract in Eng.)
6.Melnikov B.F., Terentyeva. Y.Y. Construction of an optimal spanning tree as a tool to ensure the stability of the communication network. University proceedings. Volga region. Technical sciences. 2021; (1):36-45. (In Russ., abstract in Eng.) DOI: https://doi.org/10.21685/2072-3059-2021-1-4
7.Terentyeva Y.Y. Some theoretical issues related to the description of practical algorithms for constructing spanning trees. International Journal of Open Information Technologies. 2021; 9(3):23-27. Available at: https://www.elibrary.ru/item.asp?id=44853580 (accessed 05.02.2021). (In Russ., abstract in Eng.)
8.Cormen T., Leiserson C., Rivest R., Stein C. Introduction to Algorithms. The MIT Press; 2009. (In Eng.)
9.Lipsky V. Kombinatorika dlia programmistov [Combinatorics for programmers]. Mir, Moscow; 1979. (In Russ.)
10.Wirth N. Algorithms and Data Structures. Oberon version. Prentice-Hall; 2004. (In Eng.)
11.Dorigo M. Ottimizzazione, apprendimento automatico, ed algoritmi basati su metafora naturale [Optimization, Learning, and Natural Algorithms]: Doctoral dissertation in Systems and Information Electronic Engineering. Politecnico di Milano, 1992. (In Italian)
12.Colorni A., Dorigo M., Maniezzo V. Distributed Optimization by Ant Colonies. In: F. Varela, P. Bourgine (Eds.) Proceedings of the European Conference on Artificial Life (ECAL’91). Paris, France, Elsevier Publishing; 1991. p. 134-142. (In Eng.)
13.Dorigo M., Maniezzo V., Colorni A. Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). 1996; 26(1):29-41. (In Eng.) DOI: https://doi.org/10.1109/3477.484436
14.Gambardella L.M., Dorigo M. Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem.Machine Learning Proceedings. Morgan Kaufmann; 1995. p. 252-260. (In Eng.) DOI: https://doi.org/10.1016/B978-1-55860-377-6.50039-6
15.Dorigo M., Gambardella L.M. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation. 1997; 1(1):53-66. (In Eng.) DOI: https://doi.org/10.1109/4235.585892
16.Stützle T., Hoos H. MAX-MIN Ant System and local search for the traveling salesman problem. Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC '97). Indianapolis, IN, USA; 1997. p. 309-314. (In Eng.) DOI: https://doi.org/10.1109/ICEC.1997.592327
17.Coltorti D., Rizzoli A.E. Ant Colony Optimization for Real-World Vehicle Routing Problems. SIGEVOlution. 2007; 2(2):2-9. (In Eng.) DOI: https://doi.org/10.1145/1329465.1329466
18.Stützle T. et al. Parameter Adaptation in Ant Colony Optimization. In: Y. Hamadi, E. Monfroy, F. Saubion (Eds.) Autonomous Search. Springer, Berlin, Heidelberg; 2011. p. 191-215. (In Eng.) DOI: https://doi.org/10.1007/978-3-642-21434-9_8
19.Melnikov B.F. Mul'tijevristicheskij podhod k zadacham diskretnoj optimizacii [A multi-heuristic approach to discrete optimization problems]. Cybernetics and System Analysis. 2006; (3):32-43. (In Russ.)
20.Amir C., Badr A., Farag I. A fuzzy logic controller for ant algorithms. Computing and Information Systems. 2007; 11(2):26-34. Available at: https://scholar.cu.edu.eg/?q=c-ahmed/files/antcolonies.pdf (accessed 05.02.2021). (In Eng.)
21.Cai Z., Huang H., Qin Y., Ma X. Ant colony optimization based on adaptive volatility rate of pheromone trail. International Journal of Communications, Network and System Sciences. 2009; 2(8):792-796. (In Eng.) DOI: https://doi.org/10.4236/ijcns.2009.28092
22.Li Y., Li W. Adaptive ant colony optimization algorithm based on information entropy: Foundation and application. Fundamenta Informaticae. 2007; 77(3):229-242. (In Eng.)
23.Merkle D., Middendorf M., Schmeck H. Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation. 2002; 6(4):333-346. (In Eng.) DOI: https://doi.org/10.1109/TEVC.2002.802450
24.Tavares Neto R.F., Godinho Filho M. Literature review regarding Ant Colony Optimization applied to scheduling problems: Guidelines for implementation and directions for future research. Engineering Applications of Artificial Intelligence. 2013; 26(1):150-161. (In Eng.) DOI: http://dx.doi.org/10.1016/j.engappai.2012.03.011
25.Haupt R.L., Haupt S.E. Practical Genetic Algorithms. 2nd ed. John Wiley & Sons, Inc.; 2004. (In Eng.)
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
