یکشنبه 30 شهریور 1399 | Sunday 20 th of September 2020 صفحه اصلی گروه الکترونیکی کامپیوتر
روش های پیاده سازی عملگر ترکیب

1.     ترکیب تک نقطه­ای[1] :

این نوع ترکیب، دو کروموزوم را با انتخاب تصادفی موقعیتی مانند Pترکیب می­کند که Pمقداری کمتر یا مساوی طول کروموزوم­ها است. اگر تعداد (طول) ژن­ها در کروموزوم­ها Nباشد، از دو کروموزوم والد، دو فرزند به صورت زیر به وجود می­اید.

یک فرزند با کپی کردن ژن­های 1,…,(P-1)از کروموزوم والد اول و ژن­های P,…,Nاز کروموزوم والد دوم ساخته می­شود. فرزند دیگر به طور مشابه، این بار با کپی کردن ژن­های 1,…,(P-1)از کروموزوم والد دوم و ژن­های P,…,Nاز کروموزوم والد اول به وجود می­اید. در این ترکیب از دو والد، دو فرزند به وجود می­اید.
نحوه این نوع ترکیب و مثالی از ان با P=4در شکل­های زیر، نشان داده شده است.

شکل 7- ترکیب تک نقطه­ای

لازم به ذکر است اگر Pبرابر 1یا طول کروموزوم­ها شود، ان گاه دو والد بدون تغییر وارد جمعیت بعدی می­شوند.

2.     ترکیب دو نقطه­ای :

در ترکیب دو نقطه­ای، دو موقعیت P1و P2 به عنوان موقعیت­های ترکیب[2] ، به طور تصادفی بین 1و طول کروموزوم­ها (N)انتخاب می­شود. روش ایجاد فرزندان مانند ترکیب تک نقطه­ای است.

فرزند اول، ژن­های 1,…,(P1-1)را از والد اول، ژن­های P1,…,(P2-1)را از والد دوم و ژن­های P2,…,Nرا مجددا از والد اول به ارث می­برد.

فرزند دوم، ژن­های 1,…,(P1-1)را از والد دوم، ژن­های P1,…,(P2-1)را از والد اول و ژن­های P2,…,Nرا مجددا از والد دوم به دست می­اورد.


در این روش ترکیب نیز از یک جفت والد، دو فرزند به وجود می­اید. در شکل­های زیر، نحوه این نوع ترکیب و مثالی از ان را با P1=2و P2=5مشاهده می­کنید.


شکل 8- چگونگی ترکیب دو نقطه ای

شکل 8- چگونگی ترکیب دو نقطه­ای

در این روش احتمال اینکه والدها بدون تغییر وارد جمعیت بعدی شوند، کمتر است.

شکل 9- ترکیب دو نقطه­ای

3.     ترکیب یکنواخت[3] :

در این نوع ترکیب، هر ژن کروموزوم جدید به صورت جداگانه انتخاب می­شود. هر ژن وابسته به موقعیتش، به صورت تصادفی از یکی از دو والد انتخاب می­شود. بر خلاف ترکیب­هایی که قبلا ذکر شد، این ترکیب یک فرزند به وجود می­اورد.
جمعیت جدیدی که با ترکیب یکنواخت به وجود می­اید، دارای تنوع ژنتیکی بیشتری نسبت به ترکیب­های تک نقطه­ای و دو نقطه­ای می­باشد. به همین دلیل، این نوع ترکیب در جمعیت­هایی که اعضای کمتری دارند، اثر بهتری دارد تا جمعیت­هایی که تعداد اعضای زیادی دارند.

شکل 10- چگونگی ترکیب یکنواخت

شکل 10- چگونگی ترکیب یکنواخت

4.     ترکیب حسابی[4] :

در این نوع ترکیب، فرزندان با توجه به قواعد و دستورات ریاضی خاصی مانند Andو غیره تولید می­شوند. اگر Aو Bدو عضو از جمعیت فعلی باشند که به عنوان والد انتخاب شده­اند، از ان­ها دو فرزند aو bبه صورت زیر به وجود می­اید.

رابطه (3)                                                                        a = dA + (1- d) B

                                                                                            b = dB + (1- d) A

پارامتر dمقداری در بازه [0,1]می­باشد که در هر ترکیب می­تواند مقدار مختلفی داشته باشد.

شکل 11- چگونگی ترکیب یکنواخت

شکل 11- چگونگی ترکیب یکنواخت 

4)    Mutation

جهش نیز عملگر دیگری است که جواب­های ممکن دیگری را متولد می­کند. در الگوریتم ژنتیک بعد از این که یک عضو در جمعیت جدید به وجود امد، هر ژن ان با احتمال جهش، جهش می­یابد. در جهش ممکن است ژنی از مجموعه ژن­های جمعیت حذف شود یا ژنی که تا به حال در جمعیت وجود نداشته است، به ان اضافه شود. جهش یک ژن به معنای تغییر ان ژن است و بسته به نوع کدگذاری، روش­های متفاوت جهش استفاده می­شود. می­توان استنباط کرد که مهم­ترین وظیفه جهش، اجتناب از همگرایی به بهینه محلی است.

احتمال جهش، Pmمقداری است که توسط کاربر تعیین می­شود. بهتر است Pmرا به صورت زیر تخمین زد:

رابطه (4)                                                                                            n  1 =   Pm 

که در ان Nتعداد ژن­های کروموزوم است. در هر حال Pm  مقداری بین 0و 1است و معمولا عددی کوچک انتخاب می­شود.

در فرزندی که توسط ترکیب به وجود امده است، به هر ژن مقداری تصادفی بین 0و 1اختصاص می­یابد. اگر این مقدار اختصاص داده شده کمتر از Pmباشد، ژن جهش می­یابد و اگر بیشتر باشد، ژن تغییر نمی­کند.

نرخ بالای جهش، باعث تنوع و پراکندگی ژنتیکی در جمعیت می­شود که این پراکندگی ممکن است همگرایی را به تاخیر بیندازد. به همین دلیل پیشنهاد می­شود برای جمعیت­های بزرگ یا در نسل­های اخر، از Pmهای کوچکتر و برای جمعیت­های کوچک یا در نسل­های ابتدایی از Pmهای بزرگتر استفاده شود.


[1]one-point crossover

[2]Crossover Point

[3] Uniform Crossover

[4]Arithmetic Crosssover

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