научная статья по теме АЛГОРИТМ ИМИТАЦИИ ОТЖИГА В ЗАДАЧАХ ПОСТРОЕНИЯ МНОГОПРОЦЕССОРНЫХ РАСПИСАНИЙ Автоматика. Вычислительная техника

Текст научной статьи на тему «АЛГОРИТМ ИМИТАЦИИ ОТЖИГА В ЗАДАЧАХ ПОСТРОЕНИЯ МНОГОПРОЦЕССОРНЫХ РАСПИСАНИЙ»

Автоматика и телемеханика, № 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 рублей.

Показать целиком