Кинетический Монте-Карло

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

Метод КМК по сути аналогичен динамическому методу Монте-Карло и алгоритму Гиллеспи .

Алгоритмы

Одна из возможных классификаций алгоритмов KMC - это KMC с отклонением (rKMC) и KMC без отклонения (rfKMC).

КМК без отказов

На каждом шаге система может перейти в несколько конечных состояний, при этом скорости перехода между начальным состоянием и всеми возможными конечными состояниями должны быть известны.

Выбор конечного состояния: случайная переменная выбирается между 0 и Γ _tot ; вероятность того, что система перейдет в состояние i , пропорциональна Γ _i .

Алгоритм rfKMC, часто называемый только KMC, для моделирования эволюции системы во времени, где некоторые процессы могут происходить с известными скоростями r, можно записать, например, следующим образом: ^{[1] : 13–14}

1. Установить время . ${\displaystyle t=0}$
2. Выберите начальное состояние k .
3. Сформируйте список всех возможных скоростей перехода в системе из состояния k в общее состояние i . Состояния, которые не взаимодействуют с k, будут иметь . ${\displaystyle N_{k}}$ ${\displaystyle r_{ki}}$ ${\displaystyle r_{ki}=0}$
4. Вычислите кумулятивную функцию для . Общая ставка составляет . ${\displaystyle R_{ki}=\sum _{j=1}^{i}r_{kj}}$ ${\displaystyle i=1,\ldots ,N_{k}}$ ${\displaystyle Q_{k}=R_{k,N_{k}}}$
5. Получите равномерное случайное число . ${\displaystyle u\in (0,1]}$
6. Найдите событие, которое должно выполнить i , найдя i , для которого (этого можно эффективно достичь с помощью двоичного поиска ). ${\displaystyle R_{k,i-1}<uQ_{k}\leq R_{ki}}$
7. Выполнить событие i (обновить текущее состояние ). ${\displaystyle k\rightarrow i}$
8. Получите новое равномерное случайное число . ${\displaystyle u^{\prime }\in (0,1]}$
9. Обновите время с помощью , где . Обратите внимание, что этот временной интервал представляет собой время, прошедшее между предыдущим событием и этим, а не интервал времени между этим событием и следующим. ^{[1] : 17–18} ${\displaystyle t=t+\Delta t}$ ${\displaystyle \Delta t=Q_{k}^{-1}\ln(1/u^{\prime })}$
10. Вернитесь к шагу 3.

