الگوریتم مونت کارلو

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

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

یک طرفه در برابر دو طرفه[ویرایش]

با وجود این که پاسخ برگردانده شده توسط یک الگوریتم قطعی همواره درست به نظر می رسد، اما این حالت برای الگوریتم مونت کارلو برقرار نیست. برای مسئله تصمیم گیری، این الگوریتم ها عمدتاً به عنوان مغرضانه-نادرست یا مغرضانه-درست محسوب می شوند. یک الگوریتم مغرضانه-نادرست مونت کارلو زمانی که پاسخ نادرست را بر می گرداند، همواره درست عمل می کند. و به همین صورت یک الگوریتم مغرضانه-درست، با تغییر آن چیزهایی که نیاز به تغییر دارند. در حالی که این الگوریتم هایی با خطای یک طرفه را ترسیم می کند، دیگر انواع این الگوریتم ممکن است حالت مغرضانه را نداشته باشند: که به آن ها خطاهای دو طرفه می گویند. در واقع، پاسخی که نوع اخیر ایجاد می کنند با احتمال کران داری یا نادرست است و یا درست.

به عنوان مثال، آزمون اعداد اول Solovay–Strassen برای تشخیص اعداد اول به کار می رود. این روش همواره پاسخ درست را برای ورودی های عدد اول ایجاد می کند. برای ورودی های مرکب، این آزمون با احتمال حداقل 1/2 پاسخ نادرست و با احتمال حداکثر 1/2 پاسخ درسترا برمی گرداند. بنابراین پاسخ های نادرست الگوریتم قطعی هستند، حال آن که وضعیت پاسخ هایدرست مشخص نیست. به این الگوریتم، الگوریتم مغرضانه-نادرست نیمه درست اطلاق می شود.

تقویت[ویرایش]

در الگوریت مونت کارلو با خطاهای یک طرفه، با اجرای الگوریتم به تعداد k بار، احتمال شکست می تواند کاهش یابد (و به همین صورت احتمال موفقیت تقویت شود). الگوریتم Solovay–Strassen را که یک الگوریتم مغرضانه-نادرست نیمه درست است، دوباره در نظر بگیرید. می توان این الگوریتم را که خروجی false می دهد، چندین بار اجرا کرد. اگر پس از k بار خروجی آن false باشد، جواب الگوریتم false و در غیر این صورت true است. بنابراین، اگر عددی اول باشد بنابراین پاسخ همواره درست است، و اگر عدد مرکب باشد، جواب با احتمال حداقل  1-2^{-k} درست است.

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

رده های پیچیدگی[ویرایش]

رده های پیچیدگی چند جمله ای احتمالی با خطای کران دار BPP به گونه ای از مسئله تصمیم گیری گفته می شود که می توانند توسط الگوریتم های زمان چند جمله ای مونت کارلو با احتمال کران داری از خطاهای دوطرفه حل شوند. رده پیچیدگی RP مسائلی را توصیف می کند که می توانند با استفاده از الگوریتم مونت کارلو با احتمال کران داری از خطای یک طرفه حل شوند یعنی: اگر پاسخ درست خیر بود، الگوریتم همان کار را کند، اما می تواند برای برخی از مثال هایی که پاسخ درست بله است، نیز پاسخ نادرست بدهد. در مقابل، رده پیچدگی ZPP مسائلی را تببین می کند که با استفاده از الگوریتم های با زمان مشخص لاس وگاس حل می شوند. بدیهی است که ZPP ⊂ RP ⊂ BPP، اما این هنوز مشخص نشده که کدام یک از این رده های پیچیدگی از بقیه متمایزند به این معنی که، الگوریتم های مونت کارلو توان محاسباتی بیشتری از الگوریتم های لاس وگاس دارند، اما این امر هنوز ثابت نشده است. یکی دیگر از رده های پیچیدگی، رده PP است که به مسائل تصمیم گیری اشاره می کند که دارای یک الگوریتم زمان چند جمله ای مونت کارلو هستند که از مسئله پرتاب سکه دقیق تر هستند، اما احتمال خطا نمی‌تواند کرانی دور از 1/2 داشته باشد.

کاربردها در نظریه محاسباتی اعداد[ویرایش]

الگوریتم های مشهور مونت کارلو که شامل آزمون اعداد اول Solovay–Strassen، آزمون اعداد اول Miller–Rabin و نسخه های سریعی از الگوریتم Schreier–Sims که در نظریه محاسباتی گروه ها کاربرد دارند، جزء کاربردهای الگوریتم مونت کارلو هستند.

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

  • گرافیک، به طور خاص خط اثر پرتو
  • مدل سازی جا به جایی نور در رشته های بیولوژیک
  • مونت کارلو در اقتصاد
  • مهندسی اطمینان
  • در شبیه سازی پیچش برای پیش بینی ساختار پروتئین
  • در تخقیقات تجهیزات نیم رسانا، برای مدل سازی جا به جایی حاملهای کنونی
  • در محیط زیست، بررسی آلاینده ها
  • کاربرد مونت کارلو در فیزیک استاتیک
  • در طراحی احتمالاتی برای شبیه سازی و درک تغییرپذیری
  • در شیمی فیزیک، به طور خاص برای شبیه سازی قالب های اتم های درگیر
  • در علوم کامپیوتر:

