وبلاگ

۱۰

۹۲

۶-۶- جمع­بندی و نتیجه ­گیری

در این فصل الگوریتم جدید معرفی شده در فصل قبل برای حل مسئله زمانبندی کار کارگاهی منعطف بکار گرفته شده و نتایج آن با نتایج حاصل از الگوریتم معرفی شده توسط کاسم و همکارانش مقایسه گردید. کاسم و همکارانش در الگوریتم خود که مبتنی بر الگوریتم بهینه­سازی حرکت جمعی ذرات است، از تصمیم ­گیری فازی برای انتخاب نقاط بهینه پارتو بهره گرفته اند. نتایج مقایسه این دو الگوریتم نشان می­دهد که روش DbMOPSO علاوه بر دقت بالا در یافتن نقاط بهینه پارتو، تعداد بیشتری راه­حل بهینه ارائه می­دهد که این از برتری­های این روش نسبت به روش آنها است.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

فصل ۷

جمع­بندی و نتیجه ­گیری

Summary and Conclusion

۷-۱- مقدمه

در تحقیق حاضر با بررسی سیستم­های تولید سفارشی­سازی در تولید انبوه، روشن گردید که یکی از مهمترین ویژگیهای این سیستمها، انعطاف­پذیری در کارگاه است. لذا مسئله برنامه­ ریزی و زمانبندی برای سیستمهای تولید سفارشی­سازی در تولید انبوه به مسئله برنامه­ ریزی و زمانبندی کارگاه تولید منعطف تقلیل یافته و مورد بررسی قرار گرفته است. از آنجایی که برنامه­ ریزی و زمانبندی در چنین سیستم­هایی، جزو پیچیده­ترین مسائل در زمینه بهینه­سازی ترکیبیاتی محسوب میشوند، برای حل این مسئله، ضمن مطالعه روش­های مختلف حل مسائل بهینه­سازی ترکیبیاتی، روش بهینه­سازی حرکت جمعی ذرات انتخاب گردیده است.

۷-۲- دستاوردهای تحقیق

در این تحقیق، مروری بر مفاهیم سفارشی­سازی در تولید انبوه، برنامه­ ریزی و زمانبندی تولید و روش های فرااکتشافی در حل مسائل بهینه­سازی صورت گرفته و ادبیات موضوعی در زمینه حل مسئله برنامه­ ریزی و زمانبندی کارگاه انعطاف­پذیر با بهره گرفتن از روش های فرااکتشافی بررسی شده ­اند. سپس حل این مسئله، با بهره گرفتن از الگوریتم حرکت جمعی ذرات، مورد بررسی قرار گرفته است. در این تحقیق، روش جدیدی در مدل­سازی فضای جستجوی مسئله زمانبندی کار کارگاهی منعطف که قابلیت حل همزمان زیر مسئله­های تخصیص وظایف به ماشینها و زمانبندی ترتیب را بطور همزمان بدست می­دهد، ارائه شده است. سپس برای حل مسئله مذکور شکل جدیدی از الگوریتم بهینه­سازی چندهدفه حرکت جمعی ذرات مبتنی بر چگالی هسته ذرات، معرفی شده و نشان داده شده است که این شکل جدید الگوریتم، میتواند در حل انواع مسائل بهینه­سازی چند هدفه، کارایی بالاتری نسبت به اشکال دیگر الگوریتم­های بهینه­سازی چند هدفه نشان دهد، بطوری­که ضمن دقت بالا در محاسبه مجموعه راه حل های بهینه پارتو، می ­تواند راه حل های بیشتری را برای تصمیم گیری ارائه دهد.

۷-۳- محورهای مطالعه و گسترش بیشتر

با توجه به دو ایده جدید ارائه شده در این تحقیق یعنی معرفی فضای جستجو و معرفی شکل جدیدی از الگوریتم بهینه سازی چندهدفه حرکت جمعی ذرات، محورهای زیر برای مطالعه و تحقیق در آینده پیشنهاد میگردد:
مطالعه خصوصیات توپولوژیکی فضای جستجو، از جهت کاهش تعداد نقاط فضای جستجو برای افزایش سرعت الگوریتم
مطالعه fitness landscape ایجاد شده توسط توابع هدف در فضای جستجوی معرفی شده برای تنظیم بهتر و سیستماتیک پارامترهای الگوریتم بهینه سازی
بررسی تأثیر استفاده از روش های مختلف خوشه بندی در الگوریتم DbMOPSO
بررسی معیارهای بیشتر در مقایسه الگوریتم DbMOPSO با اشکال دیگر الگوریتم بهینه سازی چندهدفه حرکت جمعی ذرات
در الگوریتمهای بهینه سازی چندهدفه، اغلب از مفهوم غلبه^[۱۰۰] پارتو استفاده میشود – همانطور که در تحقیق حاضر هم از همین مفهوم شده است. بررسی تعاریف دیگر مانند استفاده از مفهوم تعادل نش^[۱۰۱] بجای غلبه پارتو ممکن است به نتایج بهتری در برخی مسائل منجر شود.

