منابع پایان نامه ارشد با موضوع رتبه بندی

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

بار اجرا، روند اجرای الگوریتم ممکن است در شرایطی پیش رود که مثلاً در بهینه‌های محلی قرار گیرد و کمتر بهبود یابد و یا بالعکس ممکن است به خوبی فضای مسأله را جستجو و به بهترین نحو به جواب برسد. به همین علت و برای اینکه اجراهای الگوریتم‌ها از حالت تصادفی خارج شود، ما از 5 اجرای مختلف برای الگوریتم‌ها استفاده کرده ایم و میانگین شاخص‌های این 5 اجرا را به عنوان نتیجه نهائی درنظر گرفته ایم. درمورد شاخص منطقه زیر پوشش دو مجموعه به گونه‌ای دیگر عمل کرده ایم. به این صورت که ما تمام آرشیوهای پارتو هر 5 اجرا را با یکدیگر مخلوط و آنهائی که مغلوب می‌شدند را حذف و یک آرشیو نهائی تشکیل دادیم.
– برای اینکه بتوان مقادیر توابع هدف الگوریتم‌ها را براساس معیارهای ذکر شده با یکدیگر مقایسه نمود، باید این مقادیر با مقیاس‌های یکسان مقایسه شوند. مثلاً ممکن است که مقادیر یک تابع هدف در بازه و تابع هدف دیگر در بازه قرار گیرند و هنگامی‌که این مقادیر در فرمول‌های محاسباتی معیارهای مختلف قرار گیرند، تقریباً تابع هدف اول درقیاس با تابع هدف دوم به حساب نمی‌آید. به همین منظور، ما قبل از اینکه معیارهای مختلف هر الگوریتم را محاسبه کنیم، مقادیر توابع هدف را نرماله می‌کنیم. یعنی مقادیر توابع هدف را در بازه قرارمی‌دهیم که برای این کار از فرمول زیر استفاده می‌کنیم:
(4-1)
که بهترین و بدترین مقادیر توابع هدف، همانطور که قبلاً ذکر شد، با اجرای جداگانه هر هدف با استفاده از الگوریتم ممتیک بدست آمده‌است. همچنین برای بهترین سرعت همگرائی، بهترین جواب بدست آمده از اجرای همه الگوریتم‌ها را بدست آوردیم.
لازم به ذکر است که ما برای اجرای الگوریتم‌ها، از نرم افزار MATLAB 7.6.0.324 (R2008a) استفاده کرده و این الگوریتم‌ها را در این نرم افزار کدگذاری نموده ایم. تمامی مسائل بر روی لپ تاپ Dell Vostro 1520 با پردازشگر Intel(R) Core(TM)2 Duo,2.67 GHz و حافظه اصلی 4.00 GB و با استفاده از سیستم عامل Windows 7 Ultimate اجرا شده‌اند. پس از اجرای الگوریتم‌های فراابتکاری بر روی مسائل درنظر گرفته شده، به منظور انجام تجزیه و تحلیل‌های آماری دقیق، از روش آنالیز واریانس یک طرفه با استفاده از نرم افزار Minitab 16 انجام شده‌است.
باتوجه توضیحاتی که ذکر گردید، نتایج معیارهای مختلف برای همه الگوریتم‌ها و برای نمونه مسأله‌های مختلف را محاسبه می‌کنیم که جداول کامل آن، در پیوست الف ارائه شده‌است. در بخش بعد، این مقادیر را با روشی مناسب با یکدیگر مقایسه و نتایج حاصله را بیان خواهیم کرد.
4-3- تجزیه و تحلیل نتایج
حال برای مقایسه نتایجی که بدست آمده‌است، نیاز به روشی داریم که آن‌ها را به درستی با یکدیگر مقایسه کند و نتایجی قطعی را درباره این مقادیر صادر کند.
برای اینکه بتوانیم زوایای مختلف و حالت‌های مختلف الگوریتم‌ها را در حل مسأله بررسی کنیم، یک بار نتایج بدست آمده از هر 30 مسأله را که توسط الگوریتم‌ها حاصل شده‌است را با یکدیگر مقایسه می‌کنیم. سپس از بین این 30 مسأله، ابتدا مسائلی که کوچک هستند را جدا نموده و نتایج حاصل شده از این مسائل توسط الگوریتم‌ها را با یکدیگر مقایسه نموده و تجزیه و تحلیل می‌کنیم. همین کار را برای مسائلی که بزرگ هستند، مسائلی که ساده هستند و مسائلی که سخت هستند نیز انجام می‌دهیم. به این علت این کار را انجام می‌دهیم که نشان دهیم که الگوریتم‌ها برای مسأله ما، در شرایط مختلف چه عکس العملی از خود نشان می‌دهند.
باتوجه به اینکه معیارهای درنظر گرفته شده برای مقایسه الگوریتم‌ها، هشت عدد می‌باشد و محاسبات انجام شده برای مقایسه آن‌ها بسیار زیاد است، برای نمونه ما فقط به توضیحات کامل یک معیار بسنده می‌کنیم و فقط به ذکر نتایج نهائی مابقی معیارها اکتفا می‌کنیم. در اینجا ما معیار تعداد جواب‌های غیرمغلوب را درنظر گرفته ایم.
ابتدا باید فرضیه برابری میانگین تعداد جواب‌های غیرمغلوب توسط الگوریتم‌ها را باید ثابت کنیم که این فرضیه به صورت زیر بیان می‌شود:

