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

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

الگوریتم‌ها و برای هر یک از مسائل، زمان اجرای 100 مرتبه تکرار این الگوریتم برای هر مسأله، درنظر گرفتیم.
مقدار نیز برای تمامی مسائل، برابر 0.5 درنظر گرفته شده‌است.
در اینجا سعی شده‌است همان ساختاری که در فصل قبل برای الگوریتم‌های مختلف ذکر شد، همان ساختار برای مسئله مورد بررسی ما نیز حفظ شود. در ادامه، اصلاحاتی که برای تطبیق الگوریتم‌ها صورت گرفته، بیان می شود.

3-2-2- تطبیق الگوریتم NSGA-II برای مسئله موردبررسی
برای انجام الگوریتم NSGA-II، اندازه جمعیت را برابر 100 و احتمال تقاطع116 و جهش117 را برابر 0.5 و 0.4 درنظر گرفته ایم. برای تولید جمعیت اولیه، به صورت تصادفی، رشته‌ای از صفر و یک به طول N ایجاد کرده ایم، اگر این رشته از لحاظ برآورده کردن محدودیت حداکثر تعداد تسهیل و زمان انتظار مشتریان، قابل قبول بود، این حل را به عنوان یک حل قابل قبول پذیرفته ایم؛ درغیر اینصورت این حل را کنار گذاشته و حل جدیدی تولید می‌کنیم.
برای عملگر تقاطع، بدین صورت عمل می‌کنیم که دو حل ازبین جمعیت انتخاب می‌کنیم، به صورت تصادفی یک نقطه را برای دو نیم کردن هر حل به دو تکه انتخاب می‌کنیم و سپس قسمت انتهایی کرموزوم اول را به انتهای قسمت اول کروموزوم دوم و بالعکس وصل می‌کنیم است که دو کروموزوم مختلف تولید می‌شود. مکانیسم این عملگر را در شکل (3-1) می‌بینید:

شکل 3-1- مکانیسم عملگر تقاطع
برای انجام مکانیسم جهش نیز، به صورت تصادفی یک عنصر از حل را انتخاب و آن را اگر صفر است به یک، و اگر یک است به صفر تبدیل می‌کنیم.
بعد از انجام عملگرهای تقاطع و جهش، ممکن است حل‌های غیر قابل قبول از لحاظ هر دو محدودیت مسأله ایجاد شود. برای مقابله با این وضعیت، اگر محدودیت اول، یعنی محدودیت حداکثر تعداد تسهیل ایجادشده، نقض شود، به صورت تصادفی، به تعدادی از یک‌های حل را صفر می‌کنیم که حل، از نظر این محدودیت قابل قبول شود؛ سپس اگر محدودیت دوم نیز رعایت شده باشد، این حل به عنوان یک حل غیرقابل قبول پذیرفته می‌شود، درغیر اینصورت این حل را کنار گذاشته و به صورت تصادفی یک حل را از مجموعه غیرمغلوب انتخاب و جایگزین این حل غیرقابل قبول می‌کنیم.
برای محاسبه فاصله ازدحام، ما نیاز به حداقل و حداکثر هر سه تابع هدف مسأله داریم. برای محاسبه این مقادیر، ما هر سه هدف را به صورت جداگانه توسط یک الگوریتم ممتیک حل نموده و بهترین و بدترین حل‌های بدست آمده توسط این الگوریتم را به عنوان، مقادیر موردنظر درنظر گرفته‌ایم.
3-2-3- تطبیق الگوریتم CNSGA-II برای مسئله موردبررسی
با توجه به اینکه این الگوریتم، برگرفته از الگوریتم NSGA-II می‌باشد، تمامی پارامترهای آن نیز مطابق آن الگوریتم می‌باشد. تنها تفاوت آن، در انجام مکانیسم انتخاب می‌باشد. همانطور که در بخش قبل نیز شرح داده شد، برای انجام این مکانیسم، نیاز به محاسبه انحراف حل‌ها، از محدودیت‌ها داریم. برای مسائلی که محدودیت‌های آن‌ها، به صورت معادلات روتین ریاضی است، محاسبه این انحراف‌ها، کار چندان مشکلی نیست؛ اما در اینجا که با محدودیت‌های نامعادله‌ای روبرو هستیم، باید روش دیگری را درنظر بگیریم. ما برای محاسبه انحراف از محدودیت اول، یعنی حداکثر تعداد مجاز برای ایجاد تسهیل، به صورت فرمول (9.3) عمل می‌کنیم:
(9.3)
برای محاسبه محدودیت دوم، یعنی رعایت حداکثر زمان انتظار مشتریان در صف، از فرمول (10.3) استفاده می‌کنیم:
(10.3)
که در صورت محدودیت (10.3)، منظور از ، تسهیلاتی است که ایجاد شده و محدودیت دوم را نقض کرده‌اند.
3-2-4- تطبیق الگوریتم NRGA برای مسئله موردبررسی
با توجه به شباهت بسیار زیاد این الگوریتم نیز با الگوریتم NSGA-II، تمامی پارامترها، همانند آن الگوریتم تنظیم شده‌است. تنها تفاوت این دو الگوریتم در مکانسیم انتخاب است که در این الگوریتم، همان طور که در بخش قبل شرح داده شد، از دو مرحله چرخ رولت استفاده شده‌است که در مرحله اول، یک لایه از لایه‌های حل انتخاب می‌کنیم و در مرحله دوم، یک حل از این لایه را انتخاب می‌کنیم. در اینجا سعی شده‌است که چرخ رولت را بر روی تمامی اعضائی که قابلیت انتخاب دارند، اجرا کنیم. یعنی به این صورت عمل نکرده ایم که مثلاً به طور تصادفی و یا جهت دار، چند حل را انتخاب و بین این چند حل، یک چرخ رولت را اجرا کنیم.
3-2-5- تطبیق الگوریتم MISA برای مسئله موردبررسی
نتایجی که بدست آمده‌اند، باتوجه به پارامترهای زیر بوده‌است: اندازه جمعیت برابر 100، اندازه حافظه ثانویه برابر 100 و یک ماتریس به عنوان شبکه تطبیقی. عملگرهای تقاطع و جهشی نیز که مورداستفاده قرار گرفته‌اند، شبیه عملگرهایی است که در الگوریتم‌های قبلی استفاده شده‌است.
3-2-6- تطبیق الگوریتم VIS برای مسئله موردبررسی
نتایج بدست آمده از اجرای الگوریتم VIS، با پارامترهای زیر بدست آمده‌است: تعداد تکثیر برای هر سلول یعنی ، برابر 5، تعداد تکرارهای داخلی یعنی برابر 3، درصد تولید حل‌های تصادفی در هر حلقه خارجی برابر 20% و اندازه حافظه برابر 100 قرار داده شده‌است. بقیه پارامترهای الگوریتم، شبیه الگوریتم‌های پیشین تعیین شده‌است.
در اینجا برای مقابله با حل‌های غیرقابل قبولی که توسط جهش ایجاد می‌شوند، رویکرد دیگری متفاوت با رویکردی که در روش اصلی توضیح داده شد، می‌توان استفاده کرد. برای توضیح این روش می‌توان به این مثال توجه کرد: فرض کنید که تعداد جهش درنظر گرفته شده برای یک حل، برابر 5 باشد. ابتدا یک جهش را بر روی این حل انجام می‌دهیم. اگر حل جدید ایجادشده، قابل قبول باشد، دومین جهش را نیز بر روی این حل انجام می‌دهیم. به همین ترتیب این جهش‌ها را تا پنجمین جهش ادامه می‌دهیم. اگر در هر مرحله‌ای از انجام این جهش‌ها، حل ایجاد شده غیرقابل قبول شد، آخرین حلی که قبل از این جهش وجود داشت و قابل قبول بود را به عنوان حل نهایی انتخاب می‌کنیم. البته باتوجه به شرایطی که بر مسأله حاکم است و برای افزایش سرعت الگوریتم، ترجیح داده شد که از همان روشی که در الگوریتم‌های پیشین برای رسیدگی به محدودیت‌ها وضع شده بود، استفاده کرد.
3-2-7- تطبیق الگوریتم NNIA برای مسئله موردبررسی
در این الگوریتم، از پارامترهای زیر استفاده کرده ایم: حداکثر اندازه جمعیت غیرمغلوب یعنی را برابر 100، حداکثر اندازه جمعیت فعال یعنی را برابر 20 و اندازه جمعیت کلون یعنی را برابر 100 درنظر گرفته ایم. مابقی پارامترهای الگوریتم نیز شبیه الگوریتم‌های پیشین تنظیم شده‌است.

تجزیه و تحلیل داده‌ها

4-1- تولید مسأله نمونه
چیزی که در اکثر تحقیقات به آن توجه نمی‌شود، چگونگی تولید مسائل نمونه است. چگونگی تولید مسأله، از این جهت حائزاهمیت است که با استفاده از این مسائل است که عملکرد الگوریتم، ارزیابی می‌شود.
برای اینکه به حالت‌های مختلف مدل پرداخته شود، مسائلی که تولید شده‌اند را از دو حیطه مورد توجه قرار داده ایم:
1) سخت118 یا ساده119
2) کوچک120 یا بزرگ121

نمونه

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
تعداد مشتری
50
50
50
80
80
80
100
100
100
150
150
150
300
300
500
تعداد سرور
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
محدوده عرضها
20
50
100
20
50
100
20
50
100
20
50
100
50
100
100
محدوده طولها
20
50
100
20
50
100
20
50
100
20
50
100
50
100
100
مجموع تقاضا
154
154
154
211
211
211
309
309
309
422
422
422
883
883
1474
تعداد سرور مجاز
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
نرخ سرویس دهی با شرایط ساده
35
35
35
45
45
45
55
55
55
80
80
80
170
170
260
نرخ سرویس دهی با شرایط سخت
25
25
25
30
30
30
38
38
38
50
50
50
95
95
155

جدول 4-1- مشخصات هر نمونه
برای ایجاد سختی و سادگی مسأله، نرخ سرویس دهی را طوری تنظیم کرده ایم که با توجه به آن، شرایط حل مسأله سخت و یا ساده شود؛ یعنی، اگر از هر دو حلی که به طور تصادفی تولید می‌شود، یک کروموزوم از لحاظ رعایت نکردن حد مجاز زمان انتظار، غیرقابل قبول باشد، آن مسأله، ساده درنظر گرفته می‌شود و اگر از هر ده کروموزومی که به طور تصادفی تولید می‌شود، نه کروموزوم از لحاظ رعایت نکردن حد مجاز زمان انتظار، غیرقابل قبول باشد، آن مسأله سخت درنظر گرفته می‌شود.
برای توجه به کوچک و بزرگ بودن مسأله، تعداد مشتری‌ها را از 150 تا 500، تعداد سرویس دهنده‌ها را 50 و محدوده عرض‌ها و طول‌ها را از 20-1 تا 100-1 متغیر گرفته ایم.
برای اینکه در تحلیل آزمایشاتی که انجام می‌دهیم، به حالت نرمال نزدیک باشیم، 30 مسأله نمونه از ترکیب این دو حیطه ایجاد کرده ایم. یعنی به این شکل که 15 مسأله را با ابعاد کوچک تا بزرگ و با شرایط ساده و 15 مسأله را با ابعاد کوچک تا بزرگ و با شرایط سخت طراحی کرده ایم. پس برای هر مسأله، مواردی که باید تعیین می‌شد شامل این موارد می‌شدند: تعداد مشتری‌ها، تعداد خدمت دهندگان، مختصات مشتری‌ها و خدمت دهندگان در ابعاد مشخص، نرخ تقاضای هر مشتری، نرخ سرویس دهی خدمت دهندگان و حداکثر تعداد خدمت دهنده‌ای که مجاز هستیم ایجاد کنیم. این موارد را برای نمونه‌های مختلف می‌توان در جدول (4-1) مشاهده نمود.
4-2- اندازه گيري عملکرد الگوريتم‌ها براساس معیارها
در ابتدا باید یادآور شد، برای اینکه نشان دهیم آیا الگوریتم‌های نوشته شده، به خوبی کار می‌کند یا خیر، از نمودار همگرائی استفاده می‌کنیم. این نمودار، معیار مناسبی است برای اینکه نشان دهیم که یک الگوریتم خوب کار می‌کند؛ به این صورت که اگر این نمودار حالت نزولی عمومی داشته باشد، الگوریتم خوب کار می‌کند، یعنی به سمت مینیمم سازی و یا بهینه شدن حرکت می‌کند. در مسائل تک هدفه، بردارهای این نمودار یکی شامل زمان یا تکرار و دیگری شامل هدف مسأله می‌باشد و نمودار حاصل شده بیانگر آن است که هدف مسأله با مرور زمان و یا تکرارهای مختلف، چگونه عمل می‌کند. اما باتوجه به اینکه این مسأله یک مسأله سه هدفه است، برای اینکه بتوانیم روند همگرائی را به صورت یک نمودار درآوریم، ما نمودار را براساس شاخص MID که در فصل قبل شرح داده شد، رسم می‌کنیم. برای اینکه مقایسه بهتری از نحوه عملکرد الگوریتم‌ها و مقایسه آن‌ها داشته باشیم، شاخص MID را برای همه الگوریتم‌ها، برای یک نمونه خاص و زمان اجرای یکسان الگوریتم‌ها در شکل (4-1) نشان داده ایم.
همانطور که در قسمت قبل مشاهده نمودید، ما هشت معیار مختلف را برای مقایسه و تجزیه و تحلیل الگوریتم‌ها با یکدیگر درنظر گرفتیم. این هشت معیار عبارتند از: فاصله نسلی، درجه توازن در رسیدن همزمان به اهداف، مساحت زیر خط رگرسیون، تعداد جواب‌های غیرمغلوب نهائی، فاصله گذاری، گسترش، سرعت همگرائی و منطقه زیر پوشش دو مجموعه. در این قسمت به اندازه گیری این معیارها برای همه الگوریتم‌ها می‌پردازیم.

شکل 4-1- نمودار همگرایی الگوریتم‌ها براساس شاخص MID

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

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