روش آنیلینگ (Simulated Annealing / Annealing Method)، در ریاضیات (Mathematics)

انواع روش های عددی (Numerical Methods) را در آموزش زیر شرح دادیم :

روش آنیلینگ (Simulated Annealing / Annealing Method) :

الگوریتم احتمالی مبتنی بر آنالوگی با فیزیک ذوب فلزات

توضیح ساده: روش آنیلینگ شبیه سازی شده (SA) یک الگوریتم فراابتکاری (Metaheuristic) برای بهینه سازی سراسری (Global Optimization) است. این روش از فرآیند آنیلینگ در متالورژی الهام گرفته است: در آنیلینگ، فلز را گرم کرده و سپس به آرامی سرد می کنند تا به ساختار بلوری پایدار با کمترین انرژی برسد. در SA، با احتمال پذیرش جواب های بدتر در مراحل اولیه (دمای بالا) از گیر افتادن در بهینه های محلی جلوگیری می شود و با کاهش تدریجی دما، الگوریتم به سمت بهینه سراسری همگرا می شود.

شرح گام به گام: الگوریتم SA:

۱. یک نقطه شروع x، دمای اولیه T₀، و نرخ کاهش دما α (مثلا ۰.۹۵) انتخاب کنید.

۲. برای تکرار تا رسیدن به شرط توقف:

   - یک همسایه x' از x (با اختلال تصادفی) تولید کنید.

   - ΔE = f(x') - f(x) را محاسبه کنید (تغییر در تابع هدف).

   - اگر ΔE < 0 (بهتر است)، x = x' را بپذیرید.

   - اگر ΔE > 0 (بدتر است)، با احتمال P = exp(-ΔE / T) آن را بپذیرید.

   - دما را کاهش دهید: T = α T.

۳. معیار توقف: دما به زیر آستانه برسد یا تعداد تکرارها تمام شود.

پذیرش جواب های بدتر در دمای بالا به الگوریتم اجازه می دهد از بهینه های محلی فرار کند.

مثال عددی: مسئله فروشنده دوره گرد (TSP) با ۱۰۰ شهر. SA با شروع از یک مسیر تصادفی و با کاهش تدریجی دما، می تواند به مسیرهای بسیار خوبی نزدیک به بهینه دست یابد. این روش برای مسائل ترکیباتی بسیار محبوب است.

مزایا: توانایی یافتن بهینه سراسری، ساده، قابل استفاده برای مسائل گسسته و پیوسته.

معایب: کند (نیاز به تعداد زیادی ارزیابی)، حساس به پارامترها (دمای اولیه، نرخ کاهش).

کاربردها: در طراحی مدارهای مجتمع، در زمان بندی، در مسیریابی، در بیوانفورماتیک.

نکته: SA یکی از اولین الگوریتم های فراابتکاری است که توسط کرک پاتریک و همکاران در ۱۹۸۳ معرفی شد.