2-2-3- مسائل پوشش…………………………………………………………………………………… 19

 

2-2-3-1-مسأله پوشش مجموعه………………………………………………………………….. 19

 

2-2-3-2- مسأله مکانیابی حداکثر پوشش………………………………………………………. 21

 

2-2-3-3- مسائل p-center……………………………………………………………………… 22

 

2-2-3-4- مسائل p-median……………………………………………………………………. 23

 

2-2-4- مسائل دیگر مکانیابی………………………………………………………………………….. 24

 

2-2-5- مسائل مکانیابی تسهیلات با تقاضای تصادفی و تراکم…………………………………. 25

 

2-2-5-1- مرور ادبیات مسائل مکانیابی تسهیلات با تقاضای تصادفی و تراکم………… 26

 

2-2-5-2- مکانیابی تسهیلات با تقاضای تصادفی و تراکم………………………………….. 29

 

2-3- نظریه صف………………………………………………………………………………………………. 35

 

2-3-1- مشخصات صف………………………………………………………………………………… 36

 

2-3-2- قانون لیتِل………………………………………………………………………………………… 38

 

2-3-3- صف M/M/1…………………………………………………………………………………. 39

 

2-4- مسائل بهینه سازی چندهدفه………………………………………………………………………….. 40

 

2-4-1- فرمول بندی مسائل بهینه سازی چندهدفه…………………………………………………. 40

 

2-4-2- الگوریتم‌های تکاملی برای بهینه سازی مسائل چندهدفه بر مبنای الگوریتم ژنتیک… 41

 

2-4-2-1- الگوریتم ژنتیک مرتب سازی نامغلوب…………………………………………….. 42

 

2-4-2-2- الگوریتم NSGA-II محدود شده…………………………………………………. 45

 

2-4-2-3- الگوریتم ژنتیک رتبه بندی نامغلوب………………………………………………… 46

 

2-4-3- الگوریتم‌های تکاملی برای بهینه سازی مسائل چندهدفه بر مبنای سیستم ایمنی مصنوعی…….. 49

 

2-4-3-1- سیستم ایمنی مصنوعی………………………………………………………………… 49

 

2-4-3-1-1- مفاهیم ایمنی…………………………………………………………………….. 49

 

2-4-3-1-2- ایمنی ذاتی………………………………………………………………………. 51

 

2-4-3-1-3- ایمنی اکتسابی…………………………………………………………………… 51

 

2-4-3-1-4- تئوری شبکه ایمنی…………………………………………………………….. 52

 

2-4-3-1-5- الگوریتم ایمنی مصنوعی……………………………………………………… 53

 

2-4-3-1-6- سیستم ایمنی مصنوعی و مسائل بهینه سازی چندهدفه…………………. 54

 

2-4-3-2- الگوریتم MISA………………………………………………………………………. 56

 

2-4-3-3- الگوریتم VIS………………………………………………………………………….. 61

 

2-4-3-4- الگوریتم NNIA………………………………………………………………………. 64

 

2-5- روش‌های اندازه گیری عملکرد الگوریتم‌های چندهدفه………………………………………… 67

 

2-5-1- فاصله نسلی……………………………………………………………………………………… 68

 

2-5-2- درجه توازن در رسیدن همزمان به اهداف…………………………………………………. 69

 

2-5-3- مساحت زیر خط رگرسیون………………………………………………………………….. 70

 

2-5-4- تعداد جواب‌های غیرمغلوب نهائی………………………………………………………….. 71

 

2-5-5- فاصله گذاری……………………………………………………………………………………. 71

 

2-5-6- گسترش………………………………………………………………………………………….. 72

 

2-5-7- سرعت همگرائی……………………………………………………………………………….. 73

 

2-5-8- منطقه زیر پوشش دو مجموعه……………………………………………………………….. 73

 

2-6- جمع بندی……………………………………………………………………………………………….. 74

 

فصل سوم: مدل سازی مسأله و توسعه الگوریتم‌ها                                                 76

 

3-1- مسأله موردتحقیق……………………………………………………………………………………….. 77

 

3-2- طراحی الگوریتم‌ها……………………………………………………………………………………… 81

 

3-2-1- تطبیق الگوریتم‌ها با مسئله موردبررسی…………………………………………………….. 81

 

3-2-1-1- ساختار حل‌ها…………………………………………………………………………… 81

 

3-2-1-2- معیار توقف……………………………………………………………………………… 82

 

3-2-2- تطبیق الگوریتم NSGA-II برای مسئله موردبررسی………………………………….. 83

 

3-2-3- تطبیق الگوریتم CNSGA-II برای مسئله موردبررسی……………………………….. 84

 

3-2-4- تطبیق الگوریتم NRGA برای مسئله موردبررسی……………………………………… 85

 

3-2-5- تطبیق الگوریتم MISA برای مسئله موردبررسی……………………………………….. 85

 

3-2-6- تطبیق الگوریتم VIS برای مسئله موردبررسی…………………………………………… 85

 

3-2-7- تطبیق الگوریتم NNIA برای مسئله موردبررسی……………………………………….. 86

 

فصل چهارم: تجزیه و تحلیل داده‌ها                                                                   87

 

 

4-1- تولید مسأله نمونه……………………………………………………………………………………….. 88

 

4-2- اندازه گیری عملکرد الگوریتم‌ها براساس معیارها………………………………………………… 89

 

4-3- تجزیه و تحلیل نتایج………………………………………………………………………………….. 92

 

