روش شبیه سازی تبرید تدریجی ( simulated Annealing)

  • 89/08/18
  • شيمي

در غیر این صورت جستجوگر جواب جدیدی را تولید و ارزیابی خواهد نمود. این حرکت گام ‌به‌گام تا ارضاء شرط توقف الگوریتم (تعداد تکرارها، زمان محاسبات، و …. ) ادامه می‌یابد.

مقدار تابع احتمال حرکت در هر بار از رابطه محاسبه می‌شود. در این رابطه اختلاف مقدار تابع هدف بین جواب فعلی و جواب جدید است.

SA در واقع یک روش جستجوی تصادفی قوی است که به منظور یافتن یک جواب خوب ( نه لزوما بهینه ) برای مسائل مشکل ترکیباتی combinatorial به کار می رود .
• این روش برخلاف روش های جستجوی معمولی، در هر تکرار علاوه بر حرکت به سوی جواب بهتر، جواب های با مقدار تابع هدف بهتر را نیز با احتمال غیر صفری قبول می کند.

SA از فرایند فیزیکی خنک سازی مواد مذاب به حالت جامد الهام گرفته است.

فرایند آنیل کردن فلزات :
• اگر ماده های جامد مذاب بسیار آهسته تبرید شوند ( تا حالت جامد ) اتم های آنها به صورت منظم در شبکه بلوری قرار گرفته و ماده جامد حاصل دارای حداقل سطح انرژی خواهد بود . به این روش تبرید آهسته آنیل کردن گویند.

• در شرایط تعادلی ( تبرید تدریجی ) برای هر دمای داده شده ، احتمال این که ذرات ماده دارای سطح انرژی خاصی باشند ، طبق تابع توزیع بولتز من محاسبه می گردد .

• این احتمال در ابتدا بزرگ است و ضمن اجرای روش متناسب با پارامتر مثبتی به نام دما    ( Temprature ) کاهش پیدا می کند. در نتیجه روش SA از نظر تئوری با غلبه بر بهینگی محلی، قادر به یافتن جواب بهینه مطلق نیز خواهد بود.

• حال یک مساله عمومی مینیمم سازی را در نظر بگیرید. ایده اصلی در روش SA تولید جواب در همسایگی جواب فعلی و محاسبه موثر تغییر در مقدار تابع هدف، Δf می باشد. سپس ضمن ذخیره بهترین جواب به دست آمده اگر ۰≥Δf باشد، جواب جدید قطعا پذیرفته می شود. در غیر این صورت اگر Δf>0 باشد، جواب جدید با احتمال پذیرفته می شود.

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

• در واقع دمای سیستم مشخص کننده زیر فضای جواب مساله است که در هر تکرار مورد قبول قرار می گیرد.

• در دمای بالا تقریبا تمام جواب های تولید شده صرف نظر از مقدار تابع هدف پذیرفته می شوند. با پیشرفت الگوریتم و کاهش دما، جواب های نامناسب شانس کمتری برای پذیرفته شدن دارند. در واقع، در هر دما، احتمال پذیرفتن جواب با مقدار تابع هدف بیشتر، بستگی به اندازه افزایش Δf دارد.

• به منظور کاربرد SA برای هر مساله بهینه سازی باید دو دسته از پارامترها تعیین گردند. دسته اول پارامترهای مربوط به کنترل دما و تعداد جواب هایی که باید تولید شوند و دسته دوم مربوط به ویژگی های خاص مساله مورد نظر می باشد.

پارامترهای SA :

• نقطه شروع : یک جواب قابل قبول که معمولا به صورت تصادفی ایجاد میشود .

• نقطه شروع بر سرعت همگرایی الگوریتم تا حدی موثر است .

• برای گسترش فضای جستجو و گریز از بهینه های محلی ، معمولا الگوریتم از چندین نقطه شروع مختلف اجرا می شود .

• دمای اولیه (c0 ) : مقدار دمای اولیه تابع توزیع بولتز من می باسیت به گونه ای ساخته باشد تا مقدار تابع نزدیک به یک باشد .

• معمولا در اکثر کاربردها مقادیر۰٫۸۵ – ۰٫۹۵ مطلوب است .

• مقادیر بسیار بزرگ C0 ( به همراه نرخ سرمایش آهسته ) موجب طولانی شدن مدت اجرا و گسترش فضای جستجو می شود .

• مقادیر بسیار کوچک C0 ممکن است موجب همگرایی زود هنگام شده الگوریتم در بهینه محلی متوقف شود .

• انتخاب پارامترهای عمومی به مساله بهینه سازی و موارد خاص مورد نظر بستگی دارد.

• دمای اولیه باید به طریقی تعیین گردد که احتمال قبول و رد جواب ها برای حالت Δf>0 در تکرار اول روش برابر باشد.

