الگوریتم تبرید شبیه‌سازی‌شده
الگوریتم تبرید شبیه‌سازی‌شده (Simulated Annealing) (SA)، یک الگوریتم بهینه‌سازی فراابتکاری ساده و اثربخش در حل مسائل بهینه‌سازی در فضاهای جستجوی بزرگ است. این الگوریتم بیشتر زمانی استفاده می‌شود که فضای جستجو گسسته باشد (مثلاً همه گشت‌هایی که از یک مجموعه از شهرها میگذرند). برای مسائلی که پیدا کردن یک پاسخ تقریبی برای بهینه کلی مهمتر از پیدا کردن یک پاسخ دقیق برای بهینه محلی در زمان محدود و مشخصی است، تبرید شبیه‌سازی شده ممکن است نسبت به باقی روش‌ها مانند گرادیان کاهشی دارای ارجحییت باشد.
تکنیک تبرید تدریجی، به وسیلهٔ متالورژیست‌ها برای رسیدن به حالتی که در آن ماده جامد، به خوبی مرتب و انرژی آن کمینه شده باشد، استفاده می‌شود. هدف از این کار این است که سایز کریستال‌ها در حالت جامد ماده در حال تبرید به بزرگترین حالت برسد. این تکنیک شامل قرار دادن ماده در دمای بالا و سپس کم کردن تدریجی این دماست. شبیه سازی تبرید رویکردی است که مسئله کمینه سازی یک تابع با تعداد بسیار زیادی متغیر است را به یک مسئله مکانیک آماری کاهش می‌دهد. بنیان گذاران این الگوریتم برای حل مسائل سخت بهینه‌سازی، روشی مبتنی بر تکنیک تبرید تدریجی و آرام پیشنهاد نمودند. این محققین برای مدلسازی تبرید یک سیستم به منظور پیدا کردن پاسخ کمینه کلی، از شبیه سازی کامپیوتری استفاده کردند.
می‌توان تبرید تدریجی و آرام در این الگوریتم را به عنوان کاهش تدریجی احتمال انتخاب پاسخ‌های بدتر حین جستجو در فضای پاسخ‌ها دانست (انتخاب پاسخ‌های بدتر یک ویژگی اساسی الگوریتم‌های فراابتگاری است و پیدا کردن بهترین پاسخ را ممکن می‌سازد). شبیه سازی را می‌توان به دو صورت حل روابط کینتیکی برای توابع چگالی (مانند کار خاچاتوریان، سمونوفسکایا و وینشتاین در سال ۱۹۷۹ و ۱۹۸۱) یا استفاده از نمونه‌گیری تصادفی، انجام داد. نمونه گیری تصادفی در سال ۱۹۸۳ توسط کریک‌پاتریک، گلت و کلی معرفی شد،‌ کرنی در سال ۱۹۸۵ و خاچاتوریان، سمونوفسکایا و وینشتاین در سال ۱۹۸۵ به‌طور مستقل این ایده را مطرح کردند. این روش یک اقتباس از الگوریتم متروپولیس-هستینگز است، یک روش مونت کارلو که نمونه حالت‌هایی را از یک سیستم ترمودینامیک تولید می‌کند.
در روش (SA)، هر نقطه "s" در فضای جستجو مشابه یک حالت از یک سیستم فیزیکی است، و تابع ("E"("s" که باید کمینه شود، مشابه با انرژی داخلی سیستم در آن حالت است. در این روش، هدف انتقال سیستم از "حالت اولیه" دلخواه، به حالتی است که سیستم در آن کمترین انرژی را داشته باشد.
در هر گام، تبرید شبیه‌سازی‌شده یک حالت همسایه را در نظر می‌گیرد و به صورت احتمالی بین جابه‌جایی به حالت جدید یا ماندن در حالت قبلی تصمیم می‌گیرد. این احتمالات در نهایت سیستم را به سمت حالت‌های با انرژی کمتر هدایت می‌کنند. معمولاً این مرحله آن قدر تکرار می‌شود که سیستم به یک حالت معقول برسد، یا اینکه میزان اعمال محاسباتی از یک حد مشخص عبور کند.
همسایه‌های یک حالت (جواب)، حالت‌های جدیدی از مسئله هستند که با تغییر در حالت کنونی و با توجه به روشی از پیش تعیین شده ایجاد می‌شوند. برای مثال در ، هر حالت به‌طور کلی یک جایگشت خاص از شهرهایی است که باید ملاقات شوند. همسایهٔ یک جواب، جایگشت‌هایی هستند که با انتخاب یک جفت از شهرهای هم جوار، از کل مجموعه جایگشت‌ها، و جابجا کردن آن دو شهر ایجاد می‌شوند. عمل تغییر در جواب فعلی و رفتن به جواب‌های همسایه «حرکت» (move) خوانده می‌شود و «حرکت»‌های متفاوت، همسایه‌های گوناگون را بدست می‌دهد.
روش‌های ابتکاری ساده مانند تپه‌نوردی، که با یافتن بهترین همسایه بین همسایه‌های بهتر از حالت کنونی حرکت می‌کنند و زمانی متوقف می‌شوند که به حالتی برسند که هیچ همسایهٔ بهتری برای حالت کنونی نباشد، نمی‌توانند تضمین کنند که همیشه به بهترین جواب رسیده‌اند و ممکن است خروجی آن‌ها تنها یک حالت بهینهٔ محلی باشد. الگوریتم‌های فراابتکاری از همسایه‌های یک جواب برای جستجو فضای جواب‌ها استفاده می‌کنند و اگر چه همسایه‌های بهتر را ترجیح می‌دهند، همسایه‌ای بدتر را هم رد نمی‌کنند تا در یک بهینه محلی گرفتار نشوند. نشان‌ داده شده‌است که این الگوریتم‌ها با صرف یک زمان کافی می‌توانند بهترین جواب کلی را پیدا کنند.
احتمال یک انتقال از حالت کنونی مانند formula_1 به یک حالت کاندید جدید مانند formula_2 با یک تابع احتمال پذیرش مثل formula_3 مشخص می‌شود که در آن formula_4 و formula_5 است (تابع formula_6 روی فضای حالت نشان‌دهنده انرژی و formula_7 نشان‌دهنده دمای متغیر‌‌ با زمان سیستم است). حالات با انرژی کمتر بهتر از حالات با انرژی بالاتر هستند. تابع احتمال formula_8 باید مثبت باشد حتی زمانی که formula_9 کوچکتر از formula_10 است. این ویژگی تضمین می‌کند که الگوریتم در یک پاسخ محلی بدتر از پاسخ سراسری بهینه گرفتار نشود.
زمانی که formula_7 به صفر میل می‌کند‌‌‌‌، احتمال formula_8 یا باید به صفر میل کند (formula_9 کوچیکتر از formula_10) یا اینکه به یک عدد مثبت میل کند (formula_10 کوچکتر از formula_9). برای مقادیر به اندازه کافی کوچک از formula_7، سیستم به مرور به سمت نقطه با کمینه انرژی حرکت می‌کند و به سمت نقاط با انرژی بیشتر حرکت نخواهد کرد. با قرار دادن formula_18 مسئله به یک الگوریتم حریصانه تقلیل پیدا می‌کند که تنها به سمت نقاط با انرژی کمتر حرکاتش را انجام می‌دهد.
در صورت اولیهٔ تبرید شبیه‌سازی شده، احتمال formula_3 زمانی که formula_10 کوچکتر از formula_9 باشد برابر ۱ می‌شود، که به این معنی است که رویه همیشه مستقل از دما به سمت نقاط پایین‌تر حرکت می‌کند. بسیاری از صورت بندی‌ها و پیاده‌سازی‌های تبرید شبیه‌سازی‌شده همچنان این شرط را به عنوان بخشی از تعریف روش در نظر می‌گیرند‌، اگر چه این شرط برای کارکردن روش الزامی نیست.
تابع formula_8 همواره به گونه‌ای انتخاب می‌شود که احتمال پذیرش یک حرکت زمانی که تفاوت بین دو حالت کمتر است کاهش یابد، به‌طور مثال حرکات کوچک رو به بالا محتمل‌تر از حرکاتبزرگ هستند. در هر حال، در صورتی که شروط قبلی برقرار باشند، این شرط به‌طور اکید الزامی نیست.
با این تفاسیر، دما نقش اساسی را در کنترل‌کردن تغییرات در سیستم با توجه به حساسیت آن نسبت به تغییرات انرژی ایفا می‌کند. به‌طور دقیق‌تر، در مقادیر بزرگ formula_7، تغییرات در حالت سیستم نسبت به تغییرات بزرگتری در سیستم حساس است تا زمانی که دما کوچکتر است. نام و ایده بنیادین الگوریتم منشا‌ٔگرفته از ویژگی دما است. این ویژگی در واقع به گونه‌ای کنترل می‌شود که دما حین شبیه‌سازی به صورت تدریجی کاهش می‌یابد. الگوریتم با قرار دادن formula_24 شروع می‌شود (در واقع دما در ابتدا یک مقدار بزرگ را اختیار می‌کند) و در هر گام طبق یک زمان‌بندی از پیش‌تعیین‌شده کاهش می‌یابد. در تعیین این زمان‌بندی باید توجه داشت که با اتمام‌ منابع مورد استفاده مانند تعداد محاسبات، زمان انجام عملیات‌ها هم تمام شود. برای انجام این کار انتظار می‌رود در ابتدا الگوریتم در فضای بزرگی از پاسخ‌ها و بی‌توجه به تابع انرژی به دنبال جواب بگردد. سپس به سمت مناطق با انرژی کمتر پرش کند و این منطقه به مرور کوچک و کوچکتر شود تا زمانی که سیستم دقیقا به پایین‌ترین نقطه سراسری برسد.دو شکل روبرو نشان‌دهندهٔ تأثیر زمان‌بندی تبرید بر کارایی الگوریتم هستند. مسئله بازترتیبی پیکسل‌های یک عکس به منظور کمینه کردن انرژی واقعی تصویر است، که باعث می‌شود رنگ‌های مشابه به هم نزدیک‌تر باشند و رنگ‌های متفاوت در فاصله دورتری از هم قرار بگیرند. دو شکل روبرو از دو زمان‌بندی سریع و آرام در بدست آمده‌اند.
برای هر مسئله با فضای متناهی، احتمال این که الگوریتم تبرید در یک نقطه بهینهٔ سراسری کار خود را تمام کند با افزایش زمان به ۱ میل می‌کند. اگرچه این نتیجهٔ نظری چندان راهگشا نیست زیرا میزان زمانی که لازم است تا احتمال رسیدن به جواب از حدی معقول بیشتر شود معمولاً بیشتر از زمانی است که برای جستجوی کل فضا لازم است.
برای حل یک مسئلهٔ بهینه‌سازی، الگوریتم SA ابتدا از یک جواب اولیه شروع می‌کند و سپس در یک حلقه تکرار به جواب‌های همسایه حرکت می‌کند. اگر جواب همسایه بهتر از جواب فعلی باشد، الگوریتم آن را به عنوان جواب فعلی قرار می‌دهد (به آن حرکت می‌کند)، در غیر این صورت، الگوریتم آن جواب را با احتمال exp(-ΔE/T) به عنوان جواب فعلی می‌پذیرد. در این رابطه ΔE تفاوت بین تابع هدف جواب فعلی و جواب همسایه‌است و T یک پارامتر به نام دما است. در هر دما، چندین تکرار اجرا می‌شود و سپس دما به آرامی کاهش داده می‌شود. در گام‌های اولیه دما خیلی بالا قرار داده می‌شود تا احتمال بیشتری برای پذیرش جواب‌های بدتر وجود داشته باشد. با کاهش تدریجی دما، در گام‌های پایانی احتمال کمتری برای پذیرش جواب‌های بدتر وجود خواهد داشت و بنابراین الگوریتم به سمت یک جواب خوب همگرا می‌شود. الگوریتم SAیک الگوریتم غیرمقید می‌باشد که برای طراحی‌های سخت به کار می‌رود.
شبه کد زیر یک پیاده‌سازی از تبرید شبیه‌سازی شده را ارائه نشان می‌دهد. این الگوریتم از حالت formula_25 شروع می‌کند و تا رسیدن به حداکثر گام‌ها‌، formula_26 یا رسیدن به حالتی با انرژی formula_27 یا کمتر از آن متوقف می‌شود. در این روند، صدا کردن تابع formula_28 یک همسایه رندوم حالت فعلی را انتخاب می‌کند. تابع formula_29 یک عدد را در بازه formula_30 به صورت یکنواخت انتخاب می‌کند. زمان‌بندی تبرید با صدا کردن تابع formula_31 تعریف می‌شود، که در هر مرحله دمای سیستم را بر حسب ‌‌‌زمان به دست می‌دهد.
برای اعمال تبرید شبیه‌سازی‌شده به یک مسئله خاص، باید این پارامترها را مشخص کرد: فضای حالت،‌ تابع انرژی formula_6، تابع formula_28، تابع احتمال پذیرش formula_8، و تابع زمان‌بندی formula_31 و البته مقدار اولیه برای دما. این انتخاب‌ها می‌توانند تأثیرات اساسی روی کارایی این روش بگذراند. متاسفانه، هیچ روشی برای انتخاب پارامترهای مناسب برای تمام مسائل وجود ندارد و برای هر مسئله باید به‌طور خاص بهترین پارامترها را یافت. در ادامه نکاتی در همین زمینه گفته خواهد شد.
تبرید شبیه‌سازی‌شده می‌تواند مانند یک قدم‌زدن تصادفی روی یک گراف جستجو مدل شود که راس‌های آن تمام حالات ممکن هستند و یال‌های آن حرکات کاندید. یک شرط لازم برای تابع formula_28 این است که باید یک مسیر نسبتا کوتاه را از حالت اولیه به هر حالت دیگری را که می‌تواند بهینهٔ سراسری باشد فراهم کند. در واقع قطر گراف جستجو باید کوتاه باشد. در مسئله فروشندهٔ دوره‌گرد اندازه‌ٔ فضای حالت دارای برای ۲۰ شهر برابر۲۴۳۲۹۰۲۰۰۸۱۷۶۶۴۰۰۰۰ است، ولی تابع همسایه که دو شهر نزدیک را همسایه می‌گیرد می‌تواند در حداکثر ۱۹۰ گام به بهینه سراسری برسد.
برای تحقیق در رفتار تبرید شبیه‌سازی‌شده در یک مسئله خاص، توجه به احتمالات گذار که نتیجهٔ انتخاب‌های اولیه در پیاده‌سازی هستند، راهگشا خواهد بود. برای هر یال formula_37 در گراف جستجو، احتمال گذار برابر احتمال آن است که الگوریتم به حالت formula_2 برود زمانی که حالت کنونی formula_1 است. این احتمال به دمای کنونی که توسط تابع formula_31 تعیین می‌شود، به ترتیبی که توسط formula_28 تعیین می‌شود و به تابع احتمال پذیرش formula_8 بستگی دارد. (دقت کنید که احتمال گذار تنها formula_3 نیست زیرا همسایه‌های کاندید در این روش تک تک بررسی می‌شوند.)
تعیین توابع formula_44، formula_31 و formula_8 شامل کمی فزون‌کاری است. در عمل تابع formula_8 برای بسیاری از مسائل یکسان انتخاب می‌شود و دو تابع دیگر با توجه به مسئله تعیین می‌شوند.
در فرمول‌بندی مسئله توسط کریک‌پاتریک و همکاران، تابع formula_3 زمانی که formula_10 کوچکتر از formula_9 باشد برابر ۱ و در غیر این صورت برابر formula_51 تعریف می‌شود. این فرمول به صورت سطحی طبق گذارهای یک سیستم فیزیکی توجیه‌پذیر است. در واقع این فرمول‌بندی مطابق الگوریتم متروپلیس-هستینگز است زمانی که formula_52 و توزیع استفاده شده در متروپلیس-هستنیگز متقارن است. با این حال، این احتمال پذیرش اکثرا در تبرید ‌شبیه‌سازی‌شده استفاده می‌شود، حتی زمانی که تابع formula_28 متقارن نباشد یا حتی زمانی که احتمالاتی نباشد. در نتیجه، احتملالات گذار در الگوریتم تبرید‌ شبیه‌سازی‌شده مطابق گذارهای سیستم فیزیکی مذکور نیستند و در توزیع حالات در بلند مدت در یک دمای ثابت formula_7 ملزم به شباهت به یک توزیع تعادل ترمودینامیکیروی حالات سیستم فیزیکی در هیچ دمایی نیست. در هر حال، بیشتر صورت‌های تبرید شبیه‌سازی‌شده همان صورت اولیه را انتخاب می‌کنند که احتمالا بارها پیاده‌سازی شده‌است.
در انتخاب تابع formula_28 باید این را در نظر گرفت که پس از تعداد معقولی تکرار الگوریتم، انتظار می‌رود حالت سیستم، انرژی به مراتب کمتری از حالت ابتدایی داشته باشد. بنابراین به عنوان یک قانون کلی باید تولیدکننده کاندیدها یا همان formula_44 را به سمت کاندیدی حرکت داد که انرژی حالت جدید formula_2، شبیه به انرژی حالت کنونی باشد. این روش فراابتکاری (که اساس الگوریتم متروپولیس-هستینگز هم هست) معمولاً حرکات "بسیار خوب" و حرکات "بسیار بد" را حذف میکند. البته بیشتر حرکات بد ممکن هستند تا حرکات خوب و این نشان می‌دهد که الگوریتم تقریباً کارا عمل می‌کند.
برای مثال در مسئله فروشندهٔ دوره‌گرد که پیش‌تر به آن اشاره شد، انتظار می‌رود جابه‌جایی از یک شهر به شهر نزدیک آن در یک گشت با انرژی کم، تأثیر نسبتاً کمی روی تغییر انرژی بگذارد، در حالیکه جابه‌جایی بین دو شهر دلخواه بسیار محتمل تر است که انرژی بیشتری را هزینه کند (منظور از انرژی اینجا همان طول است).
یک بیان دقیق‌تر از این روش فراابتکاری این است که حالات formula_2 که برای آن‌ها formula_3 بزرگ است را انتخاب کند. بنابراین، در مثال فروشندهٔ دوره‌گرد، می‌توان از formula_44 ی استفاده کرد که احتمال انتخاب دو شهر برای جابه‌جایی با افزایش فاصله آن‌ها کاهش يابد.
برای انتخاب تابع formula_44 علاوه بر ملاحظات قبلی باید تلاش کرد تا تعداد کمینه‌های محلی "عمیق" (حالاتی که به میزان زیادی از همسایه‌هایشان انرژی کمتری دارند) را کاهش داد. چنین نقاطی می‌توانند الگوریتم تبرید‌ شبیه‌سازی‌شده را با احتمال بالایی (تقریبا متناسب با کل تعداد حالات در یک همسایگی) و برای زمان زیادی (تقریبا نمایی بر حسب تفاوت انرژی با همسایه‌ها در همسایگی) به دام بیاندازند.
به عنوان یک اصل، طراحی یک تولیدکننده‌ کاندید که بتواند این هدف را ارضا کند غیرممکن است. به علاوه معمولاً میتوان کارایی تبرید ‌شبیه‌سازی‌شده را با تغییرات ساده در تابع formula_44 به میزان زیادی افزایش داد.
توجیه فیزیکی که برای تبرید شبیه‌سازی‌شده استفاده می‌شود، فرض می‌کند که نرخ سردکردن به اندازهٔ کافی آرام است به‌طوری‌که توزیع احتمال حالت کنونی همواره نزدیک به تعادل ترمودینامیکی باشد. متاسفانه، زمان سست سازی یا relaxation (زمانی که باید صبر کرد تا تعادل ترمودینامیکی که به دلیل تغییر دما بر هم خورده‌است دوباره برقرار شود) بسیار به شکل تابع انرژی و دمای کنونی وابسته است. در الگوریتم تبرید شبیه‌سازی‌شده، زمان سست سازی همچینین به تابع تولید‌کننده‌ کاندید هم به شکل پیچیده‌ای واسبته است. توجه کنید که تمام این پارامترها معمولاً به عنوان توابع پییچده و نه چندان مشخصی برای الگوریتم تعیین می‌شوند. بنابراین، بهترین نرخ سردسازی (کاهش دما)‌ را نمی‌توان پیش از اجرای الگوریتم تعیین کرد و باید به صورت تجربی برای هر مسئله‌ای به‌طور خاص محاسبته شود. الگوریتم‌های تبرید‌ شبیه‌سازی‌شده تطبقی این مسئله را با ربط دادن زمان‌بندی سرسازی به فرایند جستجو حل می‌کنند.
گاهی اوقات بهتر است تا به یک پاسخی که قبلا پیدا شده‌است و بسیار بهتر بوده برگردیم تا اینکه از همین حالت فعلی حرکتی را انجام دهیم . این رویه را شروع دوباره یا restarting می‌گویند. برای انجام این کار باید در شبه کد بالا s و e را برابر sbest و ebest قرار دهیم و دوباره الگوریتم را آغاز کنیم. تصمیم برای آغاز مجدد می‌تواند بر حسب معیارهای مختلفی باشد. یکی از رایج‌ترین روش‌ها شروع مجدد بعد از تعدادی گام مشخص، شروع مجدد به دلیل رد شدن از حداکثر انرژی سیستم، شروع مجدد تصادفی و ... است.