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

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

 روشهاي ايجاد كننده يك يا چند سري جواب از ميان يك مجموعه جواب انتخاب شده وسپس بهترين جواب ازميان آنها انتخاب مي شود.
 روشهاي بهبود دهنده از يك جواب اوليه شروع مي شود و سعي مي كند انرا با تغيير و تبديل در هر تكرار بهبود دهد.در اين روش يك جواب همسايگي انتخاب مي شود كه به كاهش بيشترين هزينه كمك ميكندوتا زماني كه ديگر بهبودي ممكن نباشد ادامه مي يابد.

 Annealing
 در لغت به معناي گداخته كردن جسم
 دراصطلاح يك فرايند فيزيكي براي بالا بردن دماي جسم تا رسيدن به نقطه ذوب وسپس سرد كردن آن طي شرايط مشخص كه در طول اين فرايند انرژی جسم به حداقل مي رسد
 در سال 1953متروپليس الگوريتمي را براي ارزيابي تغييرات دماي جسم جامد ارائه داد.او ابتدا دماي جسم را بالا برده تا جسم به حالت مذاب درآيد و سپس براي كاهش انرژي دروني جسم اتمهاي جسم راجابجا نموده تا انرژي جسم كاهش يابد.اين جابجايي ما بين دو اتم انجام ميگيرد سپس در همسايگي اين اتم اتم ديگري را انتخاب نموده كه با اين اتم جابجا مي گردد.در اين دما چندين جابجايي صورت مي گيرد و وقتي هيچ تغييري در انرژي جسم حاصل نشد دماي جسم را كاهش مي دهند.قبل از اينكه دماي جسم را كاهش دهند تست تعادلي انجام ميگيرددر صورتي كه در اثر جابجايي انرژي جسم كاهش يابد جابجايي پذيرفته مي شود در غير اينصورت جابجايي با يك احتمال پذيرفته ميشود.

در الگوريتم SA يكسري پارامترها مطرح هستند كه ممكن است بسته به نوع مسئله تغيير كند ويا مشابه مسئله ديگر در نظر گرفته شوند, بر اين اساس پارامترهاي الگوريتم به دو دسته عمده تقسيم مي شوند.
• پارامترهاي خاص مسئله
• پارامترهاي عمومي
 جواب اوليه درSA استاندارد اين جواب بطورتصادفي تعيين مي گردد.
 مكانيزم ايجاد همسايگي
1. شيفت
2. تعويض
3. تعويض جفت كنارهم
علاوه بر پارامترهاي ذكر شده, يكسري پارامترهاى ديگرى هستند كه در هر الگوريتم SA وجود دارند كه برنامه سرد كردن راتشكيل مي دهند, اين پارامترها را مي توان بطور خلاصه بصورت زير بيان كرد
1. مقدار اوليه پارامتردما
2. يك تابع دما T(t) براي تعيين چگونگي تغيير دما
3. تعدادتكرارهابراي اجرا در هر دما
4. مقياس توقف براي پايان دادن الگوريتم
5. مقياس حالت تعادلي سيستم
كه در اينجا هر كدام از پارامترها توضيح داده مي شوند