روش شبیه سازی تبريد تدریجی ( simulated Annealing )
روش شبیه سازی تبريد تدریجی ( simulated Annealing )
• SA یک روش جستجوی تصادفی قوی است که به منظور یافتن یک جواب خوب ( نه لزوما بهینه ) برای مسائل مشکل ترکیباتی combinatorial به کار می رود .
SA از فرايند فيزيكي خنك سازي مواد مذاب به حالت جامد الهام گرفته است.
• این روش برخلاف روش های جستجوی معمولی، در هر تکرار علاوه بر حرکت به سوی جواب بهتر، جواب های با مقدار تابع هدف بهتر را نیز با احتمال غیر صفری قبول می کند.
فرایند آنیل کردن فلزات :
• اگر ماده های جامد مذاب بسیار آهسته تبرید شوند ( تا حالت جامد ) اتم های آنها به صورت منظم در شبکه بلوری قرار گرفته و ماده جامد حاصل دارای حداقل سطح انرژی خواهد بود . به این روش تبرید آهسته آنیل کردن گویند.
• در شرایط تعادلی ( تبرید تدریجی ) برای هر دمای داده شده ، احتمال این که ذرات ماده دارای سطح انرژی خاصی باشند ، طبق تابع توزیع بولتز من محاسبه می گردد .
• این احتمال در ابتدا بزرگ است و ضمن اجرای روش متناسب با پارامتر مثبتی به نام دما
( Temprature ) کاهش پیدا می کند. در نتیجه روش SA از نظر تئوری با غلبه بر بهینگی محلی، قادر به یافتن جواب بهینه مطلق نیز خواهد بود.
• حال یک مساله عمومی مینیمم سازی را در نظر بگیرید. ایده اصلی در روش SA تولید جواب در همسایگی جواب فعلی و محاسبه موثر تغییر در مقدار تابع هدف، Δf می باشد. سپس ضمن ذخیره بهترین جواب به دست آمده اگر 0≥Δf باشد، جواب جدید قطعا پذیرفته می شود. در غیر این صورت اگر Δf>0 باشد، جواب جدید با احتمال پذیرفته می شود.
• T دمای سیستم که درجه تصادفی بودن حرکت به سوی جواب را تعیین می کند، مطابق با یک برنامه معین با پیشرفت روش حل، کاسته می شود.
• در واقع دمای سیستم مشخص کننده زیر فضای جواب مساله است که در هر تکرار مورد قبول قرار می گیرد.
• در دمای بالا تقریبا تمام جواب های تولید شده صرف نظر از مقدار تابع هدف پذیرفته می شوند. با پیشرفت الگوریتم و کاهش دما، جواب های نامناسب شانس کمتری برای پذیرفته شدن دارند. در واقع، در هر دما، احتمال پذیرفتن جواب با مقدار تابع هدف بیشتر، بستگی به اندازه افزایش Δf دارد.
• به منظور کاربرد SA برای هر مساله بهینه سازی باید دو دسته از پارامترها تعیین گردند. دسته اول پارامترهای مربوط به کنترل دما و تعداد جواب هایی که باید تولید شوند و دسته دوم مربوط به ویژگی های خاص مساله مورد نظر می باشد.
پارامترهای SA :
• نقطه شروع : یک جواب قابل قبول که معمولا به صورت تصادفی ایجاد میشود .
• نقطه شروع بر سرعت همگرایی الگوریتم تا حدی موثر است .
• برای گسترش فضای جستجو و گریز از بهینه های محلی ، معمولا الگوریتم از چندین نقطه شروع مختلف اجرا می شود .
• دمای اولیه (c0 ) : مقدار دمای اولیه تابع توزیع بولتز من می باسیت به گونه ای ساخته باشد تا مقدار تابع نزدیک به یک باشد .
• معمولا در اکثر کاربردها مقادیر0.85 – 0.95 مطلوب است .
• مقادیر بسیار بزرگ C0 ( به همراه نرخ سرمایش آهسته ) موجب طولانی شدن مدت اجرا و گسترش فضای جستجو می شود .
• مقادیر بسیار کوچک C0 ممکن است موجب همگرایی زود هنگام شده الگوریتم در بهینه محلی متوقف شود .
• انتخاب پارامترهای عمومی به مساله بهینه سازی و موارد خاص مورد نظر بستگی دارد.
• دمای اولیه بايد به طریقی تعیین گردد که احتمال قبول و رد جواب ها برای حالت Δf>0 در تکرار اول روش برابر باشد.
• استراتژی خنک کردن سیستم، چگونگی کاهش دما را در حین تکرارهای روش تعیین می کند. کیفیت جواب SA به میزان زیادی بستگی به تعداد جواب هایی دارد که در هر دما مورد بررسی قرار می گیرند.
• بنابراین مقدار این پارامترهم بستگی به ابعاد مساله دارد و با چندبار اجرای آزمایشی روش برای مقادیر مختلف تعیین می شود.
• تصمیمات اختصاصی شامل اين است كه در هر تکرار روش SA بایستی تعداد زیادی جواب تولید شوند تا یک تعادل حرارتی در هر دما برقرار گردد.
• اگرچه SA ضمن سادگی ابزاری قوی برای حل مسائل بهینه سازی ترکیباتي می باشد ولی دقت زیادی در انتخاب نحوه تولید موثر جواب ها، زمان بندی خنک کردن و کفایت تعداد جواب های تولید شده لازم است. با این وجود زمینه هایی نیز برای بهبود روش وجود دارد.
• همگرایی به یک راه حل بهینه در SA بعد از تعداد نامحدود تکرار ها به وسیله برنامه خنک سازی کنترل می شود. پارامتر کنترل اصلی در برنامه خنک سازی پارامتر دما T می باشد.
|