برنامه نویسی 97 بازدید

در این راهنما در مورد الگوریتم «تبرید شبیه‌سازی‌ شده» (Simulated Annealing) صحبت خواهیم کرد و مثالی از پیاده‌سازی آن را بر مبنای مسئله فروشنده دوره گرد (TSP) ارائه می‌کنیم.

تبرید شبیه‌سازی‌ شده

الگوریتم شبیه‌سازی‌شده یک راه‌حل شهودی برای حل کردن مسائلی با فضای جستجوی بزرگ محسوب می‌شود. نام و منبع الهام این الگوریتم از موضوع تبرید در متالوژی ناشی می‌شود. این تکنیکی است که در آن حرارت‌دهی و خنک کردن کنترل‌شده یک ماده صورت می‌گیرد.

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

مسئله فروشنده دوره گرد

همان طور که مشاهده می‌کنید؛ الگوریتم از یک بازه وسیعی از راه‌حل با دمای بالای سیستم استفاده می‌کند و به دنبال نقطه بهینه سراسری می‌گردد. زمانی که دما کاهش می‌یابد، بازه جستجو کوچک‌تر می‌شود تا این که به بهینه سراسری می‌رسد.

این الگوریتم چند پارامتر دارد که با آن‌ها کار می‌کند:

  • تعداد تکرارها: شرط توقف برای شبیه‌سازی است.
  • دمای اولیه: انرژی آغازین سیستم است.
  • پارامتر نرخ خنک‌سازی: درصد کاهش دمای سیستم را تعیین می‌کند.
  • کمینه دما: شرایط اختیاری توقف است.
  • زمان شبیه‌سازی: شرایط اختیاری توقف است.

مقادیر این پارامترها باید به دقت انتخاب شوند، چون ممکن است تأثیر زیادی روی عملکرد فرایند بگذارند.

مسئله فروشنده دوره‌گرد

مسئله فروشنده دوره‌گرد (TSP) شناخته‌شده‌ترین مسئله بهینه‌سازی رایانه در دنیای مدرن محسوب می‌شود. به بیان ساده این مسئله به یافتن مسیر بهینه بین گره‌های یک گراف گفته می‌شود. مسافت کلی سفر می‌تواند یکی از معیارهای سفر باشد.

مدل جاوا

برای حل مسئله TSP باید کلاس‌های مدل را که City و Travel نام دارند در اختیار داشته باشیم. در کلاس اول شرایط گره‌ها را در گراف ذخیره می‌کنیم:

متد سازنده کلاس City، امکان ایجاد موقعیت‌های تصادفی شهرها را به ما می‌دهد. منطق (..)distanceToCity مسئول محاسبه مسافت بین شهرها است.

کد زیر مسئول مدل‌سازی گردش یک فروشنده دوره‌گرد است. کار خود را با ایجاد ترتیب اولیه شهرها در سفر آغاز می‌کنیم:

علاوه بر ایجاد مسیر اولیه، باید متدهایی برای تعویض دو شهر تصادفی در ترتیب سفر نیز تهیه کنیم. ما از آن برای جستجوی راه‌حل‌های بهتر درون الگوریتم تبرید شبیه‌سازی‌ شده استفاده می‌کنیم:

افزون بر آن باید یک متد برای بازگرداندن تعویض ایجاد شده در مرحله قبلی نیز داشته باشیم که اگر راه‌حل جدید پذیرفته نشود مورد استفاده قرار می‌گیرد:

آخرین متد که باید داشته باشیم، محاسبه مسافت کلی سفر است که به عنوان معیار بهینه بودن استفاده می‌شود:

اینک روی بخش اصلی مسئله یعنی پیاده‌سازی الگوریتم تبرید شبیه‌سازی‌ شده متمرکز می‌شویم.

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

در پیاده‌سازی زیر برای الگوریتم تبرید شبیه‌سازی‌ شده قصد داریم مسئله TSP را حل کنیم. به عنوان یادآوری باید بگوییم که هدف ما یافتن کوتاه‌ترین مسافت برای سفر بین دو شهر است.

