محاسبه تابع برازندگی^[۱۰۷] (تابع ارزش)
یک «تابع هزینه»، خروجی را بر اساس مجموعه ­ای از متغیرهای ورودی تولید می­ کند. تابع هزینه ممکن است یک تابع ریاضی، یک آزمایش تجربی و یا حتی یک بازی باشد. هدف، اصلاح خروجی به­ صورت مطلوب با بهره گرفتن از یافتن مقادیر مناسب برای متغیرهای ورودی می­باشد. ما در زندگی روزانه خود با این گونه مسائل روبرو هستیم. به عنوان یک مثال ساده، هنگام پُر کردن وان حمام با آب، این کار را انجام می­دهیم بدون آن­که تا به حال فکر کرده باشیم که نوعی بهینه­سازی در حال انجام است. در این مثال، هزینه همان اختلاف بین دمای آب مورد نظر و دمای آب پُر شده در وان می­باشد. متغیرهای ورودی عبارتند از میزان باز کردن شیرهای آب سرد و گرم. در این حالت، تابع هزینه نتیجه عملی بدست آمده از فرو بردن دست به درون آب داخل وان می­باشد. بنابراین می­بینیم که تعیین یک تابع هزینه­ مناسب و تصمیم ­گیری درباره این که کدام­یک از متغیرها را تغییر دهیم به شدت به­هم وابسته­اند. در کتب و مقالات مربوط به GA، بسیاری برای خروجی تابع هدف^[۱۰۸] (تابع هدف یعنی تـابعی که قرار است بهینـه شود)، از اصطـلاح شایستگی (برازندگی)^[۱۰۹] استفـاده کرده ­اند (شاه­حسینی، موسوی و ملاجعفری،۱۳۹۱).

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

به عبارت دیگر، تابع برازندگی از اِعمال تبدیل مناسب بر روی تابع هدف یعنی تابعی که قرار است بهینه شود، بدست می‌آید. این تابع هر رشته را با یک مقدار عددی ارزیابی می‌کند که کیفیت آن را مشخص می کند. هر چه کیفیت رشته جواب بالاتر باشد مقدار برازندگی جواب بیشتر است و احتمال مشارکت برای تولید نسل بعدی نیز افزایش خواهد یافت (خلیلی­نیا، ۱۳۹۰، عباسی­کیا، ۱۳۸۸).

اعمال عملگرهای ژنتیکی^[۱۱۰]
در الگوریتم ژنتیک سه عملگر ژنتیک زیر بر روی کروموزوم­ها اِعمال می­شوند:
انتخاب
ترکیب یا ادغام
جهش
شرح هر کدام از این عملگرها در ادامه آمده است.

انتخاب^[۱۱۱]
در مرحله انتخاب، یک جفت از کروموزوم‌ها برگزیده می‌شوند تا با هم ترکیب شوند، عملگر انتخاب رابط بین دو نسل است و بعضی از اعضای نسل کنونی را به نسل آینده منتقل می‌کند (خلیلی­نیا، ۱۳۹۰). افرادی از جمعیت که دارای بیشترین برازندگی هستند، باقی می­مانند و افراد یا کروموزوم­های دارای بیشترین هزینه حذف می­شوند (شکل(۲-۳)) (شاه­حسینی، موسوی و ملاجعفری، ۱۳۹۱).
شکل(۲-۳): افراد دارای بهترین خصوصیات باقی می مانند و گونه های نامناسب در طبیعت از بین می روند. (شاه­حسینی، موسوی و ملاجعفری، ۱۳۹۱)
به همین ترتیب در GA نیز کروموزوم­های دارای بیشترین هزینه حذف می­شوند.

انواع روش‌های انتخاب
روش­های جفت­گیری کروموزوم­ها در GA به اندازه­ جفت­گیری در گونه­ های حیوانات، جالب و متنوع می­باشد. حال به روش­های مختلف انتخاب می­پردازیم (شاه­حسینی، موسوی و ملاجعفری، ۱۳۹۱).
برخی از روش‌های متداول انتخاب عبارتند از (خلیلی­نیا، ۱۳۹۰، عباسی­کیا، ۱۳۸۸):
انتخاب چرخ رولت
انتخاب ترتیبی
نخبه سالاری
انتخاب رقابتی
انتخاب مسابقه
انتخاب مسابقه تصادفی
حال شرح مختصری از پرکاربردترین و معروف­ترین آن­ها را در ادامه بیان می­کنیم.
انتخاب چرخ رولت^[۱۱۲]
احتمالاتی که به کروموزوم­های موجود در استخر جفت­گیری نسبت داده می­ شود، به شدت به هزینه آن­ها بستگی دارد. کروموزومی که دارای کم­ترین هزینه است، بیش­ترین احتمال جفت­گیری را دارا است؛ در حالی که کروموزومِ دارای بیش­ترین هزینه، کم­ترین شانس را برای جفت­گیری دارد. یک عدد تصادفی مشخص می­ کند که کدام کروموزوم­ها انتخاب شوند. برای این روش وزن­دهی معمولا دو روش وجود دارد: وزن­دهی بر اساس رتبه^[۱۱۳] و وزن­دهی بر اساس هزینه^[۱۱۴] (شاه­حسینی، موسوی و ملاجعفری، ۱۳۹۱).
البته روش پیاده‌سازیِ چرخ رولت به این شکل است که ما یک دایره را در نظر گرفته و آن را به تعداد کروموزوم‌ها طوری تقسیم می‌کنیم که هر بخش، متناظر با مقدار برازندگیِ کروموزومِ مربوطه باشد، حال چرخ را چرخانده و هر کجا که چرخ متوقف شد به شاخص چرخ نگاه کرده، کروموزوم مربوط به آن بخش انتخاب می‌گردد (خلیلی­نیا، ۱۳۹۰، عباسی­کیا، ۱۳۸۸).
شکل(۲-۴): چرخ رولت (خلیلی­نیا، ۱۳۹۰)
انتخاب ترتیبی^[۱۱۵]
در انتخاب ترتیبی، اعضای جمعیت بر اساس تطابقشان مرتب می­شوند. ارزش منتظره­ی هر عضو به جای تطابقش، در این روش به رتبه­اش بستگی دارد (خلیلی­نیا، ۱۳۹۰، عباسی­کیا، ۱۳۸۸).
انتخاب نخبه سالاری^[۱۱۶]
در نخبه سالاری، بهترین عضو هر جمعیت، زنده می‌ماند و در جمعیتِ بعد حضور دارد؛ به عبارت دیگر عضوی که بالاترین تطابق را دارد به طور خودکار به جمعیت جدید منتقل می‌شود (خلیلی­نیا، ۱۳۹۰، عباسی­کیا، ۱۳۸۸).
انتخاب رقابتی^[۱۱۷]
روش انتخاب رقابتی، تعدادی از اعضای جمعیت را به تصادف انتخاب می‌کند و سپس اگر شرطی خاص برقرار باشد، بهترین یا تعدادی از بهترین‌های آن­ها را به عنوان والد برمی‌گزیند. اگر شرط برقرار نشود، بدترین عضو یا تعدادی از بدترین‌ها، در تشکیل جمعیت آینده به عنوان والد در نظر گرفته می‌شوند (خلیلی­نیا، ۱۳۹۰، عباسی­کیا، ۱۳۸۸).
انتخاب مسابقه^[۱۱۸]
روش انتخاب مسابقه که توسط «گلدبرگ» ارائه شد، به تعداد Pop-Size^[119] مجموعه شامل چند عضو که از قبل مشخص شده، تولید کرده و در هر مجموعه بهترین عضو انتخاب می­گردد. اندازه مجموعه فوق که به آن «اندازه مسابقه» گفته می­ شود معمولا برابر ۲ فرض می‌گردد (خلیلی­نیا، ۱۳۹۰، عباسی­کیا، ۱۳۸۸).
انتخاب مسابقه تصادفی^[۱۲۰]
روش انتخاب مسابقه تصادفی، مانند حالت قبل بوده با این تفاوت که به جای این­که مجموعه به صورت تصادفی انتخاب شود، با کمک چرخ رولت انتخاب شده و بهترین آن به عنوان یک عضو از نسل جدید درنظر گرفته می‌شود (خلیلی­نیا، ۱۳۹۰، عباسی­کیا، ۱۳۸۸).

ادغام^[۱۲۱]
مهم­ترین عملگر در الگوریتم ژنتیک، عملگر ادغام است. ادغام، فرآیندی است که در آن، نسلِ قدیمی کروموزوم‌ها با یکدیگر مخلوط و ترکیب می‌شوند تا نسل تازه‌ای از کروموزوم‌ها به ­وجود بیایند. جفت‌هایی که در قسمت انتخاب، به عنوان والد در نظر گرفته شدند، در این مرحله ژن‌هایشان را با هم مبادله می‌کنند و اعضایی جدید به ­وجود می‌آورند (خلیلی­نیا، ۱۳۹۰، عباسی­کیا، ۱۳۸۸).
به عبارت دیگر، ادغام، ایجاد یک یا چند فرزند توسط والدین انتخاب شده در فرایند جفت­گیری است. ساختار ژنتیکی جمعیت به وسیله اعضای فعلی جمعیت محدود می­ شود. رایج­ترین صورت ادغام شامل دو والد است که دو فرزند را تولید می­ کنند (شکل (۲-۵) را ملاحظه کنید) (شاه­حسینی، موسوی و ملاجعفری، ۱۳۹۱).
والد۱