Труды семинара Бурбаки за 1988 г (947402), страница 49
Текст из файла (страница 49)
Один из примеров таких задач глобальной оптимизации дается спин-глассовыми моделями в статистической механике; в них х, представляет физическое состояние вершины з в кри- сталлической решетке 5 с очень большим числом вершин )Ч = =саг(5). Решетка погружена в двух- нли трехмерное евкли- дова пространство, а Н(х) выражает энергию конфигурации х. Для спин-глассовой модели энергия обычно имеет вид Н (х) = Е (ук (х), Кюс где С множество «клик» вЂ” семейство всех подмножеств К решетки 5 с диаметром ~р и где каждый потенциал действия .(/к(х) зависит лишь от (х,), в~ К. Непосредственно вычислить Н;„нельзя, так как в ситуации спин-глассовой модели, которая должна служить моделью кристаллов со случайно разбросанными примесями, предполагается, что отображение К-»(7» назначает «наугад» каждой клике К Азепсоы моЬег1. Шгпи1а1ей аппеаипк.
— Бещ. ВоигЬаш, 1987 — 88, № 697, Ав!ег!вчие 16! — 162, 1988, р. 223 — 237. © перевод на русский язык, А. Д. Вентцель, 1990 Р. Аееякатт Процедура «отпуска» потенциал 6к, принадлежащий фиксированному линейному пространству вещественнозначных функций. Для особенно простых взаимодействий асимптотическое поведение среднего Н,„при У- оо было получено в физической литературе (Паризи, Мезар (Раг!з), Мехагб)) методом реплик,, с помощью которого были также найдены грубые описания «основных состояний» (минимизирующих конфигураций) при больших Н. Из-за того что в этих выкладках большую роль играли эвристические соображения, было важно эмпирическое подтверждение результатов, и, таким образом, естественно, что специалисты по спин-глассовой модели, такие, как Кирпатрик, Тулуз, Мезар, Гутфренд, Амит (К!Г)тра!г!с)с, Тои!опзе, Мехагб, Оп((геппе(, Апп1) и др., постоянно использовали осуществимые алгоритмы минимизации, такие, как знаменитая теперь «процедура отпуска».
Одна из сложных черт в типичной спин-глассовой модели— это то, что для больших Н число «локальных минимумов» Н(х) громадно, так что детерминированный градиентный алгоритм любого рода в таких ситуациях бесполезен. Понятие локального минимума, о котором мы здесь говорим, связано с так называемым хемминговским расстоянием: две конфигурации х и у являются соседними тогда и только тогда, когда они отличаются не более чем в одном месте.
2. ГИББСОВСКОЕ РАСПРЕДЕЛЕНИЕ В контексте статистической механики имеет смысл на любом данном конфигурационном пространстве Е = Ее рассматривать множество М, распределений вероятностей Р, для которых на среднюю энергию наложено ограничение (2.1) Р (х) Н (х) = а. хив В пределах множества М, так называемое «наиболее неупорядоченное» распределение Р должно максимизировать энтропию — Р (х) !оп Р (х), хая и отсюда, пользуясь множителями Лагранжа, мы легко находим, что наиболее неупорядоченные распределения в М,— гиббсовскив распределения бт(х)= д ехр~ т 1 Н (х) гДе Хг= ~Ч~ ехР~ — — 1 — «стагистическаЯ сУмма», а поло- П (х) з т х~ я жительный параметр Т, определяемый (2.1), обычно интерпретируется как «температура».
Очевидное свойство бг, играющее здесь решающую роль,— то, что при Т вЂ” О распределение 6, все более концентрируется на множестве (2.2) Еяпм(х ~ Е(Н(х)= пппН(у)). еяв Точнее, мы имеем 1пп бг (х) = ба (х) для всех х ~ Е, г-еа гДе бе — РавномеРное РаспРеделение веРоатностей на Емгю Итак, если мы можем эффективно выбрать случайную конфигурацию х ее Е с распределением вероятностей бт, а Т достаточно мало, такая конфигурация будет в подавляющем проценте случаев почти минимизирующей конфигурацией для энергии Н.
Однако при большом числе элементов в 3 построение эффективного метода случайного выбора на Е в соответствии с вероятностью бг оказывается серьезной вычислительной проблемой, которая первоначально была решена Глаубером, Метрополисом (01апЬет, Ме(горо!!з) и др. 3. ГЛАУБЕРОВСКАЯ ДИНАМИКА Сейчас мы набросаем предложенный Глаубером (О1апЬег) и ставший теперь классическим алгоритм для построения случайной величины Х со значениями в пространстве конфигураций Е с распределением вероятностей, близким к бт Отметим, что температура Т здесь фиксирована. Сначала мы фиксируем произвольную симметричную марковскую переходную матрицу 6 =(д,е), где х, у ее Е. Например, типичный выбор для спин-глассовой модели состоит в том, что полагают д„е=О, если у Ее)г, ~,(х), в„е= —,, если у ее е'„', (х), 1 где ух — множество соседей х в Е для хемминговского расстояния (см.
$1), а (1+ г) — число элементов в у' (общее для всех хееЕ). Мы хотим построить случайную последовательность Х„ конфигураций. Допустим, что конфигурация Х„ уже получена. 239 Р. Ааенкотт Процедура «отпуска» Выберем такую случайную конфигурацию У„, что (3.2) Р (У = У! Х'о .. Х ) = чх т Затем мы полагаем с вероятностью 1 (3.3) либо Х„»,= У„, либо Х„+~ =Х„. Этот (случайный) выбор делается в соответствии со следующим правилом: (3.4) Р(Х„+,— — У„[Ха, ..., Х„, У„)=ехр— (П (Рл! — П (Х„)1» где [о]+= о при о) О и [о]+=О при о (О. Нетрудно доказать, что марковская цепь Х„имеет равновесное распределение, совпадающее с гиббсовским распределением се„если только матрица «выбора» Я симметрична и неприводима. Другими словами, в этом случае (3.5) Вш Р(Х„=х) =етт(х), х е-:Е.
л-»л» Здесь неприводимость Я означает, что любые две конфигурации можно соединить такой конечной цепочкой конфигураций хь что д„,„,.+, ) О. Конечно, действительное вычисление Х,+, при данном Х„становится более длительным, когда возрастает число элементов в (у ее Е(дну) О). 4. ПРОЦЕДУРА «ОТПУСКА«н ЭВРИСТИЧЕСКИЕ СООБРАЖЕНИЯ Результат (3.5) и тот факт, что при низкой температуре распределение Т сосредоточивается на минимизирующих конфигурациях, наводят на мысль использовать глауберовскую случайную динамику в обстановке, когда температура Т уже не постоянна, а убывает к О при и- +со.
Если мы фиксируем убывающую последовательность Т„, такую, что !цп Т„= О, и замел++а ним в условных распределениях (3.4) Т на Т„, мы получим новую марковскую цепь Х„, для которой можно надеяться, что (4,1) 1пп Р (Х„ее Е, ) = 1. л.++ Этот новый алгоритм был назван введшими эту идею Кирпатриком, Гелаттом, Векки (К!гира!г!ск, Ое1аН, Чесс!т!) [13] процедурой «отпуска» (или «отжига»). Их (эвристические)' аргументы были основаны на формальной аналогии с постепенным и очень медленным физическим охлаждением, которое издавна применяется с целью приведения реальных физических систем в устойчивые низкоэнергетнческие состояния, тогда как быстрое охлаждение заморозило бы систему в нежелательном высокоэнергетическом метастабильном состоянии. На самом деле не все режимы охлаждения (Т,) будут обладать существенным для нас минимизирующим свойством (4.1).
Первое достаточное условие для (4.1) было получено Д. и С. Геман (1». и 5. Оешап) [6], которые строго доказали, что если (4.2) 1!ш Т„1оп и ) !т, л-»+лл где !с ) О достаточно велико, то для процедуры «отпуска» будет выполняться минимизирующее свойство (4.1). Были предъявлены, например, Бретаньоль (Вге!аппо!!е), легко конструируемые примеры, показывающие, что при 1нп Т, 1оц и = О минимизирующее свойство (4.1) не может л -» +»» быть выполнено в общей ситуации.
Затем Гаек вычислил величину наилучшей константы )с в (4.2), а впоследствии в нескольких математических статьях асимптотическое исследование этих алгоритмов и их аналогов с непрерывным временем было уточнено. Упомянем несколько имен; Холли — Струк (Но!!еу— 8!тоос(с) [11], Фоллмер (Ро!1гпег) [5], Гидас [О1баз], Вон— Шеу (Ннапп — Зйеп) [12], Чан — Чоу (С!т!апд — С!тото) [3], Катани (Са!оп!) [4], Труве (Тгоцче) [15] и многие другие.
Одновременно большим сообществом физиков и/или специалистов по вычислительной математике, таких как Шеррингтон (3!тегг!п5!оп), Тулуз (Топ1опзе), Дрейфус (1)геу!пз), Аартс— Лаарховен (Аау(з — ЕаагЬочеп), Бономи — Луттон (Вопопп'— — 1л!!оп), Д. Ури (()Бгу 0.), Д. и С.
Геман (1». и 5. Оешап) и т.д., были исследованы практические применения процедуры «отпуска» к задачам глобальной минимизации. 5. ПРО»(ЕДУРА «ОТПУСКА»: АБСТРАКТНАЯ ПОСТАНОВКА Рассмотрим абстрактное конечное множество Е, которое мы будем называть конфигурационным пространством. Пусть Н: Е -~- Г« — произвольная функция, сохраняющая название функции энергии. Зафиксируем симметричную стохастическую матрицу =(в„е), х~ Е, уееЕ, такую, что любые две конфигурации х и у можно соединить конечной цепью хл ~ Е, д» „„+1) О. Матрицу (г будем называть матрицей разведки.
Процедура «отпуска» 241 р. Азенкотт Зафиксируем убывающую последовательность Т„температур, стремяшуюся к нулю при и-»+ос. Эта последовательность будет называться режимом охлаждения. На пространстве состояний Е определим (неоднородную) марковскую цепь Х„с произвольным начальным состоянием Х, и переходной мртрицей Р„(х, у) = Р (Х„„1 —— у (Х„= х), задаваемой формулами р„(х, у) =д„уехр —, при у Ф х, (Н (у! — Н (х)1~ р„(х, х) 1 ~ р„(х, у). ы» Прежде чем сформулировать основные асимптотические результаты, касающиеся алгоритма «отпуска» (Х„), нам понадобится еще несколько определений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
