مقاله درباره ، كروموزوم، پيوند، باينري، برازندگي، x1، كروموزومها، ش2

دانلود پایان نامه

مورد اعداد اعشاري بايد ابتدا آنها را با ضرب در يك عدد به عدد صحيح تبديل كرده و سپس به باينري تبديل كرد.
2-1-2-3 توليد جمعيت اوليه
پس از تعين طول كروموزوم بايد آنرا به طور اتفاقي از 0 و 1 پركنيم. اينكار بهوسيله دستور زیر انجام ميشود:
L= round (rand)
با توجه به اینکه تعداد تركيبهاي جايگيري 0 و 1 براي كروموزوم به طول L برابر است با لذا بهتر است تعداد كروموزومهاي يك جمعيت را، از تعداد تركيبهاي نشستن صفر و يكها در يك كروموزوم بيشتر نگيريم، چرا كه در بعضي از كروموزومها به ناچار تكرار ميگردند.
مقدار بهينه تعداد كروموزومها در يك جمعيت بهطور تقريبي از رابطه npop=1.65*20.21 L بهدست میآید که در آن L، طول رشته است.
فرض كنيد براي یک تابع دومتغيره5 كروموزوم با تعداد 10ژن در هركدام انتخاب كردهايم. مانند جدول (2-1)

جدول 2-1: تشکیل کروموزمx2x1كروموزم ش 1 0 0 1 1 1 0 0 1 0 1
ادامه جدول 2-1: تشکیل کروموزم
x2x1كروموزم ش2 0 1 1 1 1 0 0 1 1 1
كروموزم ش3 0 0 1 0 1 0 0 1 1 0
كروموزم ش4 1 1 0 1 0 1 1 0 0 0
كروموزم ش5 0 1 0 1 0 1 1 0 1 0
در جدول (2-1)، 5 بيت اول هر كروموزوم، مربوط به مقدار باينري x1 و 5 بيت دوم هر كروموزوم مربوط به مقدار باينريx2 ميباشد.
2-2-2-4 تبدیل کروموزمها به اعدادی در بازهی دامنهی همان متغیرهااگر محدوده متغيرx1 برابر است با: ≤ b x1 ≥ a بايد 0 و 1 هاي كروموزوم را به اعدادي در بازهی مورد نظر تبديل كنيم. فرض كنيد يك تكه ژني از كروموزومي به طول L را كه متعلق بهx1 است ميخواهيم به بازه a≤x1≤b تبديل كنيم. اگر ∝=5. كوچكترين عددي كه با 5 ژن در مبناي 2 ميتوان ساخت بهصورت زیر است:
0 0 0 0 0

كوچكترين عدد از بردن يك تكه كروموزوم ژني به مبناي 10 برابر است با:
u=0*20+0*21+0*22+…+0*2∝-1=01 1 1 1 1
بزرگترين عددي كه در 5 ژن از يك كروموزوم ميتوان داشت برابر است با:
و با بردن بزرگترین كروموزوم ∝ژني به مبناي 10 داريم:
u=1*20+1*21+1*22+…+1*2∝-1=2∝-1تمامي جايگشتهاي 0 و 1 در يك بايت ∝ بيتي ميتوانند اعدادي بين 0 تا 2∝-1 در مبناي 10 توليد كند. در حاليكه مجموعه x1 ما اعدادي در بازه a تا b ميخواهد. تبديل اين دو مجموعه بهوسيله نگاشت انجام ميشود. نگاشت خطي كه بازهها را بههم تبديل مي كند. (u یک عدد در مبنای 10 است).
0,2∝-1r=c1+c2ua,bu=0 , r=a →c1=au=2l-1 , r=b →c2=b-a2∝-1⇒r=a+b-a2∝-1*uبههمين ترتيب ميتوانيم براي x2با دامنه مختص به خودش نگاشتي بنويسيم و اعداد باينري هر متغير را به مقداري در مبناي 10 در بازه مجاز همان متغير تبديل كنيم.
جدول2-2: مثالی از تبدیل کد گذاریمتغير x1 متغير x2
كروموزم ش 1 0 1 1 0 0 1 1 1 0 1
مقداردرمبناي 10 6 23
2-1-2-5 بهدست آوردن مقدار تابع تناسب
مقدار متغيرها را در تابع هدف قرار داده و مقدار تابع را به ازاي هر بردار x=[x1, x2,…, xn] بهدست ميآوريم بدين ترتيب براي مجموعه 5 كروموزومي و تابع هدف زير داريم:
fx=x12+x22+3x1x2جدول2-3: محاسبه تابع بهینهكروموزم ها متغير x1به صورت باينري متغير x2 به صورت باينري x1x2f(x)كروموزمش1 0 0 1 1 1 0 0 1 0 1 28 20 2864
كروموزم ش2 0 1 1 1 1 0 0 1 1 1 30 28 4204
كروموزم ش 3 1 0 1 0 1 0 0 1 1 0 21 12 1341
كروموزم ش 4 1 1 0 1 0 1 1 0 0 0 11 3 229
كروموزم ش 5 0 1 0 1 0 1 1 0 1 1 10 27 1639
2-1-2-6 محاسبه درصد برازندگی
درصد برازندگي هر كروموزوم را حساب ميكنيم مثلا براي يك تابع دو متغيره درصد برازندگي برابر است با:
100* (جمع تمام برازندگيها / مقدار تابع به ازاي )
كه براي مجموعه 6 كروموزمي بالا و fx=x12+x22+3x1x2 به صورت جدول (2-4) درمیآید:
جدول2-4: محاسبه درصد برازندگیكروموزم ها متغير x1 به صورت باينري متغير x2به صورت باينري f(x)درصد برازندگي
كروموزم ش 1 0 0 1 1 1 0 0 1 0 1 2864 28%
كروموزم ش 2 0 1 1 1 1 0 0 1 1 1 4204 1/41%
ادامه جدول 2-4
كروموزم ها متغير x1 به صورت باينري متغير x2به صورت باينري f(x)درصد برازندگي
كروموزم ش 3 1 0 1 0 1 0 0 1 1 0 1341 1/13%
كروموزم ش 4 1 1 0 1 0 1 1 0 0 0 229 2/2%
كروموزم ش 5 0 1 0 1 0 1 1 0 1 1 1639 16%
جمع: 10227 100%

