بهینه سازی چند هدفه و اندازه گیری کارایی

دانلود پایان نامه

برای یک مسئله مینیمم سازی بردار تصمیم بردار تصمیم دیگر را مغلوب می کند اگر و فقط اگر
یک بردار تصمیم بهینه پارتو نامیده می شود زمانی که هیچ برداری مثل نباشد که بتواند را مغلوب کند. یک بردار هدف بهینه پارتو نامیده می شود زمانی که هیچ برداری مثل نباشد که بتواند را مغلوب کند. مجموعه جواب های نامغلوب را مجموعه پارتو و مجموعه بردار های تابع هدف متناظر را لبه پارتو نامیده می شوند. شکل (2-1) نشان دهنده ی یک فضای تصمیم سه بعدی و یک فضای هدف دو بعدی . قسمت برجسته شامل تمامی بردارهای هدف پارتو، لبه پارتو می باشد [64].
شکل (2-1)- محیط سه متغیر تصمیم و دو تابع هدف [64]
شکل (2-1)- محیط سه متغیر تصمیم و دو تابع هدف [64]
2-6-2- ارزیابی عملکرد
در بهینه سازی چند هدفه، به دلیل تفاوت در ارائه جواب های نهایی و تناقضی که در اهداف وجود دارد ارزیابی عملکرد الگوریتم ها کار مشکلی می تواند باشد. وجود معیارهای مختلف ارزیابی عملکرد برای شناسایی بهترین مجموعه حل های نامغلوب زمانیکه تفسیر دیداری نتایج بسیار مشکل است، امری ضروری می باشد.
در اوایل دهه 90 میلادی از روش های دیداری برای مقایسه مجموعه های پارتو استفاده می کردند. ولی این روش ها دارای دو مشکل اساسی بودند، اولاً این که در مقایسات علمی نیازمند مبنایی قابل اندازه گیری و کمی هستیم و تنها اظهار نظر کیفی اشخاص نمی تواند محکی مناسب در اندازه گیری کارایی الگوریتم ها باشد. ثانیاً مشکل اساسی دیگر این روش ها در مقایسه مجموعه های پارتو این بود که فقط برای حداکثر مسئله سه هدفه کاربرد داشتند، به این دلیل که امکان ترسیم فضای بیشتر از سه بعد در جهت مقایسه مجموعه جواب ها وجود نداشت. این مشکلات باعث شد تا پژوهشگران به فکر بیافتند تا روش های منطقی، جامع و مناسب را به این منظور ارائه نمایند. زیتزلر و همکاران [65] سه معیار اصلی را که باید در ارزیابی کیفیت مجموعه جواب های نامغلوب در نظر گرفته شوند، پیشنهاد کردند.
فاصله بین مجموعه جواب های نامغلوب بدست آمده و لبه ی پارتو واقعی می بایستی کمینه شود.
توزیع یکنواخت پاسخ های بدست آمده همواره مطلوب است.
تعداد جواب های بدست آمده توسط الگوریتم ها می بایستی ماکزیمم شود.
برای مقایسه توانایی الگوریتم های مختلف در حل مسائل چند هدفه از روش ها و ابزار مختلفی استفاده می شود. در ادامه به بررسی چند مورد از این روش ها که در ادبیات مسائل چند هدفه بیشتر مورد توجه بوده اند، می پردازیم.
تعداد پاسخ های پارتو (NPS) : این معیار تعداد حل های نامغلوبی که در هر با اجرا یک الگوریتم بدست می آورد را محاسبه می کند.
نسبت خطا : برای محاسبه این معیار نیاز به لبه ی پارتو واقعی مسئله هستیم که این امر در بسیاری از مسائل چند هدفه امکان پذیر نمی باشد. اگر را لبه ی پارتو نهایی بدست آمده از الگوریتم و را لبه ی پارتو واقعی مسئله بنامیم، آنگاه این معیار می تواند بصورت زیر محاسبه شود.

این مطلب مشابه را هم بخوانید :   عناصر آمیخته بازاریابی و شبکه جهانی اینترنت

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

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