Genetic algorithm for network structure optimization using network reliability cumu-lative updating
Abstract
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.
About the Authors
D. .. Migov
Институт вычислительной математики и математической геофизики СО РАН
Russian Federation
Russian Federation
K. .. Nechunaeva
Институт вычислительной математики и математической геофизики СО РАН
Russian Federation
Russian Federation
A. .. Rodionov
СибГУТИ
Russian Federation
Russian Federation
References
1. Colbourn Ch. J. The combinatorics of network reliability. N.Y.: Oxford Univ. press, 1987. 160 p.
2. РодионовА. С., РодионоваО. К.Кумулятивныеоценкисреднейвероятностисвязностипарывершинслучайногографа // Проблемыинформатики. 2013. № 19. C. 3-12.
3. 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.
4. Мигов Д. А. Расчет надежности двухполюсной сети с ограничением на диаметр с использованием сечений // Проблемы информатики. 2011. № 11. C. 4-9.
5. Мигов Д. А., Нестеров С. Н., Родионов А. С. Методы ускорения расчета надежности сетей с ограничением на диаметр // Вестник СибГУТИ. 2014. № 1. C. 49-56.
6. Родионов А. С., Сакерин А. В., Мигов Д. А. Некоторые вопросы реализации полного перебора (на примере задач надёжности сетей) // Вестник СибГУТИ. 2014.№ 4. С. 79-84.
7. Shooman A. M., Kershenbaum A. Methods for communication-network reliability analysis: probabilistic graph reduction // Proc. ofReliability and Maintainability Symposium. IEEE, 1992. P.441-448.
8. Соколова Э. С., Капранов С. Н., Балашова Т. И. Поиск полного множества минимальных сечений в сетях передачи данных //Научно-технический вестник Поволжья. 2013. № 6. С. 431-434.
9. Лотоцкий А. Д. Исследование точных методов вычисления структурной надёжности компьютерных сетей // Инновации на основе информационных и коммуникационных технологий. 2014. № 1. С. 233-235.
10. Мигов Д. А. Формулы для быстрого расчета вероятности связности подмножества вершин в графах небольшой размерности // Проблемы информатики. 2010. № 6. С.10-17.
11. Цициашвили Г. Ш., Осипова М. А., Лосев А. С. Асимптотика вероятности связности графа с низконадёжными ребрами // Прикладная дискретная математика. 2013.№ 1. С. 93-98.
12. Цициашвили Г. Ш., Осипова М. А., Лосев А. С. Вывод асимптотических констант для вероятности несвязности планарного взвешенного графа // Прикладная дискретная математика. 2014. № 2. С. 97-100.
13. 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.
14. 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.
15. 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.
16. 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.
17. Балашова Т. И.Обеспечение отказоустойчивости сети повышением надёжности её топлогии // Современные проблемы науки и образования. 2014. № 6. (www.science-education.ru/120-16846)
18. Мочалов В. А. Гибридный бионический алгоритм синтеза структуры беспроводной сенсорной сети // T-Comm: Телекоммуникации и транспорт. 2013. Т. 7. № 10. С. 72-77.
19. Нечунаева К. А. Оптимальное по показателям связности объединение сетей в условиях структурных и стоимостных ограничений // Проблемы информатики. 2010. № 2. С. 18-26.
20. 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.
21. 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.
Review
For citations:
Migov D..., Nechunaeva K..., Rodionov A... Genetic algorithm for network structure optimization using network reliability cumu-lative updating. The Herald of the Siberian State University of Telecommunications and Information Science. 2015;(4):55-61. (In Russ.)
Views:
191
Email this article 
