Автоматика и телемеханика, № 10, 2014
Системный анализ и исследование
операций
© 2014 г. Д.А. ЗОРИН (juan@lvk.cs.msu.su), В.А. КОСТЕНКО, канд. техн. наук (kost@cs.msu.su) (Московский государственный университет им. М.В. Ломоносова)
АЛГОРИТМ ИМИТАЦИИ ОТЖИГА В ЗАДАЧАХ ПОСТРОЕНИЯ
МНОГОПРОЦЕССОРНЫХ РАСПИСАНИЙ
Предложен алгоритм имитации отжига для решения задачи определения минимального необходимого числа процессоров и построения статического расписания выполнения прикладных программ с учетом заданных ограничений на время выполнения расписания и требований к надежности. Приводится теоретическое и экспериментальное обоснование свойств разработанного алгоритма: сравниваются различные законы понижения температуры в алгоритме имитации отжига.
1. Введение
Задача условной оптимизации заключается в нахождении компонент вектора X = (xi,... ,xn), минимизирующих целевую функцию f (X) при выполнении ограничений, заданных функциями gi(X) и X € S:
min f (X), gi(X) < 0, i = 1 ,...,m, X € S.
Если X € S, то как минимум одна из функций f, gi будет не определена на этом значении X.
По свойствам функций f, gi и определению множества S можно ввести классификацию различных задач оптимизации [1]. Например, если функции f, gi - линейные и S С Zn, то задача относится к классу задач целочисленного линейного программирования.
Если функций f, gi заданы правилами/алгоритмами их вычисления, то проблематично применение точных и эвристических методов, использующих априорно известные свойства этих функций для организации поиска оптимального решения. При большой размерности задачи условной оптимизации методы полного перебора допустимых решений также оказываются неприемлемыми из-за сложности.
Идея о целесообразности случайного поведения при наличии неопределенности, т.е. при отсутствии достаточной информации, которая может быть использована для организации поиска оптимального решения/поведения, впервые в четкой форме была сформулирована в [2] и реализована в известном гомеостате Эшби. Применительно к сложным задачам условной оптимизации алгоритм поиска оптимального решения должен опираться на метод проб и ошибок. Только такой процесс позволяет извлечь информацию, необходимую
4 Автоматика и телемеханика, № 10
97
для организации поиска решения. Метод проб и ошибок основан на понятии случайного эксперимента: случайного выбора значений компонент вектора X, что дает возможность получить информацию о функциях /, д^ и множестве 5, которая может быть использована для организации поиска решения сложной задачи условной оптимизации.
Широко применяемыми подходами к построению алгоритмов оптимизации, опирающихся на метод проб и ошибок, являются следующие:
- алгоритмы случайного поиска (ненаправленного, направленного, направленного с самообучением) [3],
- алгоритмы имитации отжига [4],
- генетические и эволюционные алгоритмы [5],
- алгоритмы муравьиных колоний [6, 7].
В отдельный класс выделим задачи комбинаторной оптимизации. Они возникают, например, при построении расписаний. В постановке любой задачи комбинаторной оптимизации присутствуют некоторые объекты, которые требуется определенным образом разместить, упорядочить или разбить на группы. В этом случае множество 5 состоит из решений X, описывающих всевозможные размещения, упорядочивания или разбиения на группы исходно заданных объектов. Математически множество 5 описывается набором ограничений, которые требуют согласованного изменения значений элементов X: изменение значения одного из элементов для сохранения корректности решения может требовать принятия конкретных значений ряда других элементов.
В работе рассматриваются проблемы, которые возникают при построении алгоритма имитации отжига для решения задачи определения минимального необходимого числа процессоров и построения статического расписания выполнения прикладных программ с учетом заданных ограничений на время выполнения расписания и требований к надежности. Также приводится теоретическое и экспериментальное обоснование свойств разработанного алгоритма.
2. Общая схема алгоритмов имитации отжига
Рассмотрим общую схему алгоритмов имитации отжига и проблемы, которые необходимо решить при реализации этого алгоритма для конкретной задачи условной оптимизации.
Алгоритмы имитации отжига в процессе поиска оптимального решения с некоторой вероятностью допускают переход к решению с более высоким значением целевой функции. Это свойство позволяет таким алгоритмам выходить из локальных оптимумов. Принципы, положенные в основу работы алгоритмов, можно объяснить на следующей физической аналогии [4]. На рис. 1 изображен шарик в коробке, внутренняя поверхность которой соответствует ландшафту целевой функции. При сильном встряхивании коробки в горизонтальном направлении шарик может переместиться из любой точки в любую другую. При постепенном уменьшении силы встряхивания будет достигнуто условие, когда сила встряхивания достаточна для перемещения шарика из точки А в точку В, но недостаточна для того, чтобы шарик мог переместиться из В в А. При дальнейшем уменьшении силы встряхивания
до нуля шарик остановится в точке В - точке минимума. В алгоритмах имитации отжига аналогом силы встряхивания является вероятность перехода в состояние с более высоким значением целевой функции. В начале работы алгоритма эта вероятность должна быть достаточно велика, чтобы была возможность перехода от выбранного начального решения к любому другому решению. В процессе работы алгоритма вероятность перехода уменьшается в соответствии с выбранным законом.
Для решения задач условной оптимизации схему имитации отжига можно представить так:
Шаг 1. Задать начальное корректное решение X0 € 5 и считать его текущим вариантом решения (X = X0).
Шаг 2. Установить начальную температуру То, приняв её текущей (Т = = То).
Шаг 3. Применить операции преобразования решения к текущему решению X и получить новый корректный вариант решения X' € 5. Если это решение является лучшим из ранее найденных решений, то запомнить его.
Шаг 4. Найти изменение функционала оценки качества решения ДТ = = Т(/(X'),gг(X')) - Т(/(X),gг(X)):
- если ДТ ^ 0 (решение улучшилось), то новый вариант решения считать текущим (X = X');
- если ДТ > 0 (решение ухудшилось), то принять с вероятностью р = = в качестве текущего решения новый вариант решения X'.
Шаг 5. Повторить заданное число раз шаги 3 и 4 без изменения текущей температуры.
Шаг 6. Если критерий останова выполнен, то завершение работы алгоритма.
Шаг 7. Понизить текущую температуру в соответствии с выбранным законом и перейти к шагу 3.
Для построения алгоритма имитации отжига для решения конкретной задачи условной оптимизации требуется решить следующие задачи:
1. Разработать способ представления решения X и операций преобразования текущего решения на шаге 3;
2. Разработать стратегию применения операций преобразования текущего решения на шаге 3: какую операцию применять, к какому элементу X и как изменять этот элемент;
3. Выбрать закон понижения температуры на шаге 7;
4. Определить функционал ¥(/(X),дг(X)), используемый для оценки качества текущего решения на шаге 4. В него входит целевая функция и могут входить все или часть функций-ограничений;
5. Выбрать критерий останова алгоритма, используемый на шаге 6.
А В
Рис. 1. Иллюстрация принципов работы алгоритмов имитации отжига.
4* 99
Способ представления решения X и операции преобразования текущего решения должны удовлетворять условиям замкнутости (после применения любой операции к корректному решению получается корректное решение) и полноты (для двух любых корректных решений X и X* существует конечная последовательность операций, приводящая X к X* такая, что все промежуточные решения корректны). Условия замкнутости и полноты системы операций преобразования решений являются достаточными условиями того, что алгоритм за конечное число итераций может перейти от заданного начального решения к оптимальному решению.
Стратегия применения операций преобразования текущего решения и закон понижения температуры определяют вычислительную сложность и точность алгоритма.
Если есть дг, не вошедшие в функционал ^(/^),дг(X)), то на шаге 3 после применения операций преобразования решения должно получаться решение, удовлетворяющее этим ограничениям. Наиболее часто функционал ^(/(X),gг(X)) строится с использованием функций штрафа или барьерных функций [1].
3. Алгоритм имитации отжига для построения многопроцессорных расписаний
Опишем алгоритм имитации отжига для решения задачи определения минимального необходимого числа процессоров и построения статического расписания выполнения прикладных программ. При этом должны соблюдаться заданные ограничения на время выполнения расписания и на требования к надежности вычислительной системы [8]. Детальное описание и обоснование построения алгоритмов имитации отжига для решения задач построения многопроцессорных расписаний можно найти в [8-10].
3.1. Формулировка задачи
Аппаратная часть системы состоит из множества процессоров, соединенных друг с другом посредством коммутатора. Все процессоры одинаковы, т.е. время выполнения одной и той же программы на любом процессоре будет одинаковым. Надежность процессоров одинакова. Известно время передачи единицы данных от одного процессора к другому. Коммутатор устроен таким образом, что если к нему подключено N процессоров, то гарантируется наличие N/2 свободных каналов в любой момент времени, т.е. для любой передачи всегда найдется канал.
Программа, для которой строится расписание, состоит из конечного множества взаимодействующих заданий. Для каждого из заданий известно, какие вычисления оно производит и каков объем данных, получаемых на выходе. Программу можно представить в виде графа потока данных С = {V, Е}, где V - вершины графа, Е - дуги. Для каждой вершины графа задано время выполнения соответствующего задания, а дуги размечены временами передачи данных. Обозначим через М множество доступных процессоров.
Для повышения отказоустойчивости используются два метода: резервирование процессоров и многоверсионное програм
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.