پیوست یک

فرااکتشافات در بهینه­سازی

Meta-Heuristics in Optimization

۴-۱- مقدمه

موضوع توابع فرااکتشافی^[۱۰۲] برای کاربرد در مسائل بهینه­سازی ترکیبی زمینه تحقیقاتی است که با سرعت در حال رشد است و این به دلیل اهمیت مسائل بهینه­سازی ترکیبی در دنیای صنعت و علم است. در این فصل مروری بر مفاهیم روش­های فرااکتشافی ارائه می­ شود و مؤلفه­ ها و مفاهیم متفاوتی که در فرااکتشافات مختلف برای تحلیل شباهت­ها و تفاوت­ها به­کار می­روند، مطرح می­گردند. دو مفهوم بسیار مهم در فرااکتشافات، متمرکزسازی^[۱۰۳] و متنوع­سازی^[۱۰۴] است. این دو مفهوم، رفتار تابع فرااکتشافی را تعیین می­ کنند. این دو از جهتی متناقض و از جهتی مکمل یکدیگر هستند. در ادامه این فصل سعی می­ شود این دو مفهوم در فرااکتشافات مختلف بررسی شوند. همچنین با طرح مزایا و معایب رویکردهای فرااکتشافی متفاوت، اهمیت ترکیب فرااکتشافات همچنین اجتماع فرااکتشافات و روش­های دیگر بهینه­سازی در این فصل مشخص می­گردد.

۴-۲- تعاریف اولیه

