Разработки СО РАН - каталоги программ и БД

Назначение - структурная оптимизация сетей различного назначения с целью повышения надёжности.

Область применения - моделирование и проектирование сетей различного назначения.

Используемый алгоритм - генетический алгоритм с использованием кумулятивных оценок верхней и нижней границ надёжности. Программа позволяет для заданного числа узлов и каналов связи сети находить структуру сети, оптимальную или близкую к оптимальной по критерию надёжности. Под надёжностью понимается вероятность связности сети. Узлы сети предполагаются абсолютно надёжными, т.е. надёжность узлов предполагается на порядки выше надёжности каналов связи. Для каждого канала связи задаются значения надёжности и стоимости прокладки. Поиск ведётся в условиях наперёд заданных ограничений на общую стоимость прокладки каналов связи и диаметр сети. Подход с использованием кумулятивных оценок позволяет быстрее принимать решение о пригодности (непригодности) получаемых в процессе работы алгоритма вариантов топологии сети.

Алгоритм опубликован в следующих работах:

[1] K. Nechunaeva, D. Migov. Speeding Up of Genetic Algorithm for Network Topology Optimization with Use of Cumulative Updating of Network Reliability // Proc. 9th Int. Conference on Ubiquitous Information Management and Communication (ACM IMCOM 2015), Bali, Indonesia, 2015. ACM New York, USA, 2015. ISBN 978-1-4503-3377-1. Article No. 42. (Indexed by Scopus)

[2] Д.А. Мигов, К.А. Нечунаева, А. С. Родионов Генетический алгоритм структурной оптимизации сетей с применением подхода кумулятивного уточнения границ надёжности. Вестник СибГУТИ, 2015, № 4. В печати.

Входные данные программы: количество узлов и каналов связи сети, значения надёжности для всех каналов связи (числа от 0 до 1), значения стоимости прокладки для всех каналов связи, параметры генетического алгоритма (размер популяции, кол-во поколений, размер турнира, вероятность мутации), ограничения на общую стоимость прокладки каналов связи, максимальное значение диаметра графа.

Функциональные возможности - структурная оптимизация сетей с количеством  каналов до 100.

Инструментальные средства создания - Delphi.

Алгоритм разработан в рамках гранта РФФИ № 14-07-31069.

Назначение – позволяет вычислять точное значение надёжности K-терминальной сети с ограничением на диаметр.
Область применения - анализ надёжности сетей различного назначения.

Одним из важных показателей сетевой надежности является вероятность связности заданного подмножества узлов. Однако существует также множество случаев, когда обычной связности терминалов недостаточно и необходимо, чтобы длина связующего пути не превышала заранее заданного числа D. Как и задача расчёта надёжности сети, задача расчёта надёжности сети с ограничением на диаметр NP-трудна [1]. В данной программе используется метод Cancela  и Petingi вычисления точного значения K-терминальной надёжности сети с ограничением на диаметр, а также методы ускорения работы программы, предложенные в [2]: предварительные сортировка рёбер, а также редукции рёбер.

[1] Cancela H., Petingi L. Reliability of communication networks with delay constraints: computational complexity and comlete topologies // Int. J. of Mathematics and Mathematical Sciences. 2004. V. 29. P. 1551-1562.

[2] D. Migov and S. Nesterov. Methods of Speeding up of Diameter Constrained Network Reliability Calculation // Springer Lecture Notes in Computer Science (in ICCSA 2015). Volume 9156, 2015, pp. 121-133.

Входные данные программы – структура сети в виде графа, значения надёжности каналов связи (т.е. вероятности их присутствия).

Выходные данные программы – значение надёжности сети.

Программа работает с графом, представленным полным файлом предшественников (списки KAO,FO), а также списком терминалов. Вводить списки представления графов и редактировать их можно в соответствующих окнах программы. Информация в файле располагается следующим образом: первая строка и вторая строка – списки KAO и FO соответственно, в третьей строке располагается список терминалов сети (Ki=1, в случае, если i-я вершина сети является терминалом, и 0 иначе). Четвёртая строка – значение надёжности каждого ребра, пятая – значение диаметра сети.

Алгоритм разработан в рамках гранта РФФИ № 14-07-31069.

Функциональные возможности – расчёт надёжности сетей с количеством элементов около  сотни.

Инструментальные средства создания – Microsoft Visual Studio 2012.

Назначение – позволяет устанавливать, является ли сеть достаточно надёжной(ненадёжной) по отношению к заранее заданному порогу надежности для  сети с ограничением на диаметр.

Область применения - анализ надёжности сетей различного назначения.

Рассматриваются сети, в которых отказам подвержены только каналы связи. Под надёжностью понимается вероятность того, что все выделенные узлы связаны между собой с помощью исправных каналов связи путями оганиченной длины. Точный расчет надёжности сети является NP-трудной задачей. Однако при анализе сети иногда достаточно знать, превосходит ли надёжность исследуемой сети величину заданного порога. Используя метод Cancela и Petingi [2], можно организовать итерационный процесс уточнения верхней и нижней границы надёжности сети с ограничением на диаметр и остановить его при достижении одной из границ значения заданного порога. Подобный подход для сетей без ограничения на диаметр был предложен в [1]. Программа позволяет устанавливать, является ли сеть достаточно надёжной по отношению к заданному порогу надежности, а также можно выбрать максимальное время работы, через которое программа остановится, показав верхнюю и нижнюю границы надёжности сети.

[1] Won J.-M., Karray F. Cumulative Update of All-Terminal Reliability for Faster Feasibility Decision // IEEE Trans. On Reliability. September 2010. Vol 59, no 3. P. 551-562.  

[2] Hector Cancela and Louis Petingi. Diameter constrained network reliability: exact evaluation by factorization and bounds. In ICIL’2001 (International Conference on Industrial Logistics), pages 359– 366, 2001.                                                                    

Входные данные программы – структура сети в виде графа, значения надёжности каналов связи (т.е. вероятности их присутствия), значение порога (число от 0 до 1) (можно отключить), ограничение на время расчёта в секундах (можно отключить).

Выходные данные программы – ответ о достаточной надёжности/ненадёжности сети. Если расчёт не был окончен за отведённое время, выводятся полученные к данному моменту значения границ надёжности.

Программа работает с графом, представленным полным файлом предшественников (списки KAO,FO), а также списком терминалов. Вводить списки представления графов и редактировать их можно в соответствующих окнах программы. Информация в файле располагается следующим образом: первая строка и вторая строка – списки KAO и FO соответственно, в третьей строке располагается список терминалов сети (Ki=1, в случае, если i-я вершина сети является терминалом, и 0 иначе). Четвёртая строка – значение надёжности каждого ребра, пятая – значение диаметра сети.

Алгоритм разработан в рамках гранта РФФИ № 14-07-31069.

Функциональные возможности – анализ надёжности сетей с количеством элементов  в несколько сотен.

Инструментальные средства создания – Microsoft Visual Studio 2012.