بخشی از پاورپوینت
اسلاید 1 :
مقدمه
nپيدا كردن جواب درست و دقيق براي مسائل مختلف از ديرباز مورد توجه بوده و روشهاي مختلفي را براي حل به دنبال داشته است.ولي با پيشرفت تكنولو‍‍‍ژي مسائل نيز پيچيده تر شد و روشهاي دقيق تري را ايجاب مي كرد .حجم محاسبات براي اين مسائل به حدي ميرسيد كه پيدا كردن جواب دقيق را غير ممكن مينمود ولي اهميت رسيدن به جواب دقيق و بهينه همچنان به قوت خود باقي بود.اين مسائل موجب شد يكسري روشهاي كندوكاوي براي حل آنها استفاده شوند.
اسلاید 2 :
مقدمه
بطور كلي روشهاي حل را ميتوان به دو دسته تقسيم كرد
nروشهاي ايجاد كننده : يك يا چند سري جواب از ميان يك مجموعه جواب انتخاب شده وسپس بهترين جواب ازميان آنها انتخاب مي شود.
n
nروشهاي بهبود دهنده : از يك جواب اوليه شروع مي شود و سعي مي كند انرا با تغيير و تبديل در هر تكرار بهبود دهد.در اين روش يك جواب همسايگي انتخاب مي شود كه به كاهش بيشترين هزينه كمك ميكندوتا زماني كه ديگر بهبودي ممكن نباشد ادامه مي يابد.
n
اسلاید 3 :
تاریخچه
Simulated Annealing
nAnnealing
n
nدر لغت به معناي گداخته كردن جسم
n
nدراصطلاح يك فرايند فيزيكي براي بالا بردن دماي جسم تا رسيدن به نقطه ذوب وسپس سرد كردن آن طي شرايط مشخص كه در طول اين فرايند انرژی جسم به حداقل مي رسد
اسلاید 4 :
تاريخچه
nSimulated
n
nدر لغت به معناي شبيه سازي كردن
n
nدر اصطلاح بازسازي رفتار يك فرايند با توجه به يكسري فرضيات با اطلاعات معلوم يا فرضي است
اسلاید 5 :
تاريخچه
nدر سال 1953متروپليس الگوريتمي را براي ارزيابي تغييرات دماي جسم جامد ارائه داد.او ابتدا دماي جسم را بالا برده تا جسم به حالت مذاب درآيد و سپس براي كاهش انرژي دروني جسم اتمهاي جسم راجابجا نموده تا انرژي جسم كاهش يابد.اين جابجايي ما بين دو اتم انجام ميگيرد سپس در همسايگي اين اتم اتم ديگري را انتخاب نموده كه با اين اتم جابجا مي گردد.در اين دما چندين جابجايي صورت مي گيرد و وقتي هيچ تغييري در انرژي جسم حاصل نشد دماي جسم را كاهش مي دهند.قبل از اينكه دماي جسم را كاهش دهند تست تعادلي انجام ميگيرددر صورتي كه در اثر جابجايي انرژي جسم كاهش يابد جابجايي پذيرفته مي شود در غير اينصورت جابجايي با يك احتمال پذيرفته ميشود.
اسلاید 6 :
تاريخچه
n
nبعدها به سال 1983 كرك پاتريك با مشابه سازي اين الگوريتم بين مينيمم كردن تابع هزينه يك مسئله و سرد كردن جسم تازمان رسيدن انرژي پايه از آن براي حل مسئله بهينه سازي استفاده كردند كه با اين جايگذاري او و همكارانش الگوريتمي بنام SA ارائه دادند.
اسلاید 7 :
پارامترهاي :SA
در الگوريتم SA يكسري پارامترها مطرح هستند كه ممكن است بسته به نوع مسئله تغيير كند ويا مشابه مسئله ديگر در نظر گرفته شوند, بر اين اساس پارامترهاي الگوريتم به دو دسته عمده تقسيم مي شوند.
¨پارامترهاي خاص مسئله
¨پارامترهاي عمومي
اسلاید 8 :
پارامترهاي خاص مسئله
nجواب اوليه: درSA استاندارد اين جواب بطورتصادفي تعيين مي گردد.
n
nمكانيزم ايجاد همسايگي:
.1شيفت
.2تعويض
.3تعويض جفت كنارهم
اسلاید 9 :
پارامترهاي عمومي
علاوه بر پارامترهاي ذكر شده, يكسري پارامترهاى ديگرى هستند كه در هر الگوريتم SA وجود دارند كه برنامه سرد كردن راتشكيل مي دهند, اين پارامترها را مي توان بطور خلاصه بصورت زير بيان كرد:
.1مقدار اوليه پارامتردما
.2يك تابع دما T(t) براي تعيين چگونگي تغيير دما
.3تعدادتكرارهابراي اجرا در هر دما
.4مقياس توقف براي پايان دادن الگوريتم
.5مقياس حالت تعادلي سيستم
كه در اينجا هر كدام از پارامترها توضيح داده مي شوند:
اسلاید 10 :
مقداراوليه پارامتر دما
nانتخاب مقداراوليه دما بايد به گونه اي صورت گيرد كه در مرحله اوليه تعدادزيادي از جوابهاي نا مطلوب پذيرفته شوند. اين كار به دليل امكان تغيير و توسعه بيشتر جواب مي باشد.
nConnolly : يكسري تكرار با تعويضهاي تصادفي براي تغيير تابع هدف صورت ميگيرد
