نمايش پست تنها
قديمي ۰۷-۷-۱۳۸۹, ۰۷:۴۰ بعد از ظهر   #1 (لینک دائم)
Astaraki Female
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Wink مروری بر الگوریتم تبرید (Simulated Annealing)

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

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

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

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

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



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



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



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

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

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

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


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

منبع
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
2Nassim (۰۱-۱۴-۱۳۹۳), damaghderaz (۰۳-۶-۱۳۹۰), innizbogzarad90 (۰۹-۱۶-۱۳۹۱), mohammadmono (۰۲-۲-۱۳۹۰), raika (۰۵-۲۰-۱۳۹۱), samaneh1390 (۰۹-۲-۱۳۹۰)

  #ADS
نشان دهنده تبلیغات
تبليغگر
 
 
 
تاريخ عضويت: -
محل سكونت: -
سن: 2010
پست ها: -
 

نشان دهنده تبلیغات is online