(Примечание: поскольку среднее значение равно единице, тот же средний масштаб времени можно получить, используя вместо него шаг 9. Однако в этом случае задержка, связанная с переходом i, не будет получена из распределения Пуассона, описываемого формулой ставка , а вместо этого будет средним значением ^{этого распределения .} ${\displaystyle \ln(1/u^{\prime })}$ ${\displaystyle \Delta t=Q_{k}^{-1}}$ ${\displaystyle Q_{k}}$

Этот алгоритм известен в разных источниках под разными названиями: алгоритм времени пребывания , n -кратный способ или алгоритм Борца-Калоса-Лебовица (BKL) . Важно отметить, что рассматриваемый временной шаг является функцией вероятности того, что все события i не произошли. ^{[1] : 13–14}

Отказ от КМК

Отклонение KMC обычно имеет преимущество более простой обработки данных и более быстрых вычислений для каждого предпринятого шага, поскольку не требуется трудоемкое действие по получению всех данных . С другой стороны, время, выделяющееся на каждом шаге, меньше, чем для rfKMC. Относительный вес плюсов и минусов варьируется в зависимости от конкретного случая и имеющихся ресурсов. ${\displaystyle r_{ki}}$

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

1. Установить время . ${\displaystyle t=0}$
2. Выберите начальное состояние k .
3. Получите количество всех возможных скоростей перехода из состояния k в общее состояние i . ${\displaystyle N_{k}}$
4. Найдите событие -кандидат для выполнения i путем равномерной выборки из приведенных выше переходов. ${\displaystyle N_{k}}$
5. Примите событие с вероятностью , где – подходящая верхняя граница для . Часто его легко найти без необходимости вычислять все (например, для вероятностей скорости перехода в мегаполисе). ${\displaystyle f_{ki}=r_{ki}/r_{0}}$ ${\displaystyle r_{0}}$ ${\displaystyle r_{ki}}$ ${\displaystyle r_{0}}$ ${\displaystyle r_{ki}}$
6. Если принято, выполнить событие i (обновить текущее состояние ). ${\displaystyle k\rightarrow i}$
7. Получите новое равномерное случайное число . ${\displaystyle u^{\prime }\in (0,1]}$
8. Обновите время с помощью , где . ${\displaystyle t=t+\Delta t}$ ${\displaystyle \Delta t=(N_{k}r_{0})^{-1}\ln(1/u^{\prime })}$
9. Вернитесь к шагу 3.

(Примечание: может меняться от одного шага МК к другому.) Этот алгоритм обычно называют стандартным алгоритмом . ${\displaystyle r_{0}}$

Были проведены теоретические ^[2] и численные ^{[1] [3]} сравнения алгоритмов.

Временные алгоритмы

Если ставки зависят от времени, шаг 9 в rfKMC должен быть изменен следующим образом: ^[4] ${\displaystyle r_{ki}(t)}$

${\displaystyle \int _{0}^{\Delta t}Q_{k}(t')dt'=\ln(1/u^{\prime })}$.

После этого необходимо выбрать реакцию (шаг 6)

${\displaystyle R_{k,i-1}(\Delta t)<uQ_{k}(\Delta t)\leq R_{ki}(\Delta t)}$

Другой очень похожий алгоритм называется методом первой реакции (FRM). Он состоит в выборе первой возникшей реакции, то есть выбора наименьшего времени и соответствующего номера реакции i по формуле ${\displaystyle \Delta t_{i}}$

${\displaystyle \int _{0}^{\Delta t_{i}}r_{ki}(t')dt'=\ln(1/u_{i})}$,

где – N случайных чисел. ${\displaystyle u_{i}\in (0,1]}$

Комментарии к алгоритму

Ключевое свойство алгоритма КМК (и алгоритма ФРМ) состоит в том, что если скорости корректны, если процессы, связанные со скоростями, относятся к типу пуассоновских процессов и если разные процессы независимы (т.е. не коррелированы), то КМК Алгоритм дает правильный временной масштаб для эволюции моделируемой системы. Были некоторые споры о правильности шкалы времени для алгоритмов rKMC, но ее правильность также была строго доказана. ^[2]

Если, кроме того, переходы следуют подробному балансу , алгоритм KMC можно использовать для моделирования термодинамического равновесия. Однако КМК широко используется для моделирования неравновесных процессов, ^[5] и в этом случае нет необходимости соблюдать детальный баланс.

Алгоритм rfKMC эффективен в том смысле, что каждая итерация гарантированно приводит к переходу. Однако в представленной выше форме требуются операции для каждого перехода, что не слишком эффективно. Во многих случаях это можно значительно улучшить, объединив одни и те же типы переходов в ячейки и/или сформировав древовидную структуру данных событий. Недавно был разработан и протестирован алгоритм масштабирования такого типа с постоянным временем. ^[6] ${\displaystyle N}$

Основным недостатком RFKMC является то, что все возможные скорости и реакции должны быть известны заранее. Сам метод ничего не может сделать для их предсказания. Скорости и реакции должны быть получены с помощью других методов, таких как диффузионные (или другие) эксперименты, молекулярная динамика или моделирование теории функционала плотности . ${\displaystyle r_{ki}}$

Примеры использования

KMC использовался при моделировании следующих физических систем:

1. Поверхностная диффузия
2. Поверхностный рост ^[7]
3. Диффузия вакансий в сплавах (первоначальное использование ^[8] )
4. Ускорение эволюции доменов
5. Подвижность и кластеризация дефектов в твердых телах, облученных ионами или нейтронами, включая, помимо прочего, модели накопления повреждений и модели аморфизации/рекристаллизации.
6. Вязкоупругость физически сшитых сетей ^[9]

Чтобы дать представление о том, какими могут быть «объекты» и «события» на практике, приведем один конкретный простой пример, соответствующий примеру 2 выше.

Рассмотрим систему, в которой отдельные атомы осаждаются на поверхность по одному (типично для физического осаждения из паровой фазы ), но также могут мигрировать по поверхности с некоторой известной скоростью скачка . В этом случае «объектами» алгоритма КМС являются просто отдельные атомы. ${\displaystyle w}$

Если два атома оказываются рядом друг с другом, они становятся неподвижными. Тогда поток поступающих атомов определяет скорость _{депозита} r , и систему можно смоделировать с помощью KMC, учитывая все осажденные мобильные атомы, которые (еще) не встретили своего аналога и не стали неподвижными. Таким образом, на каждом этапе KMC возможны следующие события:

• Новый атом приходит с _{депозитом по ставке}
• Уже осажденный атом прыгает на один шаг со скоростью w .

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

Естественно, применяя КМК к задачам физики и химии, нужно сначала подумать, достаточно ли хорошо реальная система следует предположениям, лежащим в основе КМК. Реальные процессы не обязательно имеют четко определенные скорости, переходные процессы могут быть коррелированными, в случае скачков атомов или частиц скачки могут происходить не в случайных направлениях и т.д. При моделировании сильно различающихся временных масштабов необходимо также учитывать, могут ли новые процессы присутствовать в более длительных временных масштабах. Если какая-либо из этих проблем верна, временная шкала и развитие системы, предсказанные KMC, могут быть искажены или даже полностью неверны.

История

Первая публикация, в которой были описаны основные особенности метода KMC (а именно использование кумулятивной функции для выбора события и расчета шкалы времени в форме 1/ R ), была сделана Янгом и Элкоком в 1966 году. ^[8] Алгоритм времени пребывания также была опубликована примерно в то же время. ^[10]

По-видимому, независимо от работ Янга и Элкока, Борц, Калос и Лебовиц ^[1] разработали алгоритм KMC для моделирования модели Изинга , который они назвали n-кратным способом . Основы их алгоритма такие же, как у Янга ^[8] , но они предоставляют гораздо более подробную информацию о методе.

В следующем году Дэн Гиллеспи опубликовал то, что сейчас известно как алгоритм Гиллеспи для описания химических реакций. ^[11] Алгоритм аналогичен, а схема продвижения по времени практически такая же, как и в KMC.

На момент написания этой статьи (июнь 2006 г.) не существовало окончательного трактата по теории КМК, но Фихторн и Вайнберг подробно обсудили теорию моделирования термодинамического равновесия КМК. ^[12] Хорошее введение также дали Art Voter, ^[13] [1] и APJ Jansen, ^[14] [2], а недавний обзор — (Chatterjee 2007) ^[15] или (Chotia 2008). ^[16] Обоснование KMC как обобщенной динамики Ланжевена с использованием подхода квазистационарного распределения было развито Т. Лельевром и его сотрудниками. ^{[17] [18]}

В марте 2006 года компания Synopsys выпустила, вероятно, первое коммерческое программное обеспечение, использующее Kinetic Monte Carlo для моделирования диффузии и активации/деактивации легирующих примесей в кремнии и кремниеподобных материалах , о чем сообщили Мартин-Брагадо и др. ^[19]

Разновидности КМК

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

• Решетка КМК ( ЛКМК ) означает КМК, выполненную на атомной решетке . Часто эту разновидность еще называют атомистической КМК, ( АКМК ). Типичным примером является моделирование диффузии вакансий в сплавах , где вакансия может прыгать по решетке со скоростью, зависящей от локального элементного состава. ^[20]
• Объект КМК ( ОКМК ) означает КМК, проводимый для дефектов или примесей , скачущих либо в случайных, либо в решеточно-специфичных направлениях. В моделирование включены только положения прыгающих объектов, а не положения «фоновых» атомов решетки. Базовый шаг KMC — прыжок на один объект.
• Событие KMC ( EKMC ) или KMC первого прохождения ( FPKMC ) означает разновидность OKMC, в которой следующая реакция между объектами (например, кластеризация двух примесей или вакансии - межузельная аннигиляция) выбирается с помощью алгоритма KMC с учетом положения объекта, и это событие затем немедленно выполняется. ^{[21] [22]}

Рекомендации

1. Bortz, AB; Калос, Миннесота; Лебовиц, Дж. Л. (1975). «Новый алгоритм моделирования спиновых систем Изинга методом Монте-Карло». Журнал вычислительной физики . Эльзевир Б.В. 17 (1): 10–18. Бибкод : 1975JCoPh..17...10B. дои : 10.1016/0021-9991(75)90060-1. ISSN  0021-9991.
2. Серебринский, Сантьяго А. (31 марта 2011 г.). «Физическая шкала времени в кинетическом моделировании цепей Маркова с непрерывным временем по методу Монте-Карло». Физический обзор E . Американское физическое общество (APS). 83 (3): 037701. Бибкод : 2011PhRvE..83c7701S. doi : 10.1103/physreve.83.037701. ISSN  1539-3755. ПМИД  21517635.
3. Садик, Абдулла (1984). «Новый алгоритм моделирования кинетики спинового обмена систем Изинга методом Монте-Карло». Журнал вычислительной физики . Эльзевир Б.В. 55 (3): 387–396. Бибкод : 1984JCoPh..55..387S. дои : 10.1016/0021-9991(84)90028-7. ISSN  0021-9991.
4. Прадос, А.; Брей, Джей-Джей; Санчес-Рей, Б. (1997). «Динамический алгоритм Монте-Карло для основных уравнений с зависящей от времени скоростью перехода». Журнал статистической физики . ООО «Спрингер Сайенс энд Бизнес Медиа». 89 (3–4): 709–734. Бибкод : 1997JSP....89..709P. дои : 10.1007/bf02765541. ISSN  0022-4715. S2CID  122985615.
5. Мэн, Б.; Вайнберг, WH (1994). «Моделирование температурно-программируемых спектров десорбции методом Монте-Карло». Журнал химической физики . Издательство АИП. 100 (7): 5280–5289. Бибкод : 1994JChPh.100.5280M. дои : 10.1063/1.467192. ISSN  0021-9606.
6. Слепой, Александр; Томпсон, Эйдан П.; Плимптон, Стивен Дж. (28 мая 2008 г.). «Кинетический алгоритм Монте-Карло с постоянным временем для моделирования больших сетей биохимических реакций». Журнал химической физики . Издательство АИП. 128 (20): 205101. Бибкод : 2008JChPh.128t5101S. дои : 10.1063/1.2919546. ISSN  0021-9606. ПМИД  18513044.
7. Мэн, Б.; Вайнберг, WH (1996). «Динамические исследования методом Монте-Карло моделей молекулярно-лучевого эпитаксиального роста: межфазное масштабирование и морфология». Поверхностная наука . Эльзевир Б.В. 364 (2): 151–163. Бибкод : 1996SurSc.364..151M. дои : 10.1016/0039-6028(96)00597-3. ISSN  0039-6028.
8. Янг, WM; Элкок, EW (1966). «Исследование Монте-Карло миграции вакансий в бинарных упорядоченных сплавах: I». Труды Физического общества . Издательство ИОП. 89 (3): 735–746. Бибкод : 1966PPS....89..735Y. дои : 10.1088/0370-1328/89/3/329. ISSN  0370-1328.
9. Берле, Стефан А.; Усами, Такао; Гусев, Андрей А. (2006). «Новый подход многомасштабного моделирования для прогнозирования механических свойств наноматериалов на основе полимеров». Полимер . Эльзевир Б.В. 47 (26): 8604–8617. doi :10.1016/j.polymer.2006.10.017. ISSN  0032-3861.
10. Д. Р. Кокс и Х. Д. Миллер, Теория случайных процессов (Метуэн, Лондон), 1965, стр. 6–7.
11. Гиллеспи, Дэниел Т. (1976). «Общий метод численного моделирования стохастической временной эволюции связанных химических реакций». Журнал вычислительной физики . Эльзевир Б.В. 22 (4): 403–434. Бибкод : 1976JCoPh..22..403G. дои : 10.1016/0021-9991(76)90041-3. ISSN  0021-9991.
12. Фихторн, Кристен А .; Вайнберг, WH (15 июля 1991 г.). «Теоретические основы динамического моделирования Монте-Карло». Журнал химической физики . Издательство АИП. 95 (2): 1090–1096. Бибкод : 1991JChPh..95.1090F. дои : 10.1063/1.461138. ISSN  0021-9606.
13. AF Voter, Введение в кинетический метод Монте-Карло, в книге «Радиационные эффекты в твердых телах», под редакцией К.Е. Сикафуса и Е.А. Котомина (Springer, Издательское подразделение НАТО, Дордрехт, Нидерланды, 2005).
14. APJ Янсен, Введение в моделирование поверхностных реакций Монте-Карло, конденсированное вещество, абстрактное cond-mat/0303028.
15. Чаттерджи, Абхиджит; Влахос, Дионисиос Г. (28 февраля 2007 г.). «Обзор пространственных микроскопических и ускоренных кинетических методов Монте-Карло». Журнал компьютерного дизайна материалов . ООО «Спрингер Сайенс энд Бизнес Медиа». 14 (2): 253–308. Бибкод : 2007JCMD...14..253C. doi : 10.1007/s10820-006-9042-9. ISSN  0928-1045. S2CID  53336314.
16. Чотия, Амодсен; Вито, Матье; Фогт, Тибо; Компарат, Дэниел; Пийе, Пьер (30 апреля 2008 г.). «Кинетическое моделирование дипольной блокады методом Монте-Карло в эксперименте по возбуждению Ридберга». Новый журнал физики . Издательство ИОП. 10 (4): 045031. arXiv : 0803.4481 . Бибкод : 2008NJPh...10d5031C. дои : 10.1088/1367-2630/10/4/045031 . ISSN  1367-2630.
17. Ди Джезу, Джакомо; Лельевр, Тони; Ле Петрек, Дориан; Некту, Борис (2016). «Модели скачка Маркова и теория переходного состояния: подход квазистационарного распределения». Фарадеевские дискуссии . 195 : 469–495. arXiv : 1605.02643 . Бибкод : 2016FaDi..195..469D. дои : 10.1039/C6FD00120C. ISSN  1364-5498. PMID  27740662. S2CID  25564764.
18. Лельевр, Тони (2018). «Математические основы методов ускоренной молекулярной динамики». В Андреони, Ванда; Ага, Сидни (ред.). Справочник по моделированию материалов . Спрингер. стр. 773–803. arXiv : 1801.05347 . дои : 10.1007/978-3-319-44677-6_27. ISBN 978-3-319-44677-6.
19. Мартин-Брагадо, Игнасио; Тиан, С.; Джонсон, М.; Кастрильо, П.; Пиначо, Р.; Рубио, Дж.; Джарайс, М. (2006). «Моделирование заряженных дефектов, механизмов диффузии примесей и активации для моделирования TCAD с использованием кинетического Монте-Карло». Ядерные приборы и методы в физических исследованиях. Раздел B: Взаимодействие пучков с материалами и атомами . Эльзевир Б.В. 253 (1–2): 63–67. Бибкод : 2006НИМПБ.253...63М. дои :10.1016/j.nimb.2006.10.035. ISSN  0168-583X.
20. Мейсон, доктор медицинских наук; Хадсон, Т.С.; Саттон, AP (январь 2005 г.). «Быстрый вызов истории состояний в кинетическом моделировании Монте-Карло с использованием ключа Зобриста». Компьютерная физика. Коммуникации . 165 (1): 37–48. Бибкод : 2005CoPhC.165...37M. дои : 10.1016/j.cpc.2004.09.007.
21. Далла Торре, Дж.; Боке, Ж.-Л.; Доан, Невада; Адам, Э.; Барбу, А. (2005). «JERK, кинетическая модель Монте-Карло на основе событий для прогнозирования эволюции микроструктуры материалов под облучением». Философский журнал . Информа ЮК Лимитед. 85 (4–7): 549–558. Бибкод : 2005PMag...85..549D. дои : 10.1080/02678370412331320134. ISSN  1478-6435. S2CID  96878847.
22. Опплеструп, Томас; Булатов Василий Владимирович; Гилмер, Джордж Х.; Калос, Малвин Х.; Садыг, Бабак (4 декабря 2006 г.). «Алгоритм Монте-Карло первого прохода: диффузия без всех прыжков». Письма о физических отзывах . Американское физическое общество (APS). 97 (23): 230602. Бибкод : 2006PhRvL..97w0602O. doi : 10.1103/physrevlett.97.230602. ISSN  0031-9007. ПМИД  17280187.

Внешние ссылки

• Трехмерное кинетическое моделирование Монте-Карло на «битовом языке»
• KMC-моделирование неустойчивости Плато-Релея
• KMC-моделирование ГЦК-вицинальной (100)-поверхностной диффузии
• Стохастическая кинетическая модель среднего поля (даёт результаты, аналогичные решеточной кинетической модели Монте-Карло, однако гораздо более экономична и проще в реализации — предоставляется программный код с открытым исходным кодом)