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

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

تبرید شبیه سازی شده (SA)، یک تکنیک احتمالاتی است که برای تخمین نقطه بهینه سراسری یک تابع خاص بکار می رود. به طور مشخص، تخمین بهینه سازی سراسری در فضای جستجوی بزرگ، در حین پیگیری مساله بهینه سازی ، یک روش فراابتکاری است. این روش معمولاً هنگامی بکار می رود که فضای جستجو، گسسته باشد (مساله فروشنده دوره گرد). برای مسائلی که یافتن نقطه بهینه سراسری تخمینی، مهم تر از یافتن بهینه محلی دقیق در یک بازه زمانی محدود است، روش تبرید شبیه سازی شده بر الگوریتم های دقیقی همچون گرادیان نزولی یا شاخه و کران، ارجحیت دارد. اسم این الگوریتم از عمل تبرید در ریخته گری ناشی می شود. در این تکنیک، گرمادهی و خنک کردن یک ماده به صورت کنترل شده انجام می شود تا اندازه بلورها گسترش یافته و نواقص آن ها کاهش یابد. هر دو مورد ویژگی های ماده هستند که به انرژی آزاد ترمودینامیکی بستگی دارند. گرم کردن و سردکردن مواد ، هم روی دما و هم انرژی آزاد ترمودینامیکی یا انرژی گیبس، تاثیرگذار هستند. می توان از تبرید شبیه سازی شده برای مسائل بهینه سازی محاسباتی خیلی سخت ، هنگامی که راه حل های دقیق، ناکارآمد هستند، استفاده نمود. هرچند این روش اکثراً راه حل تخمینی را برای مینیمم سراسری بدست می آورد، اما برای بسیاری از مسائل کاربردی کافی خواهد بود. مسائل حل شده توسط SA ، اکنون بر اساس تابع هدف شامل تعداد زیادی متغیر فرمول بندی می شوند، و تحت چندین محدودیت قرار می گیرند. در عمل، محدودیت ها به عنوان بخشی از تابع هدف جریمه می شوند. تکنیک های مشابهی به صورت مستقل در چندین زمان مطرح شده اند. در سال 1983، این روش توسط کرک پاتریک، جلات جونیور وکی برای حل مساله فروشنده دوره گرد بکار رفته است. آن ها اسم کنونی آن ، یعنی تبرید شبیه سازی شده را نیز معرفی کردند. این مفهوم پردازی از خنک سازی آهسته که در تبرید شبیه سازی شده اجرا می شود ، به منزله کاهش آهسته احتمال پذیرش بدترین راه حل در فضای راه حل مورد بررسی است. پذیرش بدترین راه حل، امکان جستجوی گسترده تر برای راه حل بهینه سراسری را فراهم می سازد. به طور کُلی، الگوریتم های تبرید شبیه سازی شده اینگونه عمل می کنند. دما به تدریج از نقطه مثبت اولیه به صفر کاهش می یابد. در هر گام زمانی، الگوریتم به صورت تصادفی، یک راه حل نزدیک به راه حل فعلی را انتخاب می کند، کیفیت آن را می سنجد، و با توجه به احتمالات وابسته به دما و انتخاب راه حل های بهتر یا بدتر ، به آن منتقل می شود. این مقدار در طول جستجو روی 1 (یا مقدار مثبت) باقی می ماند و به صفر کاهش می یابد. می توان شبیه سازی را با استفاده از راه حل معادلات کینتیک تابع چگالی، یا با اعمال روش نمونه گیری تصادفی انجام داد. این روش، حالت تطبیق یافته ای از الگوریتم متروپلیس – هستینگز است. این روش مونت کارلو ، حالت های نمونه برای یک سیستم ترمودینامیکی را ایجاد می کند که توسط ان.متروپلیس و همکاران در 1953 معرفی شده است.

این محصول یک فایل پاورپوینت 35 اسلایدی است و در ادامه نیز تصویر تعدادی از اسلایدهای آن قرار داده شده است: