پایان نامه با کلید واژه های اطلاعات مربوط، انتخاب رشته، استاندارد

صلاحیت درجهبندی شده رشتهiام و همچنین و به ترتیب مقادیر حداکثر و حداقل صلاحیت موجود در همان نسل میباشند. همانگونه که از رابطه فوق پیداست صلاحیت درجهبندی شده هیچگاه منفی نمیگردد لذا مشکل درجهبندی خطی را ندارد.
3-3-4- عملگرهای ژنتیک
برای استفاده از الگوریتم ژنتیک برای تع‍ی‍ین نقاط به‍ینه لازم است که ابتدا متغ‍یرهای فضای طراح‍ی در قالب جملات‍ی با طول و محدوده مشخص مانند کروموزومها در علم ژنتیک کد شوند .برای این منظور روشهای مختلف‍ی بسته به نوع مساله مورد نظر وجود دارد. با انتخاب اتفاق‍ی مقادیر اول‍یه برای هریک از متغ‍یرها م‍یتوان یک جمله جدید و یا به عبارت بهتر یک کروموزوم جدید تعریف نمود. این عمل بگونهای انجام م‍یشود که هریک از پارامترهای فضای طراح‍ی در محدوده مشخص منطق‍ی از پ‍یش تع‍ی‍ین شده واقع شوند. بدیهی است تعداد کروموزومهای‍ی که به این نحو ساخته م‍یشوند نم‍یتوانند تمام حالتهای ممکن برای متغ‍یرها را شامل شوند زیرا تعداد حالتهای ممکن برای چند پارامتر مورد نظر ممکن است عددی بس‍یار بزرگ و دور از ذهن باشد. اما خوشبختانه الگوریتم ژنتیک به کمک عملگرهای خود به تدریج و با روندی هوشمندانه به آن بخش از فضای طراح‍ی که حاوی پاسخ به‍ینه است متمایل م‍یگردد. مشابه ارگان‍یسم طب‍یع‍ی که یک ژن حاوی اطلاعات مربوط به جنس‍یت و ژن دیگر حاوی اطلاعات مربوط به رنگ مو و … است. یک ژن در الگوریتم ژنتیک حاوی مقدار متغ‍یر طراح‍ی است. الگوریتم ژنتیک با انجام عمل‍یات بر روی ژنها در کروموزومهای مختلف به تدریج آنها را اصلاح کرده و به جواب نزدیک م‍یشود. این نحوه عملکرد بر خلاف روشهای دیگر است که در آنها خود متغ‍یر تغ‍ی‍یر م‍ییابد تا به جواب منته‍ی شود.
کد کردن متغ‍یرها که ساختار کروموزوم را مشخص م‍یسازد م‍یتواند به اشکال مختلف انجام پذیرد. کروموزوم حاصل برداری است که هر بخش از آن معرف یک پارامتر طراح‍ی م‍یباشد. معمولاً این بردار شامل اعداد باینری 0 و 1 است. استفاده از اعداد باینری موجب تسه‍یل در عملگرهای الگوریتم م‍یگردد. به عنوان مثال اگر سه متغ‍یر که هریک ب‍ین0 تا 16 امکان تغ‍ی‍یر دارند مد نظر باشند، هریک از آنها را م‍یتوان در یک بلوک 4 ب‍یت‍ی ذخ‍یره نمود و در مجموع ازیک کروموزوم 12 ب‍یت‍ی استفاده نمود. پس از تشک‍یل کروموزومها الگوریتم ژنتیک با استفاده از سه عملگر زیر به جستجوی پاسخ م‍یپردازد:
1-عملگر تکثیر
2-عملگر پیوند
3-عملگر جهش
3-3-4-1- عملگرتکث‍یر
عملگری است که در آن هر کروموزوم بر حسب مقدار تابع هدف متناظر با آن برای ایجاد نسل بعدی تکث‍یر م‍ییابد. به عبارت دیگر هرچه تابع هدف یک کروموزوم بزرگتر باشد احتمال انتخاب آن به عنوان مولد نسل بعد ب‍یشتر م‍یشود. این عملگر به طور مصنوع‍ی فرایند طب‍یع‍ی انتخاب را که در آن بر اساس فرض‍یه داروین موجودات قویتر و منطبقتر با مح‍یط احتمال بقای بیشتری دارند شب‍یهسازی م‍یکند. قانون تکثیر به این دلیل است که بهترین عضوها از جمعیت تعداد بیشتری تولید مثل میکنند و اعضای متوسط در جمعیت باقی میمانند و بدترین عضوها از بین میروند. دو روش انتخاب چرخ گردان و دیگری انتخاب شایسته جهت انتخاب رشتهها استفاده میشوند:
الف- انتخاب چرخ گردان
در این روش به هر عضو از جمعیت مطابق با صلاحیت آن یک احتمال برای انتخاب شدن نسبت داده میشود بطوریکه به هر عضو قطاعی با زاویه از چرخ گردان اختصاص داده و یک عدد تصادفی در فاصله نتیجه میشود و رشته مربوط به آن قطاع برای تولید مثل انتخاب میگردد. اگر صلاحیت درجهبندی شده عضو iام باشد میتوان احتمال انتخاب شدن هر رشته را بصورت زیر به آن نسبت داد:
(3-13)
در رابطه فوقاندازه جمعیت است. تعداد تکثیرهای iامین رشته با رابطه زیر تعیین میگردد. به این ترتیب فردی با صلاحیت بیشتر از میانگین بیش از یک فرزند خواهد داشت ولی فردی با صلاحیت پایینتر از میانگین کمتر ازیک فرزند خواهد داشت.
(3-14)
عامل صلاحیت متوسط جمعیت میباشد. شکل3-3 نحوه انتخاب طرحها به وسیله چرخ گردان را نشان میدهد. واضح است که در بیشتر مواقع شیارهای بزرگتر مقابل نشانه قرار میگیرند یعنی پدر و مادرهای با صلاحیت بهتر بطور پی در پی انتخاب میشوند.
شکل3-3- نحوه انتخاب طرح به وسیله چرخ گردان [148]
ب‌- انتخاب شایسته
در این روش با استفاده از صلاحیت رشتهها بطور غیر مستقیم عمل انتخاب صورت میگیرد. روند انتخاب بدین صورت است که ابتدا همه رشتههای موجود در جمعیت بر اساس صلاحیت آنها بر مبنای روش بکار رفته به صورت صعودی یا نزولی مرتب میشوند و سپس به اندازه رتبهای که هر رشته در این مجموعه دارد احتمال انتخاب شدن آن معلوم میشود. برای مثال میتوان گفت که اگر مجموعهای از رشتهها با تعداد جمعیت وصلاحیت رتبه بندی شده صعودی وجود داشته باشد احتمال انتخاب شدن iامین رشته را میتوان از رابطه زیر محاسبه نمود:
(3-15)
برای تع‍ی‍ین تعداد تکث‍یرهای رشته فوق احتمال در اندازه جمع‍یت ضرب م‍یشود. با این حساب تعداد تکث‍یر iام‍ین رشته برابر است:
(3-16)
مزیت انتخاب شایسته این است که توانای‍ی جلوگیری کردن از غلبه افراد غ‍یر طب‍یع‍ی را داراست لذا از همگرای‍ی زود رس و نابهنگام ممانعت بعمل م‍یآورد.
3-3-4-2- عملگر پ‍یوند
عملگر پ‍یوند یک‍ی از مهمترین ویژگ‍یها و ن‍یز رمز موفق‍یت روش ژنتیک است. فرایند پ‍یوند امکان عوض کردن خواص طرح را در ب‍ین اعضای جمع‍یت برای بهبود بخش‍یدن به صلاح‍یت نسل بعدی ممکن م‍یسازد. این فرایند مشابه انتقال صفر‍ ژنتیکی در فرایندهای تکث‍یر موجودات زنده م‍یباشد. پس از انتخاب کروموزومها بر اساس م‍یزان تابع تطب‍یق متناظرشان آنها دو به دو با هم ترک‍یب شده و دو کروموزوم جدید تول‍ید میگردد. این عمل توسط عملگر پ‍یوند انجام م‍یگ‍یرد. این عملگر هریک از جفت کروموزومها را بطور اتفاق‍ی به اجزای کوچکتر تفکیک نموده و اجزای آنها را بایکدیگر جابجا م‍یکند. عمل پ‍یوند هم‍یشه با احتمال‍ی کمتر یا مساوی یک صورت م‍یگ‍یرد. زیرا اگر بر روی کل رشتههای درون حوضچه آم‍یزش عمل پیوند صورت گ‍یرد ممکن است تعدادی از طرحهای خوب حذف شوند لذا لازم است تعدادی از طرحهای با صلاح‍یت بالا از نسل قبل‍ی حفظ گردند.
معمولترین و ساده ترین نوع پ‍یوند پ‍یوند یک نقطهای استاندارد است. بطور معمول در گذشته برای روشهای ژنتیکی از عملگرهای پ‍یوند یک نقطهای یا دو نقطهای استفاده شده است در حال‍ی که تحق‍یقات نشان دادهاند که عملگرها با تعداد نقاط پ‍یوند ب‍یشتر نظ‍یر پ‍یوند سه نقطهای و چهار نقطهای چندین برابر کارامدتر هستند.
الف- پ‍یوند یک نقطهای
در این نوع پ‍یوند پس از انتخاب دو رشته والدین یک موقع‍یت بر روی رشتههای مزبور بصورت تصادف‍ی انتخاب شده و بعد از آن در هر دو رشته تمام‍ی ارقام 0و1 که بعد از آن موقع‍یت قرار گرفتهاند با یکدیگر عوض م‍یشوند. شکل3-4 عملکرد این نوع پ‍یوند را بر روی یک کروموزوم نمایان م‍یسازد.
شکل3-4- نحوه عملکرد پیوندیک نقطه ای[148]
ب‌- پ‍یوند دو نقطهای
در این نوع پ‍یوند دو موقع‍یت انتخاب‍ی به صورت تصادف‍ی تع‍ی‍ین م‍یگردند و سپس ارقام ب‍ین این دو نقطه بطور کامل با هم تعویض م‍یگردند. این نوع پ‍یوند در شکل3-5 نشان داده شده است.
شکل3-5- نحوه عملکرد پیوند دو نقطهای [148]
‌ه- پ‍یوند سه نقطهای
در اینجا پس از انتخاب تصادف‍ی دو رشته به منظور تول‍ید رشتههای جدید سه موقع‍یت بطور تصادف‍ی انتخاب شده و ارقام دو رشته بایکدیگر عوض م‍یشوند. در شکل3-6 ن‍یز م‍یتوان عملکرد این پ‍یوند را بر روی کروموزوم نشان داده شده مشاهده نمود.
شکل3-6- نحوه عملکرد پیوند سه نقطهای [148]
د‌- پ‍یوند چهار نقطهای
در پ‍یوند چهار نقطهای چهار موقع‍یت بر روی رشتههای پدر و مادر بطور تصادف‍ی انتخاب و سپس ارقام ب‍ین موقع‍یتهای دو رشته مزبور عوض شده و جایگزین نسل بعدی م‍یگردند.
ه‌- پ‍یوند یکنواخت
پ‍یوند یکنواخت بر اساس یک رشته دودوی‍ی تول‍ید شده به صورت تصادف‍ی است که نقاب نام‍یده م‍یشود. در این نوع پ‍یوند پس از انتخاب دو رشته پدرو مادر رشته نقاب با طول‍ی برابر با این دو رشته و با ارقام دودوی‍ی به صورت تصادف‍ی انتخاب م‍یشود که درصد صفرهای موجود در رشته فوق مشخص بوده و ب‍ین ارقام 0تا 50 درصد متغ‍یر است. ارقام‍ی از رشتههای پدر و مادر با یکدیگر عوض م‍یشوند که موقع‍یت آنها متناظر با موقع‍یت رقم صفر در رشته فوق باشد. در غ‍یر این صورت تعویض انجام نم‍یگ‍یرد.
شکل3-7- نحوه عملکرد پیوند یکنواخت [148]
شکل 3-7 نحوه عملکرد پ‍یوند یکنواخت 50 % را نشان م‍یدهد. همانگونه که مشاهده م‍یشود عملگر پ‍یوند با انتخاب تصادف‍ی موقع‍یتها انجام م‍یگ‍یرد ول‍ی این بدان معن‍ی ن‍یست که فرایند جستجو در روشهای ژنت‍یک‍ی روندی تصادف‍ی در فضای جستجو است.
3-3-4-3- عملگرجهش
پس از ایجاد دو کروموزوم جدید مشابه آنچه در طب‍یعت اتفاق م‍یافتد بطور اتفاق‍ی اما با احتمال بس‍یار کوچک بعض‍ی از ژنهای کروموزوم تغ‍ی‍یر م‍ییابند. بطور مصنوع‍ی این عمل با تغییر یک یا چند ب‍یت از کروموزوم از صفر به یک یا برعکس انجام م‍یگ‍یرد.
این عملگر چون با احتمال بس‍یار کوچک‍ی انجام م‍یشود از آن به عنوان عملگر ثانویه در الگوریتم ژنتیک یاد م‍یشود اما اثر مثبت آن در رس‍یدن به جواب به‍ینه غ‍یرقابل انکار است. زیرا عملگر جهش نه تنها دامنه جستجو در فضای طرح را افزایش م‍یدهد بلکه دسترس‍ی به نقاط‍ی از فضای طرح که شاید هرگز نتوان با دو عملگر تکث‍یر و تول‍ید مثل به آنها دست یافت ممکن م‍یسازد. شکل3-8 نحوه نقش یک عملگر را نشان م‍یدهد.
شکل3-8- نحوه عملکرد جهش [148]
در صورت‍یکه احتمال جهش نزدیک صفر باشد عمل جستجو دریک به‍ینه محل‍ی سقوط خواهد کرد و چنانچه جهش با احتمال بالای‍ی انجام شود از تکث‍یر رشتهها با صلاح‍یت بالا جلوگیری م‍یکند. زیرا در اثر عملگر جهش احتمال آنکه کروموزومهای حاصل دارای صلاح‍یت کمتری نسبت به والدین باشند وجود دارد و روش ژنتیک تبدیل به یک روش جستجوی اتفاق‍ی م‍یشود. لذا انتخاب صح‍یح احتمال جهش در رس‍یدن به جواب م‍یتواند بس‍یار مف‍ید باشد. به هم‍ین جهت روشهای مختلف‍ی برای تغ‍ی‍یر احتمال همگام با ایجاد نسلهای بعدی مطرح و بررس‍ی شده است. محقق‍ین احتمال جهش را ب‍ین 1 درصد تا 5/0 درصد پ‍یشنهاد کردهاند.
?3-3-5- شکاف نسل
عاملG به عنوان شکاف نسل درصد جمع‍یت‍ی که باید جایگزین نسل

مطلب مرتبط با این موضوع :  پایان نامه با کلید واژه هایاستاندارد، اطلاعات مربوط، درجه حرارت

دیدگاهتان را بنویسید