الگوریتم‌ها و روش‌های مونت‌کارلو

Sarp

Sarp

مدیر بازنشسته
روش‌های مونت‌کارلو یک دسته از الگوریتم‌های محاسباتی هستند که بر اساس تکرار تصادفی نمونه برداری برای محاسبهٔ نتایج هستند.روشهای مونت کارلو همچنین در زمان شبیه سازی سیستم‌های فیزیکی و ریاضیاتی نیز استفاده می‌شوند.به دلیل اتکای این روش به تکرار محاسبات و اعداد تصادفی و اعداد شبه تصادفی، مناسب برای محاسبه توسط کامپیوتر است.روشهای مونت کارلو معمولا زمانی استفاده می‌شوند که امکان محاسبهٔ نتیجهٔ دقیق با یک الگوریتم قطعی(Deterministic Algorithm) نباشد. اصطلاح مونت کارلو در سال ۱۹۴۰ توسط فعالیت‌های فیزیکدانان بر روی پروژهٔ بمب اتمی در آزمایشگاه بین المللی لس آلاموس مطرح شد.

خلاصه
روشهای مونت کارلوی منحصر به فرد وجود ندارند مگر، عباراتی که دسته‌ای از دیدگاه‌های بزرگ و پراستفاده را مطرح می‌کند.هر چند این دیدگاه‌ها گرایش به دنبال کردن الگوی خاصی دارند:

  • تعریف دامنهٔ ورودی‌های ممکن
  • تولید ورودی‌های تصادفی از دامنه، و اجرای یک عملیات قطعی بر روی آنها
  • جمع بندی نتایج حاصل از تک تک محاسبات در نتیجهٔ نهایی
برای مثال مقدار عددπ را می‌توان با روش مونت کارلو به صورت تقریبی به دست آورد.مربعی به مساحت ۱ رسم کنید و سپس دایره‌ای در آن محاط کنید، حال اشیای کوچکی را روی آن پراکنده کنید(مثل دانه‌های برنج یا شن)، اگر اشیا به صورت یکنواخت پراکنده شده باشند آنگاه نسبت اشیای داخل دایره به اشیای داخل مربع تقریبا بایدπ/۴ باشد، که نسبت مساحت دایره به مساحت مربع است. بنابراین اگر ما تعداد اشیای داخل دایره را، ضرب در ۴، وتقسیم بر تعداد اشیای داخل مربع بکنیم، مقدار تقریبی π به دست می‌آید.
توجه داشته باشیم که سه گام اشاره شده در بالا در این مثال همانطور که می‌بینیم اجرا شده‌است.

تاریخچه
مونت‌کارلو (در فرانسوی: Monte-Carlo) نام منطقه‌ای است بسیار مشهور در کشور خودمختار موناکو واقع در اروپای غربی. جمعیت ساکن در مونت‌کارلو در حدود ۳۰۰۰ نفر را شامل می‌شود. منطقه مونت‌کارلو، ثروتمندترین منطقه از کشور خودمختار موناکو است.[۱]


نام «مونت‌کارلو»
ریشه نام «مونت‌کارلو» از زبان ایتالیایی است و به اصلیت اسم شاهزاده کارلو سوم از موناکو بر می‌گردد که زیر نفوذ و حمایت دربار ایتالیا قرار داشت. تا قبل از سال ۱۸۶۱ که موناکو به شکلی خودمختار درآمد، زبان رسمی ایتالیایی بود، اما در یکصد سال گذشته، زبان رسمی به فرانسوی تغییر داده شد.[۲]

