الگوریتم بهینه‌سازی ازدحام ذرات و الگوریتم های فراابتکاری


Widget not in any sidebars

چنگ و لیو [45] مسأله در حالت دو ماشینه را با محدودیت زمان خرابی یا تعمیر ماشین‌ها و با هدف کمینه‌کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرار داده و یک الگوریتم ابتکاری برای حل تقریبی آن ارائه میدهند.
آیدوسان و الله وردی [46] روش ابتکاری برای حل مسأله تابع هدف کمینه‌کردن زمان تکمیل پردازش آخرین کار ارائه میدهند. کوبزین و استراسویچ [47] مسأله در حالت دو ماشینه را با فرض خرابی ماشینها و با هدف کمینه‌کردن زمان تکمیل پردازش آخرین کار در نظر میگیرند و یک روش ابتکاری برای حل آن ارائه میدهند. وانگ و همکاران [48] مسأله انعطاف‌پذیر دو مرحله ای را مورد برررسی قرار میدهند. آنها پیچیدگی مسأله را مورد بحث قرار داده و الگوریتم ابتکاری برای حل آن ارائه میدهند. بوقارد و همکاران [49] مسأله را با هدف کمینه‌کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرارداده و روشی تقریبی برای حل آن ارائه میدهند.
لی و همکاران [50] مسأله را با تابع هدف کمینه‌کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرار داده و یک الگوریتم ابتکاری برای حل آن ارائه میدهند.
کالشینسکی و کامبوروسکی [51] مسأله را با هدف کمینه‌کردن زمان تکمیل پردازش آخرین کار را مورد بررسی قرار میدهند و یک الگوریتم ابتکاری برای حل آن ارائه میدهند و نشان می‌دهند این الگوریتم قابل استفاده برای مسأله جریان‌کارگاهی انعطافپذیر نیز میباشد و یک حد پایینی برای آن تعیین میکنند.
رویز و الله وردی [52] یک الگوریتم ابتکاری برای مسأله با تابع‌های کمینه‌کردن زمان تکمیل پردازش آخرین کار و کمینه‌کردن حداکثر دیرکرد ارائه کرده و نشان دادند این الگوریتم الهام گرفته از الگوریتم ژنتیک است که جواب‌های با کیفیتی را بدست میدهد.
فرامین و همکاران [53] مسأله را با هدف کمینه‌کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرار داده، یک الگوریتم ابتکاری برای حل آن ارائه داده و نشان دادند که این الگوریتم قابلیت اجرا به عنوان یک جستجوی محلی را دارا می باشد.
مروری بر الگوریتم‌های فراابتکاری مسئله جریان‌کارگاهی با محدودیت عدم‌توقف
الگوریتم‌های فراابتکاری دارای چارچوبی از پیش تعیین شده هستند که برای حل هر مسأله بهینه‌سازی کافی است که آن مسأله را در قالب چارچوب الگوریتم فراابتکاری درآورد. در اغلب مقاله‌های که الگوریتم‌هایی برای حل مسائل بهینه‌سازی پیچیده با استفاده از الگوریتم‌های فراابتکاری ارائه شده، جواب‌هایی با کیفیت بالا در زمان کوتاهی بدست آمده است. در صورتی که جواب‌های ابتکاری همواره به یک جواب مشخص می‌رسند، الگوریتم های فراابتکاری بدلیل ماهیت تصادفی خود، قابلیت ایجاد جواب‌های متنوع را خواهند داشت. به همین دلیل شانس بیشتری در دستیابی به جواب‌هایی با کیفیت در مقایسه با الگوریتم‌های ابتکاری را دارند. برای حل مسأله جریان‌کارگاهی با محدودیت عدم‌توقف نیز الگوریتم‌های فراابتکاری متعددی از جمله الگوریتم جستجوی پراکنده، الگوریتم ژنتیک، الگوریتم جست وجوی ممنوع و الگوریتم مورچگان ارائه شده است.
فینک و وب [54] از الگوریتم فراابتکاری شبیه‌سازی تبرید و جستجوی ممنوع به همراه یک روش جستجوی محلی برای حل مسأله استفاده کردند. آیدوسان و الله‌وردی [55] دو روش مبتنی بر شبیه‌سازی تبرید شده و تکنیک‌های الگوریتم ژنتیک برای یک مسأله با هدف کمینه‌سازی طولانی‌ترین زمان تکمیل کارها ارائه نمودند. ژنگ و ژو [56] مسأله را با هدف کمینه‌سازی همزمان دو تابع زمان تکمیل پردازش آخرین کار و مجموع زودکرد و دیرکرد کارها در یک محیط فازی مورد بررسی قرار دادند و از الگوریتم شبیه‌سازی تبرید برای حل آن استفاده کردند. مسأله با در نظر گرفتن زمان‌های آماده‌سازی و با تابع هدف کمینه‌کردن حداکثر دیرکرد توسط رویز و الله‌وردی [52] مورد بررسی قرار گرفت. آنها چهار الگوریتم جدید و کارا بر اساس الگوریتم فراابتکاری ژنتیک برای حل آن پیشنهاد نمودند. پن و همکاران [57] مسأله را با تابع هدف‌های زمان تکمیل پردازش آخرین کار و کل زمان‌های تکمیل را مورد بررسی قرار دادند و دو الگوریتم جدید بر اساس الگوریتم بهینه‌سازی ازدحام ذرات پیشنهاد نمودند. مسأله جریان‌کارگاهی با محدودیت عدم‌توقف با تابع هدف زمان تکمیل پردازش آخرین کار توسط لاها و چاکرابورتی [58] نیز مورد بررسی قرار گرفته شده است. آنها برای حل الگوریتمی ترکیبی بر پایه‌ی الگوریتم شبیه‌سازی تبرید و الگوریتم ابتکاری ارائه شده توسط نواز و همکاران [16] استفاده کردند. کیم و جونگ [59] الگوریتم ژنتیک را برای حل یک مسأله با هدف کمینه کردن زمان تکمیل پردازش آخرین کار و گروه‌بندی کارها مورد بررسی قرار داده‌اند. سنگ و لین [60] الگوریتمی بر پایه الگوریتم ژنتیک و یک الگوریتم ابتکاری که خود ترکیب دو الگوریتم ابتکاری دیگر بود، برای حل مسأله جریان‌کارگاهی با فرض عدم‌توقف ارائه دادند. همچنین نشان دادند که این الگوریتم مخصوصا برای مسائل نمونه بزرگ بسیار کاراست. ژاو و تانگ [61] مسئله با تابع هدف تکمیل پردازش را مورد بررسی قرار داده و الگوریتمی بر اساس الگوریتم سیستم ایمنی مصنوعی و نظریه‌ی هرم سلسله مراتب نیازهای مزلو برای آن پیشنهاد نمودند. کارایی الگوریتم با بررسی آن بر روی مسائل مختلف نشان داده شده است. جاربویی و همکاران [62] یک الگوریتم ابتکاری بر اساس جستجوی پراکنده همسایگی برای مسئله با تابع هدف‌های طولانی‌ترین زمان تکمیل پیشنهاد دادند. آنها در گام آخر الگوریتم‌شان از الگوریتم ژنتیک استفاده کردند. ژو و همکاران [63] مسئله را با تابع هدف کمینه‌کردن مجموع کل زمان تکمیل پردازش کارها بررسی کرده و الگوریتم ترکیبی بر اساس جستجوی هارمونی گسسته ارائه دادند. ناگونو و همکاران [64] مسئله را در حالتی که زمان‌های آماده‌سازی وابسته به توالی کارها بوده با هدف کمینه‌کردن مجموع کل زمان تکمیل پردازش کارها مورد بررسی قرار دادند. آنها برای حل آن، الگوریتمی ژنتیک که در آن جستجوی دسته‌ای استفاده شده است، ارائه نمودند. ژو و همکاران [65] مسئله را بر پایه‌ی یک الگوریتم آزمندانه و با استفاده از یک الگوریتم جستجوی محلی حل نمودند.
سمرقندی [66] در مقاله خود الگوریتمی بر پایه الگوریتم فراابتکاری بهینه‌سازی ازدحام ذرات و الگوریتم جستجوی ممنوع برای حل مسئله با تابع هدف‌های طولانی‌ترین زمان تکمیل و مجموع کل زمان تکمیل پردازش کارها ارائه دادند. سلماسی و عرب‌عامری [35] به بررسی مسائل زمان‌بندی جریان‌کارگاهی با محدودیت عدم‌توقف با هدف کمینه‌کردن زودکرد و دیرکرد با استفاده از الگوریتم بهینه‌سازی ازدحام ذرات و جستجوی ممنوع پرداختند و الگوریتم‌هایی کارا برای مسائلی در ابعاد کوچک،متوسط و بزرگ ارائه نمودند. پانگ [67] در تحقیق خود، مسئله توسط دو ماشین با زمان‌های آماده‌سازی دسته‌ای و تابع هدف کمینه کردن حداکثر دیرکرد را مورد بررسی قرار داد و برای حل آن الگوریتم ژنتیک و دو الگوریتم ابتکاری ارائه نمود. رمضانی و همکاران [68] مسئله جریان‌کارگاهی انعطاف‌پذیر با محدودیت عدم‌توقف و ماشین‌های موازی و زمان‌های آماده‌سازی وابسته به توالی را با تابع هدف طولانی‌ترین زمان تکمیل مورد بررسی قرار دادند. در این پژوهش برای حل مسئله از الگوریتم ترکیبی جستجوی پراکنده همسایگی و الگوریتم شبیه‌سازی تبرید استفاده میشود.
تشریحی بر بهترین الگوریتم در ادبیات موضوع
برترین الگوریتمی که تاکنون برای حل مسئله NWFS با تابع هدف زودترین زمان اتمام کارها ارائه شده است، الگوریتمی است که در سال 2008 توسط پن، تسقتیران و لیانگ پیشنهاد شده است [57]. این الگوریتم بر پایه الگوریتم فراابتکاری ازدحام ذرات است. آنها از الگوریتم جستجوی پراکنده همسایگی برای جستحوی محلی استفاده نمودند.
الگوریتم ازدحام ذرات نخستین بار توسط جیمز کندی، روانشناس اجتماعی، و راسل سی ابرهارت، مهندس برق، در سال 1996 معرفی گردید. آنها در ابتدا قصد داشتند که با بهره‌گیری از مدل‌های اجتماعی و روابط موجود اجتماعی، نوعی از هوش محاسباتی را به وجود بیاورند که به توانایی‌های فردی ویژه نیازی نداشته باشد. این کار منجر به ایجاد الگوریتم بهینه‌سازی گروه ذرات یا شد [69]. در الگوریتم عمل جست‌وجو در فضای جواب توسط ذرات صورت می‌گیرد. این ذرات در فضای جواب مسئله پخش شده‌اند. هر ذره مقدار تابع هدف را در موقعیتی از فضا که در آن قرار گرفته‌ است محاسبه می‌کند. ترکیب اطلاعات محل فعلی هر ذره و بهترین محلی که در گذشته در آن بوده است، به همراه اطلاعات یک و یا چند ذره از بهترین ذرات موجود، جهت ذره را برای حرکت در فضای جواب مشخص می‌سازد. پس از تعیین جهت و انجام حرکت تمام ذرات یک مرحله از الگوریتم به پایان می‌رسد. با تکرار این مراحل و رسیدن به شرط توقف الگوریتم خاتمه می‌یابد.
هر ذره در الگوریتم با استفاده از سه بردار مشخص می‌شود. این سه بردار برای ذره عبارتند از: موقعیت فعلی ذره، سرعت حرکت ذره و بهترین موقعیتی که ذره تا به حال تجربه کرده است. نحوه تعیین بردار و بعد آن به نوع مسئله دارد. در هر مرحله‌ای که الگوریتم تکرار می‌شود، به عنوان یک جواب برای مسأله محاسبه می‌شود و اگر این موقعیت بهتر از جواب‌های پیشین باشد، در ذخیره می‌شود. مقدار تابع هدف در و مقدار تابع هدف در است که هر دو از عناصر تشکیل‌دهنده‌ی هر ذره به حساب می‌آیند. در هر تکرار و جدیدی به دست می‌آیند و منظور از اجرای الگوریتم، بهتر کردن مقدار می‌باشد. الگوریتم نمونه‌ای از یک الگوریتم هوش جمعی است که در آن با تعامل مجموعه‌ای از اجزا جواب مسئله به دست می‌آید. در واقع هیچ‌کدام از ذرات به تنهایی قادر به حل مسأله نیستند و تنها ارتباط آنها با یکدیگر منجر به دستیابی به جواب مناسب خواهد شد.
در ادامه به معرفی روابط برای مساله زمان‌بندی کارها می‌پردازیم.
در کاربرد الگوریتم ازدحام ذرات در زمان‌بندی، هر توالی نشان‌دهنده ذره در الگوریتم ارذحام ذرات می‌باشد. همان‌طور که گفته شد هر ذره دارای مختصات و سرعت می‌باشد که این ویژگی شامل هر توالی در مسئله زمان‌بندی نیز می‌باشد. یعنی در مسئله زمان‌بندی، هر مکان از یک توالی شامل یک مختصات و سرعت می‌باشد. در این مسئله، ابتدا به تعداد جواب‌های اولیه و به تعداد مکان‌های یک توالی مقدار مختصات و سرعت تولید می‌شود. بعد از تولید مختصات هر مکان از جواب‌های اولیه بر اساس میزان کیفیت مختصات آنها، توالی‌شان را مشخص می‌کنیم و سپس میزان تابع هدف انها را تعیین می‌کنیم. بعد از تعیین توالی و مقدار تابع هدف جواب‌های اولیه، بهترین ذره شناسایی شده و در حرکت سایر ذرات نیز اثر می‌گذارد. در این مرحله با توجه به موقعیت کنونی ذرات و موقعیت بهترین ذره‌ی شناسایی شده، هر ذره با توجه به روابط زیر حرکتی در فضای جستجو انجام می‌دهد.
3-4
3-5
در این روابط، ضریب اینرسی، و اعدادی تصادفی در بازه [0,1] با توزیع یکنواخت و همچنین، و ضرایب یادگیری هستند. و باعث می‌شوند که نوعی گوناگونی در جواب‌ها به‌وجود بیاید و به این نحو جستجوی کاملی روی فضا انجام پذیرد. ، ضریب یادگیری مربوط به تجارب شخصی هر ذره و ضریب یادگیری مربوط به تجارب کل جمع می‌باشد. از معادله بالا می‌توان به این نتیجه رسید که، هر ذره به هنگام حرکت، (الف) جهت حرکت قبلی خود، (ب) بهترین موقعیتی که در آن قرار داشته است و (پ) بهترین موقعیتی را که به وسیله کل جمع تجربه شده است، در نظر می‌گیرد.
بعد از انجام حرکت در فضای جستجو توسط تمامی ذرات یک مرجله از الگوریم به پایان می‌رسد.
جمع‌بندی
مسئله جریان‌کارگاهی با محدودیت عدم‌توقف کاربرد بسیار زیادی در سیستم‌های تولیدی و خدماتی دارد. با توجه به اهمیت این مسئله در دنیای واقعی ارائه الگوریتم کارا برای حل مسئله بسیار مهم می باشد.
تاکنون برای حل مسئله مورد بررسی الگوریتم‌های ابتکاری متعددی ارائه شده است که تمامی آنها قابلیت بدست آوردن جوابی خوب در کمترین زمان را دارا می‌باشند. در سال‌های اخیر استفاده از روش‌های فراابتکاری برای حل مسئله با توجه به قابلیت‌های این الگوریتم‌ها رو به رشد می‌باشد. در این فصل مروری کامل بر روش ‌های‌ابتکاری و فراابتکاری ارائه شده برای حل مسئله جریان‌کارگاهی با محدودیت عدم‌توقف پرداختیم و همچنین بهترین الگوریتم ارائه شده برای حل مسئله در ادبیات را مورد بررسی قرار دادیم.
الگوریتم و روش حل پیشنهادی
در این فصل، سه الگوریتمی فراابتکاری بر پایه الگوریتم مورچگان برای حل مسئله جریان‌کارگاهی با محدودیت عدم‌توقف ارائه می‌شود. تفاوت این الگوریتم ها در نحوه استفاده از الگوریتم جست‌وجوی محلی است. در پایان نتایج بدست آمده گزارش شده است.