مروری بر الگوریتم تبرید (Simulated Annealing)

الگوریتم تبرید یا شبیه‌سازی حرارتی، یکی از مجموعه الگوریتمهای متاهیوریستیک (فرا اکتشافی) معروف در زمینه الگوریتمهای هوش مصنوعی است.
این الگوریتم در سال 1983 و توسط Scott Kirkpatrick و Daniel Gelatt ابداع شده است. اصولا اکثر الگوریتمهای متاهیوریستیک با الگوگیری و شبیه‌سازی یکی از قوانین یا روابط موجود در طبیعت بنا نهاده می‌شوند. این الگوریتم هم بر مبنای فرآیند تبرید یا بازپخت فلزات بنا نهاده شده است.
در فرآیند تبرید، ابتدا حرارت فلزات را تا دمای بسیار بالایی افزایش داده و سپس، یک فرآیند سردسازی و کاهش دمای تدریجی بر روی آنها صورت می‌گیرد. در این فرآیند در هنگام افزایش حرارت فلز، سرعت جنبش اتمهای آن به شدت افزایش یافته و در مرحله بعد، کاهش تدریجی دما موجب شکل گیری الگوهای خاصی در جایگیری اتمهای آن می‌شود.
این تغییر الگوی اتمها باعث بروز خواص ارزشمندی در فلز تبرید شده می‌گردد که از جمله می‌توان به افزایش استحکام آن اشاره نمود.
simulated annealing pattern
فلوچارت این الگوریتم به صورت زیر است:
SA flowchart
همچنین الگوریتم آن:
SA code
همانطور که می‌بینید اساس این الگوریتم بر مبنای جستجوی محلی (Local search) است، بنابراین طراحی متدهای جستجوی محلی مناسب با توجه به شرایط و محدودیتهای مسائل شبیه‌سازی شده در این الگوریتم، از اهمیت بسیار بالایی برخوردار است.
به طور کلی پس از تحلیل این الگوریتم، مزایا و معایب آن را به صورت زیر می‌توان معرفی نمود:
مزایا:
– مصرف حافظه بسیار پایین (بر خلاف الگوریتم ژنتیک که مصرف بالایی دارد).
– پیاده‌سازی آن نسبت به الگوریتمهای دیگر هم رده خود، نسبتا ساده‌تر است.
– به دلیل تمرکز بر جستجوی محلی، معمولا جوابهای قابل قبولی پیدا می‌کند.
– به دلیل وجود روند تصادفی هدایت شده (احتمال پذیرش پایین برای پاسخهای غیر بهینه) توانایی گذر از بهینه محلی (Local Optima) را دارد.
معایب:
– وابستگی زیادی به مقدار اولیه پارامترها دارد.
– در صورت انتخاب مقدار نامناسب برای پارامتر دمای اولیه، به احتمال زیاد در بهینه محلی گیر می‌کند.
– پیش بینی مقدار اولیه مناسب برای پارامترهای مسئله، بدون بنچمارک (Benchmark) ممکن نیست.
پ.ن: این الگوریتم در مسائل مختلفی مانند TSP یا PSP نتایج بهتری نسبت به الگوریتم ژنتیک کسب می‌نماید.
پ.ن: ساختار ایستا و کم هزینه آن به الگوریتم ژنتیک پایدار (Steady-State Genetic Algorithm) شباهت دارد.

About محمد شمس

برنامه‌نویس، طراح انیمیشن و علاقمند به هوش مصنوعی

5 Comments

  1. سلام  با سپاس فراوان از شما، بخاطر مطلب “مروری بر الگوریتم تبرید (Simulated Annealing)”. 

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

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

  4. سلام
    با تشکر از مطالب مفیدتان
    لطفا منبع این متن رو هم اعلام بفرمایین
    تشکر

    در ضمن اگر ممکن است مزایای استفاده از ذوب فلز در شبیه سازی ها نسبت به الگوریتم مهاجرت پرندگان را درصورت امکان به اینجانب بفرمایین

پاسخ دهید

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


4 × = 36