آموزش الگوریتم شبیه سازی حرارتی SA | الگوریتم تبرید شبیه سازی شده

مقدمه مقاله آموزش الگوریتم شبیه سازی حرارتی SA

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

کرک پاتریک و همکارانش در سال ۱۹۸۳ الگوریتم شبیه سازی حرارتی SA را با الهام از روش باز پخت فلز معرفی کردند. روش باز پخت، آرایش مولکولی بهینه ذرات فلز را که در آن انرژی پتانسیل جرم به حداقل می‌رسد را تعریف می‌کند و به خنک شدن تدریجی فلزات پس از قرار گرفتن در معرض حرارت زیاد اشاره می‌کند. به‌طور کلی، الگوریتم شبیه سازی حرارتی SA یک حرکت تکراری را با توجه به پارامتری به نام دما که متغیر است، انجام می‌دهد که برای انجام آن، از عملیات انجام‌شده در کار باز پخت فلزات تقلید می‌کند.

بسیاری از مسائل در رشته‌های مختلف را می‌توان به‌عنوان مسائل بهینه‌سازی فرموله کرد و بسیاری از آنها را می‌توان با اتخاذ یکی از دو رویکرد “محبوب” حل کرد: تکنیک‌های تقسیم و حل یا تپه نوردی. در رویکرد اول، راه‌حل وابسته به مسئله است و معمولاً اطلاعات دقیق در مورد مسئله به‌منظور توسعه استراتژی راه‌حل موردنیاز است. همچنین، بسیاری از مسائل را نمی‌توان به بخش‌های کوچک‌تر تقسیم کرد که آنها را جداگانه حل کرد و سپس دوباره ترکیب کرد. در رویکرد دوم، اکثر الگوریتم‌های تپه نوردی مبتنی بر روش‌های گرادیان کاهشی (gradient descent) هستند.

این روش‌ها از یک اشکال عمده یعنی از به دام افتادن در حداقل محلی رنج می‌برند. به این معنا که الگوریتم ممکن است در دره‌ای “به دام” بیفتد، که درنتیجه همه مسیرها به راه‌حل‌های محلی بدتر منتهی می‌شوند و هرگز به راه‌حل بهینه‌ای که خارج از دره قرار دارد نمی‌رسد. الگوریتم SA با واردکردن عنصر تصادفی در فرآیند جستجو از حداقل‌های محلی جلوگیری می‌کند.

در چند سال گذشته الگوریتم شبیه سازی حرارتی SA و توسعه‌ها و اصلاحات فراوان آن به‌طور گسترده برای حل طیف وسیعی از حوزه‌های کاربردی، به‌ویژه در مسائل بهینه‌سازی ترکیبی استفاده‌شده است.

یکی از ویژگی‌های مهم الگوریتم تبرید شبیه سازی شده این است که نیازی به دانش تخصصی در مورد چگونگی حل یک مشکل خاص ندارد. این امر الگوریتم را عمومی می‌کند به این معنا که می‌تواند در انواع مسائل بهینه‌سازی بدون نیاز به تغییر ساختار اساسی محاسبات استفاده شود.

ایده اصلی الگوریتم شبیه سازی حرارتی SA

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

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

آنچه در شبیه سازی الگوریتم حرارتی SA اتفاق می‌افتد بدین شکل است که اگر در فضای جستجو هر نقطه مثل S را شبیه حالتی از فضای فیزیکی در نظر بگیریم و تابع کمینه F(S) انرژی داخلی سیستم در آن حالت باشد هدف این است که سیستم را از حالت اولیه به حالتی ببریم که کمترین انرژی را داشته باشد.

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

پاورپوینت الگوریتم شبیه ساز حرارتی SA

کلیک کنید

تفاوت الگوریتم شبیه سازی حرارتی SA با یک الگوریتم بهینه سازی ساده

یک الگوریتم بهینه‌سازی ساده، خروجی‌های توابع هدف را که در حال اجرا هستند به‌صورت مکرر با نقطه فعلی و نقاط همسایه در دامنه مدنظر مقایسه می‌کند، به‌طوری‌که اگر نقطه همسایه نتیجه بهتری نسبت به فعلی ایجاد کند، به‌عنوان راه‌حل پایه برای تکرار بعدی ذخیره می‌شود. در غیر این صورت، الگوریتم بدون جستجوی دامنه وسیع‌تر برای نتایج بهتر، روند کار را خاتمه می‌دهد.به طوری که الگوریتم مستعد گرفتار شدن در حداقل یا حداکثر محلی است. در عوض، الگوریتم شبیه سازی حرارتی SA یک راه‌حل مؤثر برای این مشکل به‌عنوان ترکیب دو حلقه تکراری پیشنهاد می‌کند که یکی روش خنک‌سازی برای فرآیند بازپخت و دیگری معیار متروپلیس (Metropolis) هست.

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

تطبیق‌پذیری الگوریتم شبیه سازی حرارتی SA در طی چندین سال محققان بسیاری را به خود جذب کرده است و اخیراً تغییرات زیادی در الگوریتم اصلی ایجاد کرده است، ازجمله نسخه‌های موازی برای سرعت بخشیدن به‌سرعت محاسبات را می‌توان نام برد.

شبه کد الگوریتم حرارتی SA

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

