Artificial Intelligence - هوش مصنوعی  
انجمن را در گوگل محبوب کنيد :

بازگشت   Artificial Intelligence - هوش مصنوعی > محاسبات نرم > الگوریتم شبیه سازی تبرید يا باز پخت (Simulated Annealing)


 
تبليغات سايت
Iranian Association for the Advancement of Artificial Intelligence
ارسال تاپيک جديد  پاسخ
 
LinkBack ابزارهاي تاپيک نحوه نمايش
قديمي ۰۷-۷-۱۳۸۹, ۰۹:۰۱ بعد از ظهر   #1 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Wink روش شبیه سازی تبريد تدریجی ( simulated Annealing )

روش شبیه سازی تبريد تدریجی ( simulated Annealing )


• SA یک روش جستجوی تصادفی قوی است که به منظور یافتن یک جواب خوب ( نه لزوما بهینه ) برای مسائل مشکل ترکیباتی combinatorial به کار می رود .

SA از فرايند فيزيكي خنك سازي مواد مذاب به حالت جامد الهام گرفته است.
• این روش برخلاف روش های جستجوی معمولی، در هر تکرار علاوه بر حرکت به سوی جواب بهتر، جواب های با مقدار تابع هدف بهتر را نیز با احتمال غیر صفری قبول می کند.

فرایند آنیل کردن فلزات :


• اگر ماده های جامد مذاب بسیار آهسته تبرید شوند ( تا حالت جامد ) اتم های آنها به صورت منظم در شبکه بلوری قرار گرفته و ماده جامد حاصل دارای حداقل سطح انرژی خواهد بود . به این روش تبرید آهسته آنیل کردن گویند.
• در شرایط تعادلی ( تبرید تدریجی ) برای هر دمای داده شده ، احتمال این که ذرات ماده دارای سطح انرژی خاصی باشند ، طبق تابع توزیع بولتز من محاسبه می گردد .




• این احتمال در ابتدا بزرگ است و ضمن اجرای روش متناسب با پارامتر مثبتی به نام دما
( Temprature ) کاهش پیدا می کند. در نتیجه روش SA از نظر تئوری با غلبه بر بهینگی محلی، قادر به یافتن جواب بهینه مطلق نیز خواهد بود.

• حال یک مساله عمومی مینیمم سازی را در نظر بگیرید. ایده اصلی در روش SA تولید جواب در همسایگی جواب فعلی و محاسبه موثر تغییر در مقدار تابع هدف، Δf می باشد. سپس ضمن ذخیره بهترین جواب به دست آمده اگر 0≥Δf باشد، جواب جدید قطعا پذیرفته می شود. در غیر این صورت اگر Δf>0 باشد، جواب جدید با احتمال پذیرفته می شود.
• T دمای سیستم که درجه تصادفی بودن حرکت به سوی جواب را تعیین می کند، مطابق با یک برنامه معین با پیشرفت روش حل، کاسته می شود.
• در واقع دمای سیستم مشخص کننده زیر فضای جواب مساله است که در هر تکرار مورد قبول قرار می گیرد.
• در دمای بالا تقریبا تمام جواب های تولید شده صرف نظر از مقدار تابع هدف پذیرفته می شوند. با پیشرفت الگوریتم و کاهش دما، جواب های نامناسب شانس کمتری برای پذیرفته شدن دارند. در واقع، در هر دما، احتمال پذیرفتن جواب با مقدار تابع هدف بیشتر، بستگی به اندازه افزایش Δf دارد.
• به منظور کاربرد SA برای هر مساله بهینه سازی باید دو دسته از پارامترها تعیین گردند. دسته اول پارامترهای مربوط به کنترل دما و تعداد جواب هایی که باید تولید شوند و دسته دوم مربوط به ویژگی های خاص مساله مورد نظر می باشد.

پارامترهای SA :

• نقطه شروع : یک جواب قابل قبول که معمولا به صورت تصادفی ایجاد میشود .
• نقطه شروع بر سرعت همگرایی الگوریتم تا حدی موثر است .
• برای گسترش فضای جستجو و گریز از بهینه های محلی ، معمولا الگوریتم از چندین نقطه شروع مختلف اجرا می شود .
• دمای اولیه (c0 ) : مقدار دمای اولیه تابع توزیع بولتز من می باسیت به گونه ای ساخته باشد تا مقدار تابع نزدیک به یک باشد .



