Лекция 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) процессорах.

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