حل مسأله زمان‌بندی جریان‌کارگاهی با فرض عدم‌توقف‌ به روش ابتکاری- قسمت 24

حل مسأله زمان‌بندی جریان‌کارگاهی با فرض عدم‌توقف‌ به روش ابتکاری- قسمت 24

شبه کد[52] الگوریتم مورچگان به کار رفته به شکل زیر می‌باشد.
Set parameters, initialize pheromone
for t=1 to [iteration number] do
for to [ant-no.] do
Repeat
Select item j fromwith probability
Until ant k make feasible solution
Calculate : the Object value of generated feasible loop
If then
Apply Local pheromone update
end{forr}
Apply Local search
Calculate
If then
If then
Apply Global pheromone update
end{forr}
Find the best solution value ().
شکل ‏4‑1: شبه کد الگوریتم مورچگان اولیه
در این پایان نامه در جهت بهبود هر چی بیشتر جواب‌ها، تغییراتی در الگوریتم ارائه شده که در ادامه به مرور این تغییرات می‌پردازیم.
ابتدا برای افزایش کیفیت جواب‌ها به جای الگوریتم جستجوی محلی از الگوریتم شبیه سازی تبرید استفاده شد که این الگوریتم باعث افزایش کارایی الگوریتم مورچگان شد، و در ادامه با روند الگوریتم شبیه‌سازی تبرید بکار رفته آشنا می‌شویم. سپس الگوریتم اصلاح شده‌ی استفاده شده در این پایان نامه را مورد بررسی قرار می‌دهیم. الگوریتم‌های پیشین دارای کارایی کافی در مسائل با تعداد کار بالا نبودند که الگوریتم اصلاح‌شده با توجه به رویکرد جدید در جستجوی محلی باعث رفع این نقیصه در الگوریتم‌های قبلی شده است.
الگوریتم شبیه‌سازی تبرید
الگوریتم شبیه‌سازی تبرید که در اوایل دهه 1980 به وسیله کیرکپاتریک و همکاران [81] ارائه شد، برگرفته از فرآیند سردکردن فلزات جهت رسیدن به تعادل ترمودینامیکی می‌باشد. این روش، فرآیند سرد کردن فلزات و مواد را شبیه‌سازی می‌کند. طی فرآیند شبیه‌سازی سرد کردن فلزات، یک ماده تا دمایی بیشتر از دمای ذوبش گرم شده و سپس بتدریج دمای آن پایین آورده می‌شود. نحوه‌ی کاهش دما بسیار کند و در حدی است که ماده در تعادل ترمودینامیکی نگه داشته می‌شود. اجسامی که ساختار بلوری‌شان در انرژی‌های بالاتر شکل گرفته باشد، شکننده‌تر نیز هستند. در شبیه‌سازی تبرید، جواب‌های پیشنهادی برای مسئله در دمای بالاتر قرار دارند و اغلب جواب‌های مناسبی نیستند. این نامناسب بودن را می‌توان به شکنندگی تشبیه نمود. سپس متغیری که نقش دما را بر عهده دارد به مرور زمان کاهش داده می‌شود تا به این ترتیب جواب‌های بهتری در دماهای پایین تشکیل شوند.
در این روش، هر چه قدر روند کاهش دما کندتر باشد جواب‌هایی که الگوریتم پیدا می‌کند دقیق‌تر خواهد بود. ثابت شده که اگر فرآیند کاهش دما به حد کافی کند باشد، جواب‌های بهینه به طور حتم پیدا خواهد شد. به عبارت دیگر هر چه قدر فرآیند شبیه‌سازی سردکردن فلزات گسترده‌تر باشد، احتمال آنکه الگوریتم به جواب بهینه سراسری برسد، به یک میل می‌کند. اما این نتیجه نظری و قضیه‌ای که در مورد آن به اثبات رسیده است از نظر عملی کاربرد چندانی ندارد. زیرا زمانی که برای پدیده‌ی شبیه‌سازی سردکردن فلزات مورد نیاز است اغلب بیشتر از زمان لازم برای جستجوی کامل فضا می‌باشد. بنابراین این کاهش دما باید به گونه‌ای باشد که هم جواب نزدیک به بهینه بدست آید و هم زمان حل مسئله معقول باشد.
الگوریتم شبیه‌سازی تبرید ارائه شده
الگوریتم شبیه‌سازی تبرید از جمله الگوریتم‌های فراابتکاری است که براساس یک جمعیت اولیه‌ و تنها با یک جواب شروع می‎‌شود. از این‌رو قابلیت بالایی برای استفاده به عنوان الگوریتم جستجوی محلی دارد. در الگوریتم پیشنهادی ارائه شده ، از این الگوریتم برای بهبود جواب‌های الگوریتم مورچگان استفاده شده است به طوری که در هر گام، پس از تولید جواب‌های اولیه توسط مورچه‌ها، بهترین جواب شناسایی شده و از الگوریتم شبیه‌سازی تبرید برای یافتن جواب‌های مناسب در اطراف بهترین جواب‌های یافت‌شده استفاده می‌شود. در این پایان‌نامه ایده‌ی اصلی الگوریتم شبیه‌سازی تبرید ارائه شده بر اساس الگوریتم ارائه شده توسط لو [82] می‌باشد. بر اساس مطالب گفته شده، پارمترهای مدل را می‌توان به صورت زیر بیان نمود:
پارامترها:

این مطلب را هم بخوانید :  جستجوی مقالات فارسی - تاثیر نوسانات بازار سهام بر عملکرد شرکت ها- قسمت 55

دانلود کامل پایان نامه در سایت pifo.ir موجود است.

مدیر سایت

: دمای نهایی در الگوریتم شبیه‌سازی تبرید
β : ضریب کاهش دما
: تابع هدف جواب برگزیده