Astaraki

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

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

این الگوریتم در سال 1983 و توسط Scott Kirkpatrick و Daniel Gelatt ابداع شده است. اصولا اکثر الگوریتمهای متاهیوریستیک با الگوگیری و شبیه‌سازی یکی از قوانین یا روابط موجود در طبیعت بنا نهاده می‌شوند. این الگوریتم هم بر مبنای فرآیند تبرید یا بازپخت فلزات بنا نهاده شده است.

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

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



فلوچارت این الگوریتم به صورت زیر است:



همچنین الگوریتم آن:



همانطور که می‌بینید اساس این الگوریتم بر مبنای جستجوی محلی (Local search) است، بنابراین طراحی متدهای جستجوی محلی مناسب با توجه به شرایط و محدودیتهای مسائل شبیه‌سازی شده در این الگوریتم، از اهمیت بسیار بالایی برخوردار است.

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

مزایا:
- مصرف حافظه بسیار پایین (بر خلاف الگوریتم ژنتیک که مصرف بالایی دارد).
- پیاده‌سازی آن نسبت به الگوریتمهای دیگر هم رده خود، نسبتا ساده‌تر است.
- به دلیل تمرکز بر جستجوی محلی، معمولا جوابهای قابل قبولی پیدا می‌کند.
- به دلیل وجود روند تصادفی هدایت شده (احتمال پذیرش پایین برای پاسخهای غیر بهینه) توانایی گذر از بهینه محلی (Local Optima) را دارد.

معایب:
- وابستگی زیادی به مقدار اولیه پارامترها دارد.
- در صورت انتخاب مقدار نامناسب برای پارامتر دمای اولیه، به احتمال زیاد در بهینه محلی گیر می‌کند.
- پیش بینی مقدار اولیه مناسب برای پارامترهای مسئله، بدون بنچمارک (Benchmark) ممکن نیست.


پ.ن: این الگوریتم در مسائل مختلفی مانند TSP یا PSP نتایج بهتری نسبت به الگوریتم ژنتیک کسب می‌نماید.
پ.ن: ساختار ایستا و کم هزینه آن به الگوریتم ژنتیک پایدار (Steady-State Genetic Algorithm) شباهت دارد.

منبع

__________________

تعرفه ارزان تبلیغات در اولین و بزرگترین سایت هوش مصنوعی ایران !
با بیش از صد و چهل هزار کاربر!

parisa_m

salam mamnon misham age anvae algoritmhaye behine sazi ro behem moarefi konin

alireartuz

Genetic Algorithm
Imperialistic Competitive Algorithm
Particle Swarm Optimization
Ant Colony
Differential Evolution
Simulated Annealing
[Simplex Algorithms]
[NSGA II - NSGA - NRGA]
Tabu Search
[Neural Network - Solving TSP & Optimization problems]

reza645

با سلام
ببخشید یه تابع دارم میخوام با الگوریتم sa شکلشو رسم کنم . ممنون میشم کسی بتونه کمکم کنه

roya_asman

سلام
ممنون از نوشته های زیباتون
قسمت مزایا و معایب برا پایان نامه من لازمه
لطفا منبعش رو ذکر بفرمایین
تشکر