پایگاه علمی سعید سان دانلود رایگان مقالات علمی کنفرانس و ژورنال
دانلود تحقیق الگوریتم ژنتیک و تکنیک جستجو در علم رایانه برای یافتن راه حل تقریبی برای بهینه سازی مسائل و حل مسئله فروشنده دوره گرد به کمک آن
اﻟﮕﻮرﻳﺘﻢ ژﻧﺘﻴﮏ و ﺣﻞ ﻣﺴﺎﻟﻪ فروشنده دوره گرد
ﭼﮑﻴﺪﻩ ﻣﻘﺎﻟﻪ : در اﻳﻦ ﻣﻘﺎﻟﻪ اﺑﺘﺪا اﻟﮕﻮرﻳﺘﻤﻬﺎﯼ ژﻧﺘﻴﮏ را ﻣﻌﺮﻓﯽ ﮐﺮدﻩ و ﻣﺮاﺣﻞ اﻧﺠﺎم ﭼﻨﻴﻦ اﻟﮕﻮرﻳﺘﻤﻬﺎﻳﯽ ﺗﻮﺿﻴﺢ دادﻩ ﻣﯽ ﺷﻮد. ﺑﻌﺪ از اﻳﻨﮑﻪ ﻳﮏ دﻳﺪ ﮐﻠﯽ ﻧﺴﺒﺖ ﺑﻪ اﻟﮕﻮرﻳﺘﻤﻬﺎﯼ ژﻧﺘﻴﮏ ﭘﻴﺪا ﮐﺮدﻳﻢ ﺑﻪ ﻣﺴﺎﻟﻪ Traveling Salesman Problemﻣﯽ ﭘﺮدازﻳﻢ. اﺑﺘﺪا ﭼﻨﺪ روﺷﯽ ﮐﻪ ﺑﺮاﯼ ﺣﻞ TSPاراﺋﻪ ﺷﺪﻩ اﺳﺖ را ﺑﻴﺎن ﻣﯽ ﮐﻨﻴﻢ و ﺑﻌﺪ ﺳﻌﯽ ﻣﯽ ﮐﻨﻴﻢ اﻟﮕﻮرﻳﺘﻤﻬﺎﯼ ژﻧﺘﻴﮏ ﻣﺨﺘﻠﻔﯽ را ﺑﺮاﯼ اﻳﻦ ﻣﺴﺎﻟﻪ ﻣﻄﺮح ﮐﻨﻴﻢ و ﺳﭙﺲ ﺑﺮرﺳﯽ ﻣﯽ ﮐﻨﻴﻢ ﮐﻪ ﮐﺪامﻳﮏ از اﻳﻦ اﻟﮕﻮرﻳﺘﻤﻬﺎﯼ ژﻧﺘﻴﮏ ﺑﻬﺘﺮ از ﺑﻘﻴﻪ روﺷﻬﺎ ﺟﻮاب ﻣﯽ دهﻨﺪ.
مقدمه: الگوريتم هاي ژنتيكي خانواده اي از مدل هاي محاسباتي مي باشند كه توسط تحويل تدريجي بوجود آمده اند . اين الگوريتم ها يك راه حل بالقوه براي يك مسئله مخصوص در ساختار داده هاي به شكلي كروموزومي ساده رمزگذاري مي كند و اپراتورهاي دوباره تركيب شده را در اين ساختارها بكار مي برد تا اينكه از اطلاعات مهم و حياتي حفاظت كند .
بكارگيري الگوريتم ژنتيكي با جمعيت ( نوعاً تصادفي ) كروموزوم ها شروع مي شود . پس مي توان اين ساختارها را ارزيابي كرد و فرصت هاي آوايي را به گونه اي مشخص نمود كه آ« كروموزوم هايي كه راه حل بهتري نسبت به مسئله مورد نظر ارائه مي كنند . شانس بيشتري نسبت به ديگر كروموزم ها داشته باشندتا تكثير شوند . كارايي يك راه حل نوعاً با توجه به جمعيت حاضر ارزيابي مي شود . اين توصيف مخصوص از الگوريتم ژنتيكي عملاً انتزاعي مي باشد زيرا از چند نظر ، واژه الگوريتم ژنتيكي دو معني دارد . در يك تفسير دقيق (سختگيرانه ) ، الگوريتم ژنتيكي مربوط به مدلي مي شود كه توسط جان هالِند ( 1975 ) ودانشجويانش معرفي و بررسي شد . هنوز همان موردي است كه بيشتر تئوري هاي موجود براي الگوريتم هاي ژنتيكي اساساً و يا تنها براي مدل معرفي شده توسط هالند بكار مي روند همانطور كه انواع مختلف اشاره شده در اين مقاله بعنوان الگوريتم ژنتيكي به كار مي روند .
پيشرفت هاي تئوريكي اخير مدلسازي الگوريتم ژنتيكي همچنين اساساً الگوريتم ژنتيكي را بكار مي برند.
در كاربرد گسترده تر اين واژه ، يك الگوريتم ژنتيكي عبارتست از هر نوع مدل وابسته به جمعيت كه از انتخاب و اپراتورهاي دوباره تركيب يافته استفاده مي كند تا نقاط ساده جديد در فضاي تحقيق بوجود آورد . بسياري از مدل هاي الگوريتم ژنتيكي توسط محققاني ارائه شده اند كه عمدتاً‌از يك ديدگاه تجربي كار مي كرده اند . بسياري از اين محققان كاربرد محور مي باشند و نوعاً علاقه مند به الگوريتم هاي ژنتيكي بعنوان ابزارهاي بهينه سازي مي باشند.
آن که در طلب دانش است باید خردور و با دانش باشد. بزرگمهر
فهرست مطالب
عنوان شماره صفحه
________________________________________
مقدمه 1
فصل 1-فصل اول: الگوریتم ژنتیک چیست؟
1-1-مقدمه ای برالگوریتم ژنتیک 3
الگوریتم ژنتیک چیست؟ 6
رمزگذاری و کارکرد ارزشیابی در الگوریتم ژنتیک 10
1-2-ساختار الگوریتم ژنتیک 12
الگوریتم ژنتیکی متعارف 12
معیارهای ارزیابی روش های انتخاب 13
انتخاب 14
انتخاب مبتنی بر شایستگی 15
انتخاب مبتنی بر رتبه 21
انتخاب مبتنی بر پایداری 24
انتخاب مبتنی بر تورنمنت 25
1-3-بخش های الگوریتم ژنتیک 25
جمعیت 25
فهرست مطالب
عنوان شماره صفحه
________________________________________
کروموزوم 26
کدگذاری 27
انتخاب 27
جابجایی(Crossover) 28
جهش(Mutation) 36
تابع هزینه 40
فصل2-فصل دوم:مسئله فروشنده دوره گرد
2-1- تعریف مساله فروشنده دوره گرد 42
2-2- حل مسأله بهينه سازي با استفاده از الگوريتم هاي تكاملي 43
تعین جواب 43
تولید جمعیت اولیه 44
ارزسابی جواب های تولید شده 45
انتخاب والدین 46
تولید فرزندان از والدین انتخاب شده 46
انتخاب بازماندگان 48
تکرار الگوریتم تا رسیدن به یک شرط خاتمه 49
تمرین فروشنده دوره گرد با استفاده از الگوریتم ژنتیک 49
نتیجه گیری 75
مراجع 76
فهرست شکل ها
عنوان شماره صفحه
________________________________________
شکل1:ساختار چرخ رولت 16
شکل2:پیاده سازی عملگر انتخاب چرخ رولت 17
شکل3:مثال چرخ رولتn=6 18
شکل4:مقیاس گذاری power law 20
شکل5:ساختار کروموزوم 26
شکل6:یک قسمت از شبکه نمونه 27
شکل7:جابجایی تک نقطه ای 28
شکل8:جابجایی دو نقطه ای 28
شکل9:بازترکیبی اعداد حقیقی 30
شکل10:بازترکیبیsimple arithmetic 30
شکل11:بازترکیبی ارائه جایگشتی 31
شکل12:بازترکیبی مرتبه یک 32
شکل13:بازترکیبی PMX 33
شکل14:بازترکیبی حلقه 34
شکل15:اعمال عملگر جهش بر روی یک کروموزوم 37
فهرست شکل ها
عنوان شماره صفحه
________________________________________
شکل16:جهش بیتی 38
شکل17:جهش درج 39
شکل18:جهش تعویض 39
شکل19:جهش عکس 39
شکل20:جهش scramble 39
فهرست نمودار
عنوان شماره صفحه
________________________________________
نمودار1:احتمال افراد بر اساس شایستگی 16
نمودار2:تابع 43
نمودار3:تابع و فضای راه حل 44
نمودار4:تابع ارزیابی شایستگی 45
نمودار5:نتیجه تولید نسل 48
نمودار6:اعمال جهش swap 55
نمودار7:اعمال roulette wheel وFlip 56-57
نمودار8:اعمال Tournament 63-58
نمودار9:اعمالTruncation 66-64
نمودار10:اعمال TruncationوFlip 68-66
نمودار11:اعمال Tournament وFlip 71-68
نمودار12:اعمال TruncationوFlip 74-72
فهرست جداول
عنوان شماره صفحه
________________________________________
جدول1:رتبه بندی خطی 23
جدول2:بازترکیبی لبه 35
جدول3:انتخاب والدین 46
جدول4:اعمال باز ترکیبی بر روی والدین انتخابی 47
جدول5:اعمال جهش بر روی فرزندان 47
جدول6:نتیجه تولید نسل 48