دانلود پروژه: ارائه یک الگوریتم ژنتیک ترکیبی جدید برای حل مسئله فروشنده دوره گرد

 

فصل اول – کلیات

• مقدمه…………………………………………………………………………………………2

• بیان مسئله و پیشینه تحقیق……………………………………………………………………2

• چالش ها و اهداف تحقیق…………………………………………………………………..3

• مروری بر فصل های پایان نامه………………………………………………………………4

فصل دوم –  مفاهیم مسئله فروشنده دوره گرد

• مقدمه…………………………………………………………………………………………7

• انواع مسئله فروشنده دوره گرد……………………………………………………………..7

• شیوه های کدینگ پاسخ برای حل مسئله فروشنده دوره گرد با الگوریتم های هوشمند.9

• کاربردهای مسئله فروشنده دوره گرد…………………………………………………….10

• چرا تحقیقات بر روی مسئله فروشنده دوره گرد…………………………………………10

• مسائل وابسته به مسئله فروشنده دوره گرد در حوزه هوش مصنوعی…………………..11

• متدهای حل مسئله فروشنده دوره گرد……………………………………………………11

فصل سوم – الگوریتم ژنتیک

3-1    مقدمه…………………………………………………………………………………………13

3-2     بهینه سازی…………………………………………………………………………………..13

            3-2-1  الگوریتم های بهینه سازی قدیمی…………………………………………………14

3-3     هیوریستیک ها………………………………………………………………………………14

            3-3-1 انواع الگوریتم های هیوریستیک…………………………………………………15

3-4     ایده اصلی استفاده از الگوریتم ژنتیک……………………………………………………..16

3-5     درباره علم ژنتیک…………………………………………………………………………..16

3-6     تکامل طبیعی…………………………………………………………………………………17

3-7     الگوریتم ژنتیک ساده……………………………………………………………………….17

3-7-1    مکانیزم الگوریتم ژنتیک ……………………………………………………….18

              3-7-2    عملگرهای الگوریتم ژنتیک…………………………………………………..19

              3-7-3     فلوچارت الگوریتم ژنتیک به همراه مراحل الگوریتم و شبه کد آن………..20

              3-7-4     تشریح جامع تر مراحل الگوریتم ژنتیک  به همراه بیان روشهای پیاده سازی هر مرحله……………………………………………………………………………………………….. 22

                        3-7-4-1  کد گذاری…………………………………………………………..23

                        3-7-4-2  جمعیّت………………………………………………………………23

                        3-7-4-3   محاسبه برازندگی…………………………………………………..23

                        3-7-4-4   انتخاب………………………………………………………………24

                        3-7-4-5  ترکیب……………………………………………………………… 26

                        3-7-4-6  جهش………………………………………………………………..28

                        3-7-4-7  اختتام اجرای الگوریتم ژنتیک……………………………………..31

3-8     استدلال همگرایی الگوریتم ژنتیک……………………………………………………….31

3-9     انواع الگوریتم ژنتیک……………………………………………………………………..32

3-10  نقاط قوّت الگوریتم ژنتیک…………………………………………………………………32

3-11  محدودیّت های الگوریتم ژنتیک……………………………………………………………33

3-12  روش های بهبود الگوریتم ژنتیک ………………………………………………………….33

3-13  چند نمونه از کاربردهای الگوریتم ژنتیک………………………………………………….33

           3-13-1 چینش بهینه حروف فارسی بر روی صفحه کلید………………………………..34

 

فصل چهارم – مروری بر روش های ارائه شده برای حل مسئله فروشنده دوره گرد

4-1     مقدمه…………………………………………………………………………………………37

4-2     بیان چند روش برای حل مسئله فروشنده دوره گرد……………………………………….37

4-3     استفاده از الگوریتم ژنتیک برای حل مسئله فروشنده دوره گرد………………………..38

           4-3-1 حل مسئله فروشنده دوره گرد با استفاده از الگوریتم ژنتیک سنتی……………..38

           4 -3-2 حل مسئله فروشنده دوره گرد توسط الگوریتم ژنتیک ترکیبی…………………39

           4-3-2-1 الگوریتم ژنتیک ترکیبی با  دو استراتژی بهینه محلی برای حل مسئله فروشنده دوره   گرد (HGA) ………………………………………………………………………………..39

                           4-3-2-1-1 کدگذاری و کد گشایی…………………………………………39

              4-3-2-1-2 تابع شایستگی و عملگر های انتخاب……………………………40

              4-3-2-1-3 عملگر ترکیب……………………………………………………41

              4-3-2-1-4 عملگر جهش……………………………………………………..42

              4-3-2-1-5 عملگرهای جستجوی محلّی……………………………………..42

4-4     روش های فرا ابتکاری برای حل مسئله فروشنده دوره گرد……………………………..44

           4-4-1 استفاده از آنیلینگ شبیه سازی شده برای حل مسئله فروشنده دوره گرد……..44

           4-4-2 استفاده از الگوریتم کلونی مورچه ها برای حل مسئله فروشنده دوره گرد…….46

فصل پنجم – الگوریتم پیشنهادی

5-1      مقدمه………………………………………………………………………………………..48

5-2     الگوریتم ژنتیک……………………………………………………………………………..49

            5-2-1 کدگذاری و تولید جمعیت اولیه………………………………………………….49

            5-2-2 تابع شایستگی و عملگر های انتخاب……………………………………………..49

            5-2-3عملگر ترکیب………………………………………………………………………50

            5-2-4عملگر جهش……………………………………………………………………….51

 5-3     جستجوهای محلی………………………………………………………………………….52

