Multicanonical ensemble

In statistics and physics, multicanonical ensemble (also called multicanonical sampling or flat histogram) is a Markov chain Monte Carlo sampling technique that uses the Metropolis–Hastings algorithm to compute integrals where the integrand has a rough landscape with multiple local minima. It samples states according to the inverse of the density of states,^[1] which has to be known a priori or be computed using other techniques like the Wang and Landau algorithm.^[2] Multicanonical sampling is an important technique for spin systems like the Ising model or spin glasses.^[1][3][4]

In systems with a large number of degrees of freedom, like spin systems, Monte Carlo integration is required. In this integration, importance sampling and in particular the Metropolis algorithm, is a very important technique.^[3] However, the Metropolis algorithm samples states according to ${\displaystyle \exp(-\beta E)}$ where beta is the inverse of the temperature. This means that an energy barrier of ${\displaystyle \Delta E}$ on the energy spectrum is exponentially difficult to overcome.^[1] Systems with multiple local energy minima like the Potts model become hard to sample as the algorithm gets stuck in the system's local minima.^[3] This motivates other approaches, namely, other sampling distributions.

Multicanonical ensemble uses the Metropolis–Hastings algorithm with a sampling distribution given by the inverse of the density of states of the system, contrary to the sampling distribution ${\displaystyle \exp(-\beta E)}$من خوارزمية متروبوليس. ^{[ 1 ]} مع هذا الاختيار، يكون عدد الحالات التي يتم أخذ عينات منها عند كل طاقة ثابتًا في المتوسط، أي أنها محاكاة ذات "مخطط توزيع مسطح" للطاقة. يؤدي هذا إلى خوارزمية لم تعد فيها حواجز الطاقة صعبة التجاوز. ميزة أخرى مقارنةً بخوارزمية متروبوليس هي أن أخذ العينات مستقل عن درجة حرارة النظام، مما يعني أن محاكاة واحدة تسمح بتقدير المتغيرات الديناميكية الحرارية لجميع درجات الحرارة (ومن هنا جاء اسم "متعددة الكانونية"): عدة درجات حرارة. يُعد هذا تحسنًا كبيرًا في دراسة انتقالات الطور من الدرجة الأولى . ^{[ 1 ]}

تكمن أكبر مشكلة في إجراء عملية التجميع متعدد المعايير في ضرورة معرفة كثافة الحالات مسبقًا . ^{[ 2 ] [ 3 ]} ومن أهم المساهمات في أخذ العينات متعددة المعايير خوارزمية وانغ ولاندو ، التي تتقارب تقاربًا مقاربًا إلى مجموعة متعددة المعايير أثناء حساب كثافة الحالات خلال عملية التقارب. ^{[ 2 ]}

لا يقتصر استخدام المجموعة متعددة المعايير على الأنظمة الفيزيائية، بل يمكن تطبيقها على الأنظمة المجردة التي لها دالة تكلفة F. وباستخدام كثافة الحالات بالنسبة إلى F، تصبح الطريقة عامة لحساب التكاملات متعددة الأبعاد أو إيجاد القيم الدنيا المحلية. ^{[ 5 ]}

لنفترض نظامًا ومساحة طوره$أوميغا$يتميز بتكوين${\displaystyle {\boldsymbol {r}}}$في$أوميغا$ودالة "تكلفة" F من فضاء طور النظام إلى فضاء أحادي البعد${\displaystyle \Gamma }$:${\displaystyle F(\Omega )=\Gamma =[\Gamma _{\min },\Gamma _{\max }]}$، طيف F.

مثال: يُعد نموذج إيزينغ ذو المواقع N مثالاً على هذا النوع من الأنظمة؛ حيث أن فضاء الطور هو فضاء طور منفصل مُحدد بجميع التكوينات الممكنة لـ N من اللفات المغزلية.${\displaystyle {\boldsymbol {r}}=(\sigma _{1},\ldots ,\sigma _{i},\ldots ,\sigma _{N})}$أين${\displaystyle \sigma _{i}\in \{-1,1\}}$دالة التكلفة هي دالة هاميلتون للنظام: ${\displaystyle H({\boldsymbol {r}})=-\sum _{\langle i~j\rangle }J_{ij}(1-\sigma _{i}\sigma _{j}),}$ أين${\displaystyle <i,j>}$هو المجموع على الأحياء و${\displaystyle J_{ij}}$هي مصفوفة التفاعل. طيف الطاقة هو${\displaystyle \Gamma =[E_{\min },E_{\max }]}$وهو ما يعتمد في هذه الحالة على الحالة الخاصة${\displaystyle J_{ij}}$مستخدم. إذا كان كل شيء${\displaystyle J_{ij}}$هي 1 (نموذج إيزينغ المغناطيسي الحديدي)،${\displaystyle E_{\min }=0}$(على سبيل المثال، جميع الدورات تساوي 1.) و${\displaystyle E_{\max }=2DN}$(نصف الدورات لأعلى، ونصف الدورات لأسفل). لاحظ أيضًا أنه في هذا النظام،${\displaystyle \Gamma \in \mathbb {Z} }$

