دانلود مقالات ISI درباره بازپخت شبیه سازی شده + ترجمه فارسی

بازپخت شبیه سازی شده(به انگلیسی: Simulated annealing) یک الگوریتم بهینه‌سازی فراابتکاری ساده و اثربخش در حل مسائل بهینه‌سازی در فضاهای جستجوی بزرگ است. این الگوریتم بیشتر زمانی استفاده میشود که فضای جستجو گسسته باشد (مثلا همه گشت‌هایی که از یک مجموعه از شهرها میگذرند). برای مسائلی که پیدا کردن یک پاسخ تقریبی برای بهینه کلی مهمتر از پیدا کردن یک پاسخ دقیق برای بهینه محلی در زمان محدود و مشخصی است، تبرید شبیه‌سازی شده ممکن است نسبت به باقی روش‌ها مانند گرادیان کاهشی دارای ارجحییت باشد. مزایا و معایب آن را به صورت زیر می‌توان معرفی نمود: مزایا: – مصرف حافظه بسیار پایین (بر خلاف الگوریتم ژنتیک که مصرف بالایی دارد). – پیاده‌سازی آن نسبت به الگوریتمهای دیگر هم رده خود، نسبتا ساده‌تر است. – به دلیل تمرکز بر جستجوی محلی، معمولا جوابهای قابل قبولی پیدا می‌کند. – به دلیل وجود روند تصادفی هدایت شده (احتمال پذیرش پایین برای پاسخهای غیر بهینه) توانایی گذر از بهینه محلی (Local Optima) را دارد. معایب: – وابستگی زیادی به مقدار اولیه پارامترها دارد. – در صورت انتخاب مقدار نامناسب برای پارامتر دمای اولیه، به احتمال زیاد در بهینه محلی گیر می‌کند. – پیش بینی مقدار اولیه مناسب برای پارامترهای مسئله، بدون بنچمارک (Benchmark) ممکن نیست. اصول الگوریتم شبیه سازی تبرید SA * انتخاب دمای اولیه ( انتخاب دمای اولیه بسیار مهم می باشد و این عامل تاثیر بسیار زیادی بر روی exploration و exploitation دارد) * ایجاد نسل اولیه و ارزیابی نسل اولیه * جستجو محلی برای بهبود جواب ها * پذیرش جواب جدید اگر بهتر از جواب قبلی باشد * پذیرش جواب جدید با تابع احتمالی بولتزمان اگر جواب جدید بدتر از جواب قبلی باشد. * کاهش دما تکرار جستجو تا رسیدن به شرط پایان در الگوریتم شبیه سازی تبرید جسم در هر دمایی باشد در همان دما نیز به جست و جوی پاسخ های محتمل می پردازد و این کار برای اطمینان یافتن از اینکه به بهترین پاسخ محتمل رسیده ایم انجام می شود. به طور دقیق می توان الگوریتم SA را الگوریتمی با دو زنجیره تکراری دانست که زنجیره اولیه مسئول کاهش دما می باشد و زنجیره دوم مسئول یافتن پاسخ های محلی در هر دما می باشد. این الگوریتم بدون حافظه می باشد و وابستگی به جواب های قبلی ندارد. همچنین الگوریتم شبیه سازی تبرید عملکرد بسیار مناسبی در مسائل بهینه سازی گسسته دارد. یکی از معایب این الگوریتم سرعت کم همگرایی می باشد که برای حل این مشکل می توان این الگوریتم را با الگوریتم ژنتیک ترکیب نمود تا به سرعت همگرایی مناسبی دست یابیم. الگوریتم شبیه سازی annealing که نسخه ای از تپه نوردی اتفاقی است و پایین آمدن از تپه مجاز است. حرکت به طرف پایین و به آسانی در اوایل زمانبندی annealing پذیرفته شده و با گذشت زمان کمتر اتفاق می افتد. تضمینی وجود ندارد که الگوریتم تپه نوردی که هرگز حرکت روبه پایین به سمت حالتهایی با مقادیر کوچکتر (با هزینه بالاتر) را انجام نمیدهد، "کامل باشد"، زیرا میتواند در یک ماکزیمم محلی متوقف شود. برعکس، یک حرکت کاملا تصادفی، یعنی حرکت به یک پسین که بطور یکنواخت و بطور تصادفی از مجموعه ای از پسین ها انتخاب شد، "کامل " است، اما کاملا غیر کارآمد است. لذا، منطقی است که ازیک تپه نوردی با حرکت تصادفی استفاده شود که کارامد و کامل است. simulated annealing چنین الگوریتمی است. در متالوژی، annealing فرآیندی است که فلزهای سخت و شیشه را با درجه بالایی حرارت میدهد و سپس آنها را به تریج سرد میکند. به این ترتیب مواد به حالت کریستالی با انرژی پایین در می آیند. برای درک simulated annealing به جای تپه نوردی، فرود آمدن از شیب (یعنی مینیمم کردن هزینه) را در نظر میگیریم. جواب simulated annealing با تکان دادن شدید شروع میشود (دمای زیاد) و به تدریج شدت تکان دادنرا کاهش میدهد (به دمای پایینتر). در شبه کد الگوریتم simulated annealing به جای انتخاب بهترین حرکت، یک حرکت تصادفی را انتخاب میکند. اگر این حرکت، وضعیت را بهبود بخشد، همواره قابل قبول است. وگرنه الگوریتم حرکت را با احتمال کمتر از 1 میپذیرد. میزان احتمال برحسب میزان بد بودن حرکت، بطور نمایی به اندازه ∆E کاهش می یابد و در نتیجه ارزیابی بدتر میشود. وقتی دمای "T" پایین می آید، این احتمال نیز کاهش می یابد: در شروع کار، وقتی دما بالا است حرکتهای "بد" با احتمال بیشتری رخ میدهند و بعید است که با کاهش T بیشتر شود. اگر زمانبندی، T را به تدریج کاهش دهد، الگوریتم یک بهینه سراسری را با احتمال نزدیک به 1 می یابد.