5-4     الگوریتم ژنتیک ترکیبی پیشنهادی جدید………………………………………………….52

فصل ششم – ارزیابی و مقایسه نتایج

6-1     مقدمه………………………………………………………………………………………..55

6-2    روند ارزیابی………………………………………………………………………………….55

6-3    پارامترهای استفاده شده و نتایج حاصله……………………………………………………..56

6-4    مقایسه الگوریتم پیشنهادی…………………………………………………………………..62

فصل هفتم- نتیجه گیری و پبشنهاد برای کارهای آتی

7-1     نتیجه گیری………………………………………………………………………………….64

7-2     پیشنهاد برای کارهای آتی………………………………………………………………….64

 

 

 

 

 

 

 

 

 

فهرست شکل ها

شکل2-1 :   نمایش کروموزوم مسئله فروشنده دوره گرد با چند فروشنده………………………..8

شکل 2-2 :  نمایش مسیر حرکت روبات برای سوراخ کاری فیبرهای مدار چاپی …………….11

شکل 3-1 :  کدینگ و دیکدینگ کروموزوم ها در الگوریتم ژنتیک…………………………..23

شکل 3-2 :    فلوچارت اول از الگوریتم ژنتیک…………………………………………………..26

شکل 3-3 :    فلوچارت دوم از الگوریتم ژنتیک………………………………………………….26

شکل 3-4 :   نحوه کدینگ درختی………………………………………………………………..28

شکل3-5  :  مکانیزم انتخاب چرخ رولت………………………………………………………….30

شکل3-6  :  مکانیزم ترکیب تک نقطه ای در الگوریتم ژنتیک………………………………….33

 شکل 3-7 : مکانیزم ترکیب دو نقطه ای در الگوریتم ژنتیک……………………………………34

شکل 3-8  : نحوه اعمال جهشی خاص در الگوریتم ژنتیک………………………………………37

شکل3-9  : اعمال جهشی خاص روی یک کروموزوم با ساختار باینری…………………………38

شکل 3-10: جهش وارونه سازی بیت برای ساختار باینری کروموزوم…………………………..38

شکل 3-11: جهش با تغییر ترتیب قرار گیری بیت برای ساختار باینری کروموزوم……………39

شکل 3-12 جهش دورانی………………………………………………………………………….40

شکل 3-13: نحوه قرارگیری بهینه دست انسان بر روی صفحه کلید……………………………..44

شکل3-14 نگاشت حروف فارسی به اعداد درشیوه کدینگ مسیر کروموزوم…………………45

شکل 4-1  :  نمودار درختی روش های مختلف حل مسئله فروشنده دوره گرد………………..49

شکل 4-2 : نمایش کروموزوم کدگزاری شده به روش مسیر برای حل مسئله فروشنده دوره گرد

شکل4-3    : نحوه عملگر ترکیب بخش نگاشته…………………………………………………..55

شکل4-4    : نمایشی از 4 گره و 3 یال نابرابر………………………………………………………57

شکل5-1  نمایش ترکیب حلقوی در فرم باینری…………………………………………………..66

شکل 6-1 : واقع قرارگیری  دو نمودار بر روی یکدیگر مربوط به روش پیشنهادی و  روش یونگ به منظور مقایسه 2 نمودار با یکدیگر است………………………………………………………….78

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

فهرست جداول

جدول 6-1: عناوین الگوریتم های مقایسه شده(سطر 1 تا7) به همراه الگوریتم پیشنهادی جدید(سطر8) و  نمایش اختصاری آنها…………………………………………………………….71

جدول6-2: (6- 3 ) تست 12 عملگر ترکیب با مکانیزم انتخاب برترین ها و چرخ رولت و جهش با تغییر ترتیب قرار گیری الگوریتم ژنتیک سنتی…………………………………………………..72

جدول6-4: تست 5 عملگر جهش با مکانیزم انتخاب برترین ها و چرخ رولت و جهش با ترکیب بخش نگاشته الگوریتم ژنتیک سنتی………………………………………………………………..73

جدول6-5: نتایج 3 نوع عملگر انتخاب به همراه عملگر ترکیب بخش نگاشته و جهش درجی و جهش تغییر ترتیب قرارگیری در الگوریتم ژنتیک سنّتی………………………………………….74

جدول6-6: نتایج 3 نوع عملگر انتخاب به همراه عملگر ترکیب حلقوی جدید و جهش درجی و جهش تغییر ترتیب قرارگیری در الگوریتم ژنتیک سنتی………………………………………….75

جدول6-7: نتایج 3 نوع عملگر انتخاب به همراه عملگر ترکیب modified  ox و جهش درجی و جهش تغییر ترتیب قرارگیری در الگوریتم ژنتیک سنتی………………………………………….75

جدول 6-8 : نتایج الگوریتم های ژنتیک وانگ یونگ و روش پیشنهادی و 6 الگوریتم ژنتیک دیگر …………………………………………………………………………………………………77

جدول 6-9:  مقایسه الگوریتم پیشنهادی با 7 الگوریتم ژنتیک دیگر براساس 6 معیار مطرح شده

فهرست منابع و مآخذ……………………………………………………………………………65

پیوست ها

پیوست1- واژه نامه انگلیسی به فارسی……………………………………………………………69

 پیوست2 – واژه نامه فارسی به انگلیسی………………………………………………………….72