Оптимизация структуры сети по критерию надёжности с использованием кумулятивных оценок границ надёжности. Версия №2

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

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

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

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

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

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

[1] Denis A. Migov, Kseniya A. Nechunaeva, Sergei N. Nesterov, Alexey S. Rodionov Cumulative Updating of Network Reliability with Diameter Constraint and Network Topology Optimization, COMPUTATIONAL SCIENCE AND ITS APPLICATIONS - ICCSA 2016, PT I. Серия книг: Lecture Notes in Computer Science, Том: 9786,  Стр.: 141-152

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

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

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

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

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