set S ← S0 (حالت آغازین بصورت تصادفی)
Set T ← T0 (دمای اولیه)
While (شرط پایانی برقرار نشده) do
  While (تعداد مراحل مورد نیاز تولید نشده است) do
   Generate a new state (S') by perturbing S
    Evaluate E
    Compute ΔΕ = E(S') - E (S)
    If (ΔΕ ≤ ۰ ) then
       S ← S'
      Else
        Generate a random variable α , ۰ ≤ α ≤ ۱
        If α ≤ e به توان(-ΔΕ)/T then S ← S'
    End
  End
  Update T (کاهشی)
End

برای اینکه بتوانیم شبیه سازی حرارتی SA یا همان شبیه سازی تبرید را در مورد مسئله خاصی پیاده‌سازی کنیم یکسری پارامترها را نیاز داریم. فضای حالت، تابع انرژی همان‌طور که در شبه کد مشخص است تابع ()E، تابع همسایه که تولید S جدید را انجام دهد. تابعی که احتمال پذیرفتن همسایه جدید را به‌عنوان حالت فعلی بررسی کند مقدار اولیه برای دما و البته تابعی که زمان‌بندی دما را انجام دهد. البته می‌دانیم که روش مشخصی برای انتخاب درست پارامترها وجود ندارد.

مثلاً اگر الگوریتم شبیه سازی حرارتی SA را در مورد مسئله فروشنده دوره‌گرد را در نظر بگیریم. چند تا شهر داریم که هدف این است که یک فردی تمام شهرها را بدون تکرار و البته با کمترین انرژی (که در اینجا منظور فاصله بین شهرها است) طی کند و درنهایت به نقطه اولیه برگردد.

روند الگوریتم شبیه سازی حرارتی SA

روند الگوریتم تبرید یا شبیه سازی حرارتی بستگی به چندین موضوع دارد که در ادامه به آن‌ها می‌پردازیم:

• حالت گذر

راه رفتن تصادفی روی S را فرض کنید که به یک توزیع یکنواخت در S همگرا می‌شود. موضوعی به نام حالت گذار داریم که در این حالت احتمال اینکه بر روی یال (s’,s) از حالت s به حالت ‘s گذر داشته باشیم، مطرح می‌شود. این احتمال به دمایی که داریم به همسایه‌ای که انتخاب می‌شود و تابعی که پذیرش این تغییر موقعیت را محاسبه می‌کند (این تابع دارای ورودی‌های E(s) و E(s’) و T است) بستگی دارد.

• احتمال پذیرفته شدن

همان‌طور که قبلاً اشاره کردیم این مسئله توسط آقای کرک پاتریک فرموله شده است در آن تابعی به‌صورت P(e,’e, T) به‌عنوان تابع پذیرش مطرح است زمانی که ‘e (انرژی گره همسایه) کمتر از e (انرژی گره کنونی) باشد برابر ۱ خواهد بود در غیر این صورت برابر e به توان (ΔΕ -) تقسیم بر Tخواهد بود که ΔΕ همان (e’-e) می‌باشد. این فرمول شبیه الگوریتم مترو پلیس هنگامی‌که T برابر ۱ هست، می‌باشد.

• ایجاد گره های کاندید مناسب

در انتخاب تابعی که همسایه را مشخص می‌کند باید انتظار داشته باشیم که بعد از تعداد تکرار قابل‌ قبول حالتی که سیستم به خود می‌گیرد انرژی کمتری نسبت به حالت اولیه آن داشته باشد. بنابراین باید طبق یک قراردادی این تولیدکننده گره کاندید باید به‌طرفی حرکت کند که انرژی ‘S شبیه انرژی S باشد. این روش نشان داده است که معمولاً حالات خیلی خوب و بیشتر حالات خیلی بد را در نظر نمی‌گیرد یا حذف می‌کند و این نشان می‌دهد که این الگوریتم خوب کار می‌کند.

به‌عنوان‌مثال در مسئله فروشنده دوره‌گرد که در بالا نیز به آن اشاره کردیم مسلماً انتظار داریم که جابه‌جایی بین دو شهر نزدیک تأثیر چندانی روی تغییر انرژی نداشته باشد ولی اگر حرکت یا رفت‌وآمد بین دو شهر دلخواه را در نظر بگیریم احتمال اینکه انرژی بیشتر صرف شود بالا است. می‌توان حالتی را که در آن تابع پذیرش P(e,’e,T) مقدار بزرگی را دارد انتخاب کنیم درواقع انتخاب دو شهر که فاصله آن‌ها از هم زیاد است را کاهش دهیم.

• دوری از موانع

در الگوریتم شبیه سازی حرارتی SA در انتخاب تابع همسایه باید به این امر توجه کنیم تا تعداد کمینه‌های محلی را کاهش دهیم. به این صورت که سعی شود حالاتی که همسایه‌های زیادی در اطراف آن انرژی کمتری دارند پیش نیاید. که اگر این اتفاق بیفتد احتمال دارد که الگوریتم شبیه سازی حرارتی SA برای مدت طولانی و با احتمال بالاتری گرفتار شود به اصلاح به دام می‌افتد. ضمنا می توان کارایی تابع همسایه را با یکسری تغییرات ساده به میزان قابل قبولی افزایش داد.

بعضی مواقع بهتر است تا به پاسخ قبلی که نتیجه بسیار بهتری بوده برگشته شود تا اینکه از حالت فعلی حرکتی در جهت ادامه داده شود. این حرکت را restarting یا شروع مجدد گفته می‌شود. برای این کار در حالت‌های قبلی باید دو حالت ebest و sbest اضافه شود و الگوریتم دوباره شروع به‌کار نماید.

الگوریتم شبیه ساز حرارتی SA برای حل مسئله فروشنده دوره گرد TSP در متلب

کلیک کنید

فلوچارت الگوریتم شبیه سازی حرارتی SA

سخن آخر در مورد الگوریتم شبیه سازی حرارتی SA

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