در این فرضیه، بیان می‌کند که میانگین به دست آمده از الگوریتم‌ها، تفاوت معناداری با یکدیگر ندارند، ولی بیان می‌کند که حداقل یکی از الگوریتم‌ها میانگین متفاوتی با بقیه الگوریتم‌ها دارد. برای آزمودن این فرضیه، از آنالیز واریانس یک طرف (ANOVA) استفاده شده‌است و نتایج حاصل از آن که توسط نرم افزار Minitab بدست آمده‌است در شکل (4-2) نشان داده شده‌است. باتوجه به این جدول، میزان p-value به دست آمده از نتایج آنالیز واریانس یک طرفه برابر صفر می‌باشد. عدد صفر بیان کننده میزان تأییدیه‌ای است که فرضیه از نمونه دریافت می‌کند. یعنی در اینجا، فرضیه ، هیچ تأییدیه‌ای از نمونه دریافت نکرده‌است، در نتیجه فرضیه رد می‌شود. همان گونه که مشخص است، در سطح اطمینان 95%، فرض رد و فرض تأیید شده‌است. این به این معنی است که میان الگوریتم‌ها تفاوت معناداری از نظر تعداد جواب‌های غیرمغلوب وجود دارد.

شکل 4-2- نتیجه بدست آمده از آنالیز واریانس برای معیار تعداد جواب‌های غیرمغلوب
حال که مشخص شد که میان الگوریتم‌ها تفاوت معناداری وجود دارد، می‌بایست الگوریتم‌ها در مقایسه با هم ارزیابی شده و مشخص شود که میان کدام الگوریتم‌ها این تفاوت معنادار وجود دارد و این تفاوت به چه میزان است. همچنین الگوریتم‌ها می‌بایست ازنظر اثربخشی رتبه بندی شوند. ما در اینجا، برای تحلیل بیشتر و یافتن اختلاف معناداری الگوریتم‌ها، از آزمون توکي122 استفاده کرده ایم. آزمون توکی با گروه بندی الگوریتم‌ها به صورت دودویی، الگوریتم‌ها را ازنظر تفاوت معناداری و میزان آن با یکدیگر مقایسه می‌کند. شکل (4-3) نتایج به دست آمده از آزمون توکی ازنظر تعداد جواب‌های غیرمغلوب را نشان می‌دهد.

