Бикритериальная модель и алгоритмы оптимизации сети передачи данных

• Автор: Лазарев, Евгений Александрович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Нижний Новгород
• Количество страниц: 120 с. : ил.

ВВЕДЕНИЕ
ГЛАВА 1.МЕТОДЫ РЕШЕНИЯ МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧ
ОПТИМИЗАЦИИ СЕТИ ПЕРЕДАЧИ ДАННЫХ
§ 1.1 Задачи транспортного типа
§1.2 Подходы к решению многокритериальных задач
§ 1.3 Применение метода ветвей и границ для решения задач оптимизации
§ 1.4 Применение генетических алгоритмов для решения задач оптимизации
§ 1.5 Применение алгоритма имитации отжига для решения задач оптимизации.
§ 1.6 Модели и методы оптимизации сетей передачи данных
Выводы по главе
ГЛАВА 2.МАТЕМАТИЧЕСКАЯ МОДЕЛЬ, ЗАДАЧА И АЛГОРИТМЫ
ОПТИМИЗАЦИИ СЕТИ ПЕРЕДАЧИ ДАННЫХ
§ 2.1 Структура сети Интернет
§ 2.2 Математическая модель сети передачи данных
§ 2.3 Задача оптимизации сети передачи данных
2.3.1 Постановка задачи
2.3.2 Пример решения задачи
§ 2.4 Нахождение множества Парето-оптимальных решений задачи оптимизации сети
передачи данных методом полного перебора
2.4.1 Описание метода
2.4.2 Результаты вычислительных экспериментов
§ 2.5 Нахождение множества Парето задачи оптимизации сети передачи данных методом
ветвей и границ
2.5.1 Описание метода
2.5.2 Пример решения задачи методом ветвей и границ
2.5.3 Результаты вычислительных экспериментов
Выводы по главе
ГЛАВА 3.СИНТЕЗ СУБОПТИМАЛЬНОГО МНОЖЕСТВА РЕШЕНИЙ
ЗАДАЧИ ОПТИМИЗАЦИИ СЕТИ ПЕРЕДАЧИ ДАННЫХ
§3.1 Представительная выборка
§ 3.2 Отыскание субоптимального множества решений

§ 3.3 Методика оценки отклонения субоптимального множества решений от совокупности Парето
3.3.1 Метод подсчета решений
3.3.2 Метод усреднения отклонения от точного решения
§ 3.4 Нахождение субоптимального множества решений задачи оптимизации сети
передачи данных с помощью генетического алгоритма
3.4.1 Описание метода
3.4.2 Дополнительные эвристики
3.4.3 Пример решения задачи с помощью генетического алгоритма
3.4.4 Пример нахождения представительной выборки субоптимального множества
решений с помощью генетического алгоритма
3.4.5 Результаты вычислительных экспериментов
§ 3.5 Нахождение субоптимального множества решений задачи оптимизации сети
передачи данных с помощью алгоритм имитации отжига
3.5.1 Описание метода
3.5.2 Дополнительные эвристики
3.5.3 Результаты вычислительных экспериментов
§ 3.6 Использование комбинированных методов
§ 3.7 Сводные графики результатов вычислительных экспериментов
Выводы по главе
ГЛАВА 4.ПРОГРАММНЫЙ КОМПЛЕКС РЕШЕНИЯ ЗАДАЧИ
ПРОЕКТИРОВАНИЯ И ОПТИМИЗАЦИИ СЕТИ ПЕРЕДАЧИ
ДАННЫХ И РЕКОМЕНДАЦИИ ПО ПРИМЕНЕНИЮ
АЛГОРИТМОВ
§ 4.1 Назначение и возможности программного комплекса
§ 4.2 Описание архитектуры программного комплекса
§ 4.3 Описание графического пользовательского интерфейса
4.3.1 Основное окно работы программы
4.3.2 Главное меню программы
4.3.3 Окно параметров алгоритма
§ 4.4 Типовой сценарий работы с программным комплексом
§ 4.5 Рекомендации по применению алгоритмов
4.5.1 Использование метода полного перебора

4.5.2 Использование метода ветвей и границ и комбинированного метода
4.5.3 Использование генетического алгоритма
4.5.4 Использование алгоритма имитации отжига
Выводы по главе
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
СПИСОК СОКРАЩЕНИЙ
ПРИЛОЖЕНИЯ
Приложение А. Справка о внедрении результатов диссертационной работы в ООО
«Теком»
Приложение Б. Акт о внедрении результатов диссертационной работы в учебный процесс
Нижегородского государственного технического университета им. Р.Е. Алексеева.
Приложение В. Свидетельство о государственной регистрации программы для ЭВМ..
Приложение Г. Теоремы о NP-тpyднocти и максимальной мощности множества Парето-
оптимальных решений задачи оптимизации сети передачи данных
Приложение Д. Архитектура интерактивного программного комплекса

(нулевой уровень дерева) соответствует всей области допустимых решений й, а любой вершине уровня к > 0 соответствует подмножество, получающееся при фиксировании первых к ребер (из множества Е') сети.
Из каждой вершины (за исключением листьев дерева ветвления, в которых зафиксированы все ребра из Е') производится ветвление на два подмножества, то есть осуществляется дихотомическое деление. Первое из подмножеств получается путем фиксирования очередного ребра, но без добавления его в 5, то есть рассматриваемое ребро не будет построено в сети. Второе из подмножеств получается путем фиксирования очередного ребра с добавлением его в 5, то есть рассматриваемое ребро будет достроено.
Нижняя оценка Ьр для плана проектирования Е* после фиксирования первых к ребер вычисляется следующим образом:
а И=1>'М+!!л).
еє5 і=к+
то есть равна сумме стоимостей строительства фиксированных ребер, которые будут достроены, и ребер, которые еще не рассматривались, то есть ребер с номерами большими к .
0-г )= |^С(У,£иХ)| >
то есть равна величине потока для графа, полученного путем добавления в исходный множества достроенных фиксированных ребер.
Верхняя оценка Н для плана проектирования Е* после фиксирования первых к ребер вычисляется следующим образом:
(е*)=£р'(є)’
то есть равна сумме стоимостей строительства фиксированных ребер, которые будут достроены,
Ог Е )= |^с(г,£и5и{г,|/>*:})| ’