Разработка больших сетей связи

оптимизационные проблемы и эвристики

Аннотация

Настоящая статья обобщает и продолжает предыдущие статьи авторов. Мы рассматриваем несколько моделей оптимизационных задач, возникающих при построении больших сетей связи. Топология сети связи формализуется неориентированным графом. Координаты вершин неориентированного графа (узлы сети связи), как правило, каким-то способом заданы заранее, и для этого множества вершин должно быть построено множество рёбер. Основную (и иногда единственную) цель – как наших предыдущих статей, так и настоящей статьи – можно сформулировать следующим образом: для некоторых специальных дополнительных требований нужно построить удовлетворяющее этим требованиям множество рёбер графа, имеющее минимальную суммарную длину. Другой важной идеей является модификация стандартных алгоритмов работы с графами – для того, чтобы иметь возможность рассматривать динамические модели (когда входные данные немного изменяются), причём должна быть возможность при изменении входных данных использовать результаты предыдущих вычислений.
С точки зрения теории графов все эти задачи давно решены – однако на практике реализация соответствующих алгоритмов сопряжена с большими трудностями: во-первых, в реальных условиях мы рассматриваем графы, состоящие из нескольких тысяч вершин и ребер; во-вторых, как мы уже отметили, построение больших сетей связи обычно включает в себя динамическое изменение требований. Следствием двух приведённых обстоятельств является то, что часто даже алгоритмы квадратичной сложности часто не могут быть применены.
Для каждой из наших моделей оптимизационных задач мы приводим один или несколько возможных алгоритмов (в первую очередь эвристических), предназначенных для её решения. Предлагаемые нами алгоритмы, как правило, итерационные – и этот факт хорошо вписывается в возможности, необходимые для построения алгоритмов, работающих с динамически изменяющимися данными.

Сведения об авторах

Boris Feliksovich Melnikov, Совместный Университет МГУ-ППИ в Шэньчжэне

профессор факультета вычислительной математики и кибернетики, доктор физико-математических наук

Yulia Yuryevna Terentyeva, Центр информационных технологий и систем органов исполнительной власти

начальник управления анализа и методологии совершенствования информационных телекоммуникационных систем, кандидат технических наук

Литература

1.Dutta B., Jackson M. The stability and efficiency of directed communication networks. Review of Economic Design. 2000; 5(3):251-272. (In Eng.) DOI: https://doi.org/10.1007/PL00013688
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.)
Опубликована
2021-04-15
Как цитировать
MELNIKOV, Boris Feliksovich; TERENTYEVA, Yulia Yuryevna. Разработка больших сетей связи. Международный научный журнал «Современные информационные технологии и ИТ-образование», [S.l.], v. 17, n. 1, p. 69-79, apr. 2021. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/727>. Дата доступа: 12 aug. 2022 doi: https://doi.org/10.25559/SITITO.17.202101.727.
Раздел
Прикладные проблемы оптимизации