sibsutisВестник СибГУТИThe Herald of the Siberian State University of Telecommunications and Information Science1998-6920СибГУТИsibsutis-521Research ArticleСтатьиГенетический алгоритм структурной оптимизации сетей с применением подхода кумулятивного уточнения границ надёжностиGenetic algorithm for network structure optimization using network reliability cumu-lative updatingМиговД. А.MigovD. ..mdinka@rav.sscc.ruНечунаеваК. А.NechunaevaK. ..ksu.nech@gmail.comРодионовА. С.RodionovA. ..alrod@sscc.ruИнститут вычислительной математики и математической геофизики СО РАНRussian FederationСибГУТИRussian Federation201526102022045561Copyright © Мигов Д.А., Нечунаева К.А., Родионов А.С., 20222022Мигов Д.А., Нечунаева К.А., Родионов А.С.Migov D..., Nechunaeva K..., Rodionov A...Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.sibsutis.ru/jour/article/view/521

В статье предлагается новый алгоритм оптимизации структуры сети по критерию надёжности в условиях различных ограничений.Рассматриваются сети с абсолютно надёжными узлами и ненадёжными каналами связи. Под надёжностью сети понимается вероятность связности соответствующего случайного графа, расчёткоторой представляет собой NP-трудную задачу.Разработанный алгоритм оптимизации является генетическим, его операторы позволяют отсеивать непригодные особи на более ранних этапах за счёт использования кумулятивного уточнения верхней и нижней границ надёжности сети. Проведённые эксперименты подтвердили эффективность предлагаемого подхода.

This paper presents a new algorithm for network structure optimization via reliability crite-rion under conditions of various constraints. Networks with unreliable communication channels and perfectly reliable nodes are investigated. We consider network reliability as connection probability. The problem of computing this characteristic is known to be NP-hard. The proposed algorithm for optimization is genetic one. Cumulative updating of network reliability bounds lets the algorithm's operators work faster due to early cutting down bad chromosomes (with worse fitness function value). The numerical experiments show the advantages of the proposed method.

