آخرين ارسالهاي تالار

خطا: mod_kunenalatest:كيوننا نسخه 1.7 (يا بالاتر) بر روي سيستم شما نصب نيست!
پیغام
  • Kunena is not installed or the installed Kunena version is not supported. The plug-in has now been disabled. Please install/upgrade Kunena to version 1.7 for the Kunena Discuss Plug-in to function properly.
روش Conjugate Gradients مشاهده در قالب PDF چاپ فرستادن به ایمیل
نوشته شده توسط admin   
شنبه, 11 تیر 1390 ساعت 01:01

روش Conjugate Gradients برای بهینه سازی

فرض کنیم F تابعی هموار ازRª→R باشد.  یک روش معمول برای پیدا کردن مینیمم این تابع این است که با شروع از نقطه ی خاصی، در جهت های انتخاب شده ای حرکت کنیم و در هر مرحله، گامی چنان برداریم که به مقدار کمینه تابع روی آن راستا برسیم. یک روش ابتدایی این است که این جهت ها را در راستای منفی گرادیان F انتخاب کنیم که منجر به روشی موسوم به "Steepest Descent Method" میشود. اما این روش معمولا کارآیی بالایی ندارد، چرا که سریعا در دام مینیمم های موضعی می افتد و خیلی کند پیش می رود. استفاده از روش ارتقا یافته ای به نام "Conjugate Gradients Method" راه بهتری است. در این روش جهت هایی را پیش میگیریم که در آن ماندهها متعامد باشند (هر کدام از این دو واﮋه تعریف دقیق و مشخصی دارند.) هر تابع هموار در نزدیکی نقاط مینیمم موضعی، شبیه یک تابع quadratic با ماتریس هسیان (Hessian Matrix) مثبت معیین رفتار می کند. این بدان معنی است که اگرA وb- ضرایب مورد نیاز برای تعریف یک تابع quadratic- را می داشتیم می توانستیم از روش CG برای بهینه سازی استفاده کنیم. در نگاه اول به نظر می رسد که بدون داشتن ماتریس هسیان-  که نقش A را بازی میکند- نمی توان CG را به کار برد. اما این مشکل رفع شدنی است. بررسی الگوریتم CG نشان می دهد که A در دو جا استفاده می شود. یکی در محاسبه ی گرادیان F و دیگری برای محاسبه ی گام حرکت در هر مرحله. مورد اول با به کارگیری روش خاصی حل شدنی است. برای دومی هم از روش های عددی برای مینیمم کردن مقدار F روی راستای خاص استفاده می کنیم. روش CG با این دو تغییرموسوم به روش Fletcher- Reeves می باشد.

 

 

مزایا و معایب

در این روشو تنها عملیاتی که با A انجام می گیرد ضرب آن در یک بردار است. اگر ماتریس A بزرگ و sparse باشد، این موضوع می تواند مفید باشد، چرا که شاید هیچوقت لازم نشود که A را در یک ماتریس m*m ذخیره کنیم. در عوض A را می توان به صورت ذخیره شده نگه داشت یا فورا محاسبه کرد. در این صورت تنها لازم است یک تابع مخصوص برای ضرب A در یک بردار نوشته شود.

CG یک روش تکراری است. به طور تئوری، تعداد تکرار های لازم برابر تعداد مقادیر وﯿﮋه متفاوت A است، یعنی m. در عمل معمولا خیلی زودتر به یک تقریب خوب می رسیم، که این عامل کارایی CG در مسایل بزرگ را توجیه می کند.

در مقایسه با روش های دیگر مرتبط با گرادیان، در CG جهت های متعامد همواره غیر صفرند و از بردار های جهت های قبلی به طور خطی مستقل هستند.

جهت بعدی از فرمول ساده ای به دست می آید، فقط کمی مشکلتر از روش steepest descent.

در مقایسه با Newton Method، که از CG کارایی بیشتری دارد، روش CG به حافظه ی کمتری احتیاج دارد. با توجه به اینکه جهت جستجو اطلاعات تمام جهت های قبلی را در خود دارد، تنها باید آخرین جهت، جهت فعلی و نقطه ی فعلی ذخیره شوند.

در حقیقت برای اطمینان از A- متعامد بودن جهت های جدید جستجو لازم نیست که نمام جهت های قبلی را داشته باشیم. این باعث می شود زمان عملیات از O(n²) به O(m) کاهش یابد (m تعداد درایه های غیر صفر A است.)

این روش توسط نرم افزار متلب قابل پیاده سازی است

نظر ها (4)
  • فرهاد یولداشی  - تشکر
    سلام. مهندس واقعاً لذت بردم.مطالب خیلی جالبی تو سایتتون هست. با آرزوی موفقیت
  • sara  - behine sazi
    سلام و با تشکر از سایت خوبتون
    میشه راجع به این قسمت بیشتر توضیح بدین؟ومطلب بیشتر بذارین یا در زمینه هلپ این قسمت توضیح بدین یا کتاب معرفل کنید یا فایل اموزشی و کتاب یا پی دی اف فارسی بذارین؟ واقعا و صمیمانه تشکرمیکنم
    من پروزه در این زمینه دارم و گرایش درسیم بهینه سازیست
    و باید الگوریتم بنویسم در این زمینهو برنامه متلبش رو هم بنویسم
    نمی دونم از کدام قسمت برنامه نویسی شروع کنم؟
    و پایان نامم هم کلا برنامه نویسی هستش
    تشکر میگنم کمککنید و راهنمایی های لازم رو در اختیارم بذارین
    اگر دوستانی هم هستن راهنمای یکنن ممنون میشم
    دستورات برنامه نویسی و استفاده از حلقه ها رو بلد نیستم
    کاش بشه 2هفته همه چی رو یاد گرفت
  • نیما
    سلام.میشه یک مثال برای یک تابع ونقاط خاص بانرم افزارمطلب بذارید
  • نیما
    منم مشکل شمارو دارم دقیقا
تنها کاربران عضو شده می توانند نظر ارسال کنند!
آخرین بروز رسانی در شنبه, 11 تیر 1390 ساعت 01:05
 
logo-samandehi