استنلی اولام، انریکو فرمی و جان فون نیومن شهرت فراوان یافت. این اسم مبدایی به یک کازینو ای در موناکو است که عموی اولام برای قمار پول قرض می‌کرده‌است.تصادفی بودن و تکرار طبیعی فرایندها مشابه فعالیت‌های در کازینوها است. نام «مونت کارلو» توسط تحقیقات فیزیکدانانی چون
روش‌های تصادفی برای محاسبه و آزمایش (که عموما به عنوان شبیه سازی تصادفی شناخته می‌شوند) را بدون تردید می‌توان تا اولین پیشگامان نظریه احتمال دنبال کرد (سوزن بافون، کار جزیی روی نمونه‌ها توسط ویلیام گوست)، ولی به طور ویژه می‌توان آن را در دوران قبل از محاسبات الکترونیکی دنبال کرد.تفاوت اساسی که معمولا دربارهٔ روش شبیه سازی مونت کارلو بیان می‌شود این است که به طور اصولی نوع روش شبیه سازی را وارون می‌کند و نظر مسایل را با یافتن مدل مشابه احتمالی به خود جلب می‌کند. روش‌های پیشین برای شبیه سازی و مدل سازی آماری عموما عکس این کار را انجام می‌دادند :استفاده از شبیه سازی برای امتحان کردن مسایل مشخص قطعی.
به هر حال همان طور که میدانیم مثال‌های دیدگاه «وارون»به صورت تاریخی نیز وجود دارند، آنها تا قبل از امدن روش مونت کارلو به عنوان یک روش عمومی در نظر گرفته نمی‌شدند.
شاید معروفترین استفادهٔ اخیر از این روش توسط انریکو فرمی در سال۱۹۳۰ باشد، هنگامی که او از یک روش تصادفی برای دستیابی به خواص نوترون تازه کشف شده، استفاده کرد.همچنین روشهای مونت کارلو مرکزیت شبیه سازی مورد نیاز در پروژهٔ منهتن را داشتند اگرچه که در آن زمان در استفاده از ابزارهای محاسباتی در محدودیت جدی قرار داشتند. بنابراین مونت کارلو در زمانی مورد مطالعه و بررسی توسط دانشمندان قرار گرفت که کامپیوتر‌های الکترونیکی برای اولین بار پا به عرصه گذاشتند.(از سال ۱۹۴۵ تا امروز)
در ۱۹۵۰ در لوس آلاموس برای تحقیقات جدیدی که دربارهٔ بمب‌های هیدروژنی آغاز شده بود مورد استفاده قرار گرفت و در رشته‌های فیزیک و شیمی فیزیک و تحقیق در عملیات مشهور شد.
شرکت رند(Rand) و نیروی هوایی ایالات متحده دو سازمان مرتبط برای جمع آوری و ارسال اطلاعات دربارهٔ روشهای مونت کارلو در طول این زمان بوده‌است، و کاربردهای گستردهٔ این روش را یافته‌اند.
استفاده از روش مونت کارلو نیاز به استفادهٔ مقادیر زیادی اعداد تصادفی دارد و این استفاده باعث کنار رفتن و عدم گسترش زاینده‌های اعداد شبه تصادفی بود.

کاربرد ها
شبیه سازی مونت کارلو به طور ویژه‌ای در مطالعهٔ سیستم‌ها با درجه آزادی زوج متعدد مورد استفاده قرار می‌گیرد مثل مایعات، مواد متخلخل، مایعات شدیدا زوج و ساختارهای حفره دار(مانند ساختار حفره دار پات). روش‌های مونت کارلو به صورت وسیعی در مدل سازی پدیده‌ها با مقادیر قابل توجهی عدم اطمینان در ورودی‌ها مورد استفاده قرار می‌گیرد مثل:
محاسبهٔ ریسک در تجارت (نمونه کاربرد آن در اقتصاد، مدل سازی تصادفی است)استفادهٔ کلاسیک از این روش‌ها برای ارزیابی و محاسبهٔ انتگرال‌های معین، به طور خاص برای انتگرال‌های چند بعدی باشد با شرایط مرزی پیچیده، استفاده می‌شود.
روش‌های مونت کارلو همچنین برای محاسبهٔ ارزش سرمایه شرکت‌ها، ارزیابی سرمایهٔ پروژه‌ها نیز استفاده می‌شود.
همچنین روش‌های مونت کارلو در فیزیک محاسباتی، شیمی فیزیک و زمینه‌های مرتبط با این دو کاربرد فراوان دارد.
مونت کارلو علاوه بر این، تحت تاثیر بسزای خود را در حل معادله دیفرانسیل‌های زوج انتگرالی در زمینهٔ تشعشعانتقال انرژی ثابت کرده‌است پس بنا براین این روش برای آشکار سازی جهانی محاسبات که مدل‌های مجازی سه بعدی تصاویر فوتوریالیستیک را تولید می‌کند، مورد استفاده قرار می‌گیرد. و
روش‌های مونت کارلو در زمینه‌های بسیاری نیز در ریاضیات محاسباتی مورد استفاده قرار می‌گیرد، که فقط یک خوش شانس می‌تواند نتیجهٔ صحیح بگیرد. یک مثال کلاسیک، الگوریتم رابین است که برای آزمایش اول بودن اعداد مورد استفاده قرار می‌گیرد.
همچنین الگوریتم لاس وگاس نیز به همین موضوع می‌پردازد ولی با ایده‌ای متفاوت.

