قاعده توقف: الگوریتم زمانی متوقف میگردد که جمعیت به سمت راه حل بهینه همگرا گردد و به عبارت دیگر به آن برسد یا نزدیک شود. قواعد توقف متعددی برای الگوریتم ژنتیک وجود دارد که بعضی از روش های آن به شرح زیر است:

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

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