Планирование обменов в сетях с топологией кольца с арбитражем для систем реального времени

• Автор: Бычков, Иван Алексеевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 170 с. : ил.

Оглавление
Введение
Глава 1. Задача построения расписания обменов в кольце с арбитражем
1.1 Понятие кольца с арбитражем
1.2 Описание задачи
1.3 Способы организации информационных обменов в кольце с арбитражем
1.3.1 Децентрализованный способ организации информационных обменов .
1.3.2 Централизованный способ организации информационных обменов
1.4 Формальная модель информационных обменов и математическая постановка задачи
1.5 Выводы
Глава 2. Задача выбора порядка абонентов в кольце с арбитражем
2.1 Топологии кольца с арбитражем
2.1.1 Топология с концентратором
2.1.2 Топология без концентратора
2.2 Описание задачи
2.3 Формальная постановка задачи
2.4 Выводы
Глава 3. Существующие методы решения рассматриваемых задач
3.1 Метод полного перебора
3.2 Жадные алгоритмы
3.3 Метод ветвей и границ
3.4 Генетические и эволюционные алгоритмы
3.5 Муравьиные алгоритмы
3.6 Метод динамического программирования
3.7 Алгоритмы на основе нейросетей Хопфилда
3.8 Ненаправленный случайный поиск
3.9 Направленный случайный поиск
3.10 Выводы

Глава 4. Предлагаемые алгоритмы решения рассматриваемых задач
4.1 Алгоритм решения задачи построения расписания обменов в кольце с арбитражем
4.1.1 Входные данные и результат работы алгоритма
4.1.2 Принцип работы алгоритма
4.1.3 Функции и переменные, используемые в алгоритме
4.1.4 Пошаговое описание алгоритма
4.1.5 Пошаговое описание используемых функций
4.1.6 Завершимость алгоритма
4.1.7 Корректность алгоритма
4.1.8 Достаточные условия, при которых алгоритм является точным
4.1.9 Вычислительная сложность алгоритма
4.2 Алгоритм решения задачи выбора порядка абонентов в кольце с арбитражем
4.2.1 Входные данные и результат работы алгоритма
4.2.2 Описание разработанного алгоритма
4.2.3 Корректность и завершимость алгоритма
4.2.4 Вычислительная сложность алгоритма
4.3 Выводы
Глава 5. Численные исследования разработанных алгоритмов
5.1 Методика статистической обработки результатов экспериментов
5.2 Исходные данные
5.2.1 Реальные данные
5.2.2 Модельные данные
5.3 Результаты исследований
5.3.1 Исследование алгоритма построения расписаний обменов
5.3.2 Исследование алгоритма выбора порядка абонентов
5.4 Выводы

Глава 6. Инструментальная система
6.1 Требования к инструментальной системе построения расписаний информационных обменов в кольце с арбитражем
6.2 Разработанная система
6.2.1 Структура разработанной библиотеки
6.2.2 Консольные приложения
6.2.3 Приложение с графическим интерфейсом пользователя
6.3 Выводы
Заключение
Литература
Приложение А. Математические определения
Приложение Б. Пространства поиска рассматриваемых задач и их конечность
Приложение В. Доказательство NP-трудности рассматриваемых задач
Приложение Г. Детализированные правила передачи сообщений в кольце
с арбитражем
Приложение Д. Детализированное описание централизованного способа
организации информационных обменов
Приложение Е. Параметры кольца с арбитражем
Приложение Ж. Вычисление длительностей передачи сообщений и минимально допустимых задержек между сообщениями
Приложение И. Вычисление времени начала выполнения предварительного этапа и времени окончания выполнения завершающего этапа информационного обмена
Приложение К. Результаты численных исследований

феромона на том или ином маршруте, тем больше вероятность того, что муравьи будут выбирать для движения именно этот маршрут.
Для задачи коммивояжёра работу муравьиного алгоритма схематично можно представить следующим образом:
1. Задать начальное количество феромона на рёбрах графа.
2. Определить количество муравьев и их начальные положения.
3. Промоделировать поиск муравьями решений в соответствии с заданным алгоритмом
построения маршрута.
4. Обновить количество феромона на рёбрах в зависимости от полученных решений.
5. Если условие останова не выполнено, то перейти к п. 2.
Муравьиные алгоритмы оказались применимы для решения не только задачи коммивояжёра, но и других комбинаторных задач, в том числе и для решения задачи построения расписаний [8, 42, 70, 76]. Численные исследования показали высокую эффективность муравьиных алгоритмов как для задач построения расписаний, так и для других классов задач [51, 70]. Однако для достижения высокой эффективности работы муравьиных алгоритмов необходимо выполнить экспериментальный подбор их параметров.
Для того, чтобы решить задачу оптимизации, используя муравьиный алгоритм, необходимо:
• свести задачу оптимизации к задаче нахождения маршрута на графе;
• выбрать локально-эвристическую функции на рёбрах графа;
• определить алгоритм построения маршрута муравьём.
При использовании муравьиных алгоритмов в некоторых случаях приходится сталкиваться проблемой неоднозначности операции восстановления решения исходной задачи по найденному алгоритмом маршруту на графе. При возникновении такой неоднозначности необходимо либо предложить другую кодировку решений с помощью маршрутов на графе, либо применять специальные алгоритмы восстановления, использование которых может привести к существенному увеличению времени работы алгоритма решения исходной задачи.
Один из возможных способов сведения задачи построения расписания обменов к задаче нахождения маршрута на графе состоит в следующем. Каждой планируемой работе ставится в соответствие одна вершина графа. Кроме того, добавляется ещё одна фиктивная вершина О, соответствующая началу расписания. В результате каждому маршруту, построенному муравьиным алгоритмом, будет соответствовать последовательность информационных обменов без повторений, по которой можно однозначно восстановить