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

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

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

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

[1] Simulated Annealing

[2] Kirkpatrick

[3] Cerny

لینک جزییات بیشتر و دانلود این پایان نامه:

توسعه یک مدل بهینه سازی چند هدفه برای طراحی شبکه زنجیره تأمین در شرایط عدم قطعیت با در نظر گرفتن سطوح کیفی