تحقیق رایگان درمورد كروموزوم، تقسيم، میکنیم.

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

معاوضه کرده و جوابهای جدید را بوجود میآورند. به این نوع عملگرها، عملگرهای تقاطعی گفته میشود.
در زیر چگونگی انجام و انواع عملگرهای تقاطعی به صورت مرحله به مرحله آورده شده است.
اپراتور تقاطع با احتمال P_c اجرا می شود.
تقاطع تک نقطهای147
تقاطع دو نقطهای148
تقاطع چند نقطهای149
تقاطع یکنواخت150
چند نکته:
هر فرزند باید خصوصیاتی را از هر والدش به ارث ببرد(اگر اپراتوری چنین واقعیتی را تضمین نکند، اپراتور جهش است).
اپراتور آمیزش باید منجر به یک کروموزوم معتبر شود.
اپراتور تقاطع، 2 کروموزوم را دریافت نموده و حداکثر 2 فرزند ایجاد میکند.
یکی از پرکاربردترین انواع اپراتور تقاطع، تقاطع تک نقطهای است. در ادامه به این نوع اپراتور و همچنین اپراتور تقاطع دو نقطهای اشاره میشود.
3-6-6-1-1. يك نقطه برش
در اين روش كه توسط ديويس151 ارائه شده است يك نقطه به صورت تصادفی بهعنوان نقطه برش در طول دو كروموزومی كه بهعنوان والدين انتخاب شده‌اند در نظر گرفته شده و كروموزوم‌ها از آن نقطه به دو قسمت تقسيم می‌شوند و جای دو بخش از آن‌ها با هم تعويض می‌گردد. در ادامه مثالی از این روش ارائه شده است.

شکل3-10 . نحوه عملکرد اپراتور تقاطع یک نقطه برش

