دانلود فایل های پایان نامه با موضوع ارائه مدل بهبود یافته حمل و نقل با در ... |
فلوچارت الگوریتم ژنتیک به طور کلی به صورت زیر است:
شکل ۴-۶- فلوچارت الگوریتم ژنتیک
تولید جوابهای اولیه:
تولید جوابهای اولیه در این الگوریتم بطور تصادفی صورت می گیرد.
نحوه انتخاب والدین:
در این پایان نامه برای انتخاب والدین از روش انتخاب چرخ رولتی استفاده شده است. انتخاب چرخ رولت که اولین بار توسط «هولند» پیشنهاد شد یکی از مناسبترین انتخابهای تصادفی بوده که ایدۀ آن، احتمال انتخاب میباشد. احتمال انتخاب متناظر با هر کروموزوم، براساس برازندگیِ آن محاسبه شده که اگر مقدار برازندگی کروموزوم k ام باشد، احتمال بقای متناظر با آن کروموزوم عبارت است از:
(۴-۳)
حال کروموزومها را براساس مرتب کرده و که همان مقادیر تجمعی می باشد که به صورت زیر به دست میآید:
(۴-۴)
چرخ رولت به این صورت عمل میکند که برای انتخاب هر کروموزوم یک عدد تصادفی بین یک و صفر تولید کرده و عدد مذکور در هر بازهای که قرار گرفت، کروموزوم متناظر با آن انتخاب میشود. البته روش پیادهسازی چرخ رولت به این شکل است که ما یک دایره را در نظر گرفته و آن را به تعداد کروموزومها طوری تقسیم میکنیم که هر بخش متناظر با مقدار برازندگی کروموزوم مربوط باشد، حال چرخ را چرخانده و هر کجا که چرخ متوقف شد به شاخص چرخ نگاه کرده، کروموزوم مربوط به آن بخش انتخاب میگردد.
شکل ۴-۷- چرخ رولت.
انتخاب چرخ رولت، روشی است که نسبت مقدار تطابق، اعضاء را انتخاب میکند. این روش یک چرخ رولت را شبیهسازی میکند تا تعیین کند کدام اعضاء شانس باز تولید را دارند.
هر عضو به نسبت تطابقش، تعدادی از بخشهای چرخ رولت را به خود اختصاص میدهد. سپس در هر مرحله انتخاب یک عضو برگزیده میشود و روند آنقدر تکرار میشود تا به اندازه کافی، جفت برای تشکیل نسل بعد انتخاب گردد.
عملگر جهش:
برای پیاده سازی عملگر جهش مورد استفاده الگوریتم ژنتیک در این کار یک عدد تصادفی مانند h بین ۱ تا ۴ تولید می شود و سپس h امین جستجوی محلی (از بین ۴ عملگر شرح داده شده) بر روی جواب اعمال می شود.
عملگر تقاطع:
عملگر تقاطع طراحی شده در این الگوریتم، یک عملگر تقاطع تک نقطه ای می باشد. پس از اینکه دو والد انتخاب شده بعنوان ورودی به عملگر تقاطع داده شدند، ۴ ماتریس مکانیابی هر والد برای عمل تقاطع بصورت نظیر به نظیر انتخاب خواهند شد. در ادامه مثالی از نحوه عملکرد تقاطع تک نقطه ای شرح داده می شود.
تقاطع تک نقطه ای: فرض کنید دو ماتریس مقابل و اندیس ۳ بعنوان ورودی تقاطع تک نقطه ای باشند:
۱ | ۱ | ۰ | ۰ | ۱ | ۰ | ۱ | ۰ |
۰ | ۱ | ۰ | ۱ | ۰ | ۰ | ۱ | ۱ |
این دو ماتریس والد ۱ و والد ۲ هستند، حال دو فرزند با بهره گرفتن از تقاطع تک نقطه ای بصورت زیر از این دو والد ایجاد می شود. ۳ خانه اول والد اول توسط فرزند اول به ارث برده می شود و همچنین فرزند اول ۵ خانه آخرش را از والد دوم می گیرد. فرزند دو نیز مانند فرزند اول تشکیل می شود با این تفاوت که سه خانه اول را از والد دوم و ۵ خانه آخر را از والد اول به ارث می برد.فرزند اول مطابق ماتریس زیر خواهد بود.
فرم در حال بارگذاری ...
[یکشنبه 1400-08-16] [ 07:16:00 ق.ظ ]
|