qweqweqe123123

Алгоритм

Статистическая механика изучает поведение сложных систем, состоящих из большого числа взаимодействующих атомов, находящихся в тепловом равновесии при конечных температурах. Исследователи обнаружили, что вероятность обнаружить систему в некотором состоянии 5 равна е-E(S)/kbT, где E(S) — энергия данного состояния, а kb, — постоянная Больцмана. Таким образом, наиболее вероятными в тепловом равновесии при любой температуре оказываются состояния атомов с минимальной энергией [158].

Аналогия между задачей комбинаторной оптимизации и определением основного состояния физической системы со множеством взаимодействующих частиц впервые была обнаружена Керкпатриком, Гелаттом и Веччи в 1983 г. [85] и, независимо от них, Церни [31]. Аналогия хорошо иллюстрируется табл. 9.1. Состояния системы соответствуют конфигурациям задачи комбинаторной оптимизации. Основные состояния системы соответствуют оптимальным конфигурациям, то есть таким конфигурациям, которые минимизируют функцию стоимости. Наконец, задача определения оптимальной конфигурации соответствует задаче поиска основного состояния системы при низкой температуре.

Алгоритм

В 1953 г. Метрополис [113] предложил процедуру вычислений, позволяющую моделировать равновесное состояние системы многих тел при конечной температуре. Алгоритм Метрополиса показан в листинге 9.1. На каждом шаге случайным образом выбирается небольшое возмущение текущей конфигурации, после чего вычисляется изменение энергии системы Δ. Новая конфигурация принимается с вероятностью 1, если Δ ≤ 0, и с вероятностью е -Δ/kbT при Δ >0. Для этого выбрасывается случайное число от 0 до 1. Если оно оказывается меньшим е -Δ/kbT, новая конфигурация принимается. Это обеспечивает заданную вероятность принятия.

Листинг. Алгоритм Метрополиса

begin

Выбрать случайную исходную конфигурацию S: repeat

S' произвольно выбранная конфигурация, соседняя с S:

Д E(S') - E(S):

Prob min(l.eΔ/kT): if randcm(O.l) s Prob then S := S':

Until false: end:

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

Керкпатрик реализовал данный подход, рассматривая систему при постепенном понижении «температуры». При каждой конкретной температуре система выдерживается до тех пор, пока она не достигнет теплового равновесия. Это обеспечивается алгоритмом Метрополиса. Общий алгоритм метода модельной закалки приведен в листинге 9.2. Обратите внимание, что в методе модельной закалки постоянная Больцмана включена в температуру, так что температурой мы называем их произведение. Температура в данном случае является только управляющим параметром процедуры оптимизации.

Листинг 9.2. Алгоритм модельной закалки begin

S         начальное решение SO:

Т     начальная температура ТО:

while (критерий завершения не выполнен) do begin

while (равновесие не достигнуто) do begin

S' произвольно выбранная конфигурация, соседняя с S:

Д :- E(S’) - E(S):

Prob min(l.e'Δ/kT): if random(O.l) Ј Prob then S :- S': end:

Изменить T: end;

Вывести лучшее решение: end;

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

Теоретический анализ показывает, что алгоритм модельной закалки сходится к глобально оптимальному решению с вероятностью 1 при условии, что выполняются некоторые ограничения на количество итераций при каждом значении температуры и на изменение этой температуры от шага к шагу. Однако общего принципа, по которому можно было бы ставить эти ограничения для конкретных задач, пока не существует. Поэтому большинство современных приложений метода модельной закалки используют простой и эффективный подход Керкпатрика и других [85] в различных разновидностях.

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

1.  Нужно сформулировать задачу, точно описав различные конфигурации.

2.  Требуется систематически порождать решения, соседние с текущим.

3.   Нужно выбрать подходящую функцию стоимости.

4.   Наконец, важно правильно определить график «закалки», то есть начальную температуру, закон ее изменения, продолжительность  выдержки при каждом значении температуры и условие завершения работы алгоритма.

Смотрите также