• معمولا در اکثر کاربردها مقادیر0.85 – 0.95 مطلوب است .
• مقادیر بسیار بزرگ C0 ( به همراه نرخ سرمایش آهسته ) موجب طولانی شدن مدت اجرا و گسترش فضای جستجو می شود .
• مقادیر بسیار کوچک C0 ممکن است موجب همگرایی زود هنگام شده الگوریتم در بهینه محلی متوقف شود .
• انتخاب پارامترهای عمومی به مساله بهینه سازی و موارد خاص مورد نظر بستگی دارد.
• دمای اولیه بايد به طریقی تعیین گردد که احتمال قبول و رد جواب ها برای حالت Δf>0 در تکرار اول روش برابر باشد.
• استراتژی خنک کردن سیستم، چگونگی کاهش دما را در حین تکرارهای روش تعیین می کند. کیفیت جواب SA به میزان زیادی بستگی به تعداد جواب هایی دارد که در هر دما مورد بررسی قرار می گیرند.
• بنابراین مقدار این پارامترهم بستگی به ابعاد مساله دارد و با چندبار اجرای آزمایشی روش برای مقادیر مختلف تعیین می شود.
• تصمیمات اختصاصی شامل اين است كه در هر تکرار روش SA بایستی تعداد زیادی جواب تولید شوند تا یک تعادل حرارتی در هر دما برقرار گردد.
• اگرچه SA ضمن سادگی ابزاری قوی برای حل مسائل بهینه سازی ترکیباتي می باشد ولی دقت زیادی در انتخاب نحوه تولید موثر جواب ها، زمان بندی خنک کردن و کفایت تعداد جواب های تولید شده لازم است. با این وجود زمینه هایی نیز برای بهبود روش وجود دارد.
• همگرایی به یک راه حل بهینه در SA بعد از تعداد نامحدود تکرار ها به وسیله برنامه خنک سازی کنترل می شود. پارامتر کنترل اصلی در برنامه خنک سازی پارامتر دما T می باشد.
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
34191207359 (۰۲-۲۸-۱۳۹۳), aa66 (۱۰-۱۳-۱۳۹۲), arashmob (۰۳-۲۲-۱۳۹۳), aref_e_sheida (۰۵-۳۰-۱۳۹۰), bluestorm (۱۲-۲۰-۱۳۸۹), damaghderaz (۰۳-۶-۱۳۹۰), m.sanam (۰۳-۹-۱۳۹۳), morteza795 (۱۰-۲۴-۱۳۹۱), ParisaAmraie (۰۲-۱-۱۳۹۳), setare.azar (۰۱-۲۸-۱۳۹۱), vahidby28 (۰۱-۱۹-۱۳۹۲)

  #ADS
نشان دهنده تبلیغات
تبليغگر
 
 
 
تاريخ عضويت: -
محل سكونت: -
سن: 2010
پست ها: -
 

نشان دهنده تبلیغات is online  
قديمي ۰۷-۷-۱۳۸۹, ۰۹:۰۲ بعد از ظهر   #2 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Wink

مراحل الگوریتم SA استاندارد:


الگوریتم :
• آغاز و آماده سازی : ورود اطلاعات مساله و تنطیم پارامترهای الگوریتم ( دمای اولیه ، نرخ سرمایش ، شرط توقف جواب اولیه تصادفی و موجه ، ......)
• 1 ) تشکیل یک جواب در همسایگی جواب فعلی
• 2 ) ارزیابی جواب همسایگی :
• 1-2 ) همسایه از جواب فعلی بهتر است : حرکت به جواب جدید
• 2-2 ) تابع احتمال از عدد تصادفی یکنواخت بزرگتر است : حرکت به جواب جدید
• در غیر این صورت بازگشت به گام 1
• 3 ) به روز رسانی پارامترهای الگوریتم و مساله
• بهترین جواب را حفظ کنیم چون لزوما همیشه بهترین نیست .
• و حرکت به گام 1

فلو چارت :

تابع سرمایش :