2-1-2-7 تعيين تعداد كروموزوم شركت كننده در عمل پيوند
تا اينجا، جمعيت اوليه توليد و درصد برازندگي هر كروموزوم محاسبه گرديد. حال بايد تعدادي از اين كروموزومها در عمل پيوند شركت كنند براي تعيين تعداد كروموزومها از فرمول زیر استفاده ميكنيم:
Nc=2*round(p0*cp2)که در آن p0، تعداد جمعيت اوليه، cp، ضريب پيوند كه معمولا حدود 0.6 ميباشد وNc تعداد كروموزومهايي از جمعيت اوليه است که در عمل پيوند شركت ميكنند.
2-1-2-8 انتخاب كروموزومهايي كه در عمل پيوند شركت ميكنند
براي اينكه نسل بعدي از نسل قبلي بهتر باشد بايد كروموزومهايي با درصد برازندگي بيشتر، شانس بيشتري براي شركت در عمل پيوند داشته باشند. لذا براي تعيين اينكه چه كروموزومهايي در عمل پيوند شركت ميكنند مكانيزمي به نام چرخرولت انتخاب ميكنيم كه متناسب با درصد برازندگي هر كروموزوم، آن را در عمل پيوند شركت ميدهد. اين مكانيزم به اينصورت است كه درصد برازندگي هر كروموزوم را روي دايرهاي به صورت قطاعي مشخص ميكند. در مثال ما كه 5 كروموزوم داريم بايد 5 قطاع به اندازههاي مختلف داشته باشيم.
جدول 2-5: تشکیل چرخ رولت
كروموزم ها درصدبرازندگي
كروموزم ش1 28%
كروموزم ش2 1/41%
كروموزم ش3 1/13%
كروموزم ش4 2/2%
كروموزم ش5 16%
-104140279400

