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

روش جستجوی تبرید شبیه سازی شده (SA ) یک جستجوگر همسایگی است که در بهینه‌سازی مسائل گسسته به طور گسترده‌ای کاربرد دارد. طبیعت تصمیم‌گیری این الگوریتم به این صورت است که برای هر حرکت، یک همسایگی جدید به صورت تصادفی تولید و ارزیابی می‌شود.
الگوریتم شبیه سازي تبرید (SA) روشی ابتکاري بر مبناي جستجوي محلی است. این الگوریتم قادر است از گیر افتادن در بهینه محلی با قبول جواب هاي بدتر، با احتمالی کم، جلوگیري کند. کیفیت جواب هاي حاصل از الگوریتم شبیه سازي تبرید موجب شده تا در حل مسائل بهینه سازي ترکیبی پیچیده در حوزه هاي مختلف مسائل دنیاي واقعی مورد استفاده قرار گیرد. شبیه سازي تبرید توسط کرك پاتریک و همکاران عمومیت پیدا کرد. مفهوم اصلی شبیه سازي تبرید از فرایند تبرید فلزات در صنعت متالورژي گرفته شده است.
فرایند بهینه سازي در شبیه سازي تبرید، جستجو براي یک جواب (نزدیک به) کمینه سراسري است. الگوریتم از یک جواب تصادفی به عنوان جواب اولیه حرکت خود را آغاز میکند و دماي سیستم برابر دماي اولیه قرار میگیرد. (T=T0) در هر تکرار یک جواب همسایه جواب فعلی به دست می آید. مقدار تابع هدف جواب جدید با جواب فعلی مقایسه می شود. اگر جواب بهتر بود، جایگزین جواب فعلی می شود و اگر جواب بدتر بود با یک احتمال که از تابع بالتزمن ()exp() به دست می آید، جایگزین جواب فعلی می شود. این مکانیزم منجر به این میشود که الگوریتم در بهینه محلی گیر نیافتد. در این رابطه برابر میزان اختلاف مقدار تابع هدف جواب فعلی با جواب جدید است،K   ضریب بالتزمن است که از قبل تعیین میشود و T نیز دماي فعلی است. فرایند جستجوي همسایگی ادامه می یابد تا زمانی که تعداد تکرارها به مقداري از پیش تعیین شده برسد. پس از اینکه تعداد تکرارها به اندازه مقداري معین و از پیش تعیین شده گشت، دماي سیستم کاهش می یابد. این فرایند تا زمانی ادامه پیدا میکند که الگوریتم به معیار خاتمه برسد (محمدی شاد و فتاحی، 1391)
حرکت به این جواب در هر یک از دو وضعیت زیر انجام خواهد یافت:
1. جواب جدید از جواب فعلی بهتر باشد
2. مقدار تابع احتمال حرکت [i] از یک عدد تصادفی از دامنه [0,1] بزرگتر باشد.
در غیر این صورت جستجوگر جواب جدیدی را تولید و ارزیابی خواهد نمود. این حرکت گام ‌به‌گام تا ارضاء شرط توقف الگوریتم (تعداد تکرارها، زمان محاسبات، و …) ادامه می‌یابد.
مقدار تابع احتمال حرکت در هر بار از رابطه محاسبه می‌شود. در این رابطه اختلاف مقدار تابع هدف بین جواب فعلی و جواب جدید است. SA در واقع یک روش جستجوی تصادفی قوی است که به منظور یافتن یک جواب خوب (نه لزوما بهینه) برای مسائل مشکل ترکیباتی combinatorial به کار می رود .این روش برخلاف روش های جستجوی معمولی، در هر تکرار علاوه بر حرکت به سوی جواب بهتر، جواب های با مقدار تابع هدف بهتر را نیز با احتمال غیر صفری قبول می کند. SA از فرایند فیزیکی خنک سازی مواد مذاب به حالت جامد الهام گرفته است.

فرایند آنیل کردن فلزات 

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

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

