تحقیق درمورد شبیه سازی و تصمیمگیری

C(t)= نوزاد نسل t
5-3 : الگوریتم فراابتکاری شبیهسازی تبرید
هدف رویکرد شبیهسازی تبرید اجتناب از بهینه های موضعی با استفاده از تغییرات دما و استراتژی پذیرش جوابهای غیربهبود دهنده (جستجوی up/down-hill) در یک محیط گسسته میباشد. رویکرد شبیهسازی تبرید دارای مزایای برجسته متعددی نسبت به سایر رویکردهای فراابتکاری است که عبارتند از:
وابستگی زیادی به نقطهی اولیه ندارد.
قابلیت فرار از بهینههای موضعی را دارد.
از لحاظ برنامهنویسی و اجرا ساده است.
ثابت شده است که زمان محاسباتی آن دارای حد بالایی از نوع چندجملهای معین برحسب ابعاد مسأله است]49[.
اساس تئوریک شبیهسازی تبرید بر مبنای توزیع بولتزمن استوار است. برطبق توزیع بولتزمن، احتمال قرار گرفتن یک سیستم فرضی در وضعیت X=[xij] طبق توزیع زیر تعیین میشود.
(1-4)
بطوریکه T مبین دمای جاری سیستم و E(X) مشابه رابطه (4-3) برابر سطح انرژی سیستم در وضعیت X می باشد. به Zتابع پارتیشن گفته میشود. در الگوریتم شبیهسازی تبرید ، برطبق قاعده تصمیمگیری متروپلیس ]49[، احتمال تغییر وضعیت سیستم از X به X مادامی که دمای سیستم در حال کاهش باشد، بصورت رابطه زیر محاسبه میگردد.
(2-4)
بطوریکه یک عدد ثابت دلخواه میباشد. رابطه فوق بیان میکند که اگر سطح انرژی سیستم در وضعیت X کمتر از X باشد، آنگاه حتماً سیستم از X به X تغییر وضعیت خواهد داد در غیراینصورت با احتمال معین این تغییر وضعیت صورت خواهد گرفت.
که این احتمال به دمای جاری سیستم و اختلاف سطح انرژی بین دو وضعیت، ، بستگی دارد. بنابراین، نکته حائز اهمیت آن است که دمای اولیه سیستم چقدر بوده و دما با چه نرخی کاهش پیدا کند. کارایی شبیه سازی تبرید به مقدار زیادی به نرخ کاهش دما یا اصطلاحاً زمانبندی سرمایش و همچنین دمای اولیه وابسته است ]14[. هدف صرف زمان بیشتر در نزدیکی دمای بحرانی Tc است. منظور از دمای بحرانی، دمایی است که در آن دستیابی به بهینه سراسری محسوستر است، یعنی فرار از بهینه موضعی بطور معناداری سخت یا طولانیتر میشود. برای T>>Tc رفتار شبیه سازی تبرید تقریباً بصورت تصادفی است، در حالیکه برای T< (3-4)
بطوریکه k شمارنده انتقالات دما میباشد. همچنین Tk برابر دمای سیستم در تکرار kام و نیز معرف ضریب یا نرخ کاهش دما میباشد که عمدتاً مقدار آن بین 8/0 تا 99/0 اختیار میگردد. مقادیر بالای مبین کاهش آهسته دما و در نتیجه جستجوی بهتر همسایگیها میباشد. ولی زمان حل را افزایش میدهد. برعکس مقادیر کمتر مبین کاهش سریع دما و در نتیجه جستجوی سریعتر همسایگیها میباشد که منجر به همگرایی زودرس الگوریتم خواهد شد. یکی دیگر از قواعد کارا برای به هنگام سازی دما توسط گاتزمن پیشنهاد شد ]39[. این قاعده بصورت زیر است.
(4-4)
بطوریکه N برابر اندازه یا ابعاد مسأله و پارامتر معرف ثابت واپاشی یا اضمحلال است که مقدار آن بصورت زیر محاسبه میگردد.

  منبع مقاله با موضوع در کودکان و سیستم‌ها

که درآن K برابر حداکثر تعداد انتقالات یا کاهش دما (یعنی حداکثر مقدار شمارنده k) است که به عنوان معیار توقف الگوریتم بکار میرود. یکی دیگر از پارامترهای اساسی در شبیه سازی تبرید ، تعداد جوابهای پذیرفته شده در هر دما، N، میباشد. این پارامتر حجم جستجوی همسایگی جوابها را در هر دما کنترل میکند. با کاهش دما، اندازه همسایگی نیز کاهش مییابد زیرا احتمال پذیرش جوابهای غیربهبود دهنده نیز در حال کاهش است. بنابراین مقدار N باید به اندازهای بزرگ باشد که موجب جستجوی مؤثر همسایگی شده و حدالمقدور به جوابهای بهتری که ممکن است در همسایگی وجود داشته باشند، دست یابد. از طرف دیگر مقدار N نباید آنقدر بزرگ باشد تا موجب جستجوی غیرمؤثر و ناکارا شده و زمان حل را افزایش دهد. اگر الگوریتم نتواند بیش از این در دمای جاری به جواب بهتری دست یابد، اصطلاحاً می گوییم سیستم در دمای جاری به تعادل رسیده است و نیاز به بهنگام سازی دما میباشد. بصورت تجربی، در بسیاری از تحقیقات مقدار N حدود 100 در نظر گرفته شده است ]90[.
یکی دیگر از نکات اساسی در شبیه سازی تبرید، استراتژی جستجوی همسایگی است. این امر میتواند با توجه به ماهیت مسأله، بسیار پیچیده باشد. چگونگی حرکت از نقطهای به نقطه دیگر (move) بستگی به ساختار عملگرهای طراحی شده دارد. دستیابی به نقاط کشف نشده فضای جواب و همچنین جستجوی دقیق همسایگی نقاط(Exploitation)، منوط به طراحی عملگرهای کارا و مؤثر میباشد. این کار در بسیاری از مسایل پیچیده بهینهسازی با متغیرهای تصمیم متنوع و محدودیتهای متعدد، امری دشوار است، تا آنجائیکه ممکن است بسیاری از رویکردهای فراابتکاری عملاً کارایی خود را از دست بدهند ]90[.
شکل (8-3) فلوچارت یک شبیه سازی تبرید کلاسیک را نشان میدهد. همانطورکه در شکل (8-3) نشان داده شده است، الگوریتم شبیهسازی تبرید از دو حلقه داخلی و خارجی تشکیل شده است. وظیفه حلقه داخلی کنترل دستیابی به تعادل در هر دما است. همچنین وظیفه حلقه خارجی بهنگام سازی دما میباشد. حلقه تصمیمگیری متروپلیس (احتمال پذیرش جوابهای غیربهبود دهنده) در درون حلقه داخلی تعبیه شده است. برطبق این حلقه تصمیمگیری، اگر جواب اخیراً تولید شده یعنی Xnew نتواند تابع هدف را نسبت به جواب فعلی یعنی Xn بیشتر بهبود دهد یعنی E = E(Xnew)- E(Xn)>0 ، آنگاه با احتمال جواب Xnew پذیرفته خواهد شد؛ بطوریکه y یک عدد تصادفی یکنواخت پیوسته در بازه [0 ,1] میباشد. بنابراین احتمال پذیرش جواب غیربهبود دهنده به تغییرات مقدار تابع زیان، E، و دمای جاری بستگی خواهد داشت. همانطورکه در شکل (8-3)، n شمارنده حلقه داخلی و k شمارنده حلقه خارجی است. همچنین E( ) معرف تابع لاگرانژین مشابه رابطه (4-2) میباشد ]90[.
شکل 9-3: فلوچارت یک شبیه سازی تبرید کلاسیک ]90[

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