Оптимизационные
алгоритмы
Дискретные
задачи размещения
Оптимизационные
алгоритмы
Главная страница
библиотеки
Демонстрационная версия
Оптимизационные
алгоритмы
Алгоритм имитации отжига
Экзотическое название данного алгоритма связано с методами имитационного моделирования в статистической физике [1], основанными на технике Монте-Карло. Исследование кристаллической решетки и поведения атомов при медленном остывании тела привело к появлению на свет вероятностных алгоритмов, которые оказались чрезвычайно эффективными в комбинаторной оптимизации. Впервые это было замечено в 1983 году [2]. Сегодня этот алгоритм является популярным как среди практиков благодаря своей простоте, гибкости и эффективности, так и среди теоретиков, поскольку для данного алгоритма удается аналитически исследовать его свойства и доказать асимптотическую сходимость.
Алгоритм имитации отжига относится к классу пороговых алгоритмов локального поиска. На каждом шаге этого алгоритма для текущего решения ik в его окрестности N(ik) выбирается некоторое решение j и, если разность по целевой функции между новым и текущим решением не превосходит заданного порога tk, то новое решение j заменяет текущее. В противном случае выбирается новое соседнее решение. Общая схема пороговых алгоритмов может быть представлена следующим образом.
Пороговый алгоритм
1. Выбрать начальное решение i0 Î I и положить f* : = f (i0), k : = 0.
2. Пока не выполнен критерий остановки делать следующее:
2.1. Случайно выбрать j Î N (ik).
2.2. Если f (j) – f (ik) < tk то ik+1 : = j.
2.3. Если f* > f (ik), то f* : = f (ik).
2.4. Положить k : = k+1.
В зависимости от способа задания последовательности {tk} различают три типа пороговых алгоритмов.
- : tk= 0, k = 0, 1, 2, …— вариант классического локального спуска с монотонным улучшением по целевой функции.
Последовательное улучшение
Пороговое улучшение: tk = ck, k = 0, 1, 2, …, ck ³ 0, ck ³ ck+1 и
— вариант локального поиска, когда допускается ухудшение по целевой функции до некоторого заданного порога, и этот порог последовательно снижается до нуля.
Имитация отжига: tk ³ 0, k = 0, 1, 2, … — случайная величина с математическим ожиданием E (tk) = ck ³ 0 — вариант локального поиска, когда допускается произвольное ухудшение по целевой функции, но вероятность такого перехода обратно пропорциональна величине ухудшения, точнее для любого j Î N(i)
Последовательность {ck} играет важную роль при анализе сходимости и выбирается так, чтобы ck ® ¥ при k ® ¥. Иногда параметр ck называют температурой [3], имея ввиду указанные выше истоки.
Существует много эвристических способов выбора конечной последовательности {ck} с целью повышения вероятности обнаружить глобальный оптимум. В некоторых работах рассматриваются небольшие примеры, для которых удается полностью исследовать характеристики цепей Маркова [4, 5]. В большинстве работ следуют рекомендациям первопроходцев [2] и используют схему геометрической прогрессии.
1. Начальное значение: c0= D fmax — максимальная разность между двумя соседними решениями.
2. Понижение порога: ck+1=a ck, k = 0, 1,…, K – 1, где a — положительная константа, достаточно близкая к 1, например, a Î [ 0,8; 0,99].
3. Конечное значение: cK > 0 определяется либо по числу сделанных изменений, либо как максимальное ck, при котором алгоритм не меняет текущее решение в течение заданного числа шагов. При каждом значении ck алгоритм выполняет порядка | N(i)| шагов, не меняя значение порога.
Главная страница
библиотеки
Демонстрационная версия
Оптимизационные
алгоритмы