زمینه‌های کاربرد مونت کارلو

  • گرافیک، به طور خاص خط اثر پرتو
  • مدل سازی جا به جایی نور در رشته‌های بیولوژیک
  • مونت کارلو در اقتصاد
  • مهندسی اطمینان
  • در شبیه سازی پیچش برای پیش بینی ساختار پروتین
  • در تخقیقات تجهیزات نیم رسانا، برای مدل سازی جا به جایی حامل‌های کنونی
  • در محیط زیست، بررسی آلاینده‌ها
  • کاربرد مونت کارلو در فیزیک استاتیک
  • در طراحی احتمالاتی برای شبیه سازی و درک تغییرپذیری
  • در شیمی فیزیک، به طور خاص برای شبیه سازی قالب‌های اتمهای درگیر
  • در علوم کامپیوتر:
    • الگوریتم لاس وگاس
    • LURCH
    • Computer Go
    • بازی‌ها
  • کاربردهای گسترده در فیزیک هسته‌ای
کاربرد در ریاضیات
به طور کلی، روش‌های مونت کارلو در ریاضیات برای حل مسایل متنوعی به وسیلهٔ تولید اعداد تصادفی مناسب و مشاهدهٔ این که جز کسری اعداد از خواص خاصی پیروی می‌کند، استفاده می‌کند.این روش برای به دست آوردن جواب‌های عددی سوالاتی که برای حل باید از تجزیه استفاده کنیم، بسیار مفید است.
رایج ترین کاربرد مونت کارلو، انتگرال گیری مونت کارلو است.
انتگرال گیری
روش‌های قطعی انتگرال گیری عددی به وسیله دریافت عدد نمونه‌های فاصله دار یکنواخت از یک تابع است. به طور کلی، این روش برای توبع یک متغییری بسیار خوب جواب می‌دهد. در حالی که برای تابعی از بردارها، روش‌های تربیع قطعی بی تاثیراند.
برای انتگرال گیری عددی از یک تابع دو متغییره از بردارها، نقاط فاصله دار به صورت چهارخانه به طور مساوی روی صفحه دو بعدی مورد نیاز است.
برای نمونه یک صفحهٔ ۱۰x۱۰ نیاز به ۱۰۰ نقطه دارد.اگر بردار ما ۱۰۰ بعدی باشد، تقسیم بندی مورد نیاز روی صفحه، نیاز به
۱۰۱۰۰
(عدد گوگول)نقطه دارد که برای محاسبه بسیار بزرگ است.
روش مونت کارلو روشی را برای خروج از این رشد نمایی پیشنهاد می‌کند. تا زمانی که تابع مورد سوال یک تابع خوش رفتار است، به وسیله انتخاب تصادفی نقاط در فضای ۱۰۰ بعدی و گرفتن نوعی میانگین از مقادیر تابع در این نقاط، می‌تواند تخمین زده شود.با به کار گیری قانون اعداد بزرگ، این روش همگرایی به
را نشان می‌دهد.
روش‌های انتگرال گیری:

  • مدل نمونه برداری مستقیم
    • نمونه برداری با اهمییت
    • نمونه برداری طبقه به طبقه
    • نمونه برداری طبقه به طبقهٔ بازگشتی
    • الگوریتم وگاس
  • راه تصادفی مونت کارلو شامل زنجیرهای مارکوو
    • الگوریتم متروپولیس-هاستینگ
  • مدل سازی گیبس