شکل 4-3- نتیجه بدست آمده از آزمون توکی برای معیار تعداد جواب‌های غیرمغلوب
همان طور که در شکل (4-3) نشان داده شده‌است، آزمون توکی، الگوریتم‌ها را در پنج مرحله و دو به دو با یکدیگر مقایسه می‌کند و آن کار را به این شکل انجام می‌دهد که ابتدا اولین الگوریتم را با الگوریتم دوم تا آخر مقایسه می‌کند، سپس دومین الگوریتم را با الگوریتم سوم تا آخر مقایسه می‌کند و الی آخر. به این شکل تمام الگوریتم‌ها با یکدیگر مقایسه می‌شوند. در هر مقایسه، می‌توان گفت که گذشتن هر فاصله از نقطه صفر، بیان کننده این است که آن الگوریتم، با الگوریتم مقایسه شده اختلاف معناداری در آن سطح اطمینان ندارد.
باتوجه به نتایج به دست آمده، می‌توان الگوریتم‌ها را با یکدیگر مقایسه کرد. همان طور که در سطر سوم تا نهم شکل (4-3) نشان داده شده‌است، نرم افزار، الگوریتم‌ها را به ترتیب مقایسه و گروه بندی کرده‌است. سطوحی که حرفی را مشترک هستند، به این معنی است که زیاد متفاوت نیستند و بالعکس، اگر حرفی را مشترک نباشند، به این معنی است که به طور معناداری متفاوت هستند. جدول گروه بندی نشان می‌دهد که گروه A، شامل الگوریتم VIS می‌باشد. همچنین گروه B شامل الگوریتم‌های CNSGA-II و NSGA-II است. درحالیکه گروه C، شامل الگوریتم‌های NSGA-II، MISA و NNIA شده‌است. و در آخر الگوریتم NRGA به گروه D تعلق دارد. درنتیجه می‌توان گفت که در سطح اطمینان 95%، عملکرد الگوریتم‌ها از نقطه نظر تعداد جواب‌های غیرمغلوب به‌صورت جدول (4-2) می‌باشد. البته به صورت شماتیک، این مقایسه در شکل (4-4) به صورت نمایان‌تر نشان داده شده‌است.

رتبه الگوریتم
الگوریتم
1
VIS
2
CNSGA-II
3
NSGA-II
4
MISA
NNIA
5
NRGA
جدول 4-2- گروه بندی الگوریتم‌ها براساس معیار تعداد جواب‌های غیرمغلوب

شکل 4-4- نتیجه به دست آمده از آنالیز واریانس برای تعداد جواب‌های غیرمغلوب
ما مشابه همین تحلیل را برای همه معیارها انجام داده ایم و همچنین این معیارها را برای تمام حالت‌های مسائل سخت، مسائل ساده، مسائل کوچک و مسائل بزرگ محاسبه کرده‌ایم که تنها به ذکر نمودارهای این تحلیل‌ها در پیوست ب اکتفا می‌کنیم. نتایج نهائی بدست آمده از این تحلیل‌ها را می‌توان در جدول (4-3) مشاهده نمود. در این جدول، الگوریتم‌ها براساس هر معیار، مقداردهی شده‌اند که این مقدار، بیانگر رتبه آن‌ها در بین الگوریتم‌های دیگر می‌باشد.
درمورد معیار «فاصله نسلی»، به غیر از حالت مسائل ساده، در تمامی حالت‌ها، الگوریتم‌ها تفاوت چندانی از خود نشان نداده‌اند؛ در حالت ساده، رتبه اول به NSGA-II، رتبه دوم به CNSGA-II، رتبه سوم به VIS و NNIA، رتبه چهارم به MISA و درنهایت رتبه آخر به NRGA رسیده‌است.
درمورد دو معیار «درجه توازن در رسیدن همزمان به اهداف» و «مساحت زیر خط رگرسیون»، الگوریتم‌ها در حالت‌های مختلف، تفاوت قابل ملاحظه‌ای از خود نشان نداده‌اند و ازنظر این دو معیار، الگوریتم‌ها تفاوت معناداری با یکدیگر ندارند.

فاصله نسلی
درجه توازن در رسیدن همزمان به اهداف
مساحت زیر خط رگرسیون
تعداد جواب های غیرمغلوب

