دانلود پایان نامه

2-6 عملگرهاي الگوریتم ژنتيك
در الگوريتم‏هاي ژنتيكي, در طي مرحله توليد مثل ازعملگرهاي ژنتيكي استفاده مي‏شود. با تاثير اين عملگرها بر روي يك جمعيت, نسل بعدي آن جمعيت توليد مي‏شود. عملگرهاي انتخاب , آميزش و جهش معمولاً بيشترين كاربرد را در الگوريتم‏هاي ژنتيكي دارند.
عملگر انتخاب
عملگر انتخاب در الگوریتم وراثتی، برداشتی از انتخاب طبیعی در وراثت طبیعی است. هدف از اعمال این عملگر، انتخاب بعضی از افراد جمعیت برای زاد و ولد و ایجاد نسل بعد است. در الگوریتم ژنتیک عملگره بر پایه احتمالات عمل می کنند و قطعیتی در کار نیست. این موضوع به این معنی است که به هر یک از کروموزوم ها متناسب با شایستگی شان، شانسی برای انتخاب تعلق می گیرد ولی انتخاب بر مبنای احتمال صورت می پذیرد.
با استفاده از این عملگر از بین کروموزوم های موجود در یک جمعیت تعدادی برای تولید مثل انتخاب شده و به حوضچه ی ازدواج منتقل می شوند. انتخاب کروموزوم ها به صورت تصادفی است اما فرآیند انتخاب به گونه ای است که کروموزوم های با شایستگی بیشتر از شانس بیشتری برای انتخاب و تولید مثل برخوردار می شوند. در طی فرآیند انتخاب این امکان وجود دارد که بعضی از کروموزوم های ضعیف حتی برای یک مرتبه هم انتخاب نشوند. اين عملگر از بين كروموزوم‏هاي موجود در يك جمعيت, تعدادي كروموزوم را براي توليد مثل انتخاب مي‏كند. كروموزوم‏هاي برازنده‏تر شانس بيشتري دارند تا براي توليد مثل انتخاب شوند.
عملگر آميزش (تقاطع)
در جریان عمل تلفیق به صورت اتفاقی بخشهایی از کروموزوم ها با یکدیگر تعویض می شوند. این موضوع باعث می شود که فرزندان ترکیبی از خصوصیات والدین خود را به همراه داشته باشند و دقیقاً مشابه یکی از والدین نباشند. عملگر ادغام مهمترین عملگر در الگوریتم ژنتیک است. این عملگر بر روی دو (چند) کروموزوم والد عمل ادغام را اجرا کرده و دو فرزند برای نسل جدید تولید می کند. هر چه کروموزوم های با خصوصیات بهتر انتخاب شوند، شانس رسیدن به جواب بهینه در تکرارهای کمتری از الگوریتم امکان پذیر می شود. هدف تولید فرزند جدید می باشد به این امید که خصوصیات خوب دو موجود در فرزندشان جمع شده و یک موجود بهتری را تولید کند.
عملگر جهش
در الگوریتم ژنتیک، اغلب عملگر جهش بعد از عملگر ادغام به کروموزوم ها اعمال می شود. اين عملگر يك ژن از يك كروموزوم را به طور تصادفي انتخاب نموده و سپس محتواي آن ژن را تغيير مي‏دهد. اگر ژن از جنس اعداد دودويي باشد، آن را به وارونش تبديل مي‏كند و چنانچه متعلق به يك مجموعه باشد، مقدار يا عنصر ديگري از آن مجموعه را به جاي آن ژن قرار مي‏دهد. عملگر جهش برای تنوع بخشیدن به جمعیت و ایجاد نقاط جدید جستجو اعمال می شود. میزان احتمال این عملگر از اهمیت بالایی برخوردار است. اگر احتمال رخدادجهش بیش از حد لازم باشد، الگوریتم توانایی همگرایی به جواب بهینه را از دست می دهد. از سوی دیگر، چنانچه مقدار جهش کم باشد، احتمال گیر افتادن الگوریتم در بهینه های محلی وهمگرایی زودرس به خاطر عدم تنوع ژنی افزایش پیدا می کند. تنطیم نرخ جهش در الگوریتم ژنتیک نقش مهمی دارد[15].
انتخاب نسل بعد
بعد از اعمال عملگرهای وراثتی تلفیق و جهش، N کروموزوم فرزند تولید می شود. حال نوبت به آن رسیده است که نسل بعد مشخص شود. در ساده ترین و متداول ترین روش، کروموزوم های فرزند نسل بعد جمعیت را می سازند و کروموزوم های والد (نسل فعلی) از بین خواهند رفت.
بررسی شرط توقف
بعد از آن که نسل بعد تولید شد، یک مرحله از اجرای الگوریتم به پایان رسیده است. برای توقف می توان از دو نوع معیار استفاده کرد. معیارهایی که در آن، توقف الگوریتم بر مبنای گذشت زمان و تعداد مراحل تکرار الگوریتم صورت می گیرد و معیارهایی که توقف با توجه به پاسخ الگوریتم انجام می شود.
چنان چه زمان پایان پذیرفتن اجرای الگوریتم فرا نرسیده باشد؛ الگوریتم به مرحله رمز گشایی کروموزوم ها منتقل خواهد شد. به همین ترتیب، الگوریتم بارها و بارها تکرار می شود تا زمانی که شرط توقف الگوریتم ارضا شده و اجرای الگوریتم پایان پذیرد. در پایان، بهترین جواب تولید شده توسط الگوریتم، در خروجی ظاهر خواهد شد[15].
2-7 مزایای الکوریتم ژنتیک
قدرت الگوریتم ژنتیک در توانایی وفق دادن خودش به صورت ذاتی می باشد. در سیستم های طبیعی، گونه های سازگار با محیط از میان تعامل پی در پی و نسل های در ارتباط با محیط هستند. بعد از چندین نسل متوالی، فقط گونه هایی که می توانند به خوبی با محیط وفق پیدا کنند باقی می مانند و بقیه ناپدید می شوند. در اصطلاح ریاضی، افراد همانند متغیر های مسئله هستند و محیط چگونگی مسئله است.
برخی از مزایای GA عبارتند از:
GA به سرعت می تواند یک مجموعه ی بزرگ از راه حل ها را پویش نماید. همچنین راه حل های بد تأثیر منفی ای بر روی راه حل نهایی نداشته و به آسانی حذف می شوند.
طبیعت GA به گونه ای است که نیازی به دانستن هیچ قاعده ای در ارتباط با مسئله مورد حل ندارد و تنها با قواعد داخلی خودش عمل می کند. این نکته در مورد مسائل پیچیده بسیار مفید واقع می شود.
GA به صورت کارا و موثری فضای مدل را جستجو می کند. بنابراین شانس بیشتری نسبت به روش های بهینه سازی محلی برای یافتن نقطه بهینه سراسری خواهد داشت.
در این روش هیچ نیازی به خطی سازی مسئله وجود ندارد.
این روش نیازی به محاسبه مشتقات جزئی ندارد.