پایان نامه درباره ، جسم، تبرید، انجماد، میگردد.، جوابها، بهینهسازی، ترمودینامیکی

کروموزومها جای دستهای از بدترین کروموزومها را میگیرند. با این عمل همگرایی به سمت عدد بهینه در اجرای الگوریتم سریعتر و زمان اجرای برنامه تا یافتن جواب مناسب کاهش مییابد.
2-1-2-12 تکرار تا زمان توقف
حال جمعیت جدیدی تولید شده است که میانگین برازندگی آن از نسل قبلی بهتر است. با این جمعیت، مجددا مراحل قبل را از گام چهارم تا یازدهم تکرار کرده و این اعمال را آنقدر انجام میدهیم تا به مقدار بهین دست پیدا کنیم.
2-2 روش شبیه سازی تبریدSA
مقایسه ساختار پیچیده پیکربندی فضای جواب مسائل بهینه سازی سخت، با بعضی از پدیدههای فیزیکی توسط کرک پاتریک و همکارانش در انجمن IBM ، منجر به ارائهی پیشنهاد یک روش جدید تکراری (تکنیک انجماد تدریجی (شبیه سازی تبرید)) که توانایی خروج از بهینه محلی را داشت، گردید. همچنین اثر مشابهی در همان زمان توسط کرنی در سال 1985 منتشر گردید. آنها از الگوریتم انجماد تدریجی (SA) برای افراز بندی گرافها استفاده نمودند. SA بهدلیل سادگی و همچنین کارایی بالا در حل مسائل بهینه سازی ترکیبی، جایگاه ویژهای در بین تکنیکهای جستجو و هیوریستیکها در دهه 1980 بهدست آورد. این تکنیک بعدها به حوزه مسائل بهینهسازی پیوسته نیز توسعه داده شد.
2-2-1: مقایسه با پدیدههای فیزیکیدر طبیعت فرایند تغییر شکل منظم را بهصورت خودبهخود، زمانیکه دمای یک سیستم بهتدریج کاهش مییابد، میتوان دید. آرایش مولکولی یک جسم داغ که در ابتدا ساختاری غیر منظم داشته و دارای فاصله زیادی از همدیگر است، زمانیکه دمای آن بهآرامی کاهش پیدا میکند، به یک ساختار منظم و نزدیک به هم تغییر شکل پیدا میکند.
به دو صورت میتوان جسم را سرد کرد. در حالت اول، جسم بهسرعت سرد میگردد که در اینحالت میزان آنتروپی (یا فاصله بین مولکولها) از همدیگر کاهش مییابد ولی بهمقدار حداقلی، نخواهد رسید. در حالت دوم، جسم بهآرامی سرد میشود و مولکولها این فرصت را پیدا میکنند که کلیه فضاهای خالی را پر کرده و آرایش منظمتری را ایجاد نمایند. در این حالت میزان آنتروپی به حداقل خود خواهد رسید.
بهمنظور تولید یک ساختار کریستالی، ابتدا جسم به اندازه کافی دما داده میشود و سپس آن جسم به آرامی سرد میگردد. در طول فرایند کاهش دما، پس از هر مرحله کاهش، مدتی جسم در آن دما باقی میماند. این مرحله به آرامی ادامه پیدا میکند تا جسم به پایینترین دما رسانده شود که منجر به ایجاد یک حالت کریستالی در جسم خواهد شد. در صورتیکه در مرحلهای کاهش دما بهتندی، صورت گیرد، حالت غیر بلوری ایجاد خواهد شد.
الگوریتم شبیه سازی تبرید که انجماد تدریجی نیز نامیده میشود، از پدیده انجماد فیزیکی فوق الگو گرفته شده است. در این الگوریتم شبیه به پدیده آنیلینگ، از یک پارامتر دما برای کنترل الگوریتم در طول بهبود جواب مساله استفاده میگردد. جدول زیر مقایسهای بین یک سیستم فیزیکی با مسائل و الگوریتم های بهینه سازی را نمایش میدهد.
جدول 2-7: مقایسه بین یک مساله و الگوریتم بهینه سازی با یک سیستم فیزیکی
سیستم فیزیکی مساله و الگوریتم بهینه سازی
وضعیت سیستم جواب
موقعیتهای مولکولی متغیرهای تصمیم
انرژی تابع هدف
وضعیت پایدار جواب بهینه سراسری
وضعیت نیمه پایدار بهینه محلی
سرد کردن سریع جستجوی محلی
دما پارامتر کنترل
آنیلینگ با دقت شبیه سازی تبرید
2-2-2- روش کار الگوریتم شبیه سازی تبریدفرض کنید فضای جواب s یک مجموعه متناهی از تمام جوابها و f مقدار تابع هدف، برای هر یک از عناصر باشد. هدف، پیدا کردن یک جواب یا حالتی مانند iєs است بهطوریکه f(i) روی s کمینه باشد. تبرید شبیه سازی شده، شکلی از روشهای سنتی کاهشی برای بهینه سازی محلی یا جستجوی همسایگی است. الگوریتم کاهش با یک جواب اولیه شروع میکند و از بین همسایگیهای این جواب، آن را که جواب حاضر را بهبود دهد انتخاب میکند و این همسایگی جدید بهجای جواب اولیه قرار میگیرد. این فرآیند ادامه مییابد تا اینکه دیگر هیچ یک از همسایگیهای جواب جاری نتواند مقدار تابع هدف را بهبود بخشد. در این حالت جواب جاری یک بهینه محلی است.
یکی از راههایی که میتوان برای بهبود این روش استفاده کرد این است که الگوریتم را چندین  بار با جوابهای اولیه مختلف اجرا کنیم و در نهایت بهینه محلی را انتخاب کنیم. شبیه سازی تبرید  بهجای استفاده ازاین استراتژی، سعی میکند در یک بهینه محلی قرار نگیرد و بنابراین برای این کار، بعضی اوقات جوابهایی که مقدار تابع هدف را افزایش داده میپذیرد. قبول یا رد این جواب به دنباله ای از اعداد تصادفی وابسته به یک کنترل احتمالی بستگی دارد. بهعلاوه اجتناب از جواب بهینه محلی، به برنامه آنیلینگ (گرم کردن و سپس به تدریج سرد کردن)، انتخاب دمای اولیه، تعداد تکرارهای لازم در هر دما و مقدار کاهش دما در هر مرحله بستگی دارد که درادامه به آنها اشاره خواهد شد.
در واقع این الگوریتم بر مبنای دو قاعده از فیزیک آماری عمل میکند:
قاعده اول بر این اساس است که وقتی تعادل ترمودینامیکی به یک دمای مشخص رسید، احتمال یک سیستم فیزیکی برای داشتن یک سطح انرژی E، با فاکتور بالتزمن، e-EkB T که در آن kB  توزیع بالتزمن در دمای مربوطه می باشد، متناسب است. بر اساس این قاعده احتمال پذیرش جوابها در دماهای مختلف متفاوت بوده و متناسب با تابع معرفی شده میباشد.
قاعده دوم نحوه رسیدن به تعادل ترمودینامیکی در یک دمای مشخص را بیان میکند. بر اساس آن، در یک دمای مشخص، با استفاده از الگوریتم متروپلیس تکامل یک سیستم فیزیکی در رسیدن به تعادل ترمودینامیکی در دمای مشخص شبیه سازی میگردد. بر اساس این قاعده، برای یک جواب یا پیکرهبندی مشخص یک سری محدود از حرکت یا تغییرات ابتدایی در نظر گرفته میشود. اگر یک تغییر شکل منجر به کاهش تابع هدف یا انرژی گردد، آن تغییر شکل پذیرفته میشود و درصورتیکه این تغییر شکل منجر به افزایش تابع هدف یا انرژی به اندازه E∆ گردد، تغییر شکل با احتمال e-∆ ET پذیرفته میشود. این پذیرش از طریق تولید یک عدد تصادفی با توزیع یکنواخت در فاصله بین ۰و۱ و مقایسه آن با تابع تعریف شده انجام میگردد. در صورتی که مقدار عدد بهدست آمده کوچکتر از تابع تعریف شده باشد، تغییر شکل پذیرفته میشود. هر جواب از روی جواب پذیرفته شده قبلی خود تولید میگردد و با تکرار تولید جوابها و پذیرش آنها با استفاده از قاعده متروپلیس، یک توالی از جوابها بهوجود میآید که زنجیره مارکف را بهوجود آوردهاند. پایان یافتن این زنجیره با طول محدود و کافی را میتوان به رسیدن یک سیستم فیزیکی به تعادل ترمودینامیکی در یک دمای مشخص تشبیه کرد.
قاعده متروپلیس بهصورت زیر عمل میکند: در دمای بالا و مراحل اولیهی الگوریتم، مقدار e-E T نزدیک به یک بوده و درنتیجه، اکثر حرکتها (تغییر شکلها) پذیرفته میشود و الگوریتم، رفتاری شبیه به یک جستجوی تصادفی را خواهد داشت. در دماهای پایین و اواخر الگوریتم، مقدار e-E T به صفر نزدیک شده و اکثر جوابهای بدتر ردشده و تنها جوابهای خوب پذیرفته میشوند. شانس جابهجایی یک جواب خوب با یک جواب بدتر، خروج الگوریتم از جواب بهینهی محلی را تضمین میکند و از طرفدیگر، کاهش احتمال پذیرش جواب بدتر با کاهش دما، موجب تضمین همگرایی SA است.
معمولا الگوریتم های بهبود دهنده، که با یک جواب اولیه شروع شده و در طی مراحلی بهبود داده میشوند، ممکن است بعد از چند تکرار در نقطه بهینه محلی قرار بگیرند، که گاهی اوقات نیز از ناحیه جواب نهایی خیلی دور است. فرق الگوریتم انجمادتدریجی با الگوریتم های بهینهسازی محلی در ایناست، که در الگوریتم بهینهسازی محلی، یک جواب در همسایگی جواب قبلی ایجاد میشود، اگر تابع هدف بهواسطه جواب جدید بهترشود، جواب جدید قبول شده و در غیراینصورت جواب جدید رد میگردد. این عمل ممکن است منجر به قرارگرفتن در نقطه بهینه محلی شده و دیگر نتواند از آن خارج شود. درحالیکه در روش تبرید شبیه سازی شده، از توقف در ناحیه بهینه محلی اجتناب کرده و بهطور گذرا از آن رد میشود. این حالت با پذیرفتن احتمالی جوابهای بد انجام میشود، تا از نقطه بهینه محلی خارج شود. این احتمال برابر است با ( e-∆fT ) که T میزان درجه حرارت و ∆f میزان تغییر در تابع هدف میباشد. اگراین احتمال از یک عدد تصادفی یکنواخت بین [ 0 ,1] ، بیشتر باشد، جواب نامناسب هم پذیرفته میشود.

2-2-3 : همگرایی الگوریتم انجماد تدریجیبسیاری از محققین همگرایی الگوریتم شبیه سازی تبرید را بررسی نمودهاند و بعضی از آنها بهدنبال ارائهی یک مدل کلی برای تحلیل روشهای تصادفی در یافتن بهینه سراسری از مسائل بهینهسازی بودهاند. دستاوردهای اصلی آنها عبارتند از: در شرایط اطمینان، احتمالا الگوریتم شبیهسازی تبرید به سمت بهینه سراسری همگرا خواهد بود و بهعبارت دیگر، الگوریتم شبیه سازی تبرید، امکان رسیدن به نقطهای نزدیک به

متن کامل در سایت homatez.com