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

[Admin]

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


مقاله ای از : محبوبه ستایش


تهیه و تنظیم جهت : سایت علمی نخبگان جوان

[Admin]

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


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

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

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


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


http://www.esnips.com/imageable/medium/0c81cbc8-bf2d-4025-aa68-8ad7e33a23b3/?du=a5dfe3bd-3f0c-416f-9930-fce031780632&uu=3e3678a6-4179-4e77-8260-1862294adf5d&dt=1199308656000&fu=32909482-e52b-459c-8691-fdbedfda7078

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

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

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

• نقطه شروع : یک جواب قابل قبول که معمولا به صورت تصادفی ایجاد میشود .
• نقطه شروع بر سرعت همگرایی الگوریتم تا حدی موثر است .
• برای گسترش فضای جستجو و گریز از بهینه های محلی ، معمولا الگوریتم از چندین نقطه شروع مختلف اجرا می شود .
• دمای اولیه (c0 ) : مقدار دمای اولیه تابع توزیع بولتز من می باسیت به گونه ای ساخته باشد تا مقدار تابع نزدیک به یک باشد .

http://www.esnips.com/nsdoc/c9936363-6ec6-496b-af75-9d296ee16141

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

[Admin]

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


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


http://www.esnips.com/nsdoc/e4c8f958-56b7-4fa7-ba8f-a40293ba6a33

تابع سرمایش :

• سرعت همگرایی الگوریتم ، وابسته به تابع سرمایش است
• ( برنا مه کاهش دما Cooling Schedul )
• مقدار دما ( بر حسب تعداد تکرارها ) در هر تکرار طبق تابع سرمایش می بایست کاهش یابد
• تعیین تابع و نرخ سرمایش وابسته به بزرگی و ساختار مساله است و توابع متعددی برای آن پیشنهاد شده است .

http://www.esnips.com/imageable/medium/43b4f94b-9c0d-43ce-b70c-35e39b00d307/?du=a5dfe3bd-3f0c-416f-9930-fce031780632&uu=3e3678a6-4179-4e77-8260-1862294adf5d&dt=1199308656000&fu=32909482-e52b-459c-8691-fdbedfda7078

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

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

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

http://www.esnips.com/nsdoc/9b94752a-bd04-4eca-bcc6-db36348797a1

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

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

خلاصه :

• روش جستجوگر " تبريد تدريجي" SA يک جستجوگر همسايگي است که در بهينه‌سازي مسائل گسسته بطور گسترده‌اي کاربرد دارد.
• طبيعت تصميم‌گيري اين الگوريتم به اين صورت است که براي هر حرکت، يک همسايگي جديد بصورت تصادفي توليد و ارزيابي مي‌شود. حرکت به اين جواب در هر يک از دو وضعيت زير انجام خواهد يافت: 1) جواب جديد از جواب فعلي بهتر باشد و 2) مقدار تابع احتمال حرکت[i] از يک عدد تصادفي از دامنه [0,1) بزرگتر باشد.
• در غير اين صورت جستجوگر جواب جديدي را توليد و ارزيابي خواهد نمود. اين حرکت گام ‌به‌گام تا ارضاء شرط توقف الگوريتم (تعداد تکرارها، زمان محاسبات، و .... ) ادامه مي‌يابد.
• مقدار تابع احتمال حرکت در هر بار از رابطه محاسبه مي‌شود. در اين رابطه اختلاف مقدار تابع هدف بين جواب فعلي و جواب جديد است.