Artificial Intelligence - هوش مصنوعی  
انجمن را در گوگل محبوب کنيد :

بازگشت   Artificial Intelligence - هوش مصنوعی > محاسبات نرم > الگوریتم شبیه سازی تبرید يا باز پخت (Simulated Annealing)


 
تبليغات سايت
Iranian Association for the Advancement of Artificial Intelligence
ارسال تاپيک جديد  پاسخ
 
LinkBack ابزارهاي تاپيک نحوه نمايش
قديمي ۰۷-۷-۱۳۸۹, ۰۹:۳۷ بعد از ظهر   #1 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Wink الگوریتم Simulated Annealing

الگوریتم Simulated Annealing

روش SA یکی از روش های متاهیوریستیکی احتمالی است که ایده آن از عمل سرد کردن تدریجی فلزات برای استحاکم بیشتر آن ها نشات گرفته است. همانند روش های تپه نوردی و تپه نوردی تعمیم یافته ، در این روش نیز مسئله از یک حالت مانند S در فضای حالت مسئله شروع کرده و با گذر از حالتی به حالت دیگر به جواب بهینه مسئله نزدیک می شود. انتخاب حالت شروع هم می تواند به صورت تصادفی انجام پذیرد و هم می تواند بر اساس یک قاعده حالت اولیه مسئله را انتخاب کنیم. در اینجا نیز تابع Objective میزان بهینگی حالت فعلی را محاسبه کرده و Neighbor یک حالت همسایه برای حالت فعلی تولید می کند.



