تابع anneal یک روش بهینه‌سازی است که با استفاده از الگوریتم شبیه‌سازی شده گرم شدن (Simulated Annealing) برای مینیمم کردن یک تابع استفاده می‌شود. این الگوریتم ابتدا در سال 1983 توسط Kirkpatrick et al. معرفی شد. روش شبیه‌سازی شده گرم شدن به گونه‌ای عمل می‌کند که دما به تدریج کاهش می‌یابد و به جستجو در فضای حل برای یافتن بهینه‌ترین جواب می‌پردازد. این روش شبیه به فرآیندهای فیزیکی است که در آن مولکول‌ها با حرکت تصادفی در دماهای بالا و پایین به وضعیت پایدار می‌رسند.

General Flowchart for Simulated Annealing (SA) algorithm. | Download Scientific Diagram

ورودی‌ها:

تابع anneal سه پارامتر ورودی دریافت می‌کند:

  1. LOSS: یک اشاره‌گر به تابع زیان (loss function) که می‌تواند هر نوع تابعی باشد و نیازی به پیوستگی ندارد. این تابع باید تنها یک مقدار خروجی بدهد.
  2. PARENT: یک بردار از مقادیر اولیه که برای شروع جستجو در فضای پارامترها استفاده می‌شود. این پارامتر باید حاوی حدس اولیه برای جواب بهینه باشد.
  3. OPTIONS: یک ساختار (struct) که تنظیمات شبیه‌سازی شده گرم شدن را شامل می‌شود. اگر این ساختار داده نشود، anneal از تنظیمات پیش‌فرض استفاده می‌کند.

گزینه‌ها در ساختار OPTIONS:

در صورتی که ساختار OPTIONS داده شود، می‌تواند شامل گزینه‌های مختلفی باشد که رفتار الگوریتم را تحت تاثیر قرار می‌دهند. این گزینه‌ها به شرح زیر هستند:

  • Verbosity: میزان نمایش اطلاعات در طول اجرا.

    • 0: هیچ‌گونه خروجی نمایش داده نمی‌شود.
    • 1: تنها گزارش نهایی نشان داده می‌شود (پیش‌فرض).
    • 2: تغییرات دما و گزارش نهایی نمایش داده می‌شود.

  • Generator: تابعی که یک جواب جدید از جواب قبلی تولید می‌کند. این تابع باید ورودی یک جواب را بگیرد و خروجی یک جواب معتبر از فضای جستجو باشد. تابع پیش‌فرض، یک بردار ردیفی تولید می‌کند که تنها یکی از عناصر آن با مقداری تصادفی تغییر می‌کند.

  • InitTemp: دمای اولیه که می‌تواند هر عدد مثبت باشد. مقدار پیش‌فرض 1 است.

  • StopTemp: دمایی که پس از آن الگوریتم متوقف می‌شود. این مقدار باید از دمای اولیه کوچک‌تر باشد. مقدار پیش‌فرض 1e-8 است.

  • StopVal: مقدار تابع زیان که در صورت رسیدن به آن، الگوریتم متوقف می‌شود. این مقدار باید مقداری کافی کوچک باشد تا نشان‌دهنده بهینه‌ترین جواب باشد. مقدار پیش‌فرض -Inf است.

  • CoolSched: تابعی که دمای بعدی را از دمای فعلی محاسبه می‌کند. تابع پیش‌فرض @(T) (.8*T) است.

  • MaxConsRej: حداکثر تعداد رد شدن‌های متوالی که قبل از کاهش دما باید اتفاق بیفتد. مقدار پیش‌فرض 1000 است.

  • MaxTries: حداکثر تعداد تلاش‌ها برای پیدا کردن جواب در یک دما. مقدار پیش‌فرض 300 است.

  • MaxSuccess: حداکثر تعداد موفقیت‌ها در یک دما. مقدار پیش‌فرض 20 است.

نحوه استفاده:

فرم کلی تابع به صورت زیر است:

[MINIMUM, FVAL] = ANNEAL(LOSS, NEWSOL, [OPTIONS]);
  • MINIMUM: جواب بهینه‌ای که کوچک‌ترین مقدار تابع زیان را تولید می‌کند.
  • FVAL: مقدار تابع زیان در نقطه بهینه MINIMUM.

در صورتی که بخواهید تنظیمات پیش‌فرض را دریافت کنید، می‌توانید از این کد استفاده کنید:

OPTIONS = ANNEAL();

مثال:

برای درک بهتر نحوه عملکرد، می‌توانیم از یک تابع معروف به نام six-hump camelback استفاده کنیم که چندین مینیمم محلی در دامنه‌های مختلف دارد. این تابع دو مینیمم جهانی دارد که در مختصات خاصی قرار دارند.

تعریف و مینیمم کردن این تابع به صورت زیر انجام می‌شود:

camel = @(x,y)(4-2.1*x.^2+x.^4/3).*x.^2+x.*y+4*(y.^2-1).*y.^2;
loss = @(p)camel(p(1),p(2));
[x f] = anneal(loss, [0 0])

خروجی این کد به شرح زیر خواهد بود:

Initial temperature: 1
Final temperature: 3.21388e-007
Consecutive rejections: 1027
Number of function calls: 6220
Total final loss: -1.03163
x =
-0.0899 0.7127
f =
-1.0316

در این مثال، الگوریتم به خوبی مینیمم جهانی تابع را تقریبا به مقدار تحلیلی آن یعنی f(-0.0898, 0.7126) = -1.0316 می‌رسد. توجه داشته باشید که به دلیل تصادفی بودن فرآیند، نتایج دقیقاً مشابه نخواهند بود.

نتیجه‌گیری:

الگوریتم simulated annealing یک روش قوی برای بهینه‌سازی توابع پیچیده با استفاده از جستجوی تصادفی است. این روش به‌ویژه در مسائل بهینه‌سازی با فضای جستجوی بزرگ و چندین مینیمم محلی مفید است و می‌تواند به یافتن بهترین راه‌حل‌های تقریبی کمک کند.

دسته بندی: برچسب ها: