روش متروپلیس (Metropolis Algorithm)، در ریاضیات (Mathematics)
انواع روش های عددی (Numerical Methods) را در آموزش زیر شرح دادیم :
روش متروپلیس (Metropolis Algorithm) :
الگوریتم زنجیر مارکوف مونت کارلو برای نمونه گیری از توزیع های دلخواه
توضیح ساده: الگوریتم متروپلیس یک روش زنجیر مارکوف مونت کارلو (MCMC) است که برای تولید دنباله ای از نمونه های تصادفی از یک توزیع احتمال دلخواه (که ممکن است نرمالایز نشده باشد) استفاده می شود. این الگوریتم در سال ۱۹۵۳ توسط نیکلاس متروپلیس و همکارانش برای شبیه سازی سیستم های مولکولی ارائه شد. ایده اصلی این است که یک زنجیر مارکوف ساخته شود که توزیع تعادلی آن همان توزیع مورد نظر باشد. با حرکت در فضای حالت و پذیرش یا رد کردن حرکات بر اساس یک معیار احتمال، به تدریج نمونه هایی از توزیع هدف بدست می آید.
شرح گام به گام: الگوریتم متروپلیس برای نمونه گیری از توزیع π(x) (متناسب با تابع f(x)):
۱. یک حالت اولیه x₀ و یک توزیع پیشنهاد (Proposal Distribution) q(y|x) (مثلا یک توزیع نرمال حول x) انتخاب کنید.
۲. برای t = ۰,۱,۲,... تا تعداد نمونه مورد نیاز:
- یک کاندید y از q(y|xₜ) تولید کنید.
- نسبت پذیرش را محاسبه کنید:
\[ A = \min\left(1, \frac{f(y) q(x_t|y)}{f(x_t) q(y|x_t)}\right) \]- یک عدد تصادفی u ~ Uniform(0,1) تولید کنید.
- اگر u < A، xₜ₊₁ = y (پذیرش)، در غیر این صورت xₜ₊₁ = xₜ (رد).
۳. نمونه های اولیه (مرحله گرم شدن - Burn-in) را دور بریزید.
۴. نمونه های باقیمانده تقریبا از توزیع هدف پیروی می کنند.
مثال عددی: شبیه سازی توزیع بولتزمن برای یک سیستم مولکولی. f(x) = exp(-E(x)/kT) که E انرژی است. الگوریتم متروپلیس با پیشنهاد جابجایی تصادفی مولکول ها، پیکربندی های با انرژی پایین تر را با احتمال بیشتر می پذیرد و به توزیع تعادلی می رسد. این روش پایه ای برای دینامیک مولکولی مونت کارلو است.
مزایا: امکان نمونه گیری از توزیع های پیچیده و با ابعاد بالا، فقط نیاز به تابع f (بدون نرمالایز).
معایب: نمونه ها همبسته هستند (نه مستقل). نیاز به تنظیم توزیع پیشنهاد. تعیین زمان گرم شدن و همگرایی دشوار است.
کاربردها: در فیزیک آماری، در یادگیری ماشین (استنباط بیزی)، در آمار، در شیمی محاسباتی.
نکته: الگوریتم متروپلیس-هیستینگز (Metropolis-Hastings) تعمیم این روش با توزیع پیشنهاد نامتقارن است.