надёжность сетислучайный графоптимизация структуры сетигенетический алгоритмметод факторизациидиаметр сетиnetwork reliabilityrandom graphnetwork structure optimization genetic algorithmfactoring methoddiameter constraintReferencesColbourn Ch. J. The combinatorics of network reliability. N.Y.: Oxford Univ. press, 1987. 160 p.Colbourn Ch. J. The combinatorics of network reliability. N.Y.: Oxford Univ. press, 1987. 160 p.РодионовА. С., РодионоваО. К.Кумулятивныеоценкисреднейвероятностисвязностипарывершинслучайногографа // Проблемыинформатики. 2013. № 19. C. 3-12.РодионовА. С., РодионоваО. К.Кумулятивныеоценкисреднейвероятностисвязностипарывершинслучайногографа // Проблемыинформатики. 2013. № 19. C. 3-12.Canale E., Cancela H., Robledo F., Rubino G., Sartor P. On computing the 2-diameter-constrained k-reliability of networks // International Transactions in Operational Research. 2013. V. 20(1). P. 49-58.Canale E., Cancela H., Robledo F., Rubino G., Sartor P. On computing the 2-diameter-constrained k-reliability of networks // International Transactions in Operational Research. 2013. V. 20(1). P. 49-58.Мигов Д. А. Расчет надежности двухполюсной сети с ограничением на диаметр с использованием сечений // Проблемы информатики. 2011. № 11. C. 4-9.Мигов Д. А. Расчет надежности двухполюсной сети с ограничением на диаметр с использованием сечений // Проблемы информатики. 2011. № 11. C. 4-9.Мигов Д. А., Нестеров С. Н., Родионов А. С. Методы ускорения расчета надежности сетей с ограничением на диаметр // Вестник СибГУТИ. 2014. № 1. C. 49-56.Мигов Д. А., Нестеров С. Н., Родионов А. С. Методы ускорения расчета надежности сетей с ограничением на диаметр // Вестник СибГУТИ. 2014. № 1. C. 49-56.Родионов А. С., Сакерин А. В., Мигов Д. А. Некоторые вопросы реализации полного перебора (на примере задач надёжности сетей) // Вестник СибГУТИ. 2014.№ 4. С. 79-84.Родионов А. С., Сакерин А. В., Мигов Д. А. Некоторые вопросы реализации полного перебора (на примере задач надёжности сетей) // Вестник СибГУТИ. 2014.№ 4. С. 79-84.Shooman A. M., Kershenbaum A. Methods for communication-network reliability analysis: probabilistic graph reduction // Proc. ofReliability and Maintainability Symposium. IEEE, 1992. P.441-448.Shooman A. M., Kershenbaum A. Methods for communication-network reliability analysis: probabilistic graph reduction // Proc. ofReliability and Maintainability Symposium. IEEE, 1992. P.441-448.Соколова Э. С., Капранов С. Н., Балашова Т. И. Поиск полного множества минимальных сечений в сетях передачи данных //Научно-технический вестник Поволжья. 2013. № 6. С. 431-434.Соколова Э. С., Капранов С. Н., Балашова Т. И. Поиск полного множества минимальных сечений в сетях передачи данных //Научно-технический вестник Поволжья. 2013. № 6. С. 431-434.Лотоцкий А. Д. Исследование точных методов вычисления структурной надёжности компьютерных сетей // Инновации на основе информационных и коммуникационных технологий. 2014. № 1. С. 233-235.Лотоцкий А. Д. Исследование точных методов вычисления структурной надёжности компьютерных сетей // Инновации на основе информационных и коммуникационных технологий. 2014. № 1. С. 233-235.Мигов Д. А. Формулы для быстрого расчета вероятности связности подмножества вершин в графах небольшой размерности // Проблемы информатики. 2010. № 6. С.10-17.Мигов Д. А. Формулы для быстрого расчета вероятности связности подмножества вершин в графах небольшой размерности // Проблемы информатики. 2010. № 6. С.10-17.Цициашвили Г. Ш., Осипова М. А., Лосев А. С. Асимптотика вероятности связности графа с низконадёжными ребрами // Прикладная дискретная математика. 2013.№ 1. С. 93-98.Цициашвили Г. Ш., Осипова М. А., Лосев А. С. Асимптотика вероятности связности графа с низконадёжными ребрами // Прикладная дискретная математика. 2013.№ 1. С. 93-98.Цициашвили Г. Ш., Осипова М. А., Лосев А. С. Вывод асимптотических констант для вероятности несвязности планарного взвешенного графа // Прикладная дискретная математика. 2014. № 2. С. 97-100.Цициашвили Г. Ш., Осипова М. А., Лосев А. С. Вывод асимптотических констант для вероятности несвязности планарного взвешенного графа // Прикладная дискретная математика. 2014. № 2. С. 97-100.Won J.-M., Karray F. Cumulative update of all-terminal reliability for faster feasibility decision // IEEE transactions on reliability. 2010. V. 59, № 3.P. 551-562.Won J.-M., Karray F. Cumulative update of all-terminal reliability for faster feasibility decision // IEEE transactions on reliability. 2010. V. 59, № 3.P. 551-562.Rodionov A., Migov D., Rodionova O. Improvements in the efficiency of cumulative updating of all terminal network reliability // IEEE Transactions on Reliability. 2012. V. 61, № 2. P. 460-465.Rodionov A., Migov D., Rodionova O. Improvements in the efficiency of cumulative updating of all terminal network reliability // IEEE Transactions on Reliability. 2012. V. 61, № 2. P. 460-465.Koide T., Shinmori S., Ishii H. Topological optimization with a network reliability constraint //Discrete Applied Mathematics. November 2001. V. 115, issues 1-3. P. 135-149.Koide T., Shinmori S., Ishii H. Topological optimization with a network reliability constraint //Discrete Applied Mathematics. November 2001. V. 115, issues 1-3. P. 135-149.Liu B., Iwamura K.Topological optimization models for communication network with multiple reliability goals //Computers & Mathematics with Applications. April 2000. V. 39, issues 7-8. P. 59-69.Liu B., Iwamura K.Topological optimization models for communication network with multiple reliability goals //Computers & Mathematics with Applications. April 2000. V. 39, issues 7-8. P. 59-69.Балашова Т. И.Обеспечение отказоустойчивости сети повышением надёжности её топлогии // Современные проблемы науки и образования. 2014. № 6. (www.science-education.ru/120-16846)Балашова Т. И.Обеспечение отказоустойчивости сети повышением надёжности её топлогии // Современные проблемы науки и образования. 2014. № 6. (www.science-education.ru/120-16846)Мочалов В. А. Гибридный бионический алгоритм синтеза структуры беспроводной сенсорной сети // T-Comm: Телекоммуникации и транспорт. 2013. Т. 7. № 10. С. 72-77.Мочалов В. А. Гибридный бионический алгоритм синтеза структуры беспроводной сенсорной сети // T-Comm: Телекоммуникации и транспорт. 2013. Т. 7. № 10. С. 72-77.Нечунаева К. А. Оптимальное по показателям связности объединение сетей в условиях структурных и стоимостных ограничений // Проблемы информатики. 2010. № 2. С. 18-26.Нечунаева К. А. Оптимальное по показателям связности объединение сетей в условиях структурных и стоимостных ограничений // Проблемы информатики. 2010. № 2. С. 18-26.Rodionov A., Nechunaeva K. Network structure optimization: genetic operators: mutation and crossover // Proc. of the 7th Int. Conference on Ubiquitous Information Management and Communication (ACM ICUIMC 2013). Kota Kinabalu, Malaysia, 2013. ACM New York, USA. Article No. 52.Rodionov A., Nechunaeva K. Network structure optimization: genetic operators: mutation and crossover // Proc. of the 7th Int. Conference on Ubiquitous Information Management and Communication (ACM ICUIMC 2013). Kota Kinabalu, Malaysia, 2013. ACM New York, USA. Article No. 52.Darwin Ch. On the origin of species by means of natural selection, or the preservation of favoured races in the struggle for life.London: John Murray, 1859. 502 P.Darwin Ch. On the origin of species by means of natural selection, or the preservation of favoured races in the struggle for life.London: John Murray, 1859. 502 P.

The authors declare that there are no conflicts of interest present.