مراحل الگوریتم SA استاندارد:
الگوریتم :
• آغاز و آماده سازی : ورود اطلاعات مساله و تنطیم پارامترهای الگوریتم ( دمای اولیه ، نرخ سرمایش ، شرط توقف جواب اولیه تصادفی و موجه ، ......)
• 1 ) تشکیل یک جواب در همسایگی جواب فعلی
• 2 ) ارزیابی جواب همسایگی :
• 1-2 ) همسایه از جواب فعلی بهتر است : حرکت به جواب جدید
• 2-2 ) تابع احتمال از عدد تصادفی یکنواخت بزرگتر است : حرکت به جواب جدید
• در غیر این صورت بازگشت به گام 1
• 3 ) به روز رسانی پارامترهای الگوریتم و مساله
• بهترین جواب را حفظ کنیم چون لزوما همیشه بهترین نیست .
• و حرکت به گام 1
فلو چارت :
تابع سرمایش :
• سرعت همگرایی الگوریتم ، وابسته به تابع سرمایش است
• ( برنا مه کاهش دما Cooling Schedul )
• مقدار دما ( بر حسب تعداد تکرارها ) در هر تکرار طبق تابع سرمایش می بایست کاهش یابد
• تعیین تابع و نرخ سرمایش وابسته به بزرگی و ساختار مساله است و توابع متعددی برای آن پیشنهاد شده است .
• نرخ سرمایش بسیار بزرگ ، باعث همگرایی زود هنگام و حبس در بهینه محلی می شود .
• نرخ سرمایش کوچک ، زمان محاسباتی را افزایش می دهد .
• نرخ بهینه و دمای اولیه، مهم ترین پارامترهای الگوریتم هستند .
• میزان کاهش دما در روش SA بسیار مهم است . برای کاهش دادن دما ، دمای فعلی را به ضریب α ضرب می کنیم . توجه کنید که α مقدار بین 0 و 1 است.
در الگوریتم SA دما به تدریج و بسیار آهسته کم می شود ، پس مقدار α باید به 1 نزدیک باشد . کاهش دادن سریع دما باعث خواهد شد تا در مینیمم محلی گیر کنیم .
موارد کاربرد:
• یک simulated annealing قوي ابتكاري براي مسائل زمانبندي فلوشاپ
طرح زمان بندي داروي سرطان با استفاده از Simulated Annealing
• براي طرح ريزي شيمي درماني هاي با چرخه خاص(cycle specific)
• ، يك متدولوژي با استفاده از Simulated Annealingپيشنهاد مي شود. اين روش متكي به مدل معادله هاي ديفرانسيلي تأخيري مي باشد كه چرخه سلولي را مورد توجه قرارمي دهد و يك زمان بندي دارويي را در طول زمان به صورت يكپارچه در مي آورد.
• هدف، رسيدن به يك روش زمان بندي مناسب براي دارو است به گونه اي كه سطح تومور كاهش پيدا كند و سيستم ايمني ، بالاي يك آستانة معين نگه داشته شود. براي تعيين يك چنين استراتژي، يك مسأله كنترل بهينه تنظيم شده است كه راه حل هاي نقطه به نقطه(bang- bang) را مجاز مي نمايد.
• حل كردن مسائل كنترل مجزا به صورت تحليلي يا عددي بسيار مشكل است ، بنابراين ما به روش هاي مكاشفه اي متوسل مي شويم؛ بويژه ما در اينجا الگوريتم Simulated Annealing را مورد بررسي قرار مي دهيم.
• الگوريتم به گونه اي موفقيت آميز مسأله كنترل بهينه مطرح شده را حل مي كند و زمان بندي هاي دارويي مناسب براي اجرا ايجاد مي نمايد.
خلاصه :
• روش جستجوگر " تبريد تدريجي" SA يک جستجوگر همسايگي است که در بهينه‌سازي مسائل گسسته بطور گسترده‌اي کاربرد دارد.
• طبيعت تصميم‌گيري اين الگوريتم به اين صورت است که براي هر حرکت، يک همسايگي جديد بصورت تصادفي توليد و ارزيابي مي‌شود. حرکت به اين جواب در هر يک از دو وضعيت زير انجام خواهد يافت: 1) جواب جديد از جواب فعلي بهتر باشد و 2) مقدار تابع احتمال حرکت[i] از يک عدد تصادفي از دامنه [0,1) بزرگتر باشد.
• در غير اين صورت جستجوگر جواب جديدي را توليد و ارزيابي خواهد نمود. اين حرکت گام به‌گام تا ارضاء شرط توقف الگوريتم (تعداد تکرارها، زمان محاسبات، و .... ) ادامه مي‌يابد.
• مقدار تابع احتمال حرکت در هر بار از رابطه محاسبه مي‌شود. در اين رابطه اختلاف مقدار تابع هدف بين جواب فعلي و جواب جديد است.
مقاله ای از : محبوبه ستایش
|