شنبه 30 تیر 1397 | Saturday 21 st of July 2018 صفحه اصلی گروه الکترونیکی کامپیوتر
1-3-5- انتخاب والد برای ایجاد نسل بعد

     در این قسمت به توضیح تعدادی از روش های انتخابی، می پردازیم.

  1. روش انتخاب طبیعی

  در این روش که بر مبنای فلسفۀ انتخاب اصلح می باشد، اول جمعیت کروموزوم ها را از کمترین تا بیشترین هزینه رتبه بندی می شود، سپس تنها بهترین کروموزوم ها به عنوان والد انتخاب و بقیه حذف

می شوند.تعداد کروموزوم های انتخاب شده،کسری از Npop  می باشد که از فرمول زیر بدست می اید:

(1-12)

Nkeep = Npop × Xrate

  Xrate   میزان انتخاب می باشد، که عددی بین صفر و یک است. و Nkeepنیز تعداد کروموزوم هایی است که به عنوان والد نگهداری می شود. در نتیجۀ این روش انتخاب کروموزوم های دارای بهترین خصوصیات باقی می مانند و کروموزوم های باهزینه های بالاتر در GAاز بین می روند.

تصمیم در مورد اینکه چه تعداد کروموزوم نگهداری شود، مساله ای اختیاری است. اگر اجازه دهیم فقط تعداد کمی کروموزوم، برای نسل بعدی باقی بمانند، ژن های در دسترس برای نسل بعدی را محدود کرده ایم. از طرفی نگهداری تعداد زیادی کروموزوم، اجازه می دهد کروموزوم های بد، شانسی برای شرکت دادن ویژگی هایشان به نسل بعد داشته باشند. . ما اغلب 50% از کروموزوم ها را در فرایند انتخاب طبیعی نگه می داریم. در مثال ما که مقدار Npop، 4 می باشد. نتایج این نوع انتخاب در جدول (1-2) نشان داده شده است. توجه کنید که کروموزوم های جدول (1-2)، از کم ارزش ترین کروموزوم ها می باشند.

جدول 1-2- کروموزوم های انتخابی

                          جدول 1-2- کروموزوم های انتخابی

  1. انتخاب از بالا به پایین

از بالای لیست شروع می شود و کروموزوم ها هر دفعه دو بار جفت گیری می کنند، تا زمانی که تمام Nkeepکروموزوم برای اتصال به یکدیگر انتخاب شده باشند . بنابراین مطابق الگوریتم، سطرهای فرد با سطرهای زوج جفت گیری می کنند . مادر سطرهایی در ماتریس جمعیت داده شده با شماره هایma = 1,3, …را دارد ؛ و پدر سطرهای شماره pa = 2,4, …را . این رویکرد مدل طبیعی خوبی ندارد، اما برای برنامه نویسی خیلی ساده است و یک مورد خوب برای شروع تلاش های بعدی است .

  1. جفت گیری تصادفی

این رویکرد، تعدادی مولد تصادفی یکنواخت را برای انتخاب کروموزوم ها انتخاب می کند . تعداد سطرهای والدین با استفاده از فرمول زیر پیدا می شود : 

(1-13)

ma = ceil (Npop  *  rand ( 1 , Nkeep ) )

 

(1-14)

Pa = ceil (Npop  *  rand ( 1 , Nkeep ) )

که ceil()، یک مقدار را به بزرگترین عدد صحیح بعدی گرد می کند .

  1. روشانتخابرقابتی یا تورنومنت[1]

    یک روش دیگر برای پیدا کردن پدر و مادر این است که تعداد Nkeep  مجموعه که در هرکدام Nt  کروموزوم  به تصادف قرار گرفته است، تولید می کنیم. Nt  عددی دلخواه می باشد، که بهتر و معمول است که مقدار ان  2، 3 و یا 4 باشد. در هر مجموعه کروموزوم ها بر اساس هزینه شان به رقابت می پردازند، و در اخر کروموزومی پیروز و انتخاب می شود که از هزینۀ کمتری برخوردار باشد. در نتیجه Nkeep  کروموزوم برگزیده به عنوان والد به مرحلۀ بعد می روند.

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

  1. روش انتخاب وزن دهی شده

      در این روش به هر کروموزوم یک وزنی داده می شود، و بعد عدد تصادفی تعیین می کند که چه کروموزومی انتخاب شود. توجه داشته باشید که کروموزوم هایی که وزن بیشتری دارند احتمال بیشتری برای انها وجود دارد که انتخاب شوند. در این روش 2 تکنیک وجود دارد:

  1. وزن دهی بر اساس رتبه[2]

   این روش مستقل از مسئله می باشد و احتمال انتخاب یک کروموزوم به رتبه ای که در بین دیگر کروموزوم ها دارد وابسته است. کروموزومی که رتبۀ بالاتر داشته باشد، احتمال انتخاب ان بیشتر است.

(1-15)

                                                                           

جدول1-3 ، نتایج را برای  Npopکرومزوم از مثال ما نشان می دهد. احتمال های تجمعی که در ستون 4 لیست شده اند، در انتخاب کروموزوم ها استفاده شده اند. برای انتخاب، یک عدد تصادفی بین صفر و یک تولید می کنیم، از بالای لیست شروع می کنیم، اولین کرومزومی که احتمال تجمعی ان از عدد تصادفی بزرگتر است، برای جفت گیری انتخاب می شود . برای مثال اگر عدد تصادفی r = 0.577باشد، درنتیجه کروموزوم دوم به عنوان والد انتخاب می شود. اعداد تصادفی باید به تعداد Nkeep تولید شود.

جدول 1-3- احتمال تجمعی کروموزوم ها

 جدول 1-3- احتمال تجمعی کروموزوم ها

  • وزن دهی براساس هزینه یاروش چرخ رولت[3]

ر این روش به جای رتبه از هزینۀ کروموزوم ها به عنوان وزن شان استفاده می کنیم. جمعیت را مرتب

می کنیم، هزینۀ مربوط به هر کروموزوم را به صورت زیر نرمال می کنیم:

جدول 1-4- احتمال اننتخاب هر کروموزوم بر مبنای هزیۀ ان

 

 

 (1-16 

احتمال مربوط به هر کدام را از روش زیر بدست می اوریم، و می توان مانند روش قبل با محاسبۀ احتمال تجمعی و تولید عدد تصادفی والد ها را انتخاب کرد.[5]


[1]Tournament Selection

[2]Rank weighting

[3]Roulette wheel 

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