فرابگیر

انجام پروژه دانشجویی، کامپیوتر، تحقیق در عملیات و آمار

حوزه فعالیت این سایت آموزش، مشاوره و انجام پروژه های دانشجویی در رشته های کامپیوتر و تحقیق در عملیات می باشد

بنیاد بیماری های نادر ایران

روش گرادیان

روش گرادیان

روش گرادیان

روش گرادیان

روش گرادیان

به یاد آورید که مجموعه سطح از تابع f: Rn -> R برابر است با مجموعه ای از نقاط X که تابع f(x) =c  را به ازای مقادیر ثابت c  راضی نماید. بنابراین، x0 ϵ Rn یکی از مجموعه سطح ها مرتبط به سطح c خواهد بود اگر f (X0) = C باشد. در مورد توابع با دو متغیر واقعی      f: R2 -> R مفهوم مجموعه سطح در شکل زیر نشان داده شده است.

ادامه مطلب...

روش گرادیان

روش گرادیان

روش گرادیان در حل مسائل چندهدفه به گفرین (Geoffrion) منتسب است. این روش قادر به حل مسائل بهینه سازی خطی و غیرخطی است به شرطی که خبره بتواند تابع مطلوبیت کلی خود را از اهداف مسئله مشخص نماید.

الگوریتم گرادیان در قالب روش فرانک- ولف مطرح شده است. در روش فرانک- ولف حرکت از یک نقطه شدنی ( Xi ) شروع می شود و از آن جا به منظور دسترسی به یک جهت بهینه حرکت (di) به نقطه جدید (yi) می رسد به طوری که خواهیم داشت: ( di = (yi –  Xسپس باید مقدار بهینه حرکت ( λi) تعیین شود.


مقدار بهینه حرکت و نقطه مقصد

برای یافتن مقدار بهینه حرکت مسئله بهینه سازی زیر باید حل شود:

بهینه کنید: f (Xi + λi di )

s.to:  λi  ≥ ۰

برای یافتن نقطه مقصد مدل زیر باید حل شود:

نقطه مقصد مدل گرادیان

نقطه مقصد مدل گرادیان


مدل گرادیان برای حل یک مسئله K هدفه

max: U {f1 (x), f2 (x), …. fk (x)} = U (F)

s.t: x ∈ S   ;   s = {x | gi(x) ≤ ۰ ; i = 1, 2, …, m }

در این مدل توابع (f(x و (g(x به طور عینی معلوم است اما تابع مطلوبیت (U(F به طور ضمنی مد نظر است.

مفروضات استفاده از شرایط فرانک- ولف

  • مجموعه متشکل از محدودیت ها محدب و بسته (مرزدار) باشد
  • (U(F (تابع مطلوبیت توابع هدف) بر روی X مشتق پذیر و مقعر باشد
  • هر یک از توابع هدف مقعر باشد
  • مشتق جزئی تابع مطلوبیت نسبت به تابع هدف اول مثبت باشد که در نتیجه این تابع هدف به عنوان هدف مرجع تلقی می گردد

الگوریتم روش گرادیان

قدم یکم: نقطه شروع xi ∈ S را انتخاب نموده و قرار دهید i=1

قدم دوم: راه حل بهینه yi را به منظور جهت یابی برای حرکت بهبودبخش از مسئله زیر بیابید:

max: ∇x U = (f1 (xi), f2 (xi), …. fk (xi)) .  yi

s.t : yi ∈ S

بخش اساسی تعامل با خبره در همین جا است زیرا (U(F به طور عینی مشخص نیست و نیاز به کمک خبره دارد. فرض بر آن است که خبره قادر است تعدیل بین هر دو هدف از اهداف مسئله را به ازای یک راه حل مشخص برآورد کند. این نرخ حاشیه ای جایگزینی بین اهداف را می توان برای برآورد گرادیان از (U(F به کار برد. اثبات ریاضی این موضوع در ادامه ارائه شده است.

اثبات مدل گرادیان

مدل بهینه سازی با تقسیم بر یک عدد ثابت تغییری نمی کند به این دلیل تابع هدف مذکور را بر (U∂/∂Fi1)   تقسیم می کنیم.

ادامه اثبات مدل گرادیان

اوزان منعکس کننده تعدیل خبره بین اهداف است زیرا:

ادامه اثبات مدل گرادیان

ادامه اثبات مدل گرادیان

حال در ادامه جهت  بدست آوردن اوزان wij باید نرخ حاشیه ای جایگزینی بین اهداف اول و jام را به کمک خبره ارزیابی نمود بدین صورت که تعدیل بی تفاوتی خبره از تغییر بسیار کوچک در هدف اول Δf1 در مقابل تغییر لازم برای هدف jام را جویا شویم. یعنی تغییر در هدف اول به میزان Δf1 با ثابت نگه داشتن بقیه اهداف به استثنای هدف jام چه اندازه از این هدف را جبران خواهد نمود. این برآورد به صورت زیر است:

wij = Δf1/Δfj

قدم سوم: مقدار بهینه λi را از مدل روبرو محاسبه نمائید:

max: U {  F (Xi + λi di ) }

s.to: 0 ≤ λi ≤ ۱

برای انجام این برآورد باید از نظرات خبره استفاده کرد. برای این کار به دو طریق می توان عمل نمود:

  1. رسم نمودار
  2. رسم جدول
نمودار برآورد نظرات خبره

نمودار برآورد نظرات خبره

قدم چهارم: اختتام الگوریتم

از نظر تئوری پایان الگوریتم زمانی است که دو راه حل متوالی با یکدیگر یکسان شوند ولی این ایده آل به ندرت اتفاق می افتد. به همین دلیل نسبتی را به نام نسبت بهبودی تعریف می کنیم که یک معیار عملی برای پایان الگوریتم است:

شرط اختتام الگوریتم گرادیان

شرط اختتام الگوریتم گرادیان

 


مثال روش گرادیان

Max  f1(x)= – x1 – ۲ x2 – ۳ x3

       f2(x) = – x1 – ۲ x2 – x3

       f3(x) = -2×1 – x2 –x3

S . to :

        ۲×۱ + ۵×۲ + ۳ x3 ≥ ۳۰

        x1 + x2 + x3 ≥ ۱۸

        ۱۰×۱ + ۸×۲ + ۴ x3 ≥۴۰

        ۳×۱+۲×۲ ≥۲۰

         x1 , x2 , x3 ≥ ۰

انتقال یکم :

نقطه عملی) :قدم یکم)         x’ ∈ S    ->   x1= (2, 9, 7)   , i=1 ,  ε =۰٫۱۵

مفروضات مسئله:                 F0 = {F1(x1), F2(x1), F3(x1)}   ->  F0 = { (-41, -27, -20)

قدم دوم : (f1 در مقابل  f2)  {(-۴۱-۲۰ )   ,   ( -۲۷ + ۲ )    , ( -۲۰ )} = > w12=-(2/-20) = 0.1

قدم دوم : (f2 در مقابل  f3)  {(-۴۱)  ,   ( -۲۷ + ۲ )    , ( -۲۰- ۱۰ )}= > w13=-(2/-10) = 0.2    ->  w1=(0.1 , 1, 0.2)

 

 

محاسبه Y1, d1 ۰٫۱(-۱  ,  -۲    ,  -۳ ) Y1  +۱( -۱  ,  -۲  ,  -۱) Y1 +  ۰٫۲ ( -۲  , -۱  , -۱ ) Y

Y1={Y11 , Y21 , Y3}

Max: 0.1f1(Y1) + 1f2(Y1)+ 0.2 f3(Y1)

S.to Y1 ∈ S

S  فضای حاصل از محدودیتهای مسئله: Y1 = {0, 0, 10}    d1= = {(0 – ۲), (۰ – ۹),  (۱۰ – ۷)} = {-۲, – ۹, ۳}

 

مشخص نمودن بهینه : قدم سوم 

برای f1  داریم ( محاسبات برای ۰٫۲= λو  ۰٫۴= λو ۰٫۶= λو ۰٫۸= λ و اگر ۱= λ) :

-۱ ( ۲ + .۲ ( -۲ )) -۲ ( ۹ + .۲ ( -۹ ))-۳( ۷ + .۲ ( ۳ )) =-۳۸٫۸

-۱ ( ۲ + .۴ ( -۲ )) -۲ ( ۹ + .۴ ( -۹ ))-۳( ۷ + .۴ ( ۳ )) =- ۳۶٫۷

-۱ ( ۲ + .۶ ( -۲ )) -۲ ( ۹ + .۶ ( -۹ ))-۳( ۷ + .۶ ( ۳ )) =-۳۴٫۴

-۱ ( ۲ + .۸ ( -۲ )) -۲ ( ۹ + .۸ ( -۹ ))-۳( ۷ + .۸ ( ۳ )) =-۳۲٫۱

-۱ ( ۲ + ۱ ( -۲ )) -۲ ( ۹ + ۱ ( -۹ ))-۳( ۷ + ۱ ( ۳ )) =-۳۰

برای f2  داریم:

-۱ ( ۲ + .۲ ( -۲ )) -۲ ( ۹ + .۲ ( -۹ ))- ( ۷ + .۲ ( ۳ )) =-۲۳٫۶

-۱ ( ۲ + .۴ ( -۲ )) -۲ ( ۹ + .۴ ( -۹ ))- ( ۷ + .۴ ( ۳ )) =- ۲۰٫۲

-۱ ( ۲ + .۶ ( -۲ )) -۲ ( ۹ + .۶ ( -۹ ))- ( ۷ + .۶ ( ۳ )) =-۱۶٫۸

-۱ ( ۲ + .۸ ( -۲ )) -۲ ( ۹ + .۸ ( -۹ ))- ( ۷ + .۸ ( ۳ )) =-۱۳٫۴

-۱ ( ۲ + ۱ ( -۲ )) -۲ ( ۹ + ۱ ( -۹ ))- ( ۷ + ۱ ( ۳ )) =-۱۰

و برای f3   داریم :

-۲ ( ۲ + .۲ ( -۲ )) -۱ ( ۹ + .۲ ( -۹ ))- ( ۷ + .۲ ( ۳ )) =-۱۸

-۲ ( ۲ + .۴ ( -۲ )) -۱ ( ۹ + .۴ ( -۹ ))- ( ۷ + .۴ ( ۳ )) =- ۱۶

-۲ ( ۲ + .۶ ( -۲ )) -۱ ( ۹ + .۶ ( -۹ ))- ( ۷ + .۶ ( ۳ )) =-۱۳٫۸

-۲ ( ۲ + .۸ ( -۲ )) -۱ ( ۹ + .۸ ( -۹ ))- ( ۷ + .۸ ( ۳ )) =-۱۲

-۲ ( ۲ + ۱ ( -۲ )) -۱ ( ۹ + ۱ ( -۹ ))- ( ۷ + ۱ ( ۳ )) =-۱۰

۱=λ۱ ۰٫۸=λ۱ ۰٫۶=λ۱ ۰٫۴=λ۱ ۰٫۲=λ۱ ۰=λ۱
-۳۰ -۳۲٫۱ -۳۴٫۴ -۳۶٫۷ -۳۸٫۸ -۴۱ F1
-۱۰ -۱۳٫۴ -۱۶٫۸ -۲۰٫۲ -۲۳٫۶ -۲۷ F2
-۱۰ -۱۲ -۱۳٫۸ -۱۶ -۱۸ -۲۰ F3

در صورتی که ۰٫۴=λ مورد نظر خبره باشد: ( -۳۶٫۷    ,   –  ۲۰٫۲     ,   -۱۶   )

 به منظور انتقال به مرحله دوم باید محاسبه شود :

x2= ( X1 + λ۱ d1)

x2= 2+ 0.4  -۲=۱٫۲

x2= 9+ 0.4  -۹=۵٫۴

x2= 7+ 0.4  ۳=۸٫۲

x2= ( 1.2  ,   ۵٫۴   ,   ۸٫۷۸  ) ->  F ={ (-38.34)  , (  -۲۰٫۷۸  )  ,  ( -۱۶٫۵۸ ) }

قدم چهارم: کلیه گام ها مانند قبل تکرار می شود و مقدار ( -۴۷٫۶۳۶   , -۱۹٫۰۳۲     ,   -۱۷٫۴۲۲   ) = F2  بدست می آید. حال شرط خاتمه بررسی می شود که در صورت تصدیق میزان بهینگی الگوریتم از حرکت باز می ایستد.

شرط اختتام الگوریتم گرادیان

شرط اختتام الگوریتم گرادیان

از ε =۰٫۱۵ کمتر است پس در همین تکرار متوقف می شود.

ادامه مطلب...

آرشیوهای برچسب : روش گرادیان