ابتدا عدد تصادفی در بازه [1 , Length chromosome] تولید میکنیم. سپس بخش اول از کروموزوم والد به کروموزوم فرزند منتقل میشود. برای تکمیل بخش دوم کروموزوم هر فرزند، کروموزوم والد دیگر (غیر متناظر) را از ابتدا اسکن نموده و هر عددی که در کروموزوم فرزند موجود نیست، به آن منتقل میشود]1[.

شکل3-11. اپراتور تقاطع تک نقطه ای
3-6-6-1-2. دو نقطه برش
در اين روش دو نقطه به صورت تصادفی بهعنوان نقطه برش در طول دو كروموزومی كه بهعنوان والدين انتخاب شده‌اند در نظر گرفته شده و كروموزوم‌ها از آن دو نقطه به سه قسمت تقسيم میشوند كه طرفین ثابت مانده و قسمت‌ میانی از دو كروموزوم با هم تعويض میشوند.
شکل3-12. اپراتور تقاطع دو نقطه برش
3-6-6-2. عملگرهای جهشی152
عملگرهایی که یک یا چند ژن از یک کروموزوم را انتخاب و و مقادیر آنها را تغییر میدهند. در این عملگرها یک یا چند محل از یک رشته کاراکتری با طول خاص در نظر گرفته شده و مقادیر کاراکترها در آن محل ها تغییر مییابد. مواردی که در این نوع مهم است عبارتند از :
تعداد محلهایی که قرار است تغییر یابند
نحوه انتخاب محلها
نحوه عملیات تغییر
با مشخص شدن موارد فوق یک عملگر خاص ایجاد میشود که به آن عملگر جهشی گفته میشود. در این نوع عملگرها از اطلاعات یک جواب استفاده کرده و جواب دیگری ایجاد میشود. این تغییر ممکن است کم یا زیاد بوده که به همان میزان از اطلاعات زیاد یا کم استفاده میشود. به عبارت دیگر هر چه تغییرات بیشتر باشد جواب حاصله تصادفیتر خواهد بود و این تصادفی بودن برای ورود مواد ژنتیکی جدید به داخل جمعیت مفید میباشد.
زمانیکه جمعیت به سمت جواب خاصی همگرا میشود احتمال جهش باید زیاد شده تا از این عمل جلوگیری نماید و بالعکس وقتیکه جمعیت دارای جوابهای غیر یکسان است، باید احتمال جهش کم شود. می توان بر اساس این موضوع احتمال جهش را بین دو مقدار در حال تغییر قرار داد و نکته دیگر درباره عملگرهای فوق یافتن تعداد نقاط جهش است که این مورد از مسئله ای به مسئله دیگر فرق میکند و برای یافتن مقدار بهینه آن باید از روش سعی و خطا استفاده کرد[1].
در زیر چگونگی انجام عملگر جهش به صورت مرحله به مرحله آورده شده است:
اندازه جهش،پارامتر مهمی است و باید تحت کنترل باشد.
اپراتور جهش، باید به یک کروموزوم معتبر منتهی شود.
جهش برای هر ژن با احتمال P_m اتفاق میافتد.
به منظور اعمال جهش روی کروموزوم روش های مختلفی وجود دارد که در ادامه به تعدادی از آن ها اشاره می شود:
3-6-6-2-1. جابجايي153
در این روش دو ژن به صورت تصادفی انتخاب شده و با يكديگر تعويض می‌شوند. مثلا اگر یک رشته جواب بصورت زیر باشد
3
4
7
5
2
8
1
6
و دو ژن انتخابی، ژن های 3 و 6 باشد آنگاه کروموزوم بصورت زیر تغییر می کند:
3
4
8
5
2
7
1
6

3-6-6-2-2. وارونگي154
در اين روش ابتدا دو عدد تصادفي را بين [1,L] كه L طول كروموزوم می‌باشد تولید كرده و كروموزوم به سه بخش تقسيم می‌شود. حال قسمت میانی وارونه می‌گردد. مثلا فرض كنيد رشته جواب بصورت زیر باشد:
4
3
5
7
1
6
2
8

اگر دو ژن تصادفی 3 و 5 باشد رشته جواب به صورت زير تغییر می کند.
4
3
1
7
5
6
2
8

3-6-6-2-3. الحاق یا جاسازی155
در اين روش ابتدا دو عدد تصادفي را بين [1,L] كه L طول كروموزوم می‌باشد تولید كرده و كروموزوم به سه بخش تقسيم می‌شود. در این حالت، دو کار انتخاب شده با یک حرکت کشویی در کنار یکدیگر قرار می گیرد. مثلا فرض کنید:
4
3
5
7
1
6
2
8

اگر دو ژن تصادفي انتخابی به ترتیب 2 و 5 باشد رشته جواب به صورت زير تغییر می کند:
4
5
7
1
6
3
2
8

و اگر دو ژن تصادفی انتخابی به ترتیب 5 و 2 باشد رشته جواب به صورت زير در می‌آيد:

4
3
6
5
7
1
2
8

3-6-7. عمل تحول
عملگری که در این بخش معرفی میشود عملگر انتخاب بوده که وظیفه اصلی آن هدایت الگوریتم به نواحی امید بخش فضای جواب میباشد و دارای سه بخش اساسی فضای نمونه گیری156 ، مکانیسم نمونه گیری157 و احتمال انتخاب158 است که در زیر به تشریح هر کدام از آنها پرداخته میشود.
3-6-7-1. فضای نمونه گیری
عملگر انتخاب برای ایجاد نسل بعد یا از همه نوزادان و والدین استفاده میکند و یا بخشی از آن ها.
3-6-7-2. فضای نمونه گیری عادی159
این روش به این صورت بوده که هر نوزاد بلافاصله پس از تولید جایگزین والد خود میشود. در این روش اگر Pop size اندازه جمعیت و off size اندازه نوزادان تولید شده در هر نسل باشد، اندازه فضای نمونه گیری برابر Pop size خواهد بود که شامل همه نوزادان تولید شده میباشد. اشکال اساسی این است که هیچ تضمینی برای اینکه نوزادان تولید شده بهتر از والدین باشد وجود ندارد. محققین برای غلبه بر این ایراد چند روش پیشنهاد کردند که به جای این که نوزادان جایگزین والدین خود شوند، جایگزین یک کروموزوم که به طور تصادفی انتخاب میگردد، شوند.
3-6-7-3. مکانیسم نمونه گیری
انتخاب چرخه رولت160 اولین بار توسط هالند[68] پیشنهاد شد. یکی از مناسبترین انتخابهای تصادفی بوده که ایده آن بر مبنای احتمال انتخاب کروموزوم، بر اساس برازندگی آن محاسبه میشود. در روش انتخاب چرخ رولت به این صورت عمل میشود که برای انتخاب هر کروموزوم ابتدا یک عدد تصادفی بین یک و صفر تولید شده و سپس عدد مذکور در هر بازهای که قرار گرفت کروموزوم متناظر با آن انتخاب میشود. البته روش پیاده کردن چرخ رولت به این شکل است که یک ناحیه دایره شکل را در نظر گرفته و آن را به تعداد کروموزومها طوری تقسیم میکنیم که هر بخش متناظر با مقدار برازندگی کروموزوم مربوطه باشد. حال چرخ را چرخانده و هر کجا که چرخ متوقف شد به شاخص چرخ نگاه کرده، کروموزوم مربوط به آن بخش انتخاب میگردد. احتمال بقاء کروموزوم k ام برابر است با:
P_k=f_k/(∑_(i=1)^n▒f_i ) , n=Pop-size ) (3-1
در زیر مراحل کلی انتخاب بر مبنای چرخه ی رولت به طور یکجا آورده شده است[69].
ایده اصلی:
کروموزومهای بهتر شانس انتخاب بیشتری دارند.
شانس انتخاب هر کروموزوم متناسب با میزان برازندگی آن کروموزوم است.

برای هر کروموزوم از جمعیت مقدار برازش محاسبه میشود.(کروموزومهای با برازش بالاتر، شانس بیشتری برای انتخاب دارند.)
ابتدا برازش تجمعی را برای هر کروموزوم محاسبه میکنیم.
برازش تجمعی آخرین کروموزوم را Sum فرض میکنیم.
عدد تصادفی در فاصله را در بازه(0,Sum) تولید میکنیم.
عدد مربوط را با برازشهای تجمعی مقایسه کنید و کروموزومی که در فاصله مربوطه قرار گرفته را انتخاب کنید.
3-6-7-4. احتمال انتخاب
این موضوع در مورد چگونگی تعیین احتمال انتخاب کروموزومها میباشد. در بعضی از تکنیکها، احتمال انتخاب یک کروموزوم متناسب آن بوده که دارای چند عیب میباشد. برای مثال در نسلهای اولیه گرایش برای تسلط تعدادی از کروموزومهای برتر فرآیند انتخاب وجود دارد، در حالی که در نسلهای آخر وقتی جمعیت به صورت کامل همگرا میشود رقابت بین کروموزومها خیلی جدی نبوده و تقریبا به صورت جستجوی تصادفی در میآید. یعنی در نسلهای اولیه چون مقدار برازشها معمولا با هم اختلاف زیادی دارند، لذا شانس حضور کروموزومی که برازش آن بیشتر است به مراتب بالاتر میباشد. در نسلهای پایانی چون مقدار برازش کروموزومها به هم نزدیک میشود بنابراین انتخابها تقریبا تصادفی بوده و شانس انتخاب برای اکثر کروموزومها برابر میشود.
3-6-8. تابع برازش161
همانطور که دیده شد در فرآیند انتخاب بارها از عبارت کروموزوم مناسبتر صحبت شد. بدیهی است که برای تشخیص کروموزوم مناسبتر باید یک شاخص جهت ارزیابی کروموزومها وجود داشته باشد.

پایان نامه
Previous Entries تحقیق رایگان درمورد الگوریتم ژنتیک، فرآیند ارزیابی، انتخاب طبیعی Next Entries دانلود پایان نامه با موضوع هويت، طراحي، معماري