Повышение эффективности кластерных систем обработки информации при решении оптимизационных задач : на примере задачи составления расписания занятий

• Автор: Милехина, Татьяна Викторовна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 153 с. : ил.

Оглавление
Введение.

Глава 1. Методы решения задач многокритериальной оптимизации

1.1 Метод моделирования отжига i i.

1.2 Генетические алгоритмы i i

1.3 Табуированный поиск

1.4 Метод роящихся частиц i .

1.5 Алгоритм раскраски графа i i

1.6 Метод муравьиных колоний i

1.7 Метод пчелиной колонии i.

1.8 Линейная свертка. Линейное целочисленное программирование. i vi. i i i

1.9 Существующие подходы к решению задачи составления расписания.
1. Выводы
Глава 2. Формализация задачи составления расписания занятий
2.1. Составление расписания, как задача многокритериальной оптимизации
2.1.1 Объекты расписания.
2.1.2 Множество критериев
2.1.3 Влияние критериев на качество расписания.
2.1.4 Дополнительные параметры.
2.2. Метод решения задачи составления расписания.
2.3 Автоматическое назначение преподавателя
2.4. Многокритериальная оптимизация в задаче составления расписания
2.5. Выбор альтернатив в задаче составления расписания.
2.6 Коэффициенты важности критериев и параметров.
2.7 Вычисление критериальных функционалов
2.7.1 Критерий окна
2.7.2 Эффективная загруженность дня
2.7.3 Эффективная загруженность недели.
2.7.4 Пожелания преподавателей.
2.8 Алгоритм выбора аудитории для занятия
2.9 Особенности составления расписания в МИЭТ
2. Оценка качества полученного решения.
2. Выводы
Глава 3. Особенности реализации параллельных программ на кластерных системах.
3.1 Основные типы и архитектуры многопроцессорных систем.
3.2 Основные характеристики производительности.
3.3 Основные проблемы разработки параллельного алгоритма.
3.4 Основные этапы разработки параллельных алгоритмов
3.5 Выделение подзадач в задаче составления расписания занятий. Информационные зависимости
3.6 Масштабирование задачи составления расписания
3.7 Взаимодействие между подзадачами составления расписания
3.8 Распределение подзадач между процессорами кластерной системы.
3.9 Параллельный алгоритм для кластерных систем решения задачи составления расписания.
3. Формирование подсписков. Динамическая балансировка загрузки узлов.
3. Обмен данными между узлами кластерной системы.
3. Выводы
Глава 4. Исследование эффективности кластера для параллельного алгоритма составления расписания занятий
4.1 Структура входных данных
4.2 Оценка качества получаемых решений
4.3 Вычислительный эксперимент
4.4. Выводы.
Заключение
Список литературы


Из множества многокритериальных задач можно выделить в отдельное множество задачи планирования, составления расписания. В основе метода моделирования отжига лежит аналогия с термодинамикой, а конкретнее методы замораживания и кристаллизации жидкости, или охлаждение и нагревание металла. При высоких температурах молекулы жидкости двигаются свободно друг относительно друга. Если жидкость охлаждается медленно, то тепловая подвижность теряется. Атомы зачастую способны формировать чистый кристалл, полностью упорядоченный на расстояниях, в миллиарды раз превышающих размеры отдельного атома, во всех направлениях. Этот кристалл - это состояние минимума энергии для данной системы. При медленном охлаждении природа способна найти такой минимум энергетического состояния. А если жидкий металл охлаждается быстро, или закаливается, то система не достигает такого состояния, процесс завершается в состояниях с несколько большей энергией. Таким образом, суть процесса — это медленное охлаждение, обеспечивающее достаточно времени для перераспределения атомов, теряющих подвижность. Конечное множество Э. Вещественная целевая функция I, определенная Б. Для каждого /е 5', множество ? Невозрастающая функция Т: ТУ—»(0, со), называемая графиком охлаждения. Где N — множество положительных чисел, и Т(1) — зависимость температуры от времени. Начальное состояние л:(0) е ? Переходя к математической модели [5], определим, что в рассматриваемой задаче составления расписания может играть роль энергии и состояние какого объекта такая «энергия» может характеризовать. Один из возможных вариантов - это рассмотрение в качестве энергии целевой функции, основанной на штрафах, добавляемых к текущему расписанию за каждый неудобный в нём момент, а в качестве низкоэнергетического состояния — корректное (хотя и неизвестное расписание). Задаются начальное, высокое значение температуры г1° и операции мутации расписания. На основе введённых операций мутации и текущего решения генерируется новое корректное расписание Х незначительно отличающееся от предыдущего. Таким образом, допускается увеличение целевой функции, но вероятность этого экспоненциально уменьшается с ростом А/. Такой подход позволяет преодолевать локальные экстремумы. Вызывается функция изменения текущей температуры. Температура и, соответственно, вероятность принять в качестве текущего расписание с большим значением целевой функции уменьшается с каждой итерацией. При высоких температурах наблюдается скачкообразное изменение целевой функции. Постепенно с уменьшением температуры ес значение должно стремиться к минимуму. Если не выполнен критерий останова, то перейти к п. З. В качестве критериев останова могут быть приняты следующие: о выполнение заданного числа итераций; о выполнение заданного числа итераций без улучшения значения целевой функции на заданное значение. Для повышения эффективности алгоритма можно реализовать сохранение т лучших решений, а также п последних сгенерированных расписаний. Это позволит предотвратить зацикливание процесса составления расписания. Точность получаемого алгоритмом решения можно увеличить за счёт более медленного изменения температуры. При этом алгоритм более тщательно исследует пространство поиска, но время его работы существенно увеличивается. Поэтому функцию температуры приходится подбирать для каждой конкретной задачи индивидуально. Генетические алгоритмы - это адаптивные методы поиска, используемые для решения задач оптимизации. В них используется аналог генетического наследования и аналог естественного отбора. При этом сохраняется биологическая терминология в упрощенном виде и основные понятия линейной алгебры [6]. Основные принципы работы ГА (рис. Генерируется начальная популяция из п хромосом. Для каждой хромосомы вычисляется ее пригодность. Выбирается одна пара хромосом-родителей с помощью одного из способов отбора. Проводится кроссинговер (обмен частями между хромосомами) двух родителей с вероятностью рс, производя двух потомков. Проводится мутация потомков с вероятностью рт.