سایت دانشجو سرا

 الگوریتم ژنتیک و تکنیک جستجو در علم رایانه برای یافتن راه حل تقریبی برای بهینه سازی مسائل و حل مسئله فروشنده دوره گرد به کمک آن

 

 

توجه داشته باشید: درصورتی که شما صاحب اثر این فایل می باشید یا به هر دلیلی نسبت به فایل تحقیقاتی مذکور در این پست مالکیت معنوی دارید و درخواست حذف آن را دارید، در واتس آپ به شماره 09100636002 پیام دهید تا ظرف 24 ساعت نسبت به حذف فایل از روی سایت دانشجوسرا اقدام شود. در صورت تمایل و درخواست، دو مقاله به صورت رایگان (به نام پژوهشگر و دانشجو) در مجلات علمی معتبر پذیرش شده و چاپ می گردد. ((حفظ حقوق معنوی صاحب اثر در اولویت فعالیت سایت دانشجوسرا می باشد))

 

 

 

مقدمه:

الگوريتم هاي ژنتيكي خانواده اي از مدل هاي محاسباتي مي باشند كه توسط تحويل تدريجي بوجود آمده اند . اين الگوريتم ها يك راه حل بالقوه براي يك مسئله مخصوص در ساختار داده هاي به شكلي كروموزومي ساده رمزگذاري مي كند و اپراتورهاي دوباره تركيب شده را در اين ساختارها بكار مي برد تا اينكه از اطلاعات مهم و حياتي حفاظت كند .

بكارگيري الگوريتم ژنتيكي با جمعيت ( نوعاً تصادفي ) كروموزوم ها شروع مي شود . پس مي توان اين ساختارها را ارزيابي كرد و فرصت هاي آوايي را به گونه اي مشخص نمود كه آ« كروموزوم هايي كه راه حل بهتري نسبت به مسئله مورد نظر ارائه مي كنند . شانس بيشتري نسبت به ديگر كروموزم ها داشته باشندتا تكثير شوند . كارايي يك راه حل نوعاً با توجه به جمعيت حاضر ارزيابي مي شود . اين توصيف مخصوص از الگوريتم ژنتيكي عملاً انتزاعي مي باشد زيرا از چند نظر ، واژه الگوريتم ژنتيكي دو معني دارد . در يك تفسير دقيق (‌سختگيرانه ) ، الگوريتم ژنتيكي مربوط به مدلي مي شود كه توسط جان هالِند ( 1975 ) ودانشجويانش معرفي و بررسي شد . هنوز همان موردي است كه بيشتر تئوري هاي موجود براي الگوريتم هاي ژنتيكي اساساً و يا تنها براي مدل معرفي شده توسط هالند بكار مي روند همانطور كه انواع مختلف اشاره شده در اين مقاله بعنوان الگوريتم ژنتيكيبه كار مي روند .

پيشرفت هاي تئوريكي اخير مدلسازي الگوريتم ژنتيكي همچنين اساساً الگوريتم ژنتيكيرا بكار مي برند.

در كاربرد گسترده تر اين واژه ، يك الگوريتم ژنتيكي عبارتست از هر نوع مدل وابسته به جمعيت كه از انتخاب و اپراتورهاي دوباره تركيب يافته استفاده مي كند تا نقاط ساده جديد در فضاي تحقيق بوجود آورد . بسياري از مدل هاي الگوريتم ژنتيكي توسط محققاني ارائه شده اند كه عمدتاً‌از يك ديدگاه تجربي كار مي كرده اند . بسياري از اين محققان كاربرد محور مي باشند و نوعاً علاقه مند به الگوريتم هاي ژنتيكي بعنوان ابزارهاي بهينه سازي مي باشند.

 

ﭼﮑﻴﺪﻩ ﻣﻘﺎﻟﻪ :

در اﻳﻦ ﻣﻘﺎﻟﻪ اﺑﺘﺪا اﻟﮕﻮرﻳﺘﻤﻬﺎﯼ ژﻧﺘﻴﮏ را ﻣﻌﺮﻓﯽ ﮐﺮدﻩ و ﻣﺮاﺣﻞ اﻧﺠﺎم ﭼﻨﻴﻦ اﻟﮕﻮرﻳﺘﻤﻬﺎﻳﯽ ﺗﻮﺿﻴﺢ دادﻩ ﻣﯽ ﺷﻮد. ﺑﻌﺪ از اﻳﻨﮑﻪ ﻳﮏ‫دﻳﺪ ﮐﻠﯽ ﻧﺴﺒﺖ ﺑﻪ اﻟﮕﻮرﻳﺘﻤﻬﺎﯼ ژﻧﺘﻴﮏ ﭘﻴﺪا ﮐﺮدﻳﻢ ﺑﻪ ﻣﺴﺎﻟﻪ ‪Traveling Salesman Problemﻣﯽ ﭘﺮدازﻳﻢ. اﺑﺘﺪا ﭼﻨﺪ روﺷﯽ ﮐﻪ ﺑﺮاﯼ ﺣﻞ ‪TSP‫اراﺋﻪ ﺷﺪﻩ اﺳﺖ را ﺑﻴﺎن ﻣﯽ ﮐﻨﻴﻢ و ﺑﻌﺪ ﺳﻌﯽ ﻣﯽ ﮐﻨﻴﻢ اﻟﮕﻮرﻳﺘﻤﻬﺎﯼ ژﻧﺘﻴﮏ ﻣﺨﺘﻠﻔﯽ را ﺑﺮاﯼ اﻳﻦ ﻣﺴﺎﻟﻪ ﻣﻄﺮح ﮐﻨﻴﻢ و ﺳﭙﺲ ﺑﺮرﺳﯽ ﻣﯽ ﮐﻨﻴﻢ ﮐﻪ ﮐﺪام‫ﻳﮏ از اﻳﻦ اﻟﮕﻮرﻳﺘﻤﻬﺎﯼ ژﻧﺘﻴﮏ ﺑﻬﺘﺮ از ﺑﻘﻴﻪ روﺷﻬﺎ ﺟﻮاب ﻣﯽ دهﻨﺪ.

 

 

