پاورپوینت آماده: بررسی تاریخچه و پارامترهای الگوریتم آنیلینگ - Simulated annealing

پاورپوینت آماده: بررسی تاریخچه و پارامترهای الگوریتم آنیلینگ - Simulated annealing

مطالب اسلایدهای ابتدایی این پاورپوینت به شرح زیر است

 

تعداد اسلاید : 23 اسلاید

بررسی تاریخچه و پارامترهای الگوریتم آنیلینگ - Simulated annealing مقدمه پيدا كردن جواب درست و دقيق براي مسائل مختلف از ديرباز مورد توجه بوده و روشهاي مختلفي را براي حل به دنبال داشته است.ولي با پيشرفت تكنولو‍‍‍ژي مسائل نيز پيچيده تر شد و روشهاي دقيق تري را ايجاب مي كرد .حجم محاسبات براي اين مسائل به حدي ميرسيد كه پيدا كردن جواب دقيق را غير ممكن مينمود ولي اهميت رسيدن به جواب دقيق و بهينه همچنان به قوت خود باقي بود.اين مسائل موجب شد يكسري روشهاي كندوكاوي براي حل آنها استفاده شوند. مقدمهبطور كلي روشهاي حل را ميتوان به دو دسته تقسيم كرد روشهاي ايجاد كننده : يك يا چند سري جواب از ميان يك مجموعه جواب انتخاب شده وسپس بهترين جواب ازميان آنها انتخاب مي شود.

روشهاي بهبود دهنده : از يك جواب اوليه شروع مي شود و سعي مي كند انرا با تغيير و تبديل در هر تكرار بهبود دهد.در اين روش يك جواب همسايگي انتخاب مي شود كه به كاهش بيشترين هزينه كمك ميكندوتا زماني كه ديگر بهبودي ممكن نباشد ادامه مي يابد.
تاریخچهSimulated Annealing Annealing

در لغت به معناي گداخته كردن جسم

دراصطلاح يك فرايند فيزيكي براي بالا بردن دماي جسم تا رسيدن به نقطه ذوب وسپس سرد كردن آن طي شرايط مشخص كه در طول اين فرايند انرژی جسم به حداقل مي رسد تاريخچه Simulated

در لغت به معناي شبيه سازي كردن

در اصطلاح بازسازي رفتار يك فرايند با توجه به يكسري فرضيات با اطلاعات معلوم يا فرضي است تاريخچه در سال 1953متروپليس الگوريتمي را براي ارزيابي تغييرات دماي جسم جامد ارائه داد.او ابتدا دماي جسم را بالا برده تا جسم به حالت مذاب درآيد و سپس براي كاهش انرژي دروني جسم اتمهاي جسم راجابجا نموده تا انرژي جسم كاهش يابد.اين جابجايي ما بين دو اتم انجام ميگيرد سپس در همسايگي اين اتم اتم ديگري را انتخاب نموده كه با اين اتم جابجا مي گردد.در اين دما چندين جابجايي صورت مي گيرد و وقتي هيچ تغييري در انرژي جسم حاصل نشد دماي جسم را كاهش مي دهند.قبل از اينكه دماي جسم را كاهش دهند تست تعادلي انجام ميگيرددر صورتي كه در اثر جابجايي انرژي جسم كاهش يابد جابجايي پذيرفته مي شود در غير اينصورت جابجايي با يك احتمال پذيرفته ميشود. تاريخچه
بعدها به سال 1983 كرك پاتريك با مشابه سازي اين الگوريتم بين مينيمم كردن تابع هزينه يك مسئله و سرد كردن جسم تازمان رسيدن انرژي پايه از آن براي حل مسئله بهينه سازي استفاده كردند كه با اين جايگذاري او و همكارانش الگوريتمي بنام SA ارائه دادند. الگوريتم Simulated Annealing پارامترهاي :SA در الگوريتم SA يكسري پارامترها مطرح هستند كه ممكن است بسته به نوع مسئله تغيير كند ويا مشابه مسئله ديگر در نظر گرفته شوند, بر اين اساس پارامترهاي الگوريتم به دو دسته عمده تقسيم مي شوند.
پارامترهاي خاص مسئله
پارامترهاي عمومي پارامترهاي خاص مسئله جواب اوليه: درSA استاندارد اين جواب بطورتصادفي تعيين مي گردد.

مكانيزم ايجاد همسايگي:
شيفت
تعويض
تعويض جفت كنارهم پارامترهاي عمومي علاوه بر پارامترهاي ذكر شده, يكسري پارامترهاى ديگرى هستند كه در هر الگوريتم SA وجود دارند كه برنامه سرد كردن راتشكيل مي دهند, اين پارامتر

دریافت فایل