بسیاری از مسائل بهینه­سازی عملی و نظری، شامل جستجوی بهترین مقادیر مجموعه ­ای از متغیرها درجهت رسیدن به یک یا مجموعه ­ای از اهداف است. این مسائل به طور طبیعی، به دو دسته تقسیم می­شوند: مسائلی که راه حل آن­ها با متغیرهای دارای مقادیر حقیقی کدگذاری شده و آن­هایی که با متغیرهای گسسته کدگذاری شده ­اند. در میان دسته دوم، کلاسی از مسائل به نام مسائل بهینه­سازی ترکیبی (CO)^[105] وجود دارد. در مسائل بهینه­سازی ترکیبی، ما در یک مجموعه متناهی یا نامتناهی ­شمارا به دنبال یک شئ می­گردیم، مانند یک عدد صحیح، زیر مجموعه، جایگشت یا ساختار گراف.
یک مسئله بهینه­سازی ترکیبی با خصوصیات زیر تعریف می­ شود:
- مجموعه ­ای از متغیرها
- دامنه­های هر کدام از متغیرها
- محدودیت­های متغیرها
- تابع هدف^[۱۰۶] که باید حداقل شود که
مجموعه کل انتساب­های ممکن به شکل زیر است که در آن مجموعه کل راه حل­هاست:
را فضای جستجو می­گویند به نحوی که هر عنصر از این مجموعه می ­تواند یک راه حل کاندید باشد.
برای حل یک مسئله بهینه­سازی ترکیبی، باید یک راه حل با کمترین مقدار تابع هدف را یافت که به ازای هر دلخواه داشته باشیم: . در این حالت، راه حل بهینه سراسری از است و مجموعه ( که زیر مجموعه می­باشد)، مجموعه راه حل­های بهینه سراسری نامیده می­ شود.
به عنوان مثال­هایی از مسائل بهینه­سازی ترکیبیاتی، مسئله فروشنده دوره گرد^[۱۰۷] (TSP) مسئله انتساب درجه دوم^[۱۰۸] (QAP)، مسائل جدول زمانی و زمانبندی را می­توان نام برد.
بدلیل اهمیت عملی مسائل بهینه­سازی ترکیبی ، الگوریتم­های زیادی برای مهارکردن^[۱۰۹] آنها، توسعه یافته­اند. این الگوریتم­ها می­توانند به دو دسته کامل یا تقریبی تقسیم ­بندی شوند. الگوریتم­های کامل، تضمین می­ کنند برای هر نمونه اندازه متناهی از مسئله بهینه­سازی ترکیبی ، راه حل بهینه­ای در زمان محدود یافت خواهد شد. هنوز، برای مسائل بهینه­سازی ترکیبی که به لحاظ پیچیدگی زمانی از نوع NP-Hard هستند الگوریتمی با زمان چند جمله­ای وجود ندارد. پس روش­های کامل ممکن است در بدترین حالت، نیاز به زمان محاسبه نمایی داشته باشند. این مسئله اغلب منجر به زمان­های محاسبه خیلی طولانی برای اهداف عملی می­گردد. بنابراین استفاده از روش­های تقریبی در طی سی سال گذشته بیشتر مورد توجه قرار گرفته است. در روش­های تقریبی، ضمانت یافتن راه حل بهینه، قربانی جستجوی راه حل­های خوب در زمان­های بسیار کوتاه می­ شود.
در میان روش­های تقریبی پایه، اغلب بین روش­های سازنده^[۱۱۰] و جستجوی محلی تفاوت قایل می­شوند. الگوریتم­های سازنده با اضافه کردن اجزایی به یک راه حل جزئی تهی اولیه، راه حل­هایی را از ابتدا تولید می­ کنند تا وقتی که راه حل کامل شود. آن­ها، نوعاً سریع­ترین روش­های تقریبی هستند. با این حال، آنها اغلب در مقایسه با الگوریتم­های جستجوی محلی، راه حل­هایی با کیفیت پایین­تر را برمی­گردانند. الگوریتم­های جستجوی محلی از راه حل اولیه­ای شروع می­ کنند و به طور تکراری برای جایگزینی راه حل فعلی با راه حل بهتری در همسایگی آن تلاش می­ کنند. در این روش­ها همسایگی به شکل زیر تعریف می­ شود.
ساختار همسایگی تابعی به شکل است که به هر مجموعه ­ای از همسایه­های را نسبت می­دهد که به آن همسایگی گفته می­ شود.
معرفی ساختار همسایگی، ما را قادر به تعریف مفهوم راه حل­های کمینه محلی می­سازد. راه حل بهینه محلی (کمینه محلی) با توجه به ساختار همسایگی ، راه حلی مانند است به نحوی که به ازای هر داشته باشیم و را یک راه حل بهینه محلی اکید^[۱۱۱]، می­نامیم اگر به ازای هر داشته باشیم .
در طی بیست سال گذشته، نوع جدیدی از الگوریتم­های تقریبی به وجود آمد که اساساً تلاش می­ کند روش­های اکتشافی پایه را با هدف جستجوی کارا و مؤثر فضای جستجو در چارچوب­های سطح بالاتر ترکیب کند. امروزه این روش­ها فرااکتشافی نامیده می­شوند. لغت فرااکتشافی ابتدا توسط گلوور^[۱۱۲] ارائه شد [۱۵] که از دو کلمه یونانی تشکیل شده است. اکتشافی^[۱۱۳] به معنای “یافتن” و پسوند “فرا”^[۱۱۴] به معنای “ورای، در سطحی بالاتر". قبل از توافق وسیع بر روی این لغت، از عبارت اکتشافات جدید^[۱۱۵] استفاده می­شد. این رده از الگوریتم­ها شامل بهینه­سازی گروه مورچگان^[۱۱۶](ACO)، بهینه­سازی حرکت جمعی ذرات^[۱۱۷] (PSO)، محاسبات تکاملی^[۱۱۸] (EC) شامل الگوریتم­های ژنتیک^[۱۱۹] (GA)، جستجوی محلی تکراری^[۱۲۰] (ILS) گداخت شبیه­سازی شده^[۱۲۱] (SA) و جستجوی ممنوع^[۱۲۲] (TS)می­باشد. تا به حال تعریف پذیرفته شده مشترکی برای فرااکتشاف ارائه نشده است. فقط در چند سال اخیر بعضی محققین در این زمینه، تعاریفی پیشنهاد کرده ­اند. مانند موارد زیر:
«فرااکتشاف به صورت فرایند تولید تکراری­ای تعریف می­ شود که یک تابع اکتشافی فرعی را با ترکیب هوشمند مفاهیم متفاوت برای کاوش و استخراج فضای جستجو، هدایت می­ کند و در آن استراتژی­ های یادگیری برای اطلاعات ساختاری، جهت یافتن راه حل­های کارای نزدیک به بهینه، مورد استفاده قرار می­گیرند [۱۶]»
«فرااکتشاف یک فرایند اصلی^[۱۲۳] تکراری است که عملیات توابع اکتشافی فرعی را برای تولید کارای راه حل­های با کیفیت بالا هدایت می­ کند. این فرایند یک روش واحد کامل (یا ناکامل) یا مجموعه ­ای از راه حل­ها در هر تکرار را به­کار می­گیرد. توابع اکتشافی فرعی می توانند رویه­های سطح بالا (یا پایین) در یک جستجوی محلی ساده یا فقط یک روش ساختاری باشند [۱۷]».
«فرااکتشاف، مجموعه مفاهیمی است که می تواند جهت تعریف روش­های اکتشافی برای مجموعه بزرگی از مسائل متفاوت مورد استفاده قرار گیرد. به بیان دیگر، فرااکتشاف را می­توان به عنوان یک چارچوب الگوریتمی کلی در نظر گرفت که می ­تواند برای مسائل بهینه­سازی مختلف، با اصلاحات نسبتاً اندکی برای تطابق با مسئله خاص، به کار برد [۱۹]».
با توجه به تعاریف ارائه شده، به طور خلاصه، ویژگی­های اساسی مشخص کننده فرااکتشافات به شرح زیر است:
فرااکتشافات استراتژی­هایی برای هدایت فرایند جستجو هستند.
هدف، کاوش کارای فضای جستجو برای یافتن راه حل­های (نزدیک) بهینه است.