o الگوریتم لاس وگاس o LURCH o Computer Go o بازیها

الگوریتم مونت کارلو در یادگیری تقویتی[ویرایش]

روش مونت کارلو به عنوان یکی از راه حل های مسئله یادگیری تقویتی بر روی میانگین گیری از بازگشت های نمونه برداری شده، استفاده شده است. این روش به صورت عمده جهت تخمین تابع ارزش و به دست آوردن سیاست های بهینه به کار می رود. در این روش، بر خلاف روش های برنامه ریزی پویا در یادگیری تقویتی، عامل دانش کاملی از محیط ندارد. روش های مونت کارلو در این زمینه تنها به تجربه، یعنی دنباله نمونه های حالت ها، اعمال و پاداش متناظر با آن ها که توسط تعامل با محیط به دست می آیند، نیاز داند. در روش یادگیری از اهمیت خاصی برخوردار است چرا که به هیچ گونه دانش قبلی از ویژگی های دینامیکی محیط نیاز ندارد. به صورت عینی، تنها نیاز داریم تا انتقال های نمونه ای را ایجاد کنیم نه توزیع احتمالی کامل از تمامی انتقال ها که در روش های برنامه ریزی پویا استفاده می شود.

با وجود تفاوت های موجود میان روش مونت کارلو و برنامه ریزی پویا، بسیاری از ایده های مهم این روش از همان روش برنامه ریزی پویا گرفته شده اند. این ایده ها نه تنها در زمینه محاسبه تابع ارزش بلکه در نحوه تعامل برای رسیدن به بهینگی دارای تشابهات زیادی هستند. همچنین این روش با روش یادگیری تفاوت زمانی نیز مشابهت های زیادی دارد. هر دو روش الگوریتم مونت کارلو و یادگیری تفاوت زمانی از تجربه برای حل مسئله پیش بینی استفاده می کنند. با داشتن چند تجربه که یک سیاست  \pi را در پیش دارند، هر دو روش تخمین  V خود از مقدار  V(s_t) را به دست می آورند. یک روش مونت کارلو ساده شامل تمامی ملاقات ها که برای محیط های ساکن مناسب است عبارت است از:

 V(s_t)= V(s_t)+\alpha[R_t-V(s_t)]

به دست آوردن سیاست در یادگیری تقویتی[ویرایش]

در مسئله یادگیری تقویتی، به صورت خاص، ما می خواهیم مقدار تابع ارزش  V^{\pi}(s) یک حالت خاص  s را تحت سیاست مورد نظر  \pi محاسبه کنیم که این کار با داشتن مجموعه ای از قسمت ها (episodes) انجام خواهد شد. الگوریتم مشاهده کلی مونت کارلو میزان متوسط بازگشت ها را برای تمامی مشاهده ها در تمامی قسمت ها محاسبه می کند. این عمل در الگوریتم مونت کارلو به صورت زیر انجام می شود که سودوکد آن نیز در زیر آمده است:

 V^{\pi}(s)= E_{\pi}[R_t|s_t=s]

مقایسه با روش های دیگر یادگیری تقویتی[ویرایش]

تصویری کلی از روش های یادگیری تقویتی.
تصویری کلی از روش های یادگیری تقویتی.

تمامی روش های یادگیری تقویتی دارای ایده ای یکسان هستند. اول، هدف تمام ان ها تخمین تابع ارزش است. دوم، تمامی آن ها با نگه داری مقادیر در عبور از حالت های مختلف ممکن یا واقعی عمل می کنند. سوم، تمامی آن ها یک راهبرد برای پیمایش کلی سیاست (GPI) دارند، به این معنی که آن ها یک تابع ارزش تقریبی و یک سیاست تقریبی را نگه می دارند و پیوسته هر کدام از آن ها را بر مبنای دیگری بهبود می بخشند.

دو بعد مهم در روش های یادگیری تقویتی در شکل روبرو مشاهده می شود. این ابعاد با نوع نگه داری که برای بهبود تابع ارزش استفاده شده است، مرتبط هستند. بعد عمودی نشان دهده این است که نگه داری آیا در نمونه هاست (بر اساس گذر از نمونه ها) یا نگه داری کامل است (بر اساس توزیع گذرهای ممکن). نگه داری های کامل نیازمند یک مدل هستند حال آن که نگه داری های نمونه ای می توانند بدون مدل نیز عمل کنند. بعد افقی به عمق این نگه داری ها، یعنی درجه bootstrapping، مرتبط است. سه گوشه از چهار گوشه اشاره شده از روش های مهم در تخمین ارزش ها هستند: برنامه ریزی پویا، یادگیری تفاوت زمانی و الگوریتم مونت کارلو.

جستارهای وابسته[ویرایش]

منابع برای مطالعه بیشتر[ویرایش]