الگوریتم 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 پیشنهاد گردید که در ادامه به بررسی آن نیز می پردازیم.