مقاله با موضوع ارزیابی کیفی، اندازه گیری عملکرد، الگوریتم ژنتیک، رتبه بندی

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

درنظر گرفته شده است.
یکی از مشکلات عمده ای که در حل مسائل چند هدفه به کمک الگوریتم های تکاملی وجود دارد، چگونگی ارزیابی کیفیت حل های نهایی آنها است، چرا که در اکثر موارد نمی توان به کمک روش های دقیقی نظیر روش اپسیلون-محدودیت به جبهه های پارتو مخصوصا برای مثال های در ابعاد متوسط و بزرگ دست یافت و از این طریق نحوه عملکرد این الگوریتم ها را مورد آزمایش قرار داد. بنابراین نیاز به روش هایی است تا بتوان به کمک آن چگونگی عملکرد الگوریتم های چند هدفه تکاملی را به تنهایی و صرفا با بررسی جبهه پارتوی نهایی الگوریتم مورد ارزیابی قرار داد. به این منظور و در اوایل دهه۹۰ میلادی از روش های دیداری(مشاهده ای) برای مقایسه مجموعه های پارتو استفاده می کردند. بدیهی است این روش ها دارای دو مشکل اساسی بودند، اولا اینکه ما در مقایسات علمی نیازمند مبنایی قابل اندازه گیری وکمی بودیم وصرف اظهار نظر کیفی اشخاص نمی توانست محکی مناسب در اندازه گیری کارایی الگوریتم ها باشد. ثانیا مشکل اساسی دیگر این روش ها در مقایسه مجموعه های پارتو این بود که فقط برای حداکثر مسأله ۳ هدفه کاربرد داشتند. به این دلیل که امکان ترسیم فضای بیشتراز سه بعد در جهت مقایسه مجموعه جواب ها وجود نداشت.تمام این مشکلات باعث شد تا پژوهشگران به فکر بیافتند تا روشهای منطقی، جامع ومناسب را به این منظور ارائه نمایند.
همانطور که قبلا گفته شد در مسائل یک هدفه، در پایان اجرای الگوریتم ها، جوابی با توجه به نوع هدف(ماکزیمم یا مینیمم) به عنوان بهترین حل انتخاب می شود، درحالیکه در مسائل چند هدفه در پایان مجموعه ای از جواب ها تولید می شوند که بایستی با توجه به این مجموعه از جواب ها راجع به عملکرد الگوریتم اظهار نظر کرد. این روش ها از این جهت مهم هستند که به پژوهشگر کمک می کنند عملکرد الگوریتم های مورد بررسی را با روشی کمی ارزیابی وانحرافات الگوریتم را مدیریت نماید.