کل
ساده
سخت
کوچک
بزرگ
کل
ساده
سخت
کوچک
بزرگ
کل
ساده
سخت
کوچک
بزرگ
کل
ساده
سخت
کوچک
بزرگ
NSGAII
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3
3
2
2
3
CNSGAII
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
NRGA
1
5
1
1
1
1
1
1
1
1
1
1
1
1
1
5
5
3
4
5
NNIA
1
3
1
1
1
1
1
1
1
1
1
1
1
1
1
4
4
2
3
4
VIS
1
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
MISA
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
4
4
2
2
4

فاصله گذاری
گسترش
سرعت همگرائی
منطقه زیر پوشش دو مجموعه

کل
ساده
سخت
کوچک
بزرگ
کل
ساده
سخت
کوچک
بزرگ
کل
ساده
سخت
کوچک
بزرگ
کل
ساده
سخت
کوچک
بزرگ
NSGAII
1
2
2
3
1
3
4
1
3
1
3
3
3
3
2
4
3
3
3
3
CNSGAII
1
2
1
2
1
2
3
1
2
1
3
3
3
3
2
2
2
2
2
2
NRGA
2
4
3
4
3
2
2
1
2
1
3
4
3
3
2
6
4
4
5
4
NNIA
1
2
1
2
2
2
4
1
2
1
3
4
3
3
2
5
3
3
4
3
VIS
1
1
1
1
1
2
3
1
2
1
2
2
2
2
2
1
1
1
1
1
MISA
1
3
1
2
2
1
1
1
1
1
1
1
1
1
1
3
3
2
3
2
جدول 4-3- مقایسه الگوریتم‌ها ازنظر معیارهای مختلف و در حالت‌های گوناگون
ازنظر معیار «تعداد جواب‌های غیرمغلوب»، الگوریتم VIS به تنهائی، رتبه اول را در تمامی حالات کسب کرده‌است و رتبه آخر به NRGA رسیده‌است. با تقریب‌های بسیار اندک برای تمام حالات، رتبه دوم به CNSGA-II، رتبه سوم به NSGA-II و رتبه چهارم مشترکاً به NNIA و MISA اختصاص یافته‌است.
درمورد معیار «فاصله گذاری»، تنها نتیجه قطعی که می‌توان گرفت این است که الگوریتم VIS جزء رتبه اول و الگوریتم NRGA جزء رتبه آخر قرار دارد. درمورد معیار گسترش نیز نمی‌توان نتیجه قطعی گرفت. تنها می‌توان نتیجه گرفت که الگوریتم MISA جزء رتبه اول و الگوریتم NSGA-II جزء آخرین رتبه واقع می‌شود.
MISA از نظر معیار «سرعت همگرائی» خوب عمل کرده و رتبه اول را در تمامی حالات کسب نموده‌است. با کمی تقریب نیز الگوریتم VIS در رتبه دوم قرار دارد. درمورد معیار «منطقه زیر پوشش دو مجموعه» که ازجمله معیارهای مهم می‌باشد، با کمی تقریب در تمامی حالات، رتبه اول به VIS، رتبه دوم به CNSGA-II، رتبه سوم به MISA، رتبه چهارم به NSGA-II، رتبه پنجم به NNIA و در آخر هم الگوریتم NRGA قرار دارد.
به این ترتیب عملکرد الگوریتم‌ها در معیارهای مختلف به طور کلی مشخص می‌شود. این دیگر به تصمیم گیرنده بستگی دارد که کدامین معیار برای او اهمیت بیشتری دارد و از الگوریتمی استفاده کند که در آن معیار خوب عمل کرده‌است. اما اگر تمامی معیارها برای تصمیم گیرنده به یک میزان اهمیت داشته باشد، می‌توان متوسط تمامی معیارها را برای الگوریتم‌ها درنظر گرفت و رتبه آن الگوریتم را باتوجه به تمامی معیارها بدست آورد که نتیجه این

پایان نامه
Previous Entries منابع پایان نامه ارشد با موضوع تحلیل داده Next Entries منابع پایان نامه ارشد با موضوع مکانیابی، الگوریتم ژنتیک، و رتبه بندی