حساب الكمية المتوسطة${\displaystyle \langle Q\rangle }$يتطلب حساب التكامل على فضاء الطور ما يلي:

${\displaystyle \langle Q\rangle =\int _{\Omega}Q({\boldsymbol {r}})P_{r}({\boldsymbol {r}})\,d{\boldsymbol {r}}}$

أين${\displaystyle P_{r}({\boldsymbol {r}})}$يمثل وزن كل ولاية (على سبيل المثال)${\displaystyle P_{r}({\boldsymbol {r}})=1/V}$(تتوافق مع الحالات الموزعة بشكل منتظم).

عندما لا تعتمد Q على الحالة المحددة ولكن فقط على قيمة F المحددة لتلك الحالة${\displaystyle F({\boldsymbol {r}})=F_{\boldsymbol {r}}}$، الصيغة لـ${\displaystyle \langle Q\rangle }$يمكن إجراء التكامل على f بإضافة دالة ديراك دلتا، ويمكن كتابتها على النحو التالي:

$\begin{aligned}\langle Q\rangle &=\int _{\Gamma _{\min }}^{\Gamma _{\max }}\int _{\Omega }Q(F_{\boldsymbol {r}})P_{r}(F_{\boldsymbol {r}})\delta (f-F_{\boldsymbol {r}})\,d{\boldsymbol {r}}\,df\\&=\int _{\Gamma _{\min }}^{\Gamma _{\max }}Q(f)\int _{\Omega }\delta (f-F_{\boldsymbol {r}})P_{r}(F_{\boldsymbol {r}})\,d{\boldsymbol {r}}\,df\\&=\int _{\Gamma _{\min }}^{\Gamma _{\max }}Q(f)P(f)\,df\\\end{aligned}}}$

أين

${\displaystyle P(f)=\int _{\Omega }P_{r}(r)\delta (fF({\boldsymbol {r}}))\,d{\boldsymbol {r}}}$

هو التوزيع الهامشي لـ F.

مثال: نظام متصل بحمام حراري عند درجة حرارة معكوسة${\displaystyle \beta }$يُعد هذا مثالاً لحساب هذا النوع من التكامل. على سبيل المثال، يتم ترجيح متوسط ​​طاقة النظام بمعامل بولتزمان : ${\displaystyle \langle E\rangle ={\frac {1}{V}}\int _{\Omega}H_{\boldsymbol {r}}{\frac {e^{-\beta H_{\boldsymbol {r}}}}{Z}}d{\boldsymbol {r}}}$ أين ${\displaystyle Z={\frac {1}{V}}\int _{\Omega }e^{-\beta H_{\boldsymbol {r}}}d{\boldsymbol {r}}.}$ التوزيع الهامشي${\displaystyle P(E)}$يُعطى بواسطة $// (E-H_{\boldsymbol {r}})d{\boldsymbol {r}}=e^{-\beta E}\rho (E)}$ أين${\displaystyle \rho (E)}$هي كثافة الحالات. متوسط ​​الطاقة${\displaystyle \langle E\rangle }$ثم يتم تحديده بواسطة ${\displaystyle \langle E\rangle =\int _{E_{\min }}^{E_{\max }}EP(E)\,dE}$

عندما يمتلك النظام عددًا كبيرًا من درجات الحرية، يكون التعبير التحليلي لـ${\displaystyle \langle Q\rangle }$غالباً ما يكون الحصول عليها صعباً، وعادةً ما يتم استخدام تكامل مونت كارلو في حساب${\displaystyle \langle Q\rangle }$في أبسط صيغة، تختار الطريقة N حالة موزعة بشكل منتظم${\displaystyle {\boldsymbol {r}}_{i}\in \Omega }$ويستخدم المُقدِّر