فهرست مطالب

عنوانشماره صفحه

مقدمه 9

فصل 1-فصل اول: الگوریتم ژنتیک چیست؟ 12

1-1-مقدمه ای برالگوریتم ژنتیک 12

الگوریتم ژنتیک چیست؟ 15

رمزگذاری و کارکرد ارزشیابی در الگوریتم ژنتیک 19

1-2-ساختار الگوریتم ژنتیک 21

الگوریتم ژنتیکی متعارف 21

معیارهای ارزیابی روش های انتخاب 22

انتخاب 23

انتخاب مبتنی بر شایستگی 24

انتخاب مبتنی بر رتبه 30

انتخاب مبتنی بر پایداری 33

انتخاب مبتنی بر تورنمنت 33

1-3-بخش های الگوریتم ژنتیک 34

جمعیت 34

 

فهرست مطالب

عنوان شماره صفحه

کروموزوم 35

کدگذاری 36

انتخاب 36

جابجایی(Crossover) 37

جهش(Mutation) 45

تابع هزینه 49

فصل2-فصل دوم:مسئله فروشنده دوره گرد 51

2-1-تعریف مسالهفروشندهدورهگرد 51

2-2-حل مسأله بهينه سازي با استفاده از الگوريتم هاي تكاملي 52

تعین جواب 52

تولید جمعیت اولیه 54

ارزسابی جواب های تولید شده 54

انتخاب والدین 55

تولید فرزندان از والدین انتخاب شده 56

انتخاب بازماندگان 57

تکرار الگوریتم تا رسیدن به یک شرط خاتمه 58

2-3-تمرین فروشنده دوره گرد با استفاده از الگوریتم ژنتیک 58

نتیجه گیری 85

مراجع 86

 

فهرست شکل ها

عنوان شماره صفحه

شکل1:ساختار چرخ رولت 25

شکل2:پیاده سازی عملگر انتخاب چرخ رولت 26

شکل3:مثال چرخ رولتn=6 27

شکل4:مقیاس گذاری power law 29

شکل5:ساختار کروموزوم 35

شکل6:یک قسمت از شبکه نمونه 36

شکل7:جابجایی تک نقطه ای 37

شکل8:جابجایی دو نقطه ای 37

شکل9:بازترکیبی اعداد حقیقی 39

شکل10:بازترکیبیsimple arithmetic 40

شکل11:بازترکیبی ارائه جایگشتی 41

شکل12:بازترکیبی مرتبه یک 41

شکل13:بازترکیبی PMX 42

شکل14:بازترکیبی حلقه 43

شکل15:اعمال عملگر جهش بر روی یک کروموزوم 46

فهرست شکل ها

عنوان شماره صفحه

شکل16:جهش بیتی 48

شکل17:جهش درج 48

شکل18:جهش تعویض 49

شکل19:جهش عکس 49

شکل20:جهش scramble 49

 

فهرست نمودار

عنوان شماره صفحه

نمودار1:احتمال افراد بر اساس شایستگی 25

نمودار2:تابع 53

نمودار3:تابع و فضای راه حل 53

نمودار4:تابع ارزیابی شایستگی 55

نمودار5:نتیجه تولید نسل 58

نمودار6:اعمال جهش swap 64-65

نمودار7:اعمالroulette wheel وFlip 66

نمودار8:اعمال Tournament 67-73

نمودار9:اعمالTruncation 45-76

نمودار10:اعمال TruncationوFlip 76-78

نمودار11:اعمال Tournament وFlip 78-82

نمودار12:اعمال TruncationوFlip 82-84

 

 

فهرست جداول

عنوان شماره صفحه

جدول1:رتبه بندی خطی 32

جدول2:بازترکیبی لبه 45

جدول3:انتخاب والدین 55

جدول4:اعمال باز ترکیبی بر روی والدین انتخابی 56

جدول5:اعمال جهش بر روی فرزندان 57

جدول6:نتیجه تولید نسل 57

 

 

توجه داشته باشید: درصورتی که شما صاحب اثر این فایل می باشید یا به هر دلیلی نسبت به فایل تحقیقاتی مذکور در این پست مالکیت معنوی دارید و درخواست حذف آن را دارید، در واتس آپ به شماره 09100636002 پیام دهید تا ظرف 24 ساعت نسبت به حذف فایل از روی سایت دانشجوسرا اقدام شود. در صورت تمایل و درخواست، دو مقاله به صورت رایگان (به نام پژوهشگر و دانشجو) در مجلات علمی معتبر پذیرش شده و چاپ می گردد. ((حفظ حقوق معنوی صاحب اثر در اولویت فعالیت سایت دانشجوسرا می باشد))