Лекции All in One (1121240), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Алгоритм обучения строится так, чтобы вообще не учитывать положительный опыт работы. Любой результат шага поиска воспринимается как отрицательный, но в разной мере:

d выбирается так чтобы всегда обеспечивалось неравенство:

Лекция 5

Алгоритмы имитации отжига

Концепция построения алгоритмов

Общая схема алгоритмов

Шаг 1. Задать начальное корректное решение X⁰S и считать его текущим вариантом решения (X=X⁰).

Шаг 2. Установить начальную температуру Т₀, приняв ее текущей (Т=Т₀).

Шаг 3. Применить операции преобразования решения к текущему решению X и получить новый корректный вариант решения X^’ S, если это решение является лучшим из ранее найденных решений, то запомнить его.

Шаг 4. Найти изменение функционала оценки качества решения :

• если (решение улучшилось), то новый вариант решения считать текущим (X=X^');

• если (решение ухудшилось), то принять с вероятностью в качестве текущего решения новый вариант решения X^'.

Шаг 5. Повторить заданное число раз шаги 3 и 4 без изменения текущей температуры.

Шаг 6. Если критерий останова выполнен, то завершение работы алгоритма.

Шаг 7. Понизить текущую температуру в соответствии с выбранным законом понижения и перейти к шагу 3.

1. Разработать способ представления решения X и операций преобразования текущего решения на шаге 3.

2. Разработать стратегию применения операций преобразования текущего решения на шаге 3: какую операцию применять, к какому элементу X, как его изменять.

3. Выбрать закон понижения температуры на шаге 7.

4. Определить функционал , используемый для оценки качества текущего решения на шаге 4.

5. Выбрать критерий останова алгоритма, используемый на шаге 6.

Закон Больцмана: .

• Закон Коши: .

• .

T - текущая температура алгоритма,

T₀ - начальная температура,

x - номер итерации алгоритма.

,

• - стандартная функция понижения температуры, например функция Больцмана или Коши,

• k - количество итераций алгоритма без улучшения решения,

• k_t - количество итераций алгоритма без улучшения решений после которых начинается повышение температуры (этот параметр подбирается таким образом, чтобы k_t итераций хватало для нахождения локального оптимума с достаточной точностью),

• c_t - коэффициент, характеризующий скорость увеличения температуры.

Методы распараллеливания алгоритмов имитации отжига

Схема параллельного асинхронного алгоритма.

Схема параллельного алгоритма с синхронизацией

Способы обмена полученными решениями и стратегии принятия решения в качестве текущего:

• Процесс i посылает процессу i+1 своё текущее решение. Процесс i+1 принимает это решение в качестве текущего, если F(X_i) < F(X_i+1). Где F(X_i) – значение целевой функции текущего решения i-ого процесса.

• Широковещательный обмен решениями. Принятие j-ым процессом решения от i-ого процесса в качестве текущего, если F(X_i) < F(X_j) и i < j.

• Отправка текущих решений координатору, выбор из них произвольного (возможно с разными вероятностями, в зависимости от значений целевой функции) и принятие его в качестве текущего всеми процессами.

Алгоритм, основанный на декомпозиции целевой функции

Большую часть времени алгоритм имитации отжига затрачивает на вычисление целевой функции.

Если целевая функция является декомпозируемой F(x₁, x₂, … , x_i, … , x_n) = F(x₁) + F(x₂) + … + F(x_i) + … +F(x_n),

то возможно параллельное её вычисление на m (m≤n) процессорах.

Подходы, основанные на декомпозиции пространства решений

Лекция 6

Поведение программы Bh(PR):

Bh(PR) = < S, {R  (PR)}, {R  (PR)}>,

S – множество всех возможных шагов процессов (рабочих интервалов) в допустимом диапазоне входных данных программы,

{R  (PR)} - отношения, определяющие частичный порядок на множестве шагов каждого процесса,

{R  (PR)} - отношения взаимодействия между процессами.

Рабочий интервал процесса - внутренние действия процесса между двумя последовательными взаимодействиями с другими процессами.

Для задачи построения расписания будем использовать одну из историй поведения программы H(PR)Bh(PR).

Для H(PR) отношение {R  (PR)} является отношением полного порядка, а множество S сужается до множества шагов, которые делают процессы для конкретного набора входных данных.

H(PR) можно представить ациклическим ориентированным размеченным графом.

Вершинам соответствуют рабочие интервалы процессов,

дугам ={ _ik=(p_i,p_k)}_{(i,k)О(1...N)} - связи, определяющие взаимодействия между рабочими интервалами из множества P (определяются объединением отношений {R(PR)}, {R(PR)}).

Модель прикладной программы определим:

1. Множеством рабочих интервалов процессов, составляющих программу PR:

Нумерация рабочих интервалов является сквозной и удовлетворяет условиям полной топологической сортировки. Каждый рабочий интервал имеет метку принадлежности к процессу.

1. Частичным порядком на P:

={ _ik=(p_i,p_k)}_{(i,k)(1...N)};

1. Вычислительной сложностью рабочих интервалов:

;

1. Объемом данных обмена для каждой связи из :

{v_ik}_{(i,k)(1...N)};.

Расписание выполнения программы определено, если заданы:

• привязка,

• порядок.

Модель расписания выполнения программы определим набором простых цепей и отношением частичного порядка _HP на множестве P:

HP=({SP_i}_i=(1...M) , _HP).

{SP_i}_i=(1...M) -набор простых цепей (ветвей параллельной программы).

Отношение частичного порядка _HP на множестве P для HP определим как объединение отношений: _HP= _c ₁ _M, _i - отношение полного порядка на SP_i, которое определяется порядковыми номерами рабочих интервалов в SP_i; _c - набор секущих ребер, которые определяются связями рабочих интервалов, распределенных на разные процессоры.

Если рабочие интервалы p_i и p_j распределены на разные процессоры и в существует связь _ij, то она определяет секущее ребро в HP.

На отношение _HP накладываются условия ацикличности и транзитивности.

Расписание HP является корректным, если выполнены следующие ограничения:

1. Каждый рабочий интервал должен быть назначен на процессор (в SP_i).

2. Каждый рабочий интервал должен быть назначен лишь на один процессор (в один SP_i).

3. Частичный порядок, заданный в H сохранен в HP:

4. Расписание HP должно быть беступиковым. Условием беступиковости является отсутствие контуров в графе HP: .

5. Все рабочие интервалы одного процесса должны быть назначены на один и тот же процессор (в один и тот же SP_i).

В дальнейшем будем говорить, что расписание корректно , если оно удовлетворяет ограничениям 1-5.

Дано:

• H(PR)=(P, )- модель программы,

• T=f(HP,HW)- функция вычисления времени выполнения расписания HP на архитектуре HW.

Требуется построить: HP– расписание выполнения программы на заданном числе процессоров M такое, что:

1. Разработать способ представления решения X и операций преобразования текущего решения на шаге 3.

2. Разработать стратегию применения операций преобразования текущего решения на шаге 3: какую операцию применять, к какому элементу X, как его изменять.

3. Выбрать закон понижения температуры на шаге 7.

4. Определить функционал , используемый для оценки качества текущего решения на шаге 4.

5. Выбрать критерий останова алгоритма, используемый на шаге 6.

Бинарное представление расписания.

Расписание задается:

• матрицей привязки Y(HP)_NM

• матрицей смежности X(HP)_NN графа HP.

Элементы матриц определяются:

M – число процессоров в ВС,

N – число рабочих интервалов в H.

Недостатком данного представления является большое число бинарных переменных N²+NM.

Целочисленное представление расписания

1. Расписание задается матрицей Y(HP)_NM, где элемент матрицы определяется: ,

c – порядковый номер рабочего интервала p_i в SP_j.

При данном способе представления расписания число целочисленных переменных равно NM.

2. Расписание задается:

• вектором привязки Y(HP)_K (i-й элемент вектора Y(HP)_K равен номеру списка в который назначены рабочие интервалы i-го процесса),

• вектором порядка X(HP)_N, (i-й элемент вектора X(HP)_N равен порядковому номеру рабочего интервала в соответствующем списке).

При данном способе представления расписания число целочисленных переменных равно K+N.

Операции преобразования расписания

Можно выделить следующие варианты отличия расписаний HP и HP^ друг от друга:

• расписания HP и HP^ отличаются лишь порядком рабочих интервалов как минимум в одном SP_j;

• расписания HP и HP^ отличаются привязкой рабочих интервалов.

Характеристики

Список файлов лекций