Р. Г. Стронгина. Ниж- ний Новгород: Изд-во Нижегородского университета, 2002, 217 с
жүктеу/скачать 1,64 Mb. Pdf көрінісі
|
Seminar 1
| t
. «Время» t – компьютерное время, реальное время не входит в уравнения, посколь- ку система инвариантна по времени. Пусть P(A,t) – вероятность быть в конфигурации A в момент вре- мени t. ) ( B A W → – вероятность перехода из состояния A в состояние B. Тогда [ ] ∑ → − → + → = + B t A P B A W t B P A B W t A P A A W t A P ) , ( ) ( ) , ( ) ( ) , ( ) ( ) , ( 1 . Отметим важное условие (не обязательно необходимое) для равно- весной системы, так называемое условие баланса = → ) , ( ) ( t A P B A W ) , ( ) ( t B P A B W → = . Данное условие может быть использовано, в част- ности, и для распределения Больцмана: ) ( ) ( ; ) ( ) ( / / ) ( / ) ( A E B E E e e e A B W B A W kT E kT A E kT B E − = ∆ = = → → ∆ − − − . Есть много способов выбора функции W такой, что удовлетворяет- ся условие баланса. В алгоритме Метрополиса выбор переходной функции осуществлен следующим образом: ≤ ∆ > ∆ = → ∆ − 0 если 1 0 если E E e B A W kT E , , ) ( / (7) На каждом шаге алгоритма производится пробное изменение кон- фигурации системы. Для Изинговой модели изменение конфигурации A производится переключением состояния выбранного спина. Полу- ченная конфигурация B принимается с вероятностью Метрополиса (7). По истечении некоторого времени система приходит к равновесной конфигурации с низкой энергией. Алгоритм Метрополиса для спиновых моделей очень легко подда- ется распараллеливанию, поскольку он является регулярным и локаль- ным. Хотя алгоритм Метрополиса прост для распараллеливания, не- возможно производить обновление всех узлов одновременно, посколь- ку это будет сказываться на условии баланса: узлы ближайших сосе- 109 дей зависимы, поэтому должны обновляться по отдельности. Рассмот- рим решетку, разделенную в шахматном порядке на черные и красные узлы. Все черные узлы можно обновить параллельно, поскольку они независимы, а затем параллельно обновить все красные узлы. Так или иначе, всегда нужно помнить, что основная идея метода Монте-Карло состоит в аппроксимации бесконечно большой суммы конечной суммой, взятой по существенным конфигурациям. Ошибка является преимущественно статистической, пропорциональной N 1 для N независимых конфигураций. Таким образом, возможна другая схема распараллеливания: различные процессоры осуществляют пол- ностью независимое решение с различными потоками случайных чи- сел, чтобы на конечном этапе добавить результат к оцениваемой сум- ме. Интересное поведение Изинговой модели наблюдается при очень низких температурах T. Для таких температур вероятность перехода в другое состояние может быть настолько мала, что нереально осущест- вить моделирование системы за разумное время вычислений. Причина кроется в том, что функция энергии имеет большое число локальных минимумов, и при малых температурах траектории сваливаются не к глобальному минимуму энергии, а лишь к некоторому локальному минимуму. Данное поведение аналогично закалке металла, когда, на- чиная с горячего (неупорядоченного) состояния, металл быстро охла- ждается до низкой температуры. Для реальных металлов это приводит к достижению локального минимума энергии, в котором он становится хрупким, некристаллизованным. Чтобы при закалке избежать «свали- вания» траекторий в метастабильные состояния, охлаждение произво- дится очень медленно, что дает металлам время на упорядочивание своей структуры до стабильной, структурно сильной конфигурации с низкой энергией. Мы можем применить подобный подход в Монте- Карло, начиная со случайной конфигурации при очень высокой темпе- ратуре и очень медленно уменьшая ее до тех пор, пока не установится требуемая очень низкая температура. Нахождение состояния наименьшей энергии является примером задачи глобальной оптимизации, т.е. задачей нахождения глобального минимума функции стоимости C(s) для значений s из допустимого множества S. Алгоритм Метрополиса может быть обобщен для реше- ния оптимизационных задач путем введения фиктивной температуры и 110 трактованием функции стоимости как энергии. Для общей задачи гло- бальной оптимизации температура является параметром, задающим вероятность увеличения функции стоимости на любом шаге посредст- вом обычного алгоритма Метрополиса в виде T C e / ∆ − , где ∆C – изменение функции стоимости при заданном изменении конфигу- рации (значений параметров). Нулевая температура соответствует ал- горитму наискорейшего спуска, при котором принимаются только те изменения, которые уменьшают значение энергии. Джеман & Джеман показали, что если температура уменьшается как k T T k log 0 = (8) для достаточно большого значения 0 T , есть статистическая гарантия нахождения оптимального значения. Хотя результаты Джема- на & Джемана могут показаться достаточно слабыми утверждениями, нужно понимать, что другие алгоритмы оптимизации не могут дать гарантии нахождения статистически оптимального решения для про- извольной оптимизационной задачи. жүктеу/скачать 1,64 Mb. Достарыңызбен бөлісу:
|