حال فرض كنيد چرخ را به گردش در آورده و نقطهاي را به عنوان شاخص در نظر ميگيريم. پس از توقف چرخ، قطاعي كه در مقابل شاخص قرار گرفت نشاندهنده كروموزومي است كه بايد در عمل پيوند شركت كند. اين كار را Nc بار انجام میدهیم تا به تعداد كافي كروموزوم براي پيوند بهدست آوريم. ملاحظه ميكنيم كه در اين مكانيزم كروموزومهاي با درصد برازندگي بالاتر شانس بيشتري براي انتخاب شدن دارند . که در شکل 2-2 نشان داده شدهاست.
30346654953000-11220454953000
↑مربوط به کروموزم بادرصد برازندگی 41.1%
شکل 2-2: نمونه ای از انتخاب در چرخ رولت2-1-2-8-الف: انتخاب به روش چرخ رولت
در اين روش هر رشته، قطاعي از چرخرولت با شعاع 2π*fiftot از مركز چرخ را به خود اختصاص ميدهد.
انتخاب چرخرولت، خطاي نمونه برداري زيادي توليد ميكند. از اينجهت كه تعداد نهايي فرزندان تخصيص داده شده به يك رشته با ميزان مورد نظر خيلي تفاوت دارد. تعداد فرزندان زماني به ميزان مورد نظر ميرسد كه اندازه جمعيت خيلي زياد باشد. در مسائل كاربردي از چرخ استفاده نميشود بلكه مقدار fifi را به هر رشته تخصيص ميدهند و با توليد يك عدد تصادفي در بازه (0,fi) رشته را انتخاب ميكنند.
2-1-2-9 تقاطع(پيوند):
عمل تركيب دو كروموزوم (والدين) و بهدست آوردن دو كروموزوم جديد (فرزندان) را پيوند مينامند. براي انجام عمل پيوند روي دو كروموزوم L ژني ابتدا بايد نقطه پيوند را مشخص كنيم. اين كار با فراخواني عددي تصادفي بين 1 و L-1 صورت ميپذيرد.
round ((L*rand) +1)
سپس ژنهاي دو كروموزوم را از نقطه پيوند با هم عوض ميكنيم. عمل پيوندي كه در فوق انجام شد تقاطع تكنقطهاي نام دارد. بهعنوان مثال براي دو كروموزوم 10 ژني با نقطه پيوند 4 داريم:
جدول 2-6: عمل پیوندكروموزم ش1 1 1 1 1 1 1 1 1 1 1
كروموزم ش2 0 0 0 0 0 0 0 0 0 0
287464518986500اگر پيوند را از نقطه 4 آغاز كنيم داريم
كروموزم جديد ش 1 0 0 0 0 1 1 1 1 1 1
كروموزم جديد ش2 1 1 1 1 0 0 0 0 0 0
2-1-2-10جهشجهش يكي از پديدههاي علم ژنتيك است كه بهندرت در برخي از كروموزومها رخ ميدهد و در طي آن فرزندان خصوصياتي پيدا ميكنند كه متعلق به هيچ يك از والدين نميباشد.
نقش جهش در الگوريتم ژنتيك بازگرداندن مواد ژنتيكي گمشده و يا پيدا نشده داخل جمعيت است. تا از همگرايي زودرس الگوريتم به جوابهاي بهينه محلي جلوگيري شود. در جهش يكسري از ژنها را بهطور تصادفي برگزيده، صفرها را به يك و يكها را به صفر تبديل ميكنيم. يكي از روشهاي جهش بدين صورت است كه ابتدا با توجه به يك عدد كوچكتر از يك، به نام احتمال جهش، براي هر ژن از جمعيت، يك عدد تصادفي فراخواني ميشود. اگر اين عدد تصادفي از احتمال جهش كوچكتر بود، در آن ژن جهش رخ ميدهد.
چون عمل جهش در طبيعت بهندرت رخ ميدهد لذا در الگوريتم ژنتيك هم با احتمال بسيار كم(كمتر از 0.05) عمل جهش را انجام ميدهيم. همانطور كه گفته شد مزيت عملگر جهش ايناست كه توان دسترسي به همه فضاي جستجو را به ما ميدهد.
در صورتي كه كاراكترها اعداد پيوسته باشند جهش را ميتوان بهصورت نمو تصادفي مثبت يا منفي حول مقدار قبلي كاراكتر انجام داد. اين نوع جهش را جهش خزنده مينامند.
2-1-2-11 حفظ بهترين كروموزومها
تا اينجا توليد جمعيت جديد خاتمه مييابد. اكنون براي آنكه بهترين كروموزوم نسل قبل را از دست ندهيم آنرا بهطور دستي در جاي بدترين كروموزوم نسل جديد قرار ميدهيم.
رهيافت ديگري براي حفظ بهترين كروموزوم ايناست كه جمعيت جديد و جمعيت قبلي را با هم در آميخته و سپس آنها را بر حسب برازندگيشان از بزرگ به كوچك طبقه بندي ميكنيم. سپس ppsz (برابر با تعداد جمعيت اولیه) كروموزوم اول جمعيت كه از همه برازندگيشان بيشتر است بهعنوان جمعيت جديد برميگزينيم.
در اين روش جمعيت با ميانگين برازندگي بالاتري تشكيل ميگردد و بهجاي انتقال بهترين كروموزوم و حذف بدترين كروموزوم دستهاي از بهترين

متن کامل در سایت homatez.com