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