الگوریتم شبیه سازی تبریدی (SA)

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

برای تعریف خصوصیات نیاز به چند تعریف داریم.  را فضای جواب در بگیرید.  را تابع هدف قرار دهید. هدف یافتن بهینه سراسری  (یعنی  که در آن  به ازای تمام ) است.  را به عنوان تابع همسایگی تعریف می کنیم. بنابراین، هر پاسخ   دارای همسایه هایی است که از طریق یک حرکت قابل تبدیل به یکدیگر هستند.

SAبا یک پاسخ اولیه  شروع می­ کند. سپس یک پاسخ همسایه  تولید می­ کند. جواب  که همسایه  است، بر اساس احتمال زیر پذیرفته می­ شود.

Simulated Annealing

Kirkpatrick

Cerny