الگوریتم تبرید شبیه‌سازی‌شده
الگوریتم تبرید شبیه‌سازی‌شده (Simulated Annealing) (SA)، یک الگوریتم بهینه‌سازی فراابتکاری ساده و اثربخش در حل مسائل بهینه‌سازی در فضاهای جستجوی بزرگ است. این الگوریتم بیشتر زمانی استفاده میشود که فضای جستجو گسسته باشد (مثلاً همه گشت‌هایی که از یک مجموعه از شهرها میگذرند).
برای مسائلی که پیدا کردن یک پاسخ تقریبی برای بهینه کلی مهمتر از پیدا کردن یک پاسخ دقیق برای بهینه محلی در زمان محدود و مشخصی است، تبرید شبیه‌سازی شده ممکن است نسبت به باقی روش‌ها مانند گرادیان کاهشی دارای ارجحییت باشد.
تکنیک الگوریتم تبرید تدریجی، به وسیلهٔ متالورژیست‌ها برای رسیدن به حالتی که در آن ماده جامد، به خوبی مرتب و انرژی آن کمینه شده باشد، استفاده میشود. هدف از این کار این است که سایز کریستال‌ها در حالت جامد ماده در حال تبرید به بزرگترین حالت برسد.
این تکنیک شامل قرار دادن ماده در دمای بالا و سپس کم کردن تدریجی این دماست. شبیه سازی تبرید رویکردی است که مسئله کمینه سازی یک تابع با تعداد بسیار زیادی متغیر است را به یک مسئله مکانیک آماری کاهش می‌دهد.
بنیان گذاران این الگوریتم تبرید برای حل مسائل سخت بهینه‌سازی، روشی مبتنی بر تکنیک تبرید تدریجی و آرام پیشنهاد نمودند. این محققین برای مدلسازی تبرید یک سیستم به منظور پیدا کردن پاسخ کمینه کلی، از شبیه سازی کامپیوتری استفاده کردند.
می‌توان تبرید تدریجی و آرام در این الگوریتم تبرید را به عنوان کاهش تدریجی احتمال انتخاب پاسخ‌های بدتر حین جستجو در فضای پاسخ‌ها دانست (انتخاب پاسخ‌های بدتر یک ویژگی اساسی الگوریتم‌های فراابتگاری است و پیدا کردن بهترین پاسخ را ممکن می‌سازد).
شبیه سازی را می‌توان به دو صورت حل روابط کینتیکی برای توابع چگالی (مانند کار خاچاتوریان، سمونوفسکایا و وینشتاین در سال ۱۹۷۹ و ۱۹۸۱) یا استفاده از نمونه‌گیری تصادفی، انجام داد.
نمونه گیری تصادفی در سال ۱۹۸۳ توسط کریک‌پاتریک، گلت و کلی معرفی شد، کرنی در سال ۱۹۸۵ و خاچاتوریان، سمونوفسکایا و وینشتاین در سال ۱۹۸۵ به‌طور مستقل این ایده را مطرح کردند. این روش یک اقتباس از الگوریتم متروپولیس-هستینگز است، یک روش مونت کارلو که نمونه حالت‌هایی را از یک سیستم ترمودینامیک تولید می‌کند.
ایده اصلی الگوریتم شبیه سازی حرارتی SA
SA یک روش بهینه‌سازی تصادفی است که بر روی رفتار ماده متراکم در دماهای پایین مدل شده است. از تکنیک‌های مکانیک آماری برای یافتن بهینه سراسری سیستم‌هایی با درجات آزادی زیاد استفاده می‌کند.
این روش مشابه روشی است که مایعات منجمد و متبلور می‌شوند یا فلزات سرد و باز پخت می‌شوند. هسته فرآیند خنک شدن آهسته است، که زمان کافی را برای توزیع مجدد اتم‌ها فراهم می‌کند زیرا اتم‌ها تا زمانی که به حداقل حالت انرژی برسند از حرکت باز می‌ایستند.
در طی فرآیند باز پخت فیزیکی، یک ماده جامد در یک حمام حرارتی قرار می‌گیرد و دما به‌طور مداوم بالا می‌رود تا زمانی که ماده جامد ذوب شود و ذرات جامد ازنظر فیزیکی از هم جداشده یا به‌صورت تصادفی قرار گیرند.جهت‌گیری ذرات به‌عنوان اسپین نامیده میشود.
از چنین سطح انرژی بالایی، حمام حرارتی با کاهش دما به‌آرامی خنک میشود تا ذرات بتوانند خود را در یک ساختار شبکه کریستالی منظم تراز کنند. این ساختار نهایی مربوط به یک حالت کم انرژی پایدار است.
آنچه در شبیه سازی الگوریتم حرارتی SA اتفاق می‌افتد بدین شکل است که اگر در فضای جستجو هر نقطه مثل S را شبیه حالتی از فضای فیزیکی در نظر بگیریم و تابع کمینه F(S) انرژی داخلی سیستم در آن حالت باشد هدف این است که سیستم را از حالت اولیه به حالتی ببریم که کمترین انرژی را داشته باشد.
دما باید به‌آرامی کاهش یابد تا جامد پس از هر افت دما به تعادل برسد. در غیر این صورت، ترازهای نامنظم ممکن است رخ دهد که منجر به نقص‌هایی در جامد به‌دست آمده میشود. البته، این امر می‌تواند منجر به ساختاری بسیار ناپایدار شود تا اینکه ساختار کم انرژی پایدار مورد نیاز را فراهم کند.
ایده باز پخت با الگوریتم معروف مونت‌کارلو ترکیب شد که در ابتدا برای انجام میانگین‌گیری عددی بر روی سیستم‌های بزرگ در مکانیک آماری استفاده می‌شد. الگوریتم شبیه سازی حرارتی SA سرعت و قابلیت اطمینان الگوریتم‌های گرادیان کاهشی را حفظ کرده که درعین‌حال از حداقل‌های محلی هم اجتناب می‌کند.
پاورپوینت الگوریتم تبرید شبیه ساز حرارتی SA در 22 اسلاید در قالب ppt. یا pptx. با قابلیت ویرایش و توضیحات اضافی برای برخی صفحات در قالب Note آماده دانلود می باشد. با دانلود این پاورپوینت ارائه جامع و بدون استرس را تجربه کنید.
SA چیست؟
SA مخفف Simulated Annealing به معنای شبیه‌سازی گداخت یا شبیه‌سازی حرارتی می‌باشد که برای آن از عبارات شبیه‌سازی بازپخت فلزات، شبیه‌سازی آب دادن فولاد و الگوریتم تبرید نیز استفاده شده است. برخی مسائل بهینه‌سازی صنعتی در ابعاد واقعی غالباً پیچیده و بزرگ می‌باشند. بنابراین روش‌های حل سنتی و استاندارد، کارایی لازم را نداشته و عموماً مستلزم صرف زمان‌های محاسباتی طولانی هستند. خوشبختانه، با پیشرفت فن‌آوری کامپیوتر و ارتقا قابلیت‌های محاسباتی، امروزه استفاده از روش‌های ابتکاری و جستجوگرهای هوشمند کاملاً متداول گردیده است.
یکی از این روش‌ها SA است. SA شباهت دارد با حرارت دادن جامدات. این ایده ابتدا توسط شخصی که در صنعت نشر فعالیت داشت به نام متروپلیس در سال 1953 بیان شد. وی تشبیه کرد کاغذ را به ماده‌ای که از سرد کردن مواد بعد از حرارت دادن آنها بدست می‌آید.
اگر یک جامد را حرارت دهیم و دمای آن را به نقطه ذوب برسانیم سپس آن را سرد کنیم جزئیات ساختمانی آن به روش و نحوه سرد کردن آن وابسته میشود. اگر آن جامد را به آرامی سرد کنیم کریستال‌های بزرگی خواهیم داشت که می‌توانند آن طور که ما می‌خواهیم فرم بگیرند ولی اگر سریع سرد کنیم آنچه که می‌خواهیم بدست نمی‌آید.
الگوریتم متروپلیس شبیه‌سازی شده بود از فرآیند سرد شدن مواد به وسیله کاهش آهسته دمای سیستم (ماده) تا زمانی که به یک حالت ثابت منجمد تبدیل شود.
این روش با ایجاد و ارزیابی جواب‌های متوالی به صورت گام به گام به سمت جواب بهینه حرکت می‌کند. برای حرکت، یک همسایگی جدید به صورت تصادفی ایجاد و ارزیابی میشود.
در این روش به بررسی نقاط نزدیک نقطه داده شده در فضای جستجو می‌پردازیم. در صورتی که نقطه جدید، نقطه بهتری باشد (تابع هزینه را کاهش دهد) به عنوان نقطه جدید در فضای جستجو انتخاب میشود و اگر بدتر باشد (تابع هزینه را افزایش دهد) براساس یک تابع احتمالی باز هم انتخاب میشود.
به عبارت ساده‌تر، برای کمینه سازی تابع هزینه، جستجو همیشه در جهت کمتر شدن مقدار تابع هزینه صورت می‌گیرد، اما این امکان وجود دارد که گاه حرکت در جهت افزایش تابع هزینه باشد.
زمان‌بندی تبرید
نام و ایده بنیادین الگوریتم تبرید منشأگرفته از ویژگی دما است. این ویژگی در واقع به گونه‌ای کنترل میشود که دما حین شبیه‌سازی به صورت تدریجی کاهش می‌یابد. الگوریتم با قرار دادن
شروع میشود (در واقع دما در ابتدا یک مقدار بزرگ را اختیار می‌کند) و در هر گام طبق یک زمان‌بندی از پیش‌تعیین‌شده کاهش می‌یابد. در تعیین این زمان‌بندی باید توجه داشت که با اتمام منابع مورد استفاده مانند تعداد محاسبات، زمان انجام عملیات‌ها هم تمام شود.
برای انجام این کار انتظار می‌رود در ابتدا الگوریتم تبرید در فضای بزرگی از پاسخ‌ها و بی‌توجه به تابع انرژی به دنبال جواب بگردد. سپس به سمت مناطق با انرژی کمتر پرش کند و این منطقه به مرور کوچک و کوچکتر شود تا زمانی که سیستم دقیقا به پایین‌ترین نقطه سراسری برسد.
الگوریتم تبرید سریع
دو شکل نشان‌دهندهٔ تأثیر زمان‌بندی تبرید بر کارایی الگوریتم هستند. مسئله بازترتیبی پیکسل‌های یک عکس به منظور کمینه کردن انرژی واقعی تصویر است، که باعث میشود رنگ‌های مشابه به هم نزدیک‌تر باشند و رنگ‌های متفاوت در فاصله دورتری از هم قرار بگیرند. دو شکل روبرو از دو زمان‌بندی سریع و آرام در بدست آمده‌اند.
برای هر مسئله با فضای متناهی، احتمال این که الگوریتم تبرید در یک نقطه بهینهٔ سراسری کار خود را تمام کند با افزایش زمان به ۱ میل می‌کند. اگرچه این نتیجهٔ نظری چندان راهگشا نیست زیرا میزان زمانی که لازم است تا احتمال رسیدن به جواب از حدی معقول بیشتر شود معمولاً بیشتر از زمانی است که برای جستجوی کل فضا لازم است.
نمونه کد الگوریتم تبرید شبیه سازی در متلب-Simulated Annealing in MATLAB
الگوریتم تبرید شبیه‌سازی‌شده (Simulated Annealing) (SA)، یک الگوریتم بهینه‌سازی فراابتکاری ساده و اثربخش در حل مسائل بهینه‌سازی در فضاهای جستجوی بزرگ است. این الگوریتم بیشتر زمانی استفاده میشود که فضای جستجو گسسته باشد (مثلا همه گشت‌هایی که از یک مجموعه از شهرها میگذرند).
برای مسائلی که پیدا کردن یک پاسخ تقریبی برای بهینه کلی مهمتر از پیدا کردن یک پاسخ دقیق برای بهینه محلی در زمان محدود و مشخصی است، تبرید شبیه‌سازی شده ممکن است نسبت به باقی روش‌ها مانند گرادیان کاهشی دارای ارجحییت باشد.
تکنیک تبرید تدریجی، به وسیلهٔ متالورژیست‌ها برای رسیدن به حالتی که در آن ماده جامد، به خوبی مرتب و انرژی آن کمینه شده باشد، استفاده میشود. هدف از این کار این است که سایز کریستال‌ها در حالت جامد ماده در حال تبرید به بزرگترین حالت برسد.
این تکنیک شامل قرار دادن ماده در دمای بالا و سپس کم کردن تدریجی این دماست. شبیه سازی تبرید رویکردی است که مسئله کمینه سازی یک تابع با تعداد بسیار زیادی متغیر است را به یک مسئله مکانیک آماری کاهش می‌دهد.
بنیان گذاران این الگوریتم برای حل مسائل سخت بهینه‌سازی، روشی مبتنی بر تکنیک تبرید تدریجی و آرام پیشنهاد نمودند. این محققین برای مدلسازی تبرید یک سیستم به منظور پیدا کردن پاسخ کمینه کلی، از شبیه سازی کامپیوتری استفاده کردند.
می‌توان تبرید تدریجی و آرام در این الگوریتم را به عنوان کاهش تدریجی احتمال انتخاب پاسخ‌های بدتر حین جستجو در فضای پاسخ‌ها دانست (انتخاب پاسخ‌های بدتر یک ویژگی اساسی الگوریتم‌های فراابتگاری است و پیدا کردن بهترین پاسخ را ممکن می‌سازد).
شبیه سازی را می‌توان به دو صورت حل روابط کینتیکی برای توابع چگالی (مانند کار خاچاتوریان، سمونوفسکایا و وینشتاین در سال ۱۹۷۹ و ۱۹۸۱) یا استفاده از نمونه‌گیری تصادفی، انجام داد.
نمونه گیری تصادفی در سال ۱۹۸۳ توسط کریک‌پاتریک، گلت و کلی معرفی شد، کرنی در سال ۱۹۸۵ و خاچاتوریان، سمونوفسکایا و وینشتاین در سال ۱۹۸۵ به طور مستقل این ایده را مطرح کردند. این روش یک اقتباس از الگوریتم متروپولیس-هستینگز است، یک روش مونت کارلو که نمونه حالت‌هایی را از یک سیستم ترمودینامیک تولید می‌کند.
بدون دیدگاه