منابع




  • Arnaud Doucet, Nando de Freitas and Neil Gordon, Sequential Monte Carlo methods in practice, ۲۰۰۱, ISBN ۰-۳۸۷-۹۵۱۴۶-۶.
  • P. Kevin MacKeown, Stochastic Simulation in Physics, ۱۹۹۷, ISBN ۹۸۱-۳۰۸۳-۲۶-۳
  • Harvey Gould & Jan Tobochnik, An Introduction to Computer Simulation Methods, Part ۲, Applications to Physical Systems, ۱۹۸۸, ISBN ۰-۲۰۱-۱۶۵۰۴-X
  • C.P. Robert and G. Casella. «Monte Carlo Statistical Methods» (second edition). New York: Springer-Verlag, ۲۰۰۴, ISBN ۰-۳۸۷-۲۱۲۳۹-۶
  • R.Y. Rubinstein and D.P. Kroese (۲۰۰۷). «Simulation and the Monte Carlo Method» (second edition). New York: John Wiley & Sons, ISBN 978-0-470-17793-8.
  • Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller and Edward Teller, «Equation of State Calculations by Fast Computing Machines», Journal of Chemical Physics, volume ۲۱, p. ۱۰۸۷ (۱۹۵۳) (الگو:DOI)
  • N. Metropolis and S. Ulam, «The Monte Carlo Method», Journal of the American Statistical Association, volume ۴۴, number ۲۴۷, pp. ۳۳۵–۳۴۱ (۱۹۴۹) (الگو:DOI)
  • Fishman, G.S., (۱۹۹۵) Monte Carlo: Concepts, Algorithms, and Applications, Springer Verlag, New York.
  • Judgement under Uncertainty: Heuristics and Biases, ed. D. Kahneman and A. Tversky,(Cambridge University Press, ۱۹۸۲)
  • R. E. Caflisch, Monte Carlo and quasi-Monte Carlo methods, Acta Numerica vol. ۷, Cambridge University Press, ۱۹۹۸, pp. ۱-۴۹. [۱]

منبع

​
 
آخرین ویرایش:
Sarp

Sarp

مدیر بازنشسته
الگوريتم مونت كارلو ES

الگوريتم مونت كارلو ES

الگوريتم ES يا Exploring starts يكي از روش‌هاي يادگيري تقويتي مونت كارلو است. پيش از ارائه اين الگوريتم، لازم است برخي اصطلاحات، تعريف شود:



اين الگوريتم از چند گام تشكيل يافته است:

1- اختيار كردن يك سياست تصادفي
2- انجام دادن يك آزمايش Exploring starts با سياست جاري
3- تخمين اميد رياضي خروجي با ميانگين‌گيري كليه خروجي‌هاي بدست آمده از زوج‌هاي (s,a)
4- تغيير سياست جاري به سياست جديدي كه در هر حالت عملي را انجام مي‌دهد كه در شبيه‌سازي قبلي، بهترين خروجي را داشته است.
5- تكرار مراحل 2 الي 4.