۲-۱۲-روشهای اندازه گیری عملکرد الگوریتم های چند هدفه
یکی از مشکلات که در حل مسائل چند هدفه وجود دارد چگونگی ارزیابی کیفیت حل های نهایی است که به دلیل تناقض اهداف به کار رفته گاها این امر کاری پیچیده خواهد بود.
به این منظور ودر اوایل دهه۹۰ میلادی از روشهای دیداری(مشاهده ای) برای مشاهده مجموعه های پارتواستفاده می کردند.بدیهی است این روشها دارای دو مشکل اساسی بودند، اولا اینکه مادر مقایسات علمی نیازمند مبنایی قابل انداره گیری وکمی بودیم وصرف اظهار نظر کیفی اشخاص نمی توانست محکی مناسب در اندازه گیری کارایی الگوریتم ها باشد.ثانیا مشکل اساسی دیگر این روشها مجموعه های پارتو این بود که فقط برای حداکثر مسأله ۳هدفه کاربرد داشتند.به این دلیل که امکان ترسیم فضای بیشتر از سه بعد در جهت مقایسه مجموعه جواب ها وجود نداشت. تمام این مشکلات باعث شد تا پژوهشگران به فکر بیافتندتا روش های منطقی، جامع و مناسب را به این منظور ارائه نمایند.
همانطورکه قبلا گفته شد در مسائل تک هدفه، در پایان اجرای الگوریتم ها حلی را با توجه به نوع هدف(ماکزیمم با مینیمم) به عنوان بهترین حل انتخاب می شود و این درحالی است که در مسائل چند هدفه در پایان حل، مجموعه ای از جواب ها ایجاد می شوند که بایستی با توجه به این مجموعه حل ها راجع به عملکرد الگوریتم اظهار نظر شود.این روش ها از این جهت مهم هستند که به پژوهشگر کمک می کنند تا عملکرد الگوریتم های مورد بررسی را باروش کمی ارزیابی و انحراف الگوریتم را مدیریت نمایند]۳[ .
– شاخص کمیت۴۷(NPS)
این شاخص، تعداد جوابهای بهینه پارتو را اندازهگیری میکند. بدیهی است که هرچه تعداد جوابهای تولید شده توسط الگوریتمی بیشتر باشد، آن الگوریتم کاراتر است.
ماکزیمم گستردگی جواب های غیر مغلوب ۴۸(MS)
هرچه مقدار این معیار بزرگتر باشد، جواب های بدست آمده از گستردگی بیشتری برخوردارند. این معیار از رابطه زیر بدست می آید:
(۲-۱۱)
MS= ?(?_(m=1)^M?((max)?(i=1:n)??f_m^i-min?(i=1:n)??f_m^i)? ? )2
شاخص تنوع۴۹(DM)
این شاخص تنوع توزیع جوابها را در مجموعه جواب پارتوی تولید شده، اندازهگیری میکند. تعریف آن بصورت زیر است:

(۲-۱۲)
D=?(?_(i=1)^N??max?(?x_i-y_j ?)?)
?x_i-y_j ?: فاصله اقلیدسی بین دو جواب پارتوی x_i و y_j
N : تعداد جوابهای مجموعه پارتو
در مقایسه دو الگوریتم، هرچه مقدار تنوع جوابها در الگوریتمی بیشتر باشد، آن الگوریتم از کارایی بالاتری برخوردار خواهد بود.
فاصله از نقطه ایده آل۵۰ (MID)
این معیار سنجشی از نزدیکی جواب های پارتو به نقطه ایده آل (۰و۰)را در صورتیکه هر دو مینیمم باشند، ارائه می کند. هر چه مقدار این فاصله کمتر باشد کیفیت جواب ها بهتر خواهد بود. با توجه به مطالب گفته شده نحوه محاسبه عملکرد مجموعه جواب های پارتو بصورت رابطه زیر خواهد بود.

)۲-۱۳( MID=(?_(i=1)^n?C_i )/n
در این رابطه n تعداد جواب های غیر مغلوب بدست آمده است و c_i فاصله اقلیدسی بین هر عضو از مجموعه از مبدأ مختصات بوده که از رابطه ?(f_1i^2+f_2i^2+…+f_ki^2 ) بدست می آید. در این رابطه منظور از f_ki مقدار k امین تابع هدف در بردار جواب پارتو i ام است. بدیهی است که برای مجموعه های مورد مقایسه هرچقدر که این مقدار کوچکتر باشد مطلوبیت آن مجموعه بیشتر خواهد بود.
درج? توازن در رسیدن همزمان به اهداف(RAS)
در اینجا روش دیگری مبتنی بر مسافت پیشنهاد شده است . اما ابتدا لازم است مقدماتی راجع به کیفیت حل ها بیان شود.

این مطلب مشابه را هم بخوانید :   روابط بین‌الملل و تکنولوژی جدید

شکل ۲-۷-نمایش حل های مناسب
در شکل(۲-۷)حلهای مناسب مسأل? دو هدفی نشان داده شده است و همچنان که مشاهده میشوداگر حلی در امتداد یک محور باشد مناسب نیست زیرا آن حل تنها برای یک هدف مناسب بوده وبرای هدف دیگر عملکرد مناسبی نداشته است ولی حلهایی که با فلش نشان داده شده اند حل های مناسبی هستند زیرا که به یک توازن قابل قبول بین اهداف مسأله رسیده اند. حال با این توصیف ، دراینجا لازم است معیاری کمی برای اندازه گیری رسیدن به این توازن در بین اهداف مختلف مسأله تعریف شود. به این منظور رابط? زیر پیشنهاد شده است.
(۲-۱۴)
RAS= (?_(i=1)^n??[(f_1i-F_i)/F_i ]+[(f_2i-F_i)/F_i ] ?)/n
که در این رابطه Fi=min{f1i , f2i} می باشد.
از جمله خصوصیات این روش میتوان به این نکته اشاره کرد که وجود حلهایی در امتداد یک محور که مقدار یک هدف در آن مناسب و مقدار هدف دیگر نامناسب باشد)حل های غیرمتوازن (باعث افزایش در مقدار معیار خواهد شد.
معیار پراکندگی۵۱ (D)
این معیار میزان پراکندگی جواب های غیر مغلوب نهایی را به صورت زیر محاسبه می کند:
(۲-۱۵) ۲ D=?(1/(n-1) ?_(i=1)^(n-1)??(d_i-¯d)?)
که در رابطه فوق d_i معرف فاصله اقلیدسی بین نقطه i وi+1 در جبهه پارتو است. هرچه این معیار کوچکتر باشد الگوریتم از کارایی بالاتری برخوردار است.
شاخص کیفیت (Q)
این شاخص به مقایسه کیفیت جوابهای پارتوی بدست آمده توسط هر الگوریتم میپردازد. در واقع همه جوابهای پارتوی بدست آمده توسط دو الگوریتم را با هم سطحبندی کرده و مشخص میکند که چند درصد جوابهای سطح یک، متعلق به هر الگوریتم میباشد. هر چه این درصد بیشتر باشد، الگوریتم از کیفیت بالاتری برخوردار است.
اما بحث مهمی که در اینجا وجود دارد این است که کدام روش اندازه گیری روش مناسب تری است و برای پاسخ به این سؤال ابتدا بایستی مشخص شود که از نظر تصمیم گیرنده چه ملاکهایی در مقایسه الگوریتم ها مهم تر بوده وثانیا نقاط قوت وضعف هر روش ارزیابی چیست تا بتوان در جای مناسب از آن استفاده نمود.به عنوان مثال اگر هدف تصمیم گیرنده داشتن تعداد حل های بیشتر در مجموعه پارتو باشد معیارهای تعداد نقاط پارتو روش مناسب تری نسبت به سایر روش ها است. اما اگر هدف تصمیم گیرنده بهتر بودن هر یک از حل های پارتو نسبت به الگوریتم های دیگر باشد روش منطقه زیر پوشش دو مجموعه مناسب تر بنظر می رسد زیرا هر حل از یک الگوریتم با حل های الگوریتم های دیگر نظیر به نظیر مقایسه می شود. اگر هدف تصمیم گیرنده داشتن حل هایی در پارتو با تمرکز بیشتر ونزدیک تر به نقطه مبدأ باشد روش پیشنهادی فاصله از نقطه ایده آل مناسب تر است و در نهایت اگر هدف تصمیم گیرنده تنها رسیدن به جواب هایی با پراکندگی بالاباشد، استفاده از دو معیار SNSو Dپیشنهاد می شود. پس همچنان که می بینیم نتایجی که هر یک از این روش ها به دست می آید لزوما یکسان نبوده ونتایج بر اساس مفاهیم خاص هر روش بدست آمده وصرفا تک بعدی به مقایسه جوابها می پردازد .در نهایت در هر یک از این موارد نیاز به تحلیل نتایج است.
۲-۱۳- ساختار کلی الگوریتمهای پیشنهادی
در این پایاننامه برای حل مسأله مورد بررسی از دو الگوریتم مرتبسازی نامغلوب ژنتیک (NSGA-II)و الگوریتم ژنتیک بر مبنای رتبه بندی نا مغلوب(NRGA)استفاده شده است که در ادامه مروری بر تاریخچه دو الگوریتم NSGA-II و NRGA خواهیم داشت.
۲-۱۳-۱- الگوریتم مرتبسازی نامغلوب ژنتیک۵۲
سرینیواس و دِب [۶۳] یک نخبهگرایی دستهبندی یا مرتبسازی نامغلوب را برای بهینهسازی چندهدفه در الگوریتمهای ژنتیک با نام NSGA پیشنهاد دادند. نکات برجستهای که در مورد این
روش بهینهسازی وجود دارد، عبارتست از:
جوابی که هیچ جواب دیگری، بطور قطع بهتر از آن نباشد، دارای امتیاز بیشتری است. جوابها بر اساس این که چند جواب بهتر از آنها وجود داشته باشند، رتبهبندی و مرتب میشوند.
شایستگی (برازندگی) برای جوابها بر حسب رتبه آنها و عدم غلبه سایر جوابها بر آنها، اختصاص مییابد.
از شیوه اشتراک برازندگی۵۳ برای جوابهای نزدیک استفاده ‏میشود تا به این ترتیب پراکندگی جوابها به نحو مطلوبی تنظیم شود و جوابهای بطور یکنواخت در فضای جستجو پخش شوند.
با توجه به حساسیت نسبتاً زیادی که نحوه عملکرد و کیفیت جوابهای الگوریتم NSGA به پارامترهای اشتراک برازندگی و سایر پارامترها دارند، نسخه دوم الگوریتم NSGA با نام NSGA-II توسط دِب و همکاران [۶۴] معرفی گردید. بر خلاف الگوریتم قبلی که از نخبهگرایی فقط در یک بعد استفاده میکرد، NSGA-II از یک مکانیسم کاملاً روشن برای فراهم آوردن چگالی در بین جوابهای بهینه پارتو هم استفاده میکند. در اغلب مواقع این الگوریتم شباهتی به NSGA ندارد ولی مبتکران، نام NSGA-II را به دلیل نقطه پیدایش آن یعنی همان NSGA، برای آن حفظ کردند. ویژگیهای عمده این الگوریتم عبارتند از:
تعریف فاصله تراکمی۵۴ بعنوان ویژگی جایگزین برای شیوههایی مانند اشتراک برازندگی

دیدگاهتان را بنویسید