روش کلی کار به این صورت است که در هر تکرار ، الگوریتم SA حالت همسایه ای مانند s' ایجاد می کند و بر اساس یک احتمال ، مسئله از حالت s به حالت s' می رود و یا اینکه در همان حالت s باقی می ماند . این روند تا زمانی تکرار می شود که به یک جواب نسبتا بهینه برسیم یا اینکه ماکزیمم تعداد تکرار ها را انجام داده باشیم. همانطور که قبلا نیز بررسی کردیم نحوه تولید حالت همسایه از اهمیت به سزایی برخوردار است.
در روش کلی الگوریتم بیان کردیم که قبولی حالت همسایه تولید شده بر اساس یک احتمال صورت می پذیرد . تابع ( P(e,e',T تعیین کننده احتمال قبولی حالت همسایه می باشد . e بهینگی حالت فعلی و e' بهینگی حالت همسایه می باشد . در صورتی که حالت همسایه از حالت فعلی بدتر باشد ، مقدار پارامتر T تعیین کننده احتمال قبولی جواب می باشد . در ابتدای امر مقدار پارامتر T را طوری انتخاب می کنیم که اکثر حالت های همسایه را مورد پذیرش قرار دهیم ، پارامتر T نشانگر دما بوده و مقدار این پارامتر به تدریج کاهش می یابد . مقدار پارامتر T را طوری انتخاب می کنیم که قبل از انجام گرفتن ماکزیمم تعداد تکرارها ، مقدار آن تقریبا صفر گردد . مستنداتی که برای الگوریتم SA وجود دارد، نشان می دهند که در ابتدای امر مقدار T بهتر است به گونه ای تعیین گردد که در ابتدا 80% جواب ها مورد پذیرش الگوریتم واقع شود. روش کلی این الگوریتم به صورت زیر خواهد بود :

كد:
 Procedure Simulated Annealing
  C = Choose an initial solution                             
  T = Choose an initial temperature                             
  REPEAT                             
    S' = Generate a neighbor of the solution C                             
    ΔE = objective( S' ) – objective( C )                             
    IF (ΔE > 0 ) THEN // S' better than C                             
      C = S'                             
    ELSE with probability EXP( ΔE/ T )                             
      C = S'                             
    END IF                             
    T = lower the T using linear/ non-linear techniques                             
  UNTIL meet the stop criteria                             
  End

در روش تپه نوردی برای گریز از بهینگی های محلی عمل جهش در فضای حالت را انجام دادیم . اما در روش SA به شکل دیگری به مقابله با این مشکل می پردازیم. در این روش وجود پارامتر T باعث می شود حتی در صورتی که بهینگی جواب همسایه بدتر از حالت فعلی باشد بر اساس مقدار T احتمال قبولی همین حالت نیز وجود دارد . قبول کردن جواب های غیربهینه باعث می شوند که این الگوریتم با موفقیت از بهینگی های محلی عبور کند.

در صورتی که e'< e باشد ، تابع P مقدار 1 برمی گرداند ( یعنی احتمال قبولی حالت همسایه 100% است ) . در غیر این صورت ( e'>e ) تابع P بر اساس مقدار T و اختلاف بین e' و e مقداری بین صفر و یک بر می گرداند که نشان دهنده احتمال قبولی حالت همسایه است .

در روش سرد کردن تدریجی فلزات ، برای استحکام هرچه بیشتر فلز ، دما به تدریج کاهش می یابد . در روش SA نیز مقدار T را به تدریج کاهش می دهیم . مقدار T به هرمیزانی که زیاد باشد ، باعث می شود که احتمال قبولی جواب های بد نیز بالا باشد . اما چون مقدار T رفته رفته کاهش می یابد ، بنابراین زمانی که مقدار T به اندازه کافی کم شد ( دما به اندازه کافی پایین آمد ) احتمال قبولی جواب های بد نیز به صفر میل می کند . از این لحظه به بعد فقط حالت هایی مورد پذیرش قرار می گیرند که هزینه آن ها بهتر از هزینه حالت فعلی باشند . به عبارت دیگر زمانی که مقدار T به صفر نزدیک شود ، در صورتی حالت همسایه به عنوان حالت فعلی انتخاب می شود که e' < e باشد . مقدار T باید به گونه ای انتخاب گردد که هنگام رسیدن به دمای صفر ، الگوریتم از بهینگی های محلی عبور کرده و در نزدیکی بهینگی سراسری قرار گرفته باشد.

برای کاهش دما، T را در یک ضریب همانند r که مقدار بین 0 و 1 دارد، ضرب می کنیم. کاهش دادن سریع دما موجب خواهد شد که همچنان با مشکل بهینگی های محلی مواجه باشیم. بنابراین مقدار این پارامتر را همیشه نزدیک به عدد 1 انتخاب می کنیم. ( مثلا 0.998 ). در الگوریتم SA انتخاب دما نقس بسیار زیادی در موفقیت الگوریتم دارد. انتخاب دمای اولیه بسیار بزرگ موجب کندی الگوریتم و انتخاب دمای کم موجب قرار گرفتن در نقاط بهینگی محلی می شود. استفاده از دمای بسیار زیاد در صورتی که مدت زمان کافی برای حل مساله داشته باشیم ، بهتر به نظر می رسد. با این حال هنگام پیاده سازی الگوریتم SA برای یک مساله خاص بهتر آن است که دمای اولیه الگوریتم با توجه به بزرگی مساله تعیین گردد. با اینکه مشکل بهینگی های محلی در الگوریتم SA حل شده است، با این حال در برخی مسائل هنگام استفاده از این الگوریتم به مشکلاتی بر خواهیم خورد. در الگوریتم SA ممکن است هنگام تولید حالت همسایگی به حالتی گذر کنیم که قبلا یکبار این حالت را مشاهده کرده ایم. البته نمی توان برگشت به حالت تکراری را مشکلی برای الگوریتم تلقی کرد. چرا که در برخی موارد همین برگشت به حالت قبلی ممکن است موجب بهبود الگوریتم گردد. اما برای رفع این مشکل نیز روش جستجوی Tabu پیشنهاد گردید که در ادامه به بررسی آن نیز می پردازیم.
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
34191207359 (۰۲-۲۸-۱۳۹۳), AmirGh2 (۰۹-۲۳-۱۳۹۲), arashmob (۰۳-۲۲-۱۳۹۳), mohammadmono (۰۲-۲-۱۳۹۰), vahidby28 (۰۱-۱۹-۱۳۹۲)

  #ADS
نشان دهنده تبلیغات
تبليغگر
 
 
 
تاريخ عضويت: -
محل سكونت: -
سن: 2010
پست ها: -
 

نشان دهنده تبلیغات is online  
قديمي ۱۲-۱۴-۱۳۸۹, ۰۱:۱۰ قبل از ظهر   #2 (لینک دائم)
عضو جدید
 
آواتار سبا
 
تاريخ عضويت: اسفند ۱۳۸۹
پست ها: 8
تشكرها: 1
0 تشكر در 0 پست
My Mood: Gerye
پيش فرض

سلام
من Pseudo code الگوریتم تپه نوردی تعمیم یافته رو میخوام
ممنون
سبا آفلاين است   پاسخ با نقل قول
قديمي ۱۲-۱۴-۱۳۸۹, ۰۱:۵۳ بعد از ظهر   #3 (لینک دائم)
عضو جدید
 
آواتار سبا
 
تاريخ عضويت: اسفند ۱۳۸۹
پست ها: 8
تشكرها: 1
0 تشكر در 0 پست
My Mood: Gerye
پيش فرض الگوریتم تپه نوردی تعمیم یافته، تو رو خدا کمککککککککککک

سلام یکی ی لطف کنه الگوریتم تپه نوردی تعمیم یافته رو برام بگه که مشکل جواب بهینه ی محلیش حل شده باشه plz
سبا آفلاين است   پاسخ با نقل قول
قديمي ۱۰-۹-۱۳۹۰, ۱۰:۰۵ بعد از ظهر   #4 (لینک دائم)
عضو جدید
 
آواتار n shiri
 
تاريخ عضويت: آذر ۱۳۹۰
پست ها: 4
تشكرها: 0
0 تشكر در 0 پست
ارسال پيغام Yahoo به n shiri
پيش فرض

سلام
در مورد fast simulated annealing هم اگه مطلبی دارید لطفا برامون بزارید استفاده کنیم.
البته cauchy نام دیگش است
n shiri آفلاين است   پاسخ با نقل قول
قديمي ۰۹-۲۳-۱۳۹۲, ۱۲:۵۷ قبل از ظهر   #5 (لینک دائم)
عضو جدید
 
آواتار AmirGh2
 
تاريخ عضويت: آذر ۱۳۹۲
پست ها: 1
تشكرها: 1
0 تشكر در 0 پست
پيش فرض

نقل قول:
نوشته اصلي بوسيله Reyhane نمايش پست
الگوریتم Simulated Annealing

روش SA یکی از روش های متاهیوریستیکی احتمالی است که ایده آن از عمل سرد کردن تدریجی فلزات برای استحاکم بیشتر آن ها نشات گرفته است. همانند روش های تپه نوردی و تپه نوردی تعمیم یافته ، در این روش نیز مسئله از یک حالت مانند S در فضای حالت مسئله شروع کرده و با گذر از حالتی به حالت دیگر به جواب بهینه مسئله نزدیک می شود. انتخاب حالت شروع هم می تواند به صورت تصادفی انجام پذیرد و هم می تواند بر اساس یک قاعده حالت اولیه مسئله را انتخاب کنیم. در اینجا نیز تابع Objective میزان بهینگی حالت فعلی را محاسبه کرده و Neighbor یک حالت همسایه برای حالت فعلی تولید می کند.



روش کلی کار به این صورت است که در هر تکرار ، الگوریتم SA حالت همسایه ای مانند s' ایجاد می کند و بر اساس یک احتمال ، مسئله از حالت s به حالت s' می رود و یا اینکه در همان حالت s باقی می ماند . این روند تا زمانی تکرار می شود که به یک جواب نسبتا بهینه برسیم یا اینکه ماکزیمم تعداد تکرار ها را انجام داده باشیم. همانطور که قبلا نیز بررسی کردیم نحوه تولید حالت همسایه از اهمیت به سزایی برخوردار است.
در روش کلی الگوریتم بیان کردیم که قبولی حالت همسایه تولید شده بر اساس یک احتمال صورت می پذیرد . تابع ( P(e,e',T تعیین کننده احتمال قبولی حالت همسایه می باشد . e بهینگی حالت فعلی و e' بهینگی حالت همسایه می باشد . در صورتی که حالت همسایه از حالت فعلی بدتر باشد ، مقدار پارامتر T تعیین کننده احتمال قبولی جواب می باشد . در ابتدای امر مقدار پارامتر T را طوری انتخاب می کنیم که اکثر حالت های همسایه را مورد پذیرش قرار دهیم ، پارامتر T نشانگر دما بوده و مقدار این پارامتر به تدریج کاهش می یابد . مقدار پارامتر T را طوری انتخاب می کنیم که قبل از انجام گرفتن ماکزیمم تعداد تکرارها ، مقدار آن تقریبا صفر گردد . مستنداتی که برای الگوریتم SA وجود دارد، نشان می دهند که در ابتدای امر مقدار T بهتر است به گونه ای تعیین گردد که در ابتدا 80% جواب ها مورد پذیرش الگوریتم واقع شود. روش کلی این الگوریتم به صورت زیر خواهد بود :

كد:
 Procedure Simulated Annealing
  C = Choose an initial solution                             
  T = Choose an initial temperature                             
  REPEAT                             
    S' = Generate a neighbor of the solution C                             
    ΔE = objective( S' ) – objective( C )                             
    IF (ΔE > 0 ) THEN // S' better than C                             
      C = S'                             
    ELSE with probability EXP( ΔE/ T )                             
      C = S'                             
    END IF                             
    T = lower the T using linear/ non-linear techniques                             
  UNTIL meet the stop criteria                             
  End

در روش تپه نوردی برای گریز از بهینگی های محلی عمل جهش در فضای حالت را انجام دادیم . اما در روش SA به شکل دیگری به مقابله با این مشکل می پردازیم. در این روش وجود پارامتر T باعث می شود حتی در صورتی که بهینگی جواب همسایه بدتر از حالت فعلی باشد بر اساس مقدار T احتمال قبولی همین حالت نیز وجود دارد . قبول کردن جواب های غیربهینه باعث می شوند که این الگوریتم با موفقیت از بهینگی های محلی عبور کند.

در صورتی که e'< e باشد ، تابع P مقدار 1 برمی گرداند ( یعنی احتمال قبولی حالت همسایه 100% است ) . در غیر این صورت ( e'>e ) تابع P بر اساس مقدار T و اختلاف بین e' و e مقداری بین صفر و یک بر می گرداند که نشان دهنده احتمال قبولی حالت همسایه است .

در روش سرد کردن تدریجی فلزات ، برای استحکام هرچه بیشتر فلز ، دما به تدریج کاهش می یابد . در روش SA نیز مقدار T را به تدریج کاهش می دهیم . مقدار T به هرمیزانی که زیاد باشد ، باعث می شود که احتمال قبولی جواب های بد نیز بالا باشد . اما چون مقدار T رفته رفته کاهش می یابد ، بنابراین زمانی که مقدار T به اندازه کافی کم شد ( دما به اندازه کافی پایین آمد ) احتمال قبولی جواب های بد نیز به صفر میل می کند . از این لحظه به بعد فقط حالت هایی مورد پذیرش قرار می گیرند که هزینه آن ها بهتر از هزینه حالت فعلی باشند . به عبارت دیگر زمانی که مقدار T به صفر نزدیک شود ، در صورتی حالت همسایه به عنوان حالت فعلی انتخاب می شود که e' < e باشد . مقدار T باید به گونه ای انتخاب گردد که هنگام رسیدن به دمای صفر ، الگوریتم از بهینگی های محلی عبور کرده و در نزدیکی بهینگی سراسری قرار گرفته باشد.

برای کاهش دما، T را در یک ضریب همانند r که مقدار بین 0 و 1 دارد، ضرب می کنیم. کاهش دادن سریع دما موجب خواهد شد که همچنان با مشکل بهینگی های محلی مواجه باشیم. بنابراین مقدار این پارامتر را همیشه نزدیک به عدد 1 انتخاب می کنیم. ( مثلا 0.998 ). در الگوریتم SA انتخاب دما نقس بسیار زیادی در موفقیت الگوریتم دارد. انتخاب دمای اولیه بسیار بزرگ موجب کندی الگوریتم و انتخاب دمای کم موجب قرار گرفتن در نقاط بهینگی محلی می شود. استفاده از دمای بسیار زیاد در صورتی که مدت زمان کافی برای حل مساله داشته باشیم ، بهتر به نظر می رسد. با این حال هنگام پیاده سازی الگوریتم SA برای یک مساله خاص بهتر آن است که دمای اولیه الگوریتم با توجه به بزرگی مساله تعیین گردد. با اینکه مشکل بهینگی های محلی در الگوریتم SA حل شده است، با این حال در برخی مسائل هنگام استفاده از این الگوریتم به مشکلاتی بر خواهیم خورد. در الگوریتم SA ممکن است هنگام تولید حالت همسایگی به حالتی گذر کنیم که قبلا یکبار این حالت را مشاهده کرده ایم. البته نمی توان برگشت به حالت تکراری را مشکلی برای الگوریتم تلقی کرد. چرا که در برخی موارد همین برگشت به حالت قبلی ممکن است موجب بهبود الگوریتم گردد. اما برای رفع این مشکل نیز روش جستجوی Tabu پیشنهاد گردید که در ادامه به بررسی آن نیز می پردازیم.
با عرض سلام
ببخشید یک تمریتی استادم به من داده درباره ی همین موضوع که استدالال مختصر نام الگوریم های متناظر با الگوریتم های زیر را بدست بیارید ؟

الگوریتم Local Beam Search با مقدار K=1

الگوریتم Simulated Annealing با مقدار T = 1

الگوریتم Simulated Annealing با مقدار T = ∞

شما می توانید من را کمک کنید ؟

با تشکر از شما
AmirGh2 آفلاين است   پاسخ با نقل قول
پاسخ



كاربران در حال ديدن تاپيک: 1 (0 عضو و 1 مهمان)
 
ابزارهاي تاپيک
نحوه نمايش

قوانين ارسال
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is فعال
شکلکها فعال است
كد [IMG] فعال است
كدهاي HTML غير فعال است
Trackbacks are فعال
Pingbacks are فعال
Refbacks are فعال




زمان محلي شما با تنظيم GMT +3.5 هم اکنون ۰۳:۳۵ بعد از ظهر ميباشد.


Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.1.0 ©2007, Crawlability, Inc.

Teach and Learn at Hexib | Sponsored by www.Syavash.com and Product In Review

استفاده از مطالب انجمن در سایر سایت ها، تنها با ذکر انجمن هوش مصنوعي به عنوان منبع و لینک مستقیم به خود مطلب مجاز است

Inactive Reminders By Icora Web Design