جمعه 31 فروردین 1397 | Friday 20 th of April 2018 صفحه اصلی گروه الکترونیکی کامپیوتر
3-3-2-3- انتخاب، ادغام و جهش

بعد از اینکه میزان سودمندی هر کروموزوم در جمعیت محاسبه شد، GPبه طور احتمالی برنامه های بهتر را از بین جمعیت انتخاب می کند، تا به عنوان والد نسل بعد را ایجاد کنند. عملگر های ژنتیکی بر روی کروموزوم های انتخاب شده  اعمال می شوند تا فرزندان جدید را ایجاد کنند. یعنی ضمانتی برای انتخاب بهترین کروموزوم در جمعیت وجود ندارد. همچنین بدترین کروموزوم ها لزوماً دور انداخته نمی شوند.

در این مثال، ما با یک عملگر باز ترکیب شروع خواهیم کرد. اولین کروموزوم بهترین و مناسب ترین

کروموزوم در جمعیت می باشد، به همین خاطر احتمال اتخاب شدن ان برای شرکت در اعمال ژنتیکی بالا

خواهد بود.

 شکل 3-8 جمعیت نسل جدید

شکل 3-8 جمعیت نسل جدید

فرض کنید ما با تولید عدد تصادفی بعد از طی فرایند انتخاب کروموزوم اول را برای عمل بازترکیب برگزیده ایم. بنابراین، این کروموزوم بدون هیچ تغییری در جمعیت نسل بعد (نسل 2) کپی می شود. در شکل(3-8) این کروموزوم به عنوان یکی از کروموزوم های نسل بعدی دیده می شود.

در مرحلۀ بعد عملگر جهش را اجرا می کنیم. به خاطر اینکه عمل انتخاب احتمالی می باشد، در نتیجه ممکن است که سومین کروموزوم شکل(3-6-c) از نظر برتری انتخاب شود. عمل جهش به این صورت انجام میشود:

یکی از سه گرۀ این کروموزوم به تصادف پاک می شود؛ به عنوان نقطۀ جهش؛ در این برنامه گرۀ پایانۀ 2 پاک می شود. سپس برنامه به طور تصادفی با جایگزین کردن یک زیر درخت؛ که تصادفی ایجاد شده است؛ به جای زیر درختی که با نقطۀ جهش ریشه دار شده است، عمل جهش را انجام می دهد. توجه داشته باشید زیر درخت تصادفی را مانند درخت هایی که برای جمعیت اولیه به تصادف ایجاد می کردیم، ایجاد می شوند.

در این مثال خاص، زیر درخت تصادفی ایجاد شده، xتقسیم بر x  می باشد که  عمل تقسیم توسط تقسیم محافظت شده % انجام می شود. نتیجه در شکل (3-8-b) دیده می شود. این جهش خاص کروموزوم را از داشتد یک مقدار ثابت 2 به یک مقدار ثابت 1 تغییر می دهد. در نتیجه سودمندی ان از 18 به 11 می رسد.

در اخر، از عملگر ادغام  برای ایجاد 2 کروموزوم اخر نسل بعد، استفاده می کنیم. چون اولین و دومین کروموزوم ها در نسل قبلی نسبت به دیگر کروموزوم ها بهتر بودند، در نتیجه احتمال بیشتری برای انتخاب انها برای عمل ادغام وجود دارد، اما نباید فراموش کنیم که ما رهیافت حیصانه را در پیش نگرفته ایم. و احتمالی هم برای انتخاب کروموزوم های بد وجود دارد. بنابراین فرض کنید برای شرکت در عمل ادغام، کروموزوم شکل(3-6-a) که میزان تابع سودمندی ان (خطاهای ان) از میانگین سودمندی ها کمتر است، به همراه کروموزوم شکل(3-6-d) که میزان تابع سودمندی ان (خطاهای ان) از میانگین سودمندی ها بیشتر است، به عنوان دو والد انتخاب کنیم.

یک نقطه از والد 1 که تابع + می باشد، به تصادف به عنوان نقطۀ ادغام انتخاب می شود. وهمچنین در والد 2، اخرین پایانه سمت چپ (x) به تصادف به عنوان نقطۀ ادغام انتخاب می شود. بنابراین زیر درخت های مربوط به هر دو والد که توسط نقطۀ ادغام ریشه دار شده است، در هر دو جابجا می شوند. که نتیجۀ این ادغام کروموزوم سوم از نسل 2 در شکل(3-8-c) می باشد، که معادل است با xکه خیلی نتیجۀ مناسبی نمی باشد.اجازه بدهید فرض کنیم در دومین عمل ادغام عملگر انتخاب 2 تا از بهترین کروموزوم ها یعنی کروموزوم 1 و 2 را برای عمل ادغام انتخاب کرده است. که کروموزوم (3-6-a) را والد 1 و کروموزوم(3-6-b) را والد 2 می نامیم.

و همچنین تصور کنید که نقطۀ ادغام در والد 2، سمت چپ ترین پایانه از والد 2  یعنی پایانۀ 1 باشد. و نقطۀ ادغام در والد 1 گرۀ مربوط به تابع + می باشد. در نتیجۀ عمل ادغام، فرزند نتیجه با x2+x+  معادل خواهد بود.که میزان تابع سودمندی ان (مجموع خطاهای مطلق) صفر می باشد. 

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26