Генетический алгоритм структурной оптимизации сетей с применением подхода кумулятивного уточнения границ надёжности
Аннотация
В статье предлагается новый алгоритм оптимизации структуры сети по критерию надёжности в условиях различных ограничений.Рассматриваются сети с абсолютно надёжными узлами и ненадёжными каналами связи. Под надёжностью сети понимается вероятность связности соответствующего случайного графа, расчёткоторой представляет собой NP-трудную задачу.Разработанный алгоритм оптимизации является генетическим, его операторы позволяют отсеивать непригодные особи на более ранних этапах за счёт использования кумулятивного уточнения верхней и нижней границ надёжности сети. Проведённые эксперименты подтвердили эффективность предлагаемого подхода.
Об авторах
Д. А. Мигов
Институт вычислительной математики и математической геофизики СО РАН
Россия
Россия
К. А. Нечунаева
Институт вычислительной математики и математической геофизики СО РАН
Россия
Россия
А. С. Родионов
СибГУТИ
Россия
Россия
Список литературы
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.
Рецензия
Для цитирования:
Мигов Д.А., Нечунаева К.А., Родионов А.С. Генетический алгоритм структурной оптимизации сетей с применением подхода кумулятивного уточнения границ надёжности. Вестник СибГУТИ. 2015;(4):55-61.
For citation:
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.)
Просмотров:
192
Послать статью по эл. почте 
