توزیع کننده
تولید کننده
۰
۱۰۰
۲۰۰
۰
۰
۰
۱۵۰
۰
۵۰۰
فرزند جدید
شکل ۳-۲۲ بخش اول عملگر جهش
پس از اجرای عملیات جهش دوباره مثل مرحله تقاطع ابتدا شدنی بودن فرزند تولید شده بررسی میشود . در صورت شدنی بودن ، فرزند مورد نظر را با تمام جواب های موجود در لبه آخر نسل قبل مقایسه می کنیم، در صورت بهتر بودن ، فرزند تولید شده به نسل بعد انتقال می یابد .
۳-۶-۳-۱۲٫نخبه گرایی :
روش کار بدین صورت است که درصدی (مثلا ۸ درصد) از بهترین جواب ها به نسل بعد منتقل میشوند .
۳-۶-۳-۱۳٫پیدا کردن همسایگی جواب ها با بهره گرفتن از الگوریتم شبیه سازی تبرید
۳-۶-۳-۳۱۱-. الگوریتم شبیه سازی تبرید[۹۸] (SA)
الگوریتم شبیه سازی تبرید یک الگوریتم جستجوی تصادفی بر مبنای مدل مونت کارلو است که به طور گسترده در عرصه های گوناگون مسایل بهینه سازی ترکیبی مورد استفاده قرار می گیرد. این الگوریتم، نخستین بار توسط کرک پاتریک و همکاران[۶۷] در ۱۹۸۳ به منظور یافتن جواب های نزدیک به بهینه مدل هایی که حل آنها با روش های معمول دشوار است، معرفی شد.
الگوریتم شبیه سازی تبرید بر اساس شباهت بین ساز و کار فرایند تبرید در فلزکاری و فرایند جستجوی جواب بهینه در مسایل بهینه سازی معرفی شده است. در فرایند فیزیکی تبرید، ابتدا جسم جامد به اندازه ای گرم می شود که اتم های آن بتوانند به شکل آزادانه و تصادفی در کنار هم قرار گیرند. سپس دما به تدریج کاهش می یابد تا اتم ها در موقعیت هایی با بیشترین پایداری و کمترین سطح انرژی مستقر شوند. این قیاس می تواند در مورد مسایل بهینه سازی ترکیبی به این صورت مطرح گردد که وضعیت جسم جامد معادل جوابی قابل قبول برای مسئله، انرژی جسم جامد در هر سطح معادل بهبود در تابع هدف و پایین ترینسطح انرژی بیانگر کمترین هزینه است. [۵۱]
( اینجا فقط تکه ای از متن پایان نامه درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )
این الگوریتم، برخلاف روش های جستجوی معمولی، در هر تکرار علاوه بر حرکت به سوی جواب بهتر، جواب های نامناسب را نیز به طور احتمالی می پذیرد و باعث گذر از بهینه های محلی جهت رسیدن به بهینه کل می شود. ایده اصلی در این الگوریتم، تولید جواب در همسایگی جواب فعلی و محاسبه تغییر در مقدار تابع هدف است. دمای سیستم که مشخص کننده فضای جواب مسئله است، بر اساس یک برنامه معین با پیشرفت روش حل، کاسته می شود. در دمای بالا تقریباً تمام جواب های تولید شده صرف نظر از مقدار تابع هدف پذیرفته می شوند اما با پیشرفت الگوریتم و کاهش دما، جواب های نامناسب شانس کمتری برای پذیرفته شدن دارند.
کاربرد آسان و راحت، ویژگی همگرایی و خاصیت واگرایی جهت عبور از بهینه های محلی از جمله دلایلی هستند که باعث شده اند الگوریتم شبیه سازی تبرید در سال های اخیر به طور موفق در حل بسیاری از مسایل زنجیره تأمین به کار برده شود[۱۲۶,۶۳, ۹ , ۱۲۸,۱۰].
گام های پیاده سازی الگوریتم شبیه سازی تبرید پیشنهادی به صورت زیر بیان می شوند:
مقدار دهی اولیه
اطلاعات ابتدایی مورد نیاز برای شروع الگوریتم شبیه سازی تبرید عبارتند از:
دمای اولیه
انتخاب دمای اولیه تأثیر زیادی در جواب نهایی مسئله دارد. چنانچه بخواهیم جواب نهایی مستقل از جواب شروع باشد، دمای اولیه باید به اندازه کافی زیاد در نظر گرفته شود تا امکان تعویض تقریباً آزاد جواب های همسایگی وجود داشته باشد و خطر قرارگیری در بهینه محلی از بین برود. از سوی دیگر، مقادیر بسیار بالای دما نیز موجب طولانی شدن مدت اجرای الگوریتم و گسترش فضای جستجو می شود. در صورتیکه اطلاعات کافی برای تخمین دمای اولیه وجود نداشته باشد، می توان با توجه به کمترین و بیشترین تغییرات تابع هدف، دمای شروع را تعیین نمود.
دمای نهایی
به طور معمول اجازه داده می شود تا دما کاهش یابد و به صفر برسد که این امر می تواند روند اجرای الگوریتم را بسیار طولانی کند. بنابراین، معیار توقف می تواند یک دمای پایین مناسب در نظر گرفته شود.
تعداد تکرارها در هر دما
کیفیت جواب الگوریتم شبیه سازی تبرید به میزان زیادی بستگی به تعداد جواب هایی دارد که در هر دما مورد بررسی قرار می گیرند. تعداد تکرارها در هر دما معمولاً به ابعاد مسئله بستگی دارد و ممکن است برای دماهای مختلف متفاوت باشد.
نرخ کاهش دما
یکی از موارد مهم در ارتباط با الگوریتم شبیه سازی تبرید، نحوه تغییر درجه حرارت در طول اجرای الگوریتم است. پرکاربردترین روش زمان بندی سرد شدن توسط کرک پاتریک و همکاران [۶۷] مطرح گردیده است. در این روش، چنانچه مقدار بالایی داشته باشد، سرعت کاهش دما کمتر بوده و امکان جستجوی بیشتر فضای جواب مسئله وجود خواهد داشت.
۲۰ – ۳
در روش دیگر زمان بندی نیز که برای نخستین بار توسط لاندی و میس [۸۰] معرفی شد، در هر دما تنها یک تکرار انجام می شود اما دما به آهستگی و طبق رابطه زیر کاهش می یابد.
۲۱ – ۳
نحوه نمایش جواب
