منبع فایل کامل این پایان نامه این سایت pipaf.ir است

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3-4
3-5

 

در این روابط، ضریب اینرسی، و اعدادی تصادفی در بازه [0,1] با توزیع یکنواخت و همچنین، و ضرایب یادگیری هستند. و باعث می‌شوند که نوعی گوناگونی در جواب‌ها به‌وجود بیاید و به این نحو جستجوی کاملی روی فضا انجام پذیرد. ، ضریب یادگیری مربوط به تجارب شخصی هر ذره و ضریب یادگیری مربوط به تجارب کل جمع می‌باشد. از معادله بالا می‌توان به این نتیجه رسید که، هر ذره به هنگام حرکت، (الف) جهت حرکت قبلی خود، (ب) بهترین موقعیتی که در آن قرار داشته است و (پ) بهترین موقعیتی را که به وسیله کل جمع تجربه شده است، در نظر می‌گیرد.
بعد از انجام حرکت در فضای جستجو توسط تمامی ذرات یک مرجله از الگوریم به پایان می‌رسد.
جمع‌بندی
مسئله جریان‌کارگاهی با محدودیت عدم‌توقف کاربرد بسیار زیادی در سیستم‌های تولیدی و خدماتی دارد. با توجه به اهمیت این مسئله در دنیای واقعی ارائه الگوریتم کارا برای حل مسئله بسیار مهم می باشد.
تاکنون برای حل مسئله مورد بررسی الگوریتم‌های ابتکاری متعددی ارائه شده است که تمامی آنها قابلیت بدست آوردن جوابی خوب در کمترین زمان را دارا می‌باشند. در سال‌های اخیر استفاده از روش‌های فراابتکاری برای حل مسئله با توجه به قابلیت‌های این الگوریتم‌ها رو به رشد می‌باشد. در این فصل مروری کامل بر روش ‌های‌ابتکاری و فراابتکاری ارائه شده برای حل مسئله جریان‌کارگاهی با محدودیت عدم‌توقف پرداختیم و همچنین بهترین الگوریتم ارائه شده برای حل مسئله در ادبیات را مورد بررسی قرار دادیم.

الگوریتم و روش حل پیشنهادی
در این فصل، سه الگوریتمی فراابتکاری بر پایه الگوریتم مورچگان برای حل مسئله جریان‌کارگاهی با محدودیت عدم‌توقف ارائه می‌شود. تفاوت این الگوریتم ها در نحوه استفاده از الگوریتم جست‌وجوی محلی است. در پایان نتایج بدست آمده گزارش شده است.
الگوریتم فراابتکاری مورچگان
الگوریتم پیشنهادی که در این پایان‌نامه ارائه شده است، بر پایه الگوریتم بهینه‌سازی مورچگان است. این الگوريتم از رفتار مورچه‌ها در طبيعت الهام گرفته شده است. كاربرد اين الگوريتم در حل مسائل بهينه‌سازي تركيبي و مقايسة نتايج حاصل از آن با ديگر الگوريتم‌ها نشان دهندة كارايي بالاي اين الگوريتم مي‌باشد. مطرح کننده این الگوریتم مارکو دوریگو [70] است که در سال 1992 در قالب رساله دکتری آن را برای حل مسأله فروشنده دوره‌گرد[44] در 75 شهر، با نام سیستم مورچگان[45] () به عنوان مدل اولیه الگوریتم عرضه کرد. دوریگو وهمکاران در سال 1997 [71] در مقاله خود به معرفی الگوریتم سیستم کلونی مورچگان[46] () پرداختند. در الگوريتم ‌از تعدادي مورچة مصنوعي استفاده ميشود كه اين مورچه‌ها از طريق مبادلة‌ اطلاعات با يكديگر، در ساختن جواب همكاري مي‌كنند. اين الگوريتم علي‌رغم آنكه در حل مسائل فروشنده دوره‌گرد با نمونه‌هاي كوچك (كمتر از 30 شهر) دارای کیفیت جواب خوبی بود، اما استفاده از اين روش به دليل نیاز به زمان زياد در حل مسائل بزرگ، كاربرد آنرا محدود مي‌ساخت. به همين دليل تغييراتي بر روي اين الگوريتم به منظور افزايش كارايي آن انجام گرفت كه مي توان از الگوريتم‌هاي [72] و [71] نام برد.
بکارگیری الگوریتم مورچگان در حل مسائل جریان‌کارگاهی
استالتز در سال 1998 [73] اولین الگوریتم برای حل مسائل جریان‌کارگاهی جایگشتی[47] با تابع هدف کمینه‌سازی زمان تکمیل آخرین کار، به نام را ارائه کرد. این الگوریتم در واقع کاربرد روش بود که استالتز و هوس [74] در سال 1997 ارائه کردند. راجندران و زیگلر [75] در سال 2004 دو الگوریتم برای مسائل جریان‌کارگاهی جایگشتی با تابع هدفهای زمان تکمیل آخرین کار و زمان در جریان کلی[48] ارائه کردند. الگوریتم اول در واقع ترکیبی از الگوریتم وSummation Rule (ارائه شده توسط مرکل و میدن‌دور [76] ) بود. همچنین آنها یک روش جست‌وجوی محلی جدید به نام را نیز با این الگوریتم ترکیب کردند. ینگ و لیاو [77] در سال 2004 برای مسائل جریان‌کارگاهی، الگوریتم دیگری که کاربردی از بود را ارائه نمودند. الگوریتم دیگری توسط رانجندران و زیگلر [78] در سال 2006 برای مسائل جریان‌کارگاهی با تابع هدف کمینه سازی زمان تکمیل همه کارهای مختلف ارائه کردند. تعداد دیگری از محققان الگوریتم‌های مشابهی با تابع هدف‌های چندگانه نیز ارائه کرده‌اند[79] .
در سال 2012 احمدی‌زار [80] الگوریتم جدیدی به نام برای مسائل جریان‌کارگاهی با تابع هدف زمان تکمیل آخرین کار ارائه کرد. در این الگوریتم بر خلاف اکثر روش‌ها که یک عدد ثابت اولیه را به همه فرومون‌های اولیه اختصاص می‌دهند، از یک ترتیب اولیه برای مقداردهی اولیه به فرومون‌ها استفاده شده است.
الگوریتم پیشنهادی مورچگان
در الگوریتم مورچگان پیشنهادی، ایده تغییر فرومون برپایه روش است. در این روش مقدار فرومون‌ها بین دو مقدار کمینه و بیشینه تغییر می‌کنند. الگوریتم مورچگان شامل گام‌های مقداردهی اولیه فرومون‌ها، قاعده تغییر حالت، قاعده به‌هنگام کردن محلی، قاعده به‌هنگام کردن نهایی و جست‌وجوی محلی است. این گام‌ها در ادامه توضیح داده می‌شود.
مقداردهی اولیه فرومون
در الگوریتم پیشنهادی، تابع فرمون نشان دهنده اهمیت قرار گیری کار ام در مکان ام تعریف شده است. مقدار فرومون نشان‌گر درجه تمایل انجام فرایند کار ام در مکان ام است. برخلاف روشی که عموما برای مقدار دهی اولیه فرومون ارائه می‌شود، در اینجا از یک ترتیب اولیه استفاده می‌شود. ترتیب اولیه با استفاده از الگوریتم راجندران [40]، که در بخش 3-4 توضیح داده شده است، ایجاد می‌شود. با ایجاد ترتیب اولیه، مقدار فرمون اولیه ها از رابطه 4-1 بدست می‌آید: