مقاله شبیه‌سازی حرارتی در word

توضیحات

 مقاله شبیه‌سازی حرارتی در word دارای 25 صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است

فایل ورد مقاله شبیه‌سازی حرارتی در word  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل ورد می باشد و در فایل اصلی مقاله شبیه‌سازی حرارتی در word،به هیچ وجه بهم ریختگی وجود ندارد

بخشی از متن مقاله شبیه‌سازی حرارتی در word :

شبیه‌سازی حرارتی

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- معیار پذیرش (یك حركت)
در الگوریتم‌های بهینه‌سازی محلی، جواب جدید تنها در صورت بهبود تابع هدف پذیرفته می‌شود.

برای دریافت اینجا کلیک کنید