بخشی از مقاله
شبيه‌سازي حرارتي
Simulated Annealing
شبيه‌سازي حرارتي
پاييز 1386
چكيده
در اين تحقيق ما به بررسي يكي از روشهاي بهينه‌سازي حل مسئله به نامSimulated Annealing مي‌پردازيم. SA در واقع الهام گرفته شده از فرآيند ذوب و دوباره سرد كردن مواد و به همين دليل به شبيه‌سازي حرارتي شهرت يافته است. در اين تحقيق ادعا نشده است كه SA لزوماً بهترين جواب را ارائه مي‌كند. بلكه SA به دنبال يك جواب خوب كه مي‌تواند بهينه هم باشد مي‌گردد. SA در حل بسياري از مسائل بخصوص مسائل Np-Complete كاربرد دارد. در پايان روش حل مسئله‌ي فروشنده‌ي دوره گرد در SA بطور مختصر آورده شده است.
فهرست مطالب
عنوان شماره صفحه
1- مقدمه 3
2. SA چيست؟ 5
3- مقايسه SA با تپه‌نوردي 8
4- معيار پذيرش (يك حركت) 9
5- رابطه‌ي بين SA و حرارت فيزيكي 11
6- اجراي SA 11
7- برنامه سرد كردن 12
1-7. درجه حرارت آغازين 13
2-7. درجه حرارت پاياني 14
3-7. كاهش درجه حرارت در هر مرحله 14
4-7. تكرار در هر دما 14
8- تابع هزينه 14
9- همسايگي 15
10- روش حل TSP با SA 15
11- نتيجهگيري 19
منابع 20
1- مقدمه
سيستم‌هاي پيچيده اجتماعي تعداد زيادي از مسائل داراي طبيعت تركيباتي را پيش روي ما قرار مي‌دهند. مسير كاميون‌هاي حمل و نقل بايد تعيين شود، انبارها يا نقاط فروش محصولات بايد جايابي شوند، شبكه‌هاي ارتباطي بايد طراحي شوند، كانتينرها بايد بارگيري شوند، رابط‌هاي
راديويي مي‌بايست داراي فركانس مناسب باشند، مواد اوليه چوب، فلز، شيشه و چرم بايد به اندازه‌هاي لازم بريده شوند؛ از اين دست مسائل بي‌شمارند. تئوري پيچيدگي به ما مي‌گويد كه مسائل تركيباتي اغلب پلي‌نوميال نيستند. اين مسائل در اندازه‌هاي كاربردي و عملي خود به قدري بزرگ هستند كه نمي‌توان جواب بهينه آنها را در مدت زمان قابل پذيرش به دست آورد. با اين وجود، اين مسائل بايد حل شوند و بنابراين چاره‌اي نيست كه به جواب‌هاي زير بهينه بسنده نمود به
گونه‌اي كه داراي كيفيت قابل پذيرش بوده و در مدت زمان قابل پذيرش به دست آيند.
چندين رويكرد براي طراحي جواب‌هاي با كيفيت قابل پذيرش تحت محدوديت زماني قابل پذيرش پيشنهاد شده است. الگوريتم‌هايي هستند كه مي‌توانند يافتن جواب‌هاي خوب در فاصله مشخصي از جواب بهينه را تضمين كنند كه به آنها الگوريتم‌هاي تقريبي مي‌گويند. الگوريتم‌هاي ديگري نيز هستند كه تضمين مي‌دهند با احتمال بالا جواب نزديك بهينه توليد كنند كه به آنها الگوريتم‌هاي
احتمالي گفته مي‌شود. جداي از اين دو دسته، مي‌توان الگوريتم‌هايي را پذيرفت كه هيچ تضميني در ارائه جواب ندارند اما براساس شواهد و سوابق نتايج آنها، به طور متوسط بهترين تقابل كيفيت و زمان حل براي مسئله مورد بررسي را به همراه داشته‌اند. به اين الگوريتم‌ها، الگوريتم‌هاي هيوريستيك گفته مي‌شود.
هيوريستيك‌ها عبارتند از معيارها، روش‌ها يا اصولي براي تصميم‌گيري بين چند گزينه خط‌مشي و انتخاب اثربخش‌ترين براي دستيابي به اهداف مورد نظر. هيوريستيك‌ها نتيجه برقراري اعتدال بين دو نياز هستند: نياز به ساخت معيار‌هاي ساده و در همان زمان توانايي تمايز درست بين انتخاب‌هاي خوب و بد. براي بهبود اين الگوريتم‌ها از اواسط دهه هفتاد، موج تازه‌اي از رويكردها آغاز گرديد. اين
رويكردها شامل الگوريتم‌هايي است كه صريحاً يا به صورت ضمني تقابل بين ايجاد تنوع جستجو (وقتي علائمي وجود دارد كه جستجو به سمت مناطق بد فضاي جستجو مي‌رود) و تشديد جستجو (با اين هدف كه بهترين جواب در منطقه مورد بررسي را پيدا كند) را مديريت مي‌كنند. اين الگوريتم‌ها متاهيوريستيك ناميده مي‌شوند. از بين اين الگوريتم‌ها مي‌توان به موارد زير اشاره كرد:
بازپخت شبيه‌سازي شده
جستجوي ممنوع
الگوريتم‌هاي ژنتيك
شبكه‌هاي عصبي مصنوعي
بهينه‌سازي مورچه‌اي يا الگوريتم‌هاي مورچه
در اين تحقيق ما به بررسي بازپخت شبيه‌سازي شده (شبيه‌سازي حرارتي) مي‌پردازيم.
2. SA چيست؟
SA مخفف Simulated Annealing به معناي شبيه‌سازي گداخت يا شبيه‌سازي حرارتي مي‌باشد كه براي آن از عبارات شبيه‌سازي بازپخت فلزات، شبيه‌سازي آب دادن فولاد و الگوريتم تبريد نيز استفاده شده است. برخي مسائل بهينه‌سازي صنعتي در ابعاد واقعي غالباً پيچيده و بزرگ مي‌باشند. بنابراين روشهاي حل سنتي و استاندارد، كارايي لازم را نداشته و عموماً مستلزم صرف زمان‌هاي محاسباتي طولاني هستند. خوشبختانه، با پيشرفت فن‌آوري كامپيوتر و ارتقا قابليت‌هاي محاسباتي، امروزه استفاده از روشهاي ابتكاري و جستجوگرهاي هوشمند كاملاً متداول گرديده است. يكي از اين روش‌ها SA است. SA شباهت دارد با حرارت دادن جامدات. اين ايده ابتدا توسط شخصي كه در صنعت نشر فعاليت داشت به نام متروپليس در سال 1953 بيان شد.[10] وي
تشبيه كرد كاغذ را به ماده‌اي كه از سرد كردن مواد بعد از حرارت دادن آنها بدست مي‌آيد. اگر يك جامد را حرارت دهيم و دماي آن را به نقطه ذوب برسانيم سپس آن را سرد كنيم جزئيات ساختماني آن به روش و نحوه سرد كردن آن وابسته مي‌شود. اگر آن جامد را به آرامي سرد كنيم كريستال‌هاي بزرگي خواهيم داشت كه مي‌توانند آن طور كه ما مي‌خواهيم فرم بگيرند ولي اگر سريع سرد كنيم آنچه كه مي‌خواهيم بدست نمي‌آيد.
الگوريتم متروپليس شبيه‌سازي شده بود از فرآيند سرد شدن مواد به وسيله كاهش آهسته دماي سيستم (ماده) تا زماني كه به يك حالت ثابت منجمد تبديل شود. اين روش با ايجاد و ارزيابي جواب‌هاي متوالي به صورت گام به گام به سمت جواب بهينه حركت مي‌كند. براي حركت، يك همسايگي جديد به صورت تصادفي ايجاد و ارزيابي مي‌شود. در اين روش به بررسي نقاط نزديك نقطه داده شده در فضاي جستجو مي‌پردازيم. در صورتي كه نقطه جديد، نقطه بهتري باشد (تابع
هزينه را كاهش دهد) به عنوان نقطه جديد در فضاي جستجو انتخاب مي‌شود و اگر بدتر باشد (تابع هزينه را افزايش دهد) براساس يك تابع احتمالي باز هم انتخاب مي‌شود. به عبارت ساده‌تر، براي كمينه سازي تابع هزينه، جستجو هميشه در جهت كمتر شدن مقدار تابع هزينه صورت مي‌گيرد، اما اين امكان وجود دارد كه گاه حركت در جهت افزايش تابع هزينه باشد. معمولاً براي پذيرفتن نقطه بعدي از معياري به نام معيار متروپليس استفاده مي شود:
P:احتمال پذيرش نقطه بعدي
C: يك پارامتر كنترلي
تغيير هزينه
پارامتر كنترل در شبيه‌سازي آب دادن فولاد، همان نقش دما را در پديده فيزيكي ايفا مي‌كند. ابتدا ذره (كه نمايش دهنده نقطه فعلي در فضاي جستجو است) با مقدار انرژي بسيار زيادي (كه نشان دهنده مقدار بالاي پارامتر كنترلي C است) نشان داده شده است. اين انرژي زياد به ذره اجازه فرار
از يك كمينه محلي را مي‌دهد. همچنانكه جستجو ادامه مي‌يابد، انرژي ذره كاهش مي‌يابد (C كم مي‌شود) و در نهايت جستجو به كمينه كلي ميل خواهد نمود. البته بايد توجه داشت كه در دماي پايين امكان فرار الگوريتم از كمينه محلي كاهش مي‌يابد، به همين دليل هر چه انرژي آغازين بالاتر، امكان رسيدن به كمينه كلي هم بيشتر است .[10]
روش بهينه سازي SA به اين ترتيب است كه با شروع از يك جواب اوليه تصادفي براي متغيرهاي تصميم‌گيري، جواب جديد در مجاورت جواب قبلي با استفاده از يك ساختار همسايگي مناسب به طور تصادفي توليد مي‌شود. بنابراين يكي از مسائل مهم در SA روش تولبد همسايگي است. براي پياده سازي الگوريتم شبيه سازي حرارتي به سه عامل اساسي به شرح زير نيازمنديم :
1. نقطه شروع:
نقطه‌اي در فضاي جستجو است كه جستجو را از آنجا آغاز مي‌كنيم. اين نقطه معمولاً به صورت تصادفي انتخاب مي شود .
2. مولد حركت:
اين مولد وظيفه توليد حالات بعدي را بعهده دارد و با توجه به محاسبه هزينه نقطه فعلي و هزينه نقطه بعدي، وضعيت حركت الگوريتم را مشخص مي‌كند .
3. برنامه سرد كردن :
پارامترهايي كه نحوه سرد كردن الگوريتم را مشخص مي‌كنند. بدين ترتيب كه دما چند وقت به چند وقت و به چه ميزان كاهش يابد و دماهاي شروع و پايان چقدر باشند. در سال 1982 كرك پاتريك ايده متروپليس را براي حل مسائل به كار برد. در سال 1983 كرك پاتريك و تعدادي از همكارانش از SA براي حل مسئله فروشنده دوره‌گرد يا TSP استفاده كردند.
TSP يكي از مسائل پايه در روشهاي بهينه‌سازي است و عبارت است از كمينه‌سازي مسافتي كه يك فروشنده دوره‌گرد ، ضمن مسافرت به تعداد معيني شهر بايد طي كند. ديدار از هر شهر بايد دقيقاً يك بار صورت پذيرد و او بايد به شهري كه مبداء حركتش است باز گردد. نتايج شبيه سازي حاكي از موفقيت روش ارائه شده توسط كرك پاتريك در حل TSP بود. از آن پس، شبيه سازي
حرارتي در مسائل بهينه‌سازي گوناگوني به كار رفت و نتايج بسيار موفقيت آميزي كسب كرد.[8]
روش بهينه‌سازي SA يك روش عددي با ساختار تصادفي هوشمند است. قابليت انعطاف در كوچك گرفتن طول گام‌هاي تصادفي در الگوريتمSA مانع از بروز هرگونه ناپايداري و ناهمگرايي در تركيب با مدل مي‌شود. علاوه بر آن توانايي SA در خروج از بهينه‌هاي محلي و همگرايي به سوي بهينه‌ي سراسري از جنبه‌ي نظري و در كاربردهاي عملي به اثبات رسيده است. به طور مثال روش SA در بهينه‌سازي بهره‌برداري كانال‌هاي آبياري در كشاورزي از الگوريتم ژنتيك مدل بهينه‌تري را مي‌دهد
. بهينه‌سازي توابع غيرصريح و مسائل Non-Complete با روشهاي كلاسيك بهينه‌سازي دشوار و گاهي غيرممكن است و بايستي از روشهاي عددي بهينه‌سازي استفاده كرد. براي حل مسئله به روش SA ابتدا مدل‌سازي رياضي صورت مي‌گيرد.
SA در خيلي از كتاب‌ها (انگليسي) شرح داده شده است. اگر شما مي‌خواهيد به دنبال راحت‌ترين تعريف باشيد، به شما توصيه مي‌كنيم كتاب (Dowsland, 1995) اين كتاب نه تنها بسيار خوب SA را شرح داده بلكه حاوي مراجع معتبر بسياري براي علاقه‌مندان مي‌باشد.[5]
3- مقايسه SA با تپه‌نوردي :
در هوش مصنوعي خوانديم كه در الگوريتم تپه‌نوردي براي حل مسائل MAX يا MIN محلي را بدست مي‌آوريم. ما تلاش مي‌كنيم در الگوريتم تپه‌نوردي استفاده كنيم از نقاط شروع متفاوت و مي‌توانيم با افزودن اندازه‌ي همسايگي فضاي حركت بيشتري براي جستجو داشته باشيم. در تپه‌نوردي اگر MAX يا MIN محلي را بدست آوريم شايد MAX يا MIN كلي را بدست نياوريم. SA اين مشكل را
حل مي‌كند. در SA ما به برخي حركت‌هاي بد براي فرار از MAX يا MIN محلي اجازه مي‌دهيم. در اين الگوريتم (SA) بجاي شروع دوباره بطور تصادفي زماني كه مثلاً در يك Max محلي گير افتاده‌ايم، مي‌توانيم اجازه دهيم كه جستجو چند قدم به طرف پايين بردارد، تا از MAX محلي فرار كند.
برخلاف تپه‌نوردي، SA بصورت Random حركت به همسايگي را انتخاب مي‌كند. (به ياد آوريد كه نپه‌نوردي بهترين حركت را كه در دسترس است، وقتي در يك سراشيبي نزول يا صعود مي‌كند
، انتخاب مي‌كند.) در واقع SA ، تپه نوردي بهبود يافته است. اگر بهترين حركت را نسبت به موقعيت جاري انجام دهيد، SA همواره مورد قبول خواهد بود. اگر اشتباه حركت كنيد (حركت بد) احتمالاً آن حركت مي‌تواند مورد قبول واقع شود. راجع به اين مبحث بيشتر توضيح خواهيم داد.
4- معيار پذيرش (يك حركت)
در الگوريتم‌هاي بهينه‌سازي محلي، جواب جديد تنها در صورت بهبود تابع هدف پذيرفته مي‌شود.
