ناب لرنینگ |
بزرگترین بانک اطلاعاتی پروژه های دانشجویی الگوریتم شبیه سازی تبرید
در الگوریتم شبیه سازی تبرید (یا تبرید شبیه سازی شده) از فرایند بازپخت که از مباحث رشته متالورژی و مواد محسوب می‌شود، الگو گرفته شده است. انتخاب نام شبیه‌سازی تبرید برای این الگوریتم، ریشه در فرایند دارد که از آن تقلید می‌کند. در بهینه‌سازی نیز مانند فرایند انیلینگ، آنچه در بخش پیشین پیرامون بازپخت مواد بیان شد، برای حل مسائل قابل انجام است. یعنی در واقع، جواب‌های یک مساله به خوبی گرم می‌شوند و با نوسانات زیادی تغییر می‌کنند؛ سپس، به تدریج دامنه تغییرات کم می‌شود و در واقع یک سری شیار به سمت جواب بهینه ساخته می‌شوند. الگوریتم شبیه سازی تبرید برای اولین بار در سال ۱۹۸۳، توسط «کریک‌پاتریک» (Kirkpatrick) و همکاران معرفی شد. شایان ذکر است، الگوریتم شبیه سازی تبرید از جمله الگوریتم‌های فراابتکاری (فراتکاملی | فرااکتشافی | Metaheuristic) محسوب می‌شود. در الگوریتم شبیه سازی تبرید، از روش احتمالاتی برای حل مساله بهینه‌سازی استفاده می‌شود.
در الگوریتم شبیه سازی تبرید (SA)، نقطه s یک حالت از سیستم فیزیکی محسوب می‌شود و تابع (E(s مشابه با انرژی داخلی سیستم در حالت s است. هدف آن است که با شروع سیستم از یک حالت اولیه دلخواه (یک s0 دلخواه)، به حالتی رسیده شود (Sn) که تابع (E(s در آن کمینه است. در واقع، با شروع از یک حالت دلخواه از سیستم فیزیکی، به حالتی رسیده می‌شود که انرژی داخلی سیستم در آن حالت کمینه است (سیستم کمترین انرژی را در آن حالت خواهد داشت). برای انجام این کار، الگوریتم از یک نقطه دلخواه آغاز به کار و سپس، یک حالت همسایه را انتخاب می‌کند. پس از آن، به طور احتمالی تصمیم می‌گیرد که در حالت کنونی بماند و یا به حالت همسایه جا به جا شود. مجموع این جا به جایی‌های احتمالی، سیستم را به سوی حالتی با انرژی داخلی کمتر هدایت می‌کند. این کار تا جایی انجام می‌شود که سیستم به یک حالت عقلانی برسد یا اینکه میزان محاسبات، از یک آستانه مشخص بیشتر شود.
مساله فروشنده دوره‌گرد را می‌توان به عنوان مثالی در نظر گرفت که الگوریتم شبیه سازی تبرید در حل آن کاربرد دارد. همانطور که پیش‌تر بیان شد، در این مساله، فروشنده باید از تعداد زیادی از شهرها در حالی عبور کند که مسافت کل پیموده شده کمینه باشد. اگر فروشنده از یک مسیر تصادفی حرکت خود را آغاز کند، بعدا می‌تواند با این امید که در هر تغییر شهر مسافت پیموده شده را کاهش دهد، به ترتیب از کلیه شهرها عبور کند.
چالش اصلی در حل مساله فروشنده دوره گرد با استفاده از روشی مانند الگوریتم «تپه‌نوردی» (Hill Climbing)، از آنجا نشات می‌گیرد که این الگوریتم با جا به جایی بین همسایه‌ها معمولا به حالت کمینه می‌رسد و در همان نقطه متوقف می‌شود (در واقع در حالتی که نسبت به دیگر همسایگی‌های بررسی شده کمینه باشد متوقف می‌شود؛ در صورتی که امکان دارد یک کمینه سراسری وجود داشته باشد). در واقع، الگوریتم تپه‌نوردی «کمینه محلی» (Local Minimum) را معمولا به سرعت پیدا می‌کند، اما ممکن است در همان جا متوقف شود و بنابراین از آنجا به «کمینه سراسری» (Global Minimum) نمی‌رسد. این در حالی است که شبیه‌سازی تبرید می‌تواند راه حل خیلی خوبی را حتی در حضور «نویز» (Noise) برای چنین مساله‌ای پیدا کند.
راهکار الگوریتم شبیه سازی تبرید برای غلبه بر این مشکل و بهبود استراتژی مذکور، استفاده از دو ترفند است. ترفند اول، از «الگوریتم متروپولیس» (Metropolis Algorithm) گرفته شده که در سال ۱۹۵۳ توسط متروپولیس و همکاران اون کشف شده است. در این الگوریتم، گاهی مسیرهای کوتاه پذیرفته نمی‌شوند، زیرا این عدم پذیرش منجر به آن می‌شود که الگوریتم «فضای راه حل ممکن» بزرگ‌تری را اکتشاف کند. ترفند دوم، مجددا با تقلید از فرایند بازپخت فلز و کاهش دما به دمای پایین‌تر اتفاق می‌افتد. پس از آنکه بررسی‌ها و جا به جایی‌های زیادی انجام شد و مشاهده شد که تابع (E(s (این تابع در واقع همان تابع هزینه یا Cost Function است) به آرامی کاهش پیدا می‌کند (دما کاهش پیدا می‌کند)، اندازه انجام جا به جایی‌های «بد» کنترل می‌شود. پس از چندین بار کاهش دما به مقدار کمتر، فرایند «فرونشانی» (Quench) با پذیرش جا به جایی‌های خوب به منظور پیدا کردن کمینه محلی تابع هزینه اتفاق می‌افتد. «زمان‌بندی‌های بازپخت» (Annealing Schedules) متعددی برای کاهش درجه حرارت وجود دارد، اما نتایج به طور کلی خیلی به جزئیات حساس نیستند.
فلوچارت الگوریتم شبیه سازی تبرید
کد الگوریتم تبرید شبیه سازی شده در جاوا