اين سوال مطرح مي‌شود كه آزمايش يا تجربه ES (با شروع‌هاي كاوشگر يا Exploring (starts به چه معناست؟ تجربه ES، تجربه‌اي است كه در آن عامل، در اپيزودهايي قرار مي‌گيرد كه در انتخاب اولين عمل خود مختار نيست. اولين عمل، بصورت تصادفي انتخاب مي‌شود و همه اعمال مجاز در حالت اوليه، شانس يكساني براي انتخاب شدن دارند.

در اين الگوريتم، اگر تجربه ES نبود، با مشكل جدي مواجه مي‌شديم زيرا بنابر سياست جاري عامل، كه سياستي قطعي است، در هر حالت، تنها يك عمل شانس انتخاب شدن خواهد داشت و تبعاً تنها، Q همان زوج نيز محاسبه مي‌شود و ديگر انتخاب بهترين زوج اصلاً مفهومي نخواهد داشت. البته اگر سياست، قطعي نبود با اين مشكل مواجه نمي‌شديم (الگوريتم e-soft بر اين مبنا است كه بحث خواهد شد.)

در واقع الگوريتم ES از 2 فاز تشكيل يافته است:

فاز ارزيابي سياست (Evaluation)
فاز بهبود سياست (Improvement)

​
​

ممكن است اين سوال مطرح شود كه چه لزومي دارد تغيير سياست با توجه به ارزيابي انجام‌شده لزوما باعث بهبود سياست گردد؟ خوشبختانه اين مطلب، اثبات شده است. در اثبات اين امر، از قضيه بهبود سياست استفاده شده است. براي آگاهي از اين اثبات مي‌توانيد به بخش‌هاي 4.2 و 5.3 از كتاب يادگيري تقويتي اثر Sutton مراجعه نماييد.

شبه‌كد الگوريتم ES در ذيل آورده شده است:



​
در اينجا يك نكته ديگر را يادآور مي‌شويم و آن، اينكه الگوريتم‌هاي مونت كارلو در يادگيري تقويتي از يك ديدگاه به دو دسته ملاقات-اول و ملاقات-همه تقسيم مي‌شوند. (Fist-Visit, Every-Visit). در الگوريتم‌هاي ملاقات-اول، براي تخمين خروجي در يك وضعيت، تنها اولين باري كه آن وضعيت در اپيزود اتفاق مي‌افتد، در عمل ميانگين‌گيري شركت مي‌كند بنابراين در اين دسته الگوريتم‌ها، لزوما داشتن تعداد مناسب تجربه اپيزوديك، ضروري است اما در الگوريتم‌هاي ملاقات-همه، كليه دفعات مشاهده وضعيت، منظور مي‌شود.

منبع
​
 
آخرین ویرایش:
Sarp

Sarp

مدیر بازنشسته
شبه کد پیاده سازی الگوریتم مونت کارلو برای الگوریتم عقبگرد مسئله n وزیر:

شبه کد پیاده سازی الگوریتم مونت کارلو برای الگوریتم عقبگرد مسئله n وزیر:

کد: 
[LEFT]int ostimate _ n_ queens (int n)
   {
          index i , j , col [۱..n];
          int m , mprod , numnodes ;
          set _of_ index  prom _children;
          i = ۰;
          numnodes =۱ ;
          m = ۱;

        mprod  = ۱ ;
        while  ( m != ۰ && i != n ) {
        mprod = mprod * m ;
        numnodes  = numnodes + mprod * n;
        i ++;
        m = ۰ ;
        prom_childern  = Ø;
        for ( j = ۱ ; j ≤ n ; j++;) {
                col [i]  = j ;
                if ( promising(i)) {

         m++;
         prom_children = prom _ children U {i};
                 }
             }
             if ( m != ۰)  {
                 j = random selection from prom _childeren;
                 col [i];
              }
         }
         return numnodes;
      }[/LEFT]

منبع
 
آخرین ویرایش:
Sarp

Sarp

مدیر بازنشسته
به کارگيري الگوريتم هاي مونت کارلو در بررسي سيستم هاي فيزيکي

به کارگيري الگوريتم هاي مونت کارلو در بررسي سيستم هاي فيزيکي

خوب، قالبا از اين الگوريتم ها براي نوشتن برنامه هاي کامپوتري جهت شبيه سازي سيستم هاي فيزيکي استفاده مي گردد. بنابراين شناخت کارکرد دقيق سيستم فيزيکي اهميت بالايي دارد. مونت کارلو الگوريتم هاي بسياري دارد. اما روند کلي در تمام آنها تقريبا يکسان است.
بگذاريد يک مثال بزنيم. فرض کنيد يک جعبه داريم که از اتم هاي يک گاز تشکيل شده است. از مکانيک آماري مي دانيم که اگر به چنين سيستمي انرژي بدهيم انرژي جنبشي اتم هاي گاز بالا رفته و دماي جعبه بيشتر مي شود. هم چنين برعکس ، اگر جعبه در ابتداء دمايي داشته باشد و سپس با يک منبع در تماس باشد که بتواند گرما را از جعبه بگيرد، دماي جعبه پس از مدتي دما کم شده و به اصطلاح سيستم بعد از مدتي به کمينه انرژي ممکن مي رسد.
هم چنين مي دانيم چنين سيستمي داراي حالتهاي بسيار زيادي است مخصوصا اگر هر اتم سه درجه آزادي داشته باشد. خوب حالا فرض کنيد بخواهيم کل حالتهاي اين جعبه يا سيستم را مرتب کنيم. يعني اگر ممکن باشد که از هر حالت يا آنسامبل عکسي گرفته باشيم، حالا مي خواهيم تمام اين عکس ها را مرتب کنيم . حالت ها بر چه اساسي بايد مرتب شوند؟ معلومه، بر اساس انرژي. هر حالت انرژي مخصوص به خودش را دارد، پس اگر سيستم بعد از مدتي دمايش را از دست دهد و انرژي کل سيستم کم شود، آنگاه مي توانيم کل حالت ها را از حالتي که بيشترين انرژي را دارد تا حالتي که کمترين انرژي را دارد مرتب کنيم.
خوب فکر مي کنيد چند تا عکس (حالت ، آنسامبل) داشته باشيم؟ معلومه خيلي زياد. اصلا نميشه مرتبشون کرد. خيلي زمان مي گيره. خوب حالا چي کار کنيم.؟!
جواب اين هست که ما براي بررسي اين سيستم لازم نيست که همه حالت ها (عکس ها ) رو بررسي کنيم. مي توانيم روي تعداد محدودي کار کنيم. مانند سرشماري و راگيري در يک کشور. قرار نيست تمام مردم در يک راي گيري شرکت کنند. بلکه به نمونه گيري آماري اکتفاء مي کنيم و نتيجه اي که از اين نمونه گيري بدست مي آيد را به تمام جمعيت نسبت مي دهيم. الگوريتم هاي مونت کارلو هم همين کار را در سيستم هاي فيزيکي که تعداد حالته ها يا تعداد ذرات بالا هستند، انجام مي دهند.
حالا ببينيم مونت کارلو چي کار مي کنه: اول يک حالت از کل حالت هاي موجود در سيستم را به صورت تصادفي انتخاب مي کنيم. بعد بايد ببينيم اين حالت به چه حالت هاي ديگري مي تواند تغيير پيدا کند. مثلا براي يک اتم در يک جعبه، به ازاي هر تغيير در مکان اين اتم و يا انرژي آن ، حالت کل سيستم هم عوض مي شود. بايد ببينيم اين اتم چه حالت هاي ديگري مي تواند داشته باشد.( اين قسمت اساس کار شما مي باشد و به درک دست و صحيح و قوي شما از سيستم فيزيکي دارد). آنگاه با توليد يک عدد تصادفي بين صفر و يک و رابطه رياضي که بايد شما آن را از مقاله ها پيدا کنيد، يکي از اين حالت هاي ممکن به صورت کاملا تصادفي انتخاب مي شود. مثلا اگر يک حالت ممکن داشته باشيم بايد از روابط رياضي مربوط به الگوريتم متروپليس استفاده کنيد. اگر تعدا حالت هاي ممکن از يکي بيشتر باشد بايد از روابط رياضي مربوط به الگوريتم مونت کارلو جنبشي استفاده کنيد.
بعد از انتخاب حالت نهايي، سيستم را به اين حالت تغيير مي دهيم. سپس دوباره از اين حالت به عنوان حالت اوليه استفاده کرده و مراحل قبلي را تکار مي کنيم.


پس دقت کنيد. کار اصلي به عهده شماست. شما بايد تشخيص بدهيد که بر اساس فيزيک مسئله چه اتفاقي قرار است بيفتد. سپس به دنبال نوشتن الگوريتم آن برويد.

منبع
 
آخرین ویرایش:
برای ارسال پاسخ شما باید وارد سیستم شوید.
بالا