${\displaystyle {\overline {Q}}_{N}=\sum _{i=1}^{N}Q({\boldsymbol {r}}_{i})VP_{r}({\boldsymbol {r}}_{i})}$

للحوسبة${\displaystyle \langle Q\rangle }$لأن${\displaystyle {\overline {Q}}_{N}}$يتقارب بشكل شبه مؤكد إلى${\displaystyle \langle Q\rangle }$بحسب قانون الأعداد الكبيرة القوي :

${\displaystyle \lim _{N\rightarrow \infty }{\overline {Q}}_{N}=\langle Q\rangle .}$

تتمثل إحدى المشكلات النموذجية لهذا التقارب في أن تباين Q يمكن أن يكون مرتفعًا للغاية، مما يؤدي إلى جهد حسابي كبير لتحقيق نتائج معقولة.

لتحسين هذا التقارب، تم اقتراح خوارزمية متروبوليس-هاستينغز . وبشكل عام، تعتمد فكرة طرق مونت كارلو على استخدام أخذ العينات المهمة لتحسين تقارب المُقدِّر.${\displaystyle {\overline {Q}}_{N}}$عن طريق أخذ عينات من الولايات وفقًا لتوزيع عشوائي${\displaystyle \pi ({\boldsymbol {r}})}$واستخدم المُقدِّر المناسب:

${\displaystyle {\overline {Q}}_{N}=\sum _{i=1}^{N}Q({\boldsymbol {r}}_{i})\pi ^{-1}({\boldsymbol {r}}_{i})P_{r}({\boldsymbol {r}}_{i})}$.

يُعمم هذا المُقدِّر مُقدِّر المتوسط ​​للعينات المسحوبة من توزيع عشوائي. لذلك، عندما${\displaystyle \pi ({\boldsymbol {r}})}$إذا كان توزيعًا منتظمًا، فإنه يتوافق مع التوزيع المستخدم في أخذ العينات المنتظمة أعلاه.

عندما يكون النظام نظامًا فيزيائيًا متصلًا بحمام حراري، فإن كل حالة${\displaystyle {\boldsymbol {r}}}$يتم ترجيحها وفقًا لعامل بولتزمان ،${\displaystyle P_{r}({\boldsymbol {r}}_{i})\propto \exp(-\beta F_{\boldsymbol {r}})}$في مونت كارلو، يتم تحديد المجموعة الكنسية عن طريق اختيار${\displaystyle \pi ({\boldsymbol {r}})}$أن يكون متناسباً مع${\displaystyle P_{r}({\boldsymbol {r}}_{i})}$في هذه الحالة، يتوافق المُقدِّر مع المتوسط ​​الحسابي البسيط:

${\displaystyle {\overline {Q}}_{N}={\frac {1}{N}}\sum _{i=1}^{N}Q({\boldsymbol {r}}_{i})}$

تاريخياً، حدث هذا لأن الفكرة الأصلية ^{[ 6 ]} كانت استخدام خوارزمية متروبوليس-هاستينغز لحساب المتوسطات على نظام متصل بحمام حراري حيث يتم تحديد الوزن بواسطة عامل بولتزمان،${\displaystyle P({\boldsymbol {x}})\propto \exp(-\beta E({\boldsymbol {r}}))}$[ ^{3 ]​}

على الرغم من أن توزيع المعاينة غالباً ما يكون${\displaystyle \pi }$يتم اختيار توزيع الوزن${\displaystyle P_{r}}$ليس بالضرورة أن يكون الأمر كذلك. من الحالات التي لا يُعد فيها التجميع الكنسي خيارًا فعالًا هي عندما يستغرق التقارب وقتًا طويلًا جدًا. ^{[ 1 ]} يحدث هذا عندما تحتوي الدالة F على عدة نقاط دنيا محلية. تزداد التكلفة الحسابية للخوارزمية للخروج من منطقة معينة ذات نقطة دنيا محلية بشكل أُسّي مع قيمة دالة التكلفة لتلك النقطة. أي، كلما زاد عمق النقطة الدنيا، زاد الوقت الذي تقضيه الخوارزمية فيها، وازدادت صعوبة الخروج منها (تزداد أُسّيًا مع عمق النقطة الدنيا المحلية).

إحدى طرق تجنب الوقوع في الحد الأدنى المحلي لدالة التكلفة هي جعل أسلوب أخذ العينات "غير مرئي" بالنسبة للحد الأدنى المحلي. وهذا هو أساس التجميع متعدد المعايير.