برای آغاز فرایند باید سه پارامتر اصلی یعنی startingTemperature ،numberOfIterations و coolingRate را ارائه کنیم:

پیش از آغاز شبیه‌سازی، ترتیب اولیه (تصادفی) شهرها را ایجاد و مسافت کلی سفر را محاسبه می‌کنیم. از آنجا که این نخستین محاسبه مسافت است باید آن را درون متغیر bestDistance همراه با currentSolution ذخیره کنیم.

در گام بعدی یک حلقه شبیه‌سازی‌های اصلی را آغاز می‌کنیم:

این حلقه به تعداد تکرارهایی که تعیین‌شده اجرا می‌شود. به علاوه یک شرط نیز برای توقف آن تعیین کرده‌ایم که به صورت کاهش دما به کمتر از 0.1 است. بدین ترتیب می‌توانیم در زمان شبیه‌سازی‌ها صرفه‌جویی کنیم، زیرا در دماهای پایین، اختلاف بهینه‌سازی‌ها چندان درخور توجه نیست. در ادامه منطق اصلی الگوریتم تبرید شبیه‌سازی‌ شده را می‌بینید:

یافتن کوتاه‌ترین مسافت

در هر گام از شبیه‌سازی به صورت تصادفی دو شهر را در ترتیب سفر قرار می‌دهیم. به علاوه currentDistance را محاسبه می‌کنیم، اگر مسافت جدید پایین‌تر از bestDistance باشد، آن را به عنوان بهترین نتیجه (bestDistance) ذخیره می‌کنیم.

در غیر این صورت بررسی می‌کنیم که آیا تابع بولتزمان احتمال توزیع پایین‌تر از مقدار انتخاب شده تصادفی در بازه 0 تا 1 است یا نه. اگر چنین بود شهرها را عوض می‌کنیم؛ در غیر این صورت ترتیب جدید شهرها را نگه می‌داریم، چون به ما کمک می‌کند که از کمینه‌های موضعی احتراز کنیم. در نهایت در هر گام از شبیه‌سازی دما را به میزان coolingRate کاهش می‌دهیم:

پس از این که شبیه‌سازی پایان یافت، بهترین راه‌حل را که با استفاده از الگوریتم تبرید شبیه‌سازی‌ شده به دست آمده است، بازگشت می‌دهیم. در ادامه چند نکته در مورد انتخاب پارامترهای بهترین شبیه‌سازی ارائه شده که باید مورد توجه قرار دهید:

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

فراموش نکنید که پیش از آغاز شبیه‌سازی‌های اصلی، زمان بیشتری را صرف تنظیم الگوریتم با وهله‌های کوچک‌تر مسئله بکنید، چون موجب بهبود نتیجه نهایی می‌شود.

سخن پایانی

در این راهنمای کوتاه با الگوریتم تبرید شبیه‌سازی‌ شده آشنا شدیم و مسئله فروشنده دوره‌گرد را حل کردیم. امیدواریم این مطلب میزان کارآمد بودن این الگوریتم ساده را در زمان استفاده برای انواع خاصی از مسائل بهینه‌سازی به شما نشان داده باشد. برای مشاهده کد کامل این پیاده‌سازی به این آدرس گیت‌هاب (+) مراجعه کنید.

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

==

به عنوان حامی، استارتاپ، محصول و خدمات خود را در انتهای مطالب مرتبط مجله فرادرس معرفی کنید.

telegram
twitter

میثم لطفی

«میثم لطفی» دانش‌آموخته کارشناسی ریاضیات کاربردی و شیفته فناوری به خصوص در حوزه رایانه است. وی در حال حاضر علاوه بر پیگیری همه علاقه‌مندی‌های خود در رشته‌های برنامه‌نویسی، کپی‌رایتینگ و تولید محتوای چندرسانه‌ای، در زمینه نگارش مقالاتی با محوریت نرم‌افزار نیز با مجله فرادرس همکاری دارد.

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *