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