Разработка эволюционных алгоритмов для решения задач теории расписаний в условиях неопределенности

• Автор: Родькина, Маргарита Борисовна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Воронеж
• Количество страниц: 157 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

ГЛАВА 1. СОВРЕМЕННОЕ СОСТОЯНИЕ

1.1 Достоинства и недостатки эволюционных алгоритмов

1.2 Основные понятия и общие схемы ЭА

1.3 Основные модификации ЭА

1.4 Задачи теории расписаний: терминология, методы решения

1.5 Цель и постановка задач исследования

ВЫВОДЫ К ПЕРВОЙ ГЛАВЕ

ГЛАВА 2. РАЗРАБОТКА И АНАЛИЗ УСЛОЖНЁННЫХ МОДЕЛЕЙ

ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ
2.1 Алгоритм имитации развития социума СЭА
2.1.1 Представление и характеристики особи
2.1.2 Особенности эволюционных операторов
2.1.3 Взаимодействие популяций СЭА
2.1.4 Общая схема и параметры алгоритма
2.1.5 Экспериментальное тестирование СЭА
2.2 Хронологический эволюционный алгоритм ХЭА
2.2.1 Этап РНК-мира
2.2.2 Клеточный этап
2.2.3 Видовой этап
2.2.4 Социальный этап
2.2.5 Параметры и особенности этапов ХЭА
2.2.6 Экспериментальное тестирование ХЭА

2.3 Самоадаптирующийся эволюционный алгоритм САЭА
2.3.1 Основные параметры алгоритмов
2.3.2 Экспериментальное тестирование самоадаптирующихся алгоритмов..
ВЫВОДЫ КО ВТОРОЙ ГЛАВЕ
ГЛАВА 3. ЗАДАЧИ НАХОЖДЕНИЯ ОПТИМАЛЬНОГО ПЛАНА
3.1 Задача планирования работы IT-отдела
3.1.1 Планирование работ IT-отдела в условиях неопределенности
3.1.2 Модификации эволюционного алгоритма для решения ЗПРО
3.1.3 Планирование с учётом важности работ
3.1.4 Результаты использования ЭА для решения ЗПРО
3.2 Задача оптимизации функционирования территориально-распределенной сети
3.2.1 Критерии оценки расписаний сети
3.2.2 Модель ЗОФТРС
3.2.3 Оптимизация функционирования сети в условиях неопределенности
3.2.4 Модификации эволюционного алгоритма для решения ЗОФТРС
3.2.5 Результаты использование ЭА для решения ЗОФТРС
ВЫВОДЫ К ТРЕТЬЕЙ ГЛАВЕ
ГЛАВА 4. ПРОГРАММНЫЙ КОМПЛЕКС SEA: SCHEDULING
EVOLUTIONARY ALGORITHM
4.1 Структура и назначение программного комплекса
4.2 Вычислительный эксперимент
4.2.1 Задача оптимизации
4.2.2 Конвейерная задача теории расписаний
4.3 Форма просмотра событий эволюционного алгоритма

ВЫВОДЫ К ЧЕТВЕРТОЙ ГЛАВЕ
ЗАКЛЮЧЕНИЕ
СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ПРИЛОЖЕНИЕ ДОКУМЕНТЫ О ВНЕДРЕНИИ

2 <х3 < 5,5. (2.4)
При ограничениях (2.2)-(2.4) и заданной точности алгоритм должен рассматривать особи, для которых выполняются условия: х, е{0; 0,5; 1; 1,5; 2;2,5;3},
х2 е {—3;—2,5;—2;—1,5;—1;—0,5; 0; 0,5; 1;1,5;2;2,5;3;3,5;4}, х3 е{2;2,5;3;3,5;4;4,5;5;5,5}.
Из неравенства (2.1) получаем, что для представления всех значений переменных х{ и х3 двоичными кодами понадобится по 3 гена, для х2 - 4 гена.
Тогда точку х = (1;-1;5,5) можно представить генотипом из трёх хромосом:
С = (0 1 0),
СИ2 = (0 1 0 0),
СИ, — (1 1 1).
Введём дополнительные социальные факторы и биологические и
психологические характеристики особи а в структуру эволюционного алгоритма.
1. Пол - биологическая характеристика, совокупность генетически
детерминированных признаков особи, определяющих её роль в процессе
оплодотворения [4]. Будем выделять мужские и женские особи. Множество мужских особей в популяции Р обозначим через 1(Р), множество женских через 1¥(Р). То есть Р = /(Р)и1Т(Р). Для простоты введём в первую хромосому генотипа дополнительный ген с аллелями: 0 - женская особь и 1 - мужская. При этом ограничим размножение оогамией, то есть оператор кроссовера будет получать потомков только от двух особей разного пола.
2. Возраст age(o^) - биологическая характеристика, количество шагов алгоритма, в течение которых особь существует. Чем больше возраст, тем больше должна быть вероятность гибели особи и меньше вероятность её участия в скрещивании. Для простоты определения того, насколько старой может считаться особь, задаётся параметр популяции а1р(Р) - средняя продолжительность жизни в популяции.