• استراتژی خنک کردن سیستم، چگونگی کاهش دما را در حین تکرارهای روش تعیین می کند. کیفیت جواب SA به میزان زیادی بستگی به تعداد جواب هایی دارد که در هر دما مورد بررسی قرار می گیرند.

• بنابراین مقدار این پارامترهم بستگی به ابعاد مساله دارد و با چندبار اجرای آزمایشی روش برای مقادیر مختلف تعیین می شود.

• تصمیمات اختصاصی شامل این است که در هر تکرار روش SA بایستی تعداد زیادی جواب تولید شوند تا یک تعادل حرارتی در هر دما برقرار گردد.

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

• همگرایی به یک راه حل بهینه در SA بعد از تعداد نامحدود تکرار ها به وسیله برنامه خنک سازی کنترل می شود. پارامتر کنترل اصلی در برنامه خنک سازی پارامتر دما T می باشد.

مراحل الگوریتم SA استاندارد:
الگوریتم :

• آغاز و آماده سازی : ورود اطلاعات مساله و تنطیم پارامترهای الگوریتم ( دمای اولیه ، نرخ سرمایش ، شرط توقف جواب اولیه تصادفی و موجه ، ……)

• ۱ ) تشکیل یک جواب در همسایگی جواب فعلی

• ۲ ) ارزیابی جواب همسایگی :

• ۱-۲ ) همسایه از جواب فعلی بهتر است : حرکت به جواب جدید

• ۲-۲ ) تابع احتمال از عدد تصادفی یکنواخت بزرگتر است : حرکت به جواب جدید

• در غیر این صورت بازگشت به گام ۱

• ۳ ) به روز رسانی پارامترهای الگوریتم و مساله

• بهترین جواب را حفظ کنیم چون لزوما همیشه بهترین نیست .

• و حرکت به گام ۱

تابع سرمایش :

• سرعت همگرایی الگوریتم ، وابسته به تابع سرمایش است

• ( برنا مه کاهش دما Cooling Schedul )

• مقدار دما ( بر حسب تعداد تکرارها ) در هر تکرار طبق تابع سرمایش می بایست کاهش یابد

• تعیین تابع و نرخ سرمایش وابسته به بزرگی و ساختار مساله است و توابع متعددی برای آن پیشنهاد شده است .

• نرخ سرمایش بسیار بزرگ ، باعث همگرایی زود هنگام و حبس در بهینه محلی می شود .

• نرخ سرمایش کوچک ، زمان محاسباتی را افزایش می دهد .

• نرخ بهینه و دمای اولیه، مهم ترین پارامترهای الگوریتم هستند .

• میزان کاهش دما در روش SA بسیار مهم است . برای کاهش دادن دما ، دمای فعلی را به ضریب α ضرب می کنیم . توجه کنید که α مقدار بین ۰ و ۱ است.

در الگوریتم SA دما به تدریج و بسیار آهسته کم می شود ، پس مقدار α باید به ۱ نزدیک باشد . کاهش دادن سریع دما باعث خواهد شد تا در مینیمم محلی گیر کنیم .

موارد کاربرد:

• یک simulated annealing قوی ابتکاری برای مسائل زمانبندی فلوشاپ

طرح زمان بندی داروی سرطان با استفاده از Simulated Annealing

• برای طرح ریزی شیمی درمانی های با چرخه خاص(cycle specific)

• ، یک متدولوژی با استفاده از Simulated Annealingپیشنهاد می شود. این روش متکی به مدل معادله های دیفرانسیلی تأخیری می باشد که چرخه سلولی را مورد توجه قرارمی دهد و یک زمان بندی دارویی را در طول زمان به صورت یکپارچه در می آورد.

• هدف، رسیدن به یک روش زمان بندی مناسب برای دارو است به گونه ای که سطح تومور کاهش پیدا کند و سیستم ایمنی ، بالای یک آستانة معین نگه داشته شود. برای تعیین یک چنین استراتژی، یک مسأله کنترل بهینه تنظیم شده است که راه حل های نقطه به نقطه(bang- bang) را مجاز می نماید.

• حل کردن مسائل کنترل مجزا به صورت تحلیلی یا عددی بسیار مشکل است ، بنابراین ما به روش های مکاشفه ای متوسل می شویم؛ بویژه ما در اینجا الگوریتم Simulated Annealing را مورد بررسی قرار می دهیم.

• الگوریتم به گونه ای موفقیت آمیز مسأله کنترل بهینه مطرح شده را حل می کند و زمان بندی های دارویی مناسب برای اجرا ایجاد می نماید.

ادامه مطلب روش شبیه سازی تبرید تدریجی ( simulated Annealing)
« استفاده از کلیه مطالب دانشکده علوم ایران مجاز می باشد »