نقطه شروع: یک جواب قابل قبول که معمولا به صورت تصادفی ایجاد میشود .
نقطه شروع بر سرعت همگرایی الگوریتم تا حدی موثر است .
برای گسترش فضای جستجو و گریز از بهینه های محلی ، معمولا الگوریتم از چندین نقطه شروع مختلف اجرا می شود .
دمای اولیه (C0) :مقدار دمای اولیه تابع توزیع بولتز من می بایست به گونه ای ساخته شده باشد تا مقدار تابع نزدیک به یک باشد .
معمولا در اکثر کاربردها مقادیر0.85 – 0.95 مطلوب است .
مقادیر بسیار بزرگ (به همراه نرخ سرمایش آهسته) موجب طولانی شدن مدت اجرا و گسترش فضای جستجو می شود .
مقادیر بسیار کوچک ممکن است موجب همگرایی زود هنگام شده الگوریتم در بهینه محلی متوقف شود .
انتخاب پارامترهای عمومی به مساله بهینه سازی و موارد خاص مورد نظر بستگی دارد.
دمای اولیه باید به طریقی تعیین گردد که احتمال قبول و رد جواب ها برای حالت Δf>0 در تکرار اول روش برابر باشد.
استراتژی خنک کردن سیستم، چگونگی کاهش دما را در حین تکرارهای روش تعیین می کند. کیفیت جواب SA به میزان زیادی بستگی به تعداد جواب هایی دارد که در هر دما مورد بررسی قرار می گیرند.
بنابراین مقدار این پارامترهم بستگی به ابعاد مساله دارد و با چندبار اجرای آزمایشی روش برای مقادیر مختلف تعیین می شود.
تصمیمات اختصاصی شامل این است که در هر تکرار روش SA بایستی تعداد زیادی جواب تولید شوند تا یک تعادل حرارتی در هر دما برقرار گردد.
اگرچه SA ضمن سادگی ابزاری قوی برای حل مسائل بهینه سازی ترکیباتی می باشد ولی دقت زیادی در انتخاب نحوه تولید موثر جواب ها، زمان بندی خنک کردن و کفایت تعداد جواب های تولید شده لازم است. با این وجود زمینه هایی نیز برای بهبود روش وجود دارد.
همگرایی به یک راه حل بهینه در SA بعد از تعداد نامحدود تکرار ها به وسیله برنامه خنک سازی کنترل می شود. پارامتر کنترل اصلی در برنامه خنک سازی پارامتر دما T می باشد.

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

آغاز و آماده سازی: ورود اطلاعات مساله و تنطیم پارامترهای الگوریتم (دمای اولیه، نرخ سرمایش، شرط توقف جواب اولیه تصادفی و موجه، ...)
-1تشکیل یک جواب در همسایگی جواب فعلی
-2ارزیابی جواب همسایگی :
الف)همسایه از جواب فعلی بهتر است: حرکت به جواب جدید
ب)تابع احتمال از عدد تصادفی یکنواخت بزرگتر است: حرکت به جواب جدید در غیر این صورت بازگشت به گام 1
-3به روز رسانی پارامترهای الگوریتم و مساله
بهترین جواب را حفظ کنیم چون لزوما همیشه بهترین نیست .و حرکت به گام 1

تابع سرمایش

سرعت همگرایی الگوریتم، وابسته به تابع سرمایش است
برنامه کاهش دما Cooling Schedul))
مقدار دما (بر حسب تعداد تکرارها) در هر تکرار طبق تابع سرمایش می بایست کاهش یابد
تعیین تابع و نرخ سرمایش وابسته به بزرگی و ساختار مساله است و توابع متعددی برای آن پیشنهاد شده است نرخ سرمایش بسیار بزرگ، باعث همگرایی زود هنگام و حبس در بهینه محلی می شود .نرخ سرمایش کوچک، زمان محاسباتی را افزایش می دهد. نرخ بهینه و دمای اولیه، مهم ترین پارامترهای الگوریتم هستند .
میزان کاهش دما در روش SA بسیار مهم است. برای کاهش دادن دما، دمای فعلی را به ضریب α ضرب می کنیم. توجه کنید که α  مقدار بین 0 و 1 است.
در الگوریتم SA دما به تدریج و بسیار آهسته کم می شود، پس مقدار α باید به 1 نزدیک باشد. کاهش دادن سریع دما باعث خواهد شد تا در مینیمم محلی گیر کنیم .

موارد کاربرد الگوریتم تبرید شبیه سازی شده 

-یک simulated annealing قوی ابتکاری برای مسائل زمانبندی فلوشاپ
-طرح زمان بندی داروی سرطان با استفاده از Simulated Annealing
-برای طرح ریزی شیمی درمانی های با چرخه خاص (cycle specific)
-یک متدولوژی با استفاده از Simulated Annealing پیشنهاد می شود. این روش متکی به مدل معادله های دیفرانسیلی تأخیری می باشد که چرخه سلولی را مورد توجه قرارمی دهد و یک زمان بندی دارویی را در طول زمان به صورت یکپارچه در می آورد.
-هدف، رسیدن به یک روش زمان بندی مناسب برای دارو است به گونه ای که سطح تومور کاهش پیدا کند و سیستم ایمنی، بالای یک آستانه معین نگه داشته شود. برای تعیین یک چنین استراتژی، یک مسأله کنترل بهینه تنظیم شده است که راه حل های نقطه به نقطه (bang- bang) را مجاز می نماید.
-حل کردن مسائل کنترل مجزا به صورت تحلیلی یا عددی بسیار مشکل است، بنابراین ما به روش های مکاشفه ای متوسل می شویم.
-الگوریتم به گونه ای موفقیت آمیز مسأله کنترل بهینه مطرح شده را حل می کند و زمان بندی های دارویی مناسب برای اجرا ایجاد می نماید.

منبع: www.daneshju.ir

  • تهران
  • 09350579640-09124635768
  • 01152218786
  • این آدرس ایمیل توسط spambots حفاظت می شود. برای دیدن شما نیاز به جاوا اسکریپت دارید

ارسال پیام

  Mail is not sent.   Your email has been sent.
Top