يتم تعريف المجموعة متعددة المعايير عن طريق اختيار توزيع المعاينة ليكون

${\displaystyle \pi ({\boldsymbol {r}})\propto {\frac {1}{P(F_{\boldsymbol {r}})}}}$

أين${\displaystyle P(f)}$يمثل التوزيع الهامشي لـ F المعرف أعلاه. ونتيجةً لهذا الاختيار، فإن متوسط ​​عدد العينات التي لها قيمة معينة لـ f ، أي m(f)، يُعطى بالعلاقة التالية:

${\displaystyle m(f)=\int _{\Omega }\delta (f-F_{\boldsymbol {r}})\pi ({\boldsymbol {r}})P_{r}({\boldsymbol {r}})\,d{\boldsymbol {r}}\propto \int _{\Omega }\delta (f-F_{\boldsymbol {r}})P_{r}({\boldsymbol {r}}){\frac {1}{P(F_{\boldsymbol {r}})}}d{\boldsymbol {r}}={\frac {1}{P(f)}}\int _{\Omega }\delta (f-F_{\boldsymbol {r}})P_{r}({\boldsymbol {r}})d{\boldsymbol {r}}=1}$

أي أن متوسط ​​عدد العينات لا يعتمد على f : تُؤخذ عينات من جميع التكاليف f بالتساوي بغض النظر عن احتمالية حدوثها. وهذا ما يفسر تسمية "المخطط البياني المسطح". بالنسبة للأنظمة المتصلة بحمام حراري، يكون أخذ العينات مستقلاً عن درجة الحرارة، وتتيح محاكاة واحدة دراسة جميع درجات الحرارة.

مثال: في نموذج إيزينغ المغناطيسي الحديدي ذي N موقعًا (كما هو موضح في القسم السابق)، يمكن حساب كثافة الحالات تحليليًا. في هذه الحالة، يمكن استخدام مجموعة متعددة الكانونات لحساب أي كمية أخرى Q عن طريق أخذ عينات من النظام وفقًا لـ${\displaystyle P({\boldsymbol {r}})}$وباستخدام المُقدِّر المناسب${\displaystyle {\overline {Q}}}$تم تعريفها في القسم السابق.

كما هو الحال في أي طريقة مونت كارلو أخرى ، توجد ارتباطات بين العينات المسحوبة من${\displaystyle P({\boldsymbol {r}})}$يُعد زمن النفق مقياسًا نموذجيًا للترابط . يُعرَّف زمن النفق بعدد خطوات ماركوف (في سلسلة ماركوف) اللازمة للمحاكاة لإتمام دورة كاملة بين الحد الأدنى والحد الأقصى لطيف F. من دوافع استخدام زمن النفق أنه عند عبوره الطيف، يمر عبر منطقة الحد الأقصى لكثافة الحالات، مما يُقلل من ترابط العملية. من ناحية أخرى، يضمن استخدام الدورات الكاملة أن النظام يمر عبر كامل الطيف.

نظرًا لأن المدرج التكراري مسطح على المتغير F ، يمكن اعتبار المجموعة متعددة القنوات عملية انتشار (أي مسار عشوائي ) على خط أحادي البعد لقيم F. ويقتضي التوازن التفصيلي للعملية عدم وجود انحراف فيها. ^{[ 7 ]} وهذا يعني أن زمن النفق، في الديناميكيات المحلية، يجب أن يتناسب مع عملية الانتشار، وبالتالي يجب أن يتناسب زمن النفق تربيعيًا مع حجم الطيف ، N.

${\displaystyle \tau _{tt}\propto N^{2}}$

مع ذلك، في بعض الأنظمة (ويُعد نموذج إيزينغ الأكثر نموذجية)، يعاني التوسع من تباطؤ حرج:${\displaystyle N^{2+z}}$أين${\displaystyle z>0}$يعتمد ذلك على النظام المحدد. ^{[ 4 ]}

طُوِّرت ديناميكيات غير محلية لتحسين التناسب إلى تناسب تربيعي ^{[ 8 ]} (انظر خوارزمية وولف )، متجاوزةً التباطؤ الحرج. ومع ذلك، لا يزال السؤال مطروحًا حول ما إذا كانت هناك ديناميكيات محلية لا تعاني من التباطؤ الحرج في أنظمة الدوران مثل نموذج إيزينغ.