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

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

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

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

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

[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.