روش رتبه بندی[۴۵]
روش حالت پایدار[۴۶]
از میان روش های فوق دو روش چرخ گردان و تورنمنت از اهمیت بیشتری برخوردارند که به اختصار به چگونگی عملکرد آن میپردازیم.
۳-۳-۱-۴-۱ انتخاب چرخ گردان[۴۷] (RWS)
معروفترین روش انتخاب متناسب، انتخاب چرخ گردان میباشد (شکل۳-۳). در این روش، اندازه هر شیار متناسب با برازندگی فرد است، بطوریکه به هر فرد قطاعی با زاویه از چرخگردان تخصیص داده می‌شود. حال عددی تصادفی در فاصله تولید می‌شود و رشته‌ای که عدد تصادفی در قطاع مربوط به آن قرار گیرد، برای ورود به استخر آمیزش انتخاب می‌گردد. این عمل تا جایی که جمعیت نسل بعدی به طور کامل تولید شود ادامه می‌یابد.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
اندازه قاچ مربوط به هر فرد در چرخ گردان از رابطه زیر محاسبه می‌گردد،
(۳-۵)
انتخاب تصادفی والدین را میتوان با به گردش درآوردن چرخ و توقف آن در مقابل نشانه ثابتی تشبیه نمود. روشن است که غالبا شیارهای بزرگتر مقابل نشانه قرار می‌گیرند. بدین معنی که والدین با برازندگی بزرگتر بطور پیاپی انتخاب میشوند.
شکل (۳-۳) انتخاب چرخگردان
هر بار که به فرزندی نیاز داشته باشیم با چرخش ساده چرخگردان، یک فرد برای تولید مثل انتخاب می‌شود، سپس نسخه‌ای از این فرد در استخر آمیزش ریخته می‌شود. این روش انتخاب، با روش های الهام گرفته از طبیعت تطابق بیشتری دارد.
۳-۳-۱-۴-۲ انتخاب رقابتی[۴۸]
ساده‌ترین روش انتخاب این است که دو فرد از میان جمعیت کنونی انتخاب می‌گردند، فردی که برازندگی بالاتری داشته باشد به استخر پیوند راه می‌یابد. بدون در نظر گرفتن اینکه کدام روش انتخاب بکار رفته باشد، عملگر انتخاب، جمعیت میانی افراد موجود در استخر آمیزش[۴۹] را تولید میکند. استخر آمیزش فقط شامل افرادی میباشد که در نسل کنونی وجود دارند. سپس دو عملگر بعدی، پیوند و جهش به استخر آمیزش جهت تولید فرزندان اعمال می‌گردد. انتخاب نخبه‌گرا باعث می‌گردد تا یک یا تعداد بیشتری از والدین نخبه بطور مستقیم به نسل بعد راه پیدا کنند و نسل بعدی شامل بهترین فرد نسل قبلی باشد.
۳-۳-۱-۵ ادغام
عملگر ادغام یا پیوند[۵۰] یک عملگر بسیار مهم و حیاتی برای تولید نسل جدید میباشد. پیوند باعث افزایش کارایی GA می‌گردد ]۲۰[. این عملگر با توجه به احتمال پیوند به هر جفت از افراد موجود در استخر آمیزش، جهت تولید یک یا دو فرزند اعمال می‌گردد. این عملگر یک عملگر ترکیبی است که شامل سه عمل است. ابتدا یک جفت رشته را به صورت تصادفی انتخاب میکند، در گام دوم یک محلی را برای عمل ادغام به طور تصادفی در طول رشته انتخاب کرده و سرانجام در سومین مرحله مقدار دو رشته را با توجه به محل ادغام جابجا میکند. روش های مختلفی برای عمل ادغام وجود دارد که از میان آنها میتوان به روش های زیر اشاره کرد.
روش ادغام تک نقطه ای یا تک مکانی
روش ادغام دو نقطهای
روش ادغام چند نقطهای
روش ادغام یکنواخت
روش ادغام دو بعدی
به تحقیق و قطعا نمیتوان گفت که کدام یک از روش های ادغام بهتر است، بنابراین یک روش ادغام مناسب، با توجه به سلیقه افراد و شرایط مساله باید انتخاب نمود. در رشته های دودویی و ادغام تک نقطهای همانند شکل (۳-۴) جای ژنهای والدین از نقاط پیوند تعویض می‌گردد.
(شکل ۳-۴) پیوند یک نقطهای
در این شکل پیوند از ژن سوم به بعد، با تعویض ژنهای باقیمانده (فقط ژن چهارم) صورت می‌گیرد.
۳-۳-۱-۵-۱ نرخ ادغام[۵۱]
در اینجا لازم است به یک مفهوم مهم دیگری به نام نرخ ادغام اشاره شود که بیانگر احتمال ادغام است که آن را با نمایش میدهند و مقدار آن بین صفر تا یک است. این نرخ در GA با پیدا کردن نسبت تعداد جفتهای ادغام شده در جمعیتهای ثابت به دست میآید و با فرض احتمال ادغام میتوان گفت که در صد از رشته ها در عملیات ادغام به کار رفتهاند و در صد از جمعیت، باقی مانده است. این نرخ بیانگر تعداد کروموزومهایی است که وارد استخر آمیزش شده اند که هرچه این مقدار بیشتر باشد یعنی کروموزومهای جدید و زیادتری وارد این استخر شده اند.
اگر این مقدار خیلی زیاد گردد باعث می شود تا فرصت تطابق در کروموزوم از بین برود و اگر این مقدار خیلی کم باشد، تعداد فرزندان تولید شده کافی نخواهند بود. این نرخ برای جمعیت هایی با اندازه ۳۰ تا ۲۰۰ مورد در محدوده ۵/۰ تا ۱ خواهد بود.
۳-۳-۱-۶ جهش
عملگر جهش به GA اجازه می‌دهد تا ژنهایی که شانس حضور در جمعیت اولیه را نداشته‌اند وارد نسل گرداند. مقادیر ژنها با توجه به احتمال جهش تغییر می‌یابند. در شیوه نمایش دودویی مقادیر صفر به یک و برعکس تبدیل می‌گردند. در شیوه نمایش حقیقی از رابطه زیر میتوان برای جهش والدین و تولید فرزندان استفاده کرد.
(۳-۶)
اگر چه عملگرهای انتخاب و پیوند جستجوی موثری را در فضای پارامترها دنبال نموده و افراد مناسب موجود را ترکیب می‌کنند، ولی گاهی باعث از بین رفتن خصوصیات مفید ژنهای افراد میشوند. در این صورت وجود جهش برای جلوگیری از دست رفتن این اطلاعات سودمند لازم است. این عملگر همچنین امکان دستیابی به ویژگیهای مثبتی که در جمعیت موجود وجود ندارد را فراهم میکند. در حالیکه عملگر پیوند باعث کاهش تنوع در افراد جامعه می‌گردد، عملگر جهش باعث افزایش آن می‌گردد. دلیل اصلی استفاده از عملگر جهش فرار از نقاط اکسترمم موضعی و رسیدن به نقطه اکسترمم مطلق است.
۳-۳-۱-۶-۱ احتمال جهش[۵۲] ))
این نرخ بیانگر میزان احتمال وقوع جهش است که بر اساس تعداد بیتهای جهش یافته به دست می آید. احتمال جهش معمولا کوچک میباشد بنحوی که در انتقال ژنهای خوب والدین از طریق عملگر پیوند خللی ایجاد نکند. مقدار آن معمولا بین ۰۰۱/۰ تا ۱/۰ انتخاب می‌گردد. مقادیر بزرگتر در شیوه نمایش حقیقی کاربرد بیشتری دارند. با افزایش احتمال جهش، GA بیشتر شبیه الگوریتمهای جستجوی کاملا تصادفی می‌گردد که البته مطلوب ما نیست.
۳-۳-۱-۷ سایر عملگرهای ژنتیکی
علاوه بر عملگرهای ژنتیکی که مورد بررسی قرار گرفت عملگرهای دیگری نیز وجود دارد که هنوز کاربرد گسترده پیدا نکرده‌اند که از آن جمله میتوان به اپراتورهای عملکردی زیر نیز اشاره کرد:
عمل معکوس کردن
عمل حذف کردن
عمل جداسازی
عمل نقل مکان
عمل بخش بندی
عمل کپی کردن
۳-۳-۲ الگوریتم ژنتیک با نخبه سالاری ساده
در این تحقیق از الگوریتم ژنتیک با نخبه‌سالاری ساده[۵۳] استفاده شده است که جزء اولین الگوریتمهای ژنتیک اصلاح یافته میباشد ]۲۱[. نمودار گردشی مربوط به این الگوریتم در شکل (۳-۵) آورده شده است. تفاوت اصلی الگوریتم ژنتیک با نخبه سالاری با الگوریتم ژنتیک معمولی در انتخاب نخبه نسل جاری پس از محاسبه برازندگی افراد جامعه میباشد. در الگوریتم ژنتیک با نخبه‌سالاری فردی که بالاترین برازندگی را دارد مستقیما به نسل بعد راه پیدا میکند. در الگوریتمهای قبلی اگر تعداد نسلها از حدی فراتر می رفت، ممکن بود بهترین جوابها از بین بروند ولی با استفاده مفهوم نخبه سالاری[۵۴] مشکل فوق برطرف شده است.
۳-۳-۳ روش های جایگزینی
در ساده‌ترین شکل GA، وقتی که عملگرهای انتخاب، پیوند و جهش بر افراد نسل جاری اعمال گردید، تمام فرزندان جایگزین نسل جاری می‌گردند. در الگوریتمهای ژنتیک نخبه‌گرا معمولا بهترین فرد مستقیما به نسل بعد راه می‌یابد و فرد باقیمانده از طریق عملگرهای الگوریتم ژنتیک تولید می‌گردند.
شکل (۳-۵) الگوریتم ژنتیک با بکارگیری مفهوم نخبه‌سالاری
۳-۳-۴ معیار همگرایی
تا کنون مطالعات بسیاری برای بررسی همگرایی GA صورت گرفته است ولی به طور کلی یک اثبات صریح و جامع ریاضی درباره همگرایی وجود ندارد.
یک معیار همگرایی را می توان به این صورت بیان کرد که وقتی یک درصد ثابتی از سطر و ستون های ماتریس جمعیت شبیه هم میشوند، می توان فرض کرد که همگرایی صورت گرفته است، این درصد ممکن است ۸۰% یا ۸۵% باشد.
رایجترین شرط توقف الگوریتم ژنتیک، رسیدن به تعداد حداکثر نسل ( ) تولید شده میباشد که قبل از شروع الگوریتم مقدار دهی شده است. تعریف سایر معیارهای همگرایی معمولا دشوار میباشد و به نوع مسئله بستگی دارد.
۳-۳-۵ معیار عملکرد