• سرعت همگرایی الگوریتم ، وابسته به تابع سرمایش است
• ( برنا مه کاهش دما Cooling Schedul )
• مقدار دما ( بر حسب تعداد تکرارها ) در هر تکرار طبق تابع سرمایش می بایست کاهش یابد
• تعیین تابع و نرخ سرمایش وابسته به بزرگی و ساختار مساله است و توابع متعددی برای آن پیشنهاد شده است .


• نرخ سرمایش بسیار بزرگ ، باعث همگرایی زود هنگام و حبس در بهینه محلی می شود .
• نرخ سرمایش کوچک ، زمان محاسباتی را افزایش می دهد .
• نرخ بهینه و دمای اولیه، مهم ترین پارامترهای الگوریتم هستند .
• میزان کاهش دما در روش SA بسیار مهم است . برای کاهش دادن دما ، دمای فعلی را به ضریب α ضرب می کنیم . توجه کنید که α مقدار بین 0 و 1 است.
در الگوریتم SA دما به تدریج و بسیار آهسته کم می شود ، پس مقدار α باید به 1 نزدیک باشد . کاهش دادن سریع دما باعث خواهد شد تا در مینیمم محلی گیر کنیم .

موارد کاربرد:

• یک simulated annealing قوي ابتكاري براي مسائل زمانبندي فلوشاپ

طرح زمان بندي داروي سرطان با استفاده از Simulated Annealing

• براي طرح ريزي شيمي درماني هاي با چرخه خاص(cycle specific)
• ، يك متدولوژي با استفاده از Simulated Annealingپيشنهاد مي شود. اين روش متكي به مدل معادله هاي ديفرانسيلي تأخيري مي باشد كه چرخه سلولي را مورد توجه قرارمي دهد و يك زمان بندي دارويي را در طول زمان به صورت يكپارچه در مي آورد.
• هدف، رسيدن به يك روش زمان بندي مناسب براي دارو است به گونه اي كه سطح تومور كاهش پيدا كند و سيستم ايمني ، بالاي يك آستانة معين نگه داشته شود. براي تعيين يك چنين استراتژي، يك مسأله كنترل بهينه تنظيم شده است كه راه حل هاي نقطه به نقطه(bang- bang) را مجاز مي نمايد.
• حل كردن مسائل كنترل مجزا به صورت تحليلي يا عددي بسيار مشكل است ، بنابراين ما به روش هاي مكاشفه اي متوسل مي شويم؛ بويژه ما در اينجا الگوريتم Simulated Annealing را مورد بررسي قرار مي دهيم.
• الگوريتم به گونه اي موفقيت آميز مسأله كنترل بهينه مطرح شده را حل مي كند و زمان بندي هاي دارويي مناسب براي اجرا ايجاد مي نمايد.

خلاصه :

• روش جستجوگر " تبريد تدريجي" SA يک جستجوگر همسايگي است که در بهينه‌سازي مسائل گسسته بطور گسترده‌اي کاربرد دارد.
• طبيعت تصميم‌گيري اين الگوريتم به اين صورت است که براي هر حرکت، يک همسايگي جديد بصورت تصادفي توليد و ارزيابي مي‌شود. حرکت به اين جواب در هر يک از دو وضعيت زير انجام خواهد يافت: 1) جواب جديد از جواب فعلي بهتر باشد و 2) مقدار تابع احتمال حرکت[i] از يک عدد تصادفي از دامنه [0,1) بزرگتر باشد.
• در غير اين صورت جستجوگر جواب جديدي را توليد و ارزيابي خواهد نمود. اين حرکت گام ‌به‌گام تا ارضاء شرط توقف الگوريتم (تعداد تکرارها، زمان محاسبات، و .... ) ادامه مي‌يابد.
• مقدار تابع احتمال حرکت در هر بار از رابطه محاسبه مي‌شود. در اين رابطه اختلاف مقدار تابع هدف بين جواب فعلي و جواب جديد است.


مقاله ای از : محبوبه ستایش
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
34191207359 (۰۲-۲۸-۱۳۹۳), aa66 (۱۰-۱۳-۱۳۹۲), bluestorm (۱۲-۲۰-۱۳۸۹), setare.azar (۰۱-۲۸-۱۳۹۱), taherir47 (۰۸-۲۳-۱۳۸۹), vahidby28 (۰۱-۱۹-۱۳۹۲)
قديمي ۰۹-۱۱-۱۳۹۲, ۱۲:۲۰ بعد از ظهر   #3 (لینک دائم)
عضو جدید
 
آواتار mousavi98
 
تاريخ عضويت: آذر ۱۳۹۲
پست ها: 5
تشكرها: 0
0 تشكر در 0 پست
پيش فرض

سلام لطف کنید در مورد الگوریت آنیلینگ مطلب دارید برام بفرستید مرسی
mousavi98 آفلاين است   پاسخ با نقل قول
قديمي ۰۹-۹-۱۳۹۳, ۰۸:۵۱ بعد از ظهر   #4 (لینک دائم)
عضو جدید
 
آواتار mahdieh1
 
تاريخ عضويت: بهمن ۱۳۹۱
پست ها: 5
تشكرها: 0
0 تشكر در 0 پست
پيش فرض

سلام
کد الگوریتم saرا در متلب میخواستم اگه کسی داره لطف کنه بذاره
mahdieh1 آفلاين است   پاسخ با نقل قول
قديمي ۰۹-۹-۱۳۹۳, ۱۰:۰۶ بعد از ظهر   #5 (لینک دائم)
عضو جدید
 
آواتار vahidtt
 
تاريخ عضويت: آذر ۱۳۹۳
پست ها: 1
تشكرها: 0
0 تشكر در 0 پست
پيش فرض

دانلود کد الگوریتم شبیه سازی تبرید برای مسأله فروشنده دوره گرد | متلب سایت
vahidtt آفلاين است   پاسخ با نقل قول
قديمي ۰۵-۲۸-۱۳۹۰, ۱۰:۰۹ بعد از ظهر   #6 (لینک دائم)
عضو جدید
 
آواتار aref_m
 
تاريخ عضويت: مرداد ۱۳۹۰
پست ها: 1
تشكرها: 0
0 تشكر در 0 پست
پيش فرض

با تشکر از شما

منظور از تکرار در هر دما چیست؟
کاربرد این الگوریتم در زمان بندی ماشین (flowshop scheduling) می خواستم البته مقاله نباشه یک جزوه فارسی آموزشی اگر باشه خیلی خوبه چون نحوه بیانش آموزشی نیست

مرسی
aref_m آفلاين است   پاسخ با نقل قول
قديمي ۰۳-۳۰-۱۳۹۲, ۰۷:۰۰ بعد از ظهر   #7 (لینک دائم)
عضو جدید
 
آواتار trazi
 
تاريخ عضويت: ارديبهشت ۱۳۹۲
پست ها: 2
تشكرها: 1
0 تشكر در 0 پست
پيش فرض

میشه مسئله کوله پشتی رو با این اگوریتم توی متلب حل کنید
trazi آفلاين است   پاسخ با نقل قول
قديمي ۰۷-۱۰-۱۳۹۴, ۰۲:۱۸ بعد از ظهر   #8 (لینک دائم)
عضو جدید
 
آواتار roya_asman
 
تاريخ عضويت: مهر ۱۳۹۴
پست ها: 3
تشكرها: 0
0 تشكر در 0 پست
پيش فرض

سلام لطفا منبع این راهنمایی های پرکاربرد رو هم ذکر بفرمایین
roya_asman آفلاين است   پاسخ با نقل قول
پاسخ



كاربران در حال ديدن تاپيک: 1 (0 عضو و 1 مهمان)
 
ابزارهاي تاپيک
نحوه نمايش

قوانين ارسال
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is فعال
شکلکها فعال است
كد [IMG] فعال است
كدهاي HTML غير فعال است
Trackbacks are فعال
Pingbacks are فعال
Refbacks are فعال




زمان محلي شما با تنظيم GMT +3.5 هم اکنون ۰۱:۰۲ بعد از ظهر ميباشد.


Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.1.0 ©2007, Crawlability, Inc.

Teach and Learn at Hexib | Sponsored by www.Syavash.com and Product In Review

استفاده از مطالب انجمن در سایر سایت ها، تنها با ذکر انجمن هوش مصنوعي به عنوان منبع و لینک مستقیم به خود مطلب مجاز است

Inactive Reminders By Icora Web Design