فصل پنجم: نتیجه گیری و مطالعات آتی                                                            100

 

5-1- نتیجه گیری…………………………………………………………………………………………….. 101

 

5-2- مطالعات آتی………………………………………………………………………………………….. 102

 

فهرست منابع و مراجع                                                                                103

 

پیوست الف: محاسبه معیارهای هشت گانه برای الگوریتم های استفاده شده                  105

 

پیوست ب: نمودارهای بدست آمده از تجزیه و تحلیل نتایج                                    113

 

پیوست ج: یک نمونه مسئله حل شده توسط الگوریتم NSGA-II                           118

 

پیوست د: کد برنامه نویسی الگوریتم NSGA-II در محیط MATLAB                  123

 

 

 

 

 

 

 

فهرست اشکال

 

شکل 2-1- مدل پایه‌ای صف………………………………………………………………………………… 36

 

شکل 2-2- مجموعه حل‌های غیرمغلوب………………………………………………………………….. 41

 

شکل 2-3- نمایشی از نحوه عملکرد NSGA-II……………………………………………………… 43

 

شکل2-4- الگوریتم NRGA………………………………………………………………………………. 47

 

شکل 2-5- سلول B، آنتی ژن، آنتی بادی، اپیتوپ، پاراتوپ و ادیوتوپ…………………………… 50

 

شکل 2-6- فلوچارت الگوریتم MISA………………………………………………………………….. 57

 

شکل 2-7- یک شبکه تطبیقی برای رسیدگی به حافظه ثانویه………………………………………… 60

 

شکل 2-8- فلوچارت الگوریتم VIS……………………………………………………………………… 62

 

شکل 2-9- تکامل جمعیت NNIA……………………………………………………………………….. 65

 

شکل 2-10- نمایش حل‌های مناسب……………………………………………………………………… 69

 

شکل 2-11- مساحت زیر خط رگرسیون………………………………………………………………… 70

 

شکل 2-12- بیشترین گسترش……………………………………………………………………………… 73

 

شکل 3-1- مکانیسم عملگر تقاطع…………………………………………………………………………. 83

 

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

 

شکل 4-2- نتیجه بدست آمده از آنالیز واریانس برای معیار تعداد جواب‌های غیرمغلوب………. 94

 

شکل 4-3- نتیجه بدست آمده از آزمون توکی برای معیار تعداد جواب‌های غیرمغلوب…………. 95

 

شکل 4-4- نتیجه به دست آمده از آنالیز واریانس برای تعداد جواب‌های غیرمغلوب…………… 97

 

 

 

 

 

 

 

فهرست جداول

 

جدول 4-1- مشخصات هر نمونه…………………………………………………………………………… 88

 

جدول 4-2- گروه بندی الگوریتم‌ها براساس معیار تعداد جواب‌های غیرمغلوب…………………. 96

 

جدول 4-3- مقایسه الگوریتم‌ها ازنظر معیارهای مختلف و در حالت‌های گوناگون……………… 98

 

جدول 4-4- متوسط معیارهای الگوریتم‌ها و رتبه بندی الگوریتم‌ها براساس آن      99

 

مقدمه

 

با رشد روز افزون معاملات تجاری در سطح جهان و در سال‌های اخیر، ظهور پدیده تجارت الکترونیک[1] و بانکداری الکترونیک[2] به عنوان بخش تفکیک ناپذیر از تجارت الکترونیک مطرح شد. بانکداری الکترونیک اوج استفاده از فناوری انفورماتیک و ارتباطات و اطلاعات برای حذف دو قید زمان و مکان از خدمات بانکی است. ضرورت یک نظام بانکی کارامد برای حضور در بازارهای داخلی و خارجی ایجاب می‌کند تا بانکداری الکترونیک نه به عنوان یک انتخاب، بلکه ضرورت مطرح شود. امروزه پایانه فروش، پایانه شعب، دستگاه‌های خودپرداز و … نماد بانکداری الکترونیک است و یافتن مکان بهینه برای این پایانه‌ها و دستگاه‌ها می‌تواند نقش مهمی در حضور یک بانک یا مؤسسه در بازارهای داخلی و خارجی داشته باشد [1].

 

1-2- مکانیابی تسهیلات

 

فرض کنید که یک شرکت رسانه‌ای می‌خواهد که ایستگاه‌های روزنامه را در یک شهر ایجاد کند. این شرکت در حال حاضر جایگاه‌هایی را به صورت بالقوه در شهرهای همسایه اش مشخص کرده‌است و هزینه ایجاد و نگهداری یک جایگاه را می‌داند. همچنین فرض کنید که تقاضای روزنامه در هر شهر همسایه مشخص است. اگر این شرکت بخواهد تعدادی از این ایستگاه‌ها را ایجاد کند، باتوجه به مینیمم کردن کل هزینه‌های ایجاد و نگهداری این ایستگاه‌ها و همچنین متوسط مسافت سفر مشتریان، این ایستگاه‌ها در کجا باید واقع شوند؟

 

سؤال قبل یک مثال از مسأله مکانیابی تسهیلات بود. مکانیابی تسهیلات یعنی اینکه مجموعه‌ای از تسهیلات (منابع) را به صورت فیزیکی به گونه‌ای در یک مکان قراردهیم که مجموع هزینه برآورده کردن نیازها (مشتریان) باتوجه به محدودیت‌هایی که سر راه این مکانیابی قرار دارد، مینیمم گردد.