نگارش پایان نامه در رابطه با بهینه سازی چندهدفی ... |
A
B
تخمین خط رگرسیون
شکل ۲-۱۱- مساحت زیر خط رگرسیون
باتوجه به اینکه مسأله این تحقیق، شامل سه تابع هدف میباشد، مبنای این مقایسه، به جای سطح، فضای زیر هر صفحه خواهد بود. امّا باتوجه به اینکه یافتن سطحی تخمینی که برایند اهداف مسأله باشد بسیار مشکل میباشد، ما اهداف را به صورت دو به دو با یکدیگر درنظر گرفته و با آنها به صورت مساحت زیر خط رگرسیون برخورد میکنیم، سپس این مساحتها را با یکدیگر جمع میکنیم. این روش، تغییر زیاد بزرگی در نتایجی که در حالت سه هدفه بدست میآید، ایجاد نمیکند.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
۲-۵-۴- تعداد جوابهای غیرمغلوب نهائی
این روش، تعداد جوابهای غیرمغلوب نهایی مسائل را با یکدیگر مقایسه میکند. بدیهی است که هرچه این تعداد بیشتر باشد، نشان دهنده این است که آن الگوریتم، جستجوی بهتری را در فضای مسأله انجام دهد. البته در بعضی از الگوریتمها، محدودیتی بر روی اندازه جمعیت نهائی وضع شدهاست که ما این محدودیت را به ماهیت الگوریتم ربط داده و الگوریتم را با همان محدودیت وضع شده درنظر گرفته ایم.
۲-۵-۵- فاصله گذاری[۱۱۰]
تنوع در حلهای بدست آمده با توجه به فضای حل، همان چیزی است که در بیشتر تحقیقات نادیده گرفته میشود. زمانی که پژوهشگر کیفیت مجموعه حلهای غیرمغلوب را بیان میکند، اطلاعاتی را درباره تنوع حلها در فضای حل بیان نمیکند. این نکته مهمّی است، زیرا اگرچه حلهای غیرمغلوب ازلحاظ توزیع و پراکندگی ممکن است خوب باشند، ولی ممکن است هیچ کدام از آنها از لحاظ ساختاری متفاوت نبوده و یا تعداد زیادی از آنها مشابه باشند.
به این منظور، معیار فاصله گذاری توسط اسکات[۱۱۱] پیشنهاد شدهاست. این معیار به نوعی واریانس فاصله از بردارهای همسایه را در را اندازه گیری میکند. این مقیاس توسط فرمول زیر محاسبه میشود:
(۳۵.۲)
که در آن برابر است با:
(۳۶.۲)
در رابطه فوق، بوده و میانگین همه هاست و n ، تعداد بردارها در است. در این روش، S=0 به این مفهوم است که همه عضوها به صورت یکنواخت و مجزا از هم پراکنده شدهاند.
۲-۵-۶- گسترش[۱۱۲]
معیار گسترش، فاصله اقلیدسی بین کرانههایی که از حلهای غیرمغلوب بدست میآید را محاسبه میکند. همانطور که در شکل (۲-۱۲) مشاهده میکنید، هرچه این مقدار بیشتر باشد، نشان دهنده آن است که الگوریتم، حلهایی با دامنه و گستردگی بیشتری را یافتهاست. گسترش باتوجه به فرمول زیر بدست میآید:
(۳۷.۲)
در این روش نیز، باتوجه به اینکه ما سه هدف داریم، ما اهداف را دو به دو درنظر گرفته و بیشترین گسترش بین آنها را محاسبه کرده و این مقادیر را با یکدیگر جمع میکنیم.
هدف ۱
هدف ۲
بیشترین گسترش
شکل ۲-۱۲- بیشترین گسترش
۲-۵-۷- سرعت همگرائی
به عنوان یک معیار برای سنجش عملکرد الگوریتها، ما از سرعت همگرا شدن الگوریتم استفاده کرده ایم. باتوجه به اینکه این مسأله، یک مسأله سه هدفه است، باید همگرایی را باتوجه به نقطه مشخصی درنظر گرفت. به همین منظور، ما این شاخص را براساس شاخص MID که در بخش (۲-۵-۱) شرح داده شد، درنظر گرفته ایم. به این معنی که ما سرعت همگرایی MID را محاسبه کردهایم. معیار ما برای همگرایی نیز، ۵۰ تکرار الگوریتم، بدون تغییر در شاخص MID بودهاست. بدیهی است که هرچه زمان همگرا شدن کمتر باشد، سرعت الگوریتم بهتر بودهاست.
۲-۵-۸- منطقه زیر پوشش دو مجموعه
معیار منطقه زیر پوشش دو مجموعه[۱۱۳] (C)، منطقه زیر پوشش دو مجموعه را مقایسه میکند و خروجی آن، نشان دهنده درصد حلهایی از یک مجموعه پارتو است که بر حلهای مجموعه دیگر غالب است. مقدار این معیار از رابطه زیر بدست میآید:
(۳۸.۲)
که در این رابطه، دو مجموعه از بردارهای متغیر تصمیم متعلق به فضای مسأله با و نمایش داده شدهاست. در این رابطه اگر C=1 شود، به این مفهوم است که بر غالب است.
۲-۶- جمع بندی
مسئلهای که برای این تحقیق درنظر گرفته شده است، سعی شده است که تا حدّامکان به واقعیت نزدیک باشد. بنابراین فرضیاتی درنظر گرفته شده است تا این نزدیک بودن را بیشتر کند. باتوجه به فرضیات و خصوصیات مدل درنظر گرفته شده و همچنین باتوجه به جستجوی بسیار در وبسایتهای معتبر انتشار مقالات و مرور ادبیاتی که انجام گرفته، مقالات و تحقیقات کمی در این زمینه صورت گرفته است و این زمینه، محیطی بکر برای کار دارد. اکثر مقالاتی که در این موضوع انجام شدهاست، مسئله را به صورت تک هدفه درنظر گرفته و آن را با روش های مختلف حل نمودهاند. ازجمله این کارها می توان به کاستیلو[۱۱۴] و همکارانش اشاره کرد که در آن دو رویکرد انتخاب ظرفیت برای مکانیابی بهینه تسهیلاتی با سرورهای ثابت، تقاضای تصادفی و تراکم درنظر گرفته شدهاست. در آن مقاله، هر تسهیل به صورت یک سیستم صف M/M/s عمل می کند. بِرمن و همکارانش، مسئله مکانیابی مجموعهای از تسهیلات خدمترسان را درون یک شبکه تحلیل کردند که در آن تقاضا به علت تراکم و پوشش ناکافی از دست می رود. هدف آن مسئله، پیدا کردن حداقل تعداد تسهیلات به گونهای است که مقدار تقاضایی که از هر منبع از دست می رود، از یک سطح مشخص فراتر نرود. یکی از مدل های مکانیابی تصادفی با توزیع تقاضای پیوسته، توسط بارُن[۱۱۵] و همکارانش انجام شده است. این مدل یک توزیع عمومی از توزیع تقاضا و ورودها و فرایندهای خدمت رسانی دارد. فرض میشود که تسهیلات به صورت اختیاری بر روی یک سطح یا فضا واقع شدهاند و مشتریان به نزدیکترین تسهیل بازشده مراجعه میکنند. به هر حال، محدودیت سطح سرویس برای مطمئن شدن از سرویس مناسب، وضع شدهاست. هدف، تعیین تعداد، مکان و ظرفیت تسهیلات با مینیمم کردن جمع هزینههای ایجاد تسهیلات و سرورهاست. در نزدیکترین مقاله به تحقیق ما، وانگ و همکارانش [۲۱] مسئلهای را درنظر گرفته اند که هر تسهیل به صورت یک سیستم صف M/M/1 ساده عمل میکند. فرض شدهاست که مشتریان به نزدیکترین تسهیل سفر میکنند. هدف، تعیین مکانیابی تسهیلات با مینیمم کردن متوسط زمان کل سفر و زمان سپری شده مشتریان می باشد. آنها دو هدف را با یکدیگر ترکیب و مسئله را با بهره گرفتن از Greedy-dropping ، Tabu search و Lagrangian relaxation به صورت تک هدفه حل نمودهاند. در تمامی مواردی که ذکر شد، باوجود اینکه آن ها از لحاظ مدلبندی و نوع مسئله، به مسئله ما بسیار نزدیک می باشند، امّا در تمامی آنها، یا یک هدف درنظر گرفته شدهاست و یا اینکه اهداف مختلف با یکدیگر ترکیب و هدفی واحد را تشکیل دادهاند. حال آنکه ما در این تحقیق، سه هدف کاملاً مجزا را درنظر گرفته و مسئله را به صورت یک مسئله چندهدفه حل نمودهایم.
۳
مدل سازی مسأله و توسعه الگوریتم ها
۳-۱- مسأله موردتحقیق
یک سیستم خدماتی را درنظر بگیرید که در آن، خدمت دهندگان ثابت هستند و مشتریان برای دریافت خدمت، باید به این خدمت دهندگان مراجعه کنند. ما فرضیات کلی زیر را درنظر میگیریم: ۱) مشتریان برای دریافت خدمت، به نزدیکترین تسهیل بازشده مراجعه میکنند، ۲) درخواست خدمت توسط هر گره مشتری، از یک جریان پواسن مستقل پیروی میکند، ۳) هر جایگاه تسهیل بازشده ای، فقط یک خدمترسان با زمانهای خدمت نمایی دارد، و ۴) یک حد بالایی بر روی حداکثر زمان انتظار مجاز مشتریان، وجود دارد.
برای مدل سازی این وضعیت، علامتهای زیر را وضع میکنیم:
-
- M={1,2,…,m} : مجموعه گرههای مشتریان
-
- N={1,2,…,n} : مجموعه گرههای تسهیل بالقوه
-
- : ماتریس فاصله گره مشتری i تا گره تسهیل j
-
- : نرخ تقاضای کلی درخواستهای سرویس در سیستم
-
- : نرخ تقاضای درخواست خدمت از گره مشتری
-
- : نرخ تقاضا در مکان تسهیل بازشده
- : متوسط نرخ خدمت در هر تسهیل
فرم در حال بارگذاری ...
[دوشنبه 1400-09-29] [ 03:10:00 ق.ظ ]
|