تلفیق
جهش
انتخاب نسل بعد
خیر
شرط توقف؟
بلی
پایان
شکل ۲- ۱- نمودار بلوکی الگوریتم ژنتیک[۱۵]
مقدار دهی پارامترها: در شروع الگوریتم ژنتیک، باید ابتدا مقادیر پارامترهای الگوریتم مقدار دهی شود. مقدار دهی پارامترها شامل تعیین تعداد اعضای جمعیت، نرخ همبری و جهش، تعداد متغیرها، طول هر متغیر، طول کروموزوم، تعیین محدوده هر متغیر و دامنه جستجو، نحو خاتمه الگوریتم و مواردی جزیی دیگر می شود.
بعضی از این پارامترها با توجه به تجربه طراح و بعضی دیگر با توجه به طبیعت مسئله تعیین می شوند. به عنوان مثال، برای محاسبه طول کروموزوم، باید طول مورد نیاز برای هر یک از متغیرها را بر حسب بیت مد نظر قرار داد. هر چه تعداد بیت های در نظر گرفته شده برای متغیری که ماهیت پیوسته دارد، بیشتر باشد، خطای چندی سازی برای آن کمتر خواهد بود.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

طول هر کروموزوم از رابطه زیر بدست می آید.
که در آن،   بیان گر تعداد متغیرها،   بیان گر تعداد بیت مورد نیاز متغیر   ام است[۱۵].
تابع شایستگی: در بدو کار، باید برای هر مسئله یک تابع شایستگی طراحی و ابداع شود. تابع شایستگی باید از خصوصیات خاصی برخوردار باشد. این تابع باید به گونه ای طراحی شود که هر جواب ارائه شده به جواب بهینه نزدیکتر باشد، عدد شایستگی بزرگ تری برگرداند که نشان دهنده شایستگی بیشتر آن کروموزم (جواب) است. فراموش نشود که تابع شایستگی با توجه به تابع هدف طراحی می شود.
جمعیت اولیه: بعد از تنظیم پارامترها و طراحی تابع شایستگی، نوبت به آن می رسد که جمعیت اولیه ساخته شود. معمولا در الگوریتم ژنتیک جمعیت اولیه به طور اتفاقی ساخته می شود. تنها در موارد خاصی که شخص طراح اطلاعات مفیدی راجع به جواب بهینه داشته باشد؛ این اطلاعات را در قالب کروموزوم هایی به جمعیت منتقل می کند.
رمزگشایی کروموزوم ها: در هر کروموزوم، اطلاعات مربوط به یک نقطه از فضای ورودی به صورت رمز وجود دارد. برای مشخص شدن نقطه ای که کروموزوم به آن اشاره می کند، باید کروموزوم رمز گشایی شود. مراحل رمز گشایی به این ترتیب است که ابتدا هر کروموزوم باید به ژن های سازنده ی آن (متغیر ها) شکسته شود. این عمل باتوجه به طول رشته ی بیتی در نظر گرفته شده برای هر متغیر اجرا می شود. بعد از تجزیه کروموزوم ها به متغیر ها، نوبت به رمز گشایی آن ها می رسد. نحوه رمز گشایی متغیرها، بسته به این که متغیر،گسسته است یا پیوسته، متفاوت است. مقادیر متغیرها ی گسسته از حالت دودویی به حالت دهدهی تبدیل می شوند. مقادیر تبدیل شده، بیان گر یک مقدار عددی یا یک حالت خاص و از پیش تعریف شده برای آن متغیر هستند.
ارزیابی کروموزوم ها: در این مرحله به ازای هر یک از بردارهای ورودی، مقدار تابع شایستگی محاسبه می شود. برای این کار، مقادیر بدست آمده برای متغیر ها در تایع شایستگی قرار می گیرد. خروجی تابع شایستگی به ازای هر یک از متغیر های ورودی به عنوان شایستگی کروموزوم مربوط به آن در نظر گرفته می شود. باید توجه داشت که هدف از بهینه سازی، بهینه کردن تابع هدف است. از آنجایی که تابع شایستگی با توجه به تابع هدف طراحی شده است، با بهینه شدن تابع شایستگی، تابع هدف نیز بهینه خواهد شد.

۲-۶ عملگرهای الگوریتم ژنتیک

در الگوریتم‏های ژنتیکی, در طی مرحله تولید مثل ازعملگرهای ژنتیکی استفاده می‏شود. با تاثیر این عملگرها بر روی یک جمعیت, نسل بعدی آن جمعیت تولید می‏شود. عملگرهای انتخاب , آمیزش و جهش معمولاً بیشترین کاربرد را در الگوریتم‏های ژنتیکی دارند.
عملگر انتخاب
عملگر انتخاب در الگوریتم وراثتی، برداشتی از انتخاب طبیعی در وراثت طبیعی است. هدف از اعمال این عملگر، انتخاب بعضی از افراد جمعیت برای زاد و ولد و ایجاد نسل بعد است. در الگوریتم ژنتیک عملگره بر پایه احتمالات عمل می کنند و قطعیتی در کار نیست. این موضوع به این معنی است که به هر یک از کروموزوم ها متناسب با شایستگی شان، شانسی برای انتخاب تعلق می گیرد ولی انتخاب بر مبنای احتمال صورت می پذیرد.
با بهره گرفتن از این عملگر از بین کروموزوم های موجود در یک جمعیت تعدادی برای تولید مثل انتخاب شده و به حوضچه ی ازدواج^[۱۰۴] منتقل می شوند. انتخاب کروموزوم ها به صورت تصادفی است اما فرایند انتخاب به گونه ای است که کروموزوم های با شایستگی بیشتر از شانس بیشتری برای انتخاب و تولید مثل برخوردار می شوند. در طی فرایند انتخاب این امکان وجود دارد که بعضی از کروموزوم های ضعیف حتی برای یک مرتبه هم انتخاب نشوند. این عملگر از بین کروموزوم‏های موجود در یک جمعیت, تعدادی کروموزوم را برای تولید مثل انتخاب می‏کند. کروموزوم‏های برازنده‏تر شانس بیشتری دارند تا برای تولید مثل انتخاب شوند.
عملگر آمیزش (تقاطع)
در جریان عمل تلفیق به صورت اتفاقی بخشهایی از کروموزوم ها با یکدیگر تعویض می شوند. این موضوع باعث می شود که فرزندان ترکیبی از خصوصیات والدین خود را به همراه داشته باشند و دقیقاً مشابه یکی از والدین نباشند. عملگر ادغام مهمترین عملگر در الگوریتم ژنتیک است. این عملگر بر روی دو (چند) کروموزوم والد عمل ادغام را اجرا کرده و دو فرزند برای نسل جدید تولید می کند. هر چه کروموزوم های با خصوصیات بهتر انتخاب شوند، شانس رسیدن به جواب بهینه در تکرارهای کمتری از الگوریتم امکان پذیر می شود. هدف تولید فرزند جدید می باشد به این امید که خصوصیات خوب دو موجود در فرزندشان جمع شده و یک موجود بهتری را تولید کند.
عملگر جهش
در الگوریتم ژنتیک، اغلب عملگر جهش بعد از عملگر ادغام به کروموزوم ها اعمال می شود. این عملگر یک ژن از یک کروموزوم را به طور تصادفی انتخاب نموده و سپس محتوای آن ژن را تغییر می‏دهد. اگر ژن از جنس اعداد دودویی باشد، آن را به وارونش تبدیل می‏کند و چنانچه متعلق به یک مجموعه باشد، مقدار یا عنصر دیگری از آن مجموعه را به جای آن ژن قرار می‏دهد. عملگر جهش برای تنوع بخشیدن به جمعیت و ایجاد نقاط جدید جستجو اعمال می شود. میزان احتمال این عملگر از اهمیت بالایی برخوردار است. اگر احتمال رخدادجهش بیش از حد لازم باشد، الگوریتم توانایی همگرایی به جواب بهینه را از دست می دهد. از سوی دیگر، چنانچه مقدار جهش کم باشد، احتمال گیر افتادن الگوریتم در بهینه های محلی وهمگرایی زودرس به خاطر عدم تنوع ژنی افزایش پیدا می کند. تنطیم نرخ جهش در الگوریتم ژنتیک نقش مهمی دارد[۱۵].
انتخاب نسل بعد
بعد از اعمال عملگرهای وراثتی تلفیق و جهش، N کروموزوم فرزند تولید می شود. حال نوبت به آن رسیده است که نسل بعد مشخص شود. در ساده ترین و متداول ترین روش، کروموزوم های فرزند نسل بعد جمعیت را می سازند و کروموزوم های والد (نسل فعلی) از بین خواهند رفت.
بررسی شرط توقف
بعد از آن که نسل بعد تولید شد، یک مرحله از اجرای الگوریتم به پایان رسیده است. برای توقف می توان از دو نوع معیار استفاده کرد. معیارهایی که در آن، توقف الگوریتم بر مبنای گذشت زمان و تعداد مراحل تکرار الگوریتم صورت می گیرد و معیارهایی که توقف با توجه به پاسخ الگوریتم انجام می شود.
چنان چه زمان پایان پذیرفتن اجرای الگوریتم فرا نرسیده باشد؛ الگوریتم به مرحله رمز گشایی کروموزوم ها منتقل خواهد شد. به همین ترتیب، الگوریتم بارها و بارها تکرار می شود تا زمانی که شرط توقف الگوریتم ارضا شده و اجرای الگوریتم پایان پذیرد. در پایان، بهترین جواب تولید شده توسط الگوریتم، در خروجی ظاهر خواهد شد[۱۵].

۲-۷ مزایای الکوریتم ژنتیک

قدرت الگوریتم ژنتیک در توانایی وفق دادن خودش به صورت ذاتی می باشد. در سیستم های طبیعی، گونه های سازگار با محیط از میان تعامل پی در پی و نسل های در ارتباط با محیط هستند. بعد از چندین نسل متوالی، فقط گونه هایی که می توانند به خوبی با محیط وفق پیدا کنند باقی می مانند و بقیه ناپدید می شوند. در اصطلاح ریاضی، افراد همانند متغیر های مسئله هستند و محیط چگونگی مسئله است.
برخی از مزایای GA عبارتند از:
GA به سرعت می تواند یک مجموعه ی بزرگ از راه حل ها را پویش نماید. همچنین راه حل های بد تأثیر منفی ای بر روی راه حل نهایی نداشته و به آسانی حذف می شوند.
طبیعت GA به گونه ای است که نیازی به دانستن هیچ قاعده ای در ارتباط با مسئله مورد حل ندارد و تنها با قواعد داخلی خودش عمل می کند. این نکته در مورد مسائل پیچیده بسیار مفید واقع می شود.
GA به صورت کارا و موثری فضای مدل را جستجو می کند. بنابراین شانس بیشتری نسبت به روش های بهینه سازی محلی برای یافتن نقطه بهینه سراسری خواهد داشت.
در این روش هیچ نیازی به خطی سازی مسئله وجود ندارد.
این روش نیازی به محاسبه مشتقات جزئی ندارد.
در این روش نمونه های بیشتری از مدل های محتمل تر نسبت به مدل های غیر محتمل ساخته می شود.

۲-۸ معایب الگوریتم ژنتیک

یک جواب خوب پیدا می کنند ولی ممکن است جواب بهینه را پیدا نکنند
به حافظه و محاسبات زیادی نیاز دارند
در مورد اینکه جواب پیدا شده چقدر خوب است و آیا جواب بهتری وجود دارد، نمی توانیم هیچگونه ادعائی داشته باشیم
پشتوانه ریاضی ضعیفی دارند
در دو بار اجرای مختلف، جواب های متفاوتی دریافت می کنیم
تعدد پارامترهای الگوریتم: هر چند الگوریتمهای ژنتیکی در دسته الگوریتمهای بهینه ‏سازی قرار می‏گیرند، اما تنظیم کردن این پارامترها گاهی به یک مسئله بهینه ‏سازی دیگر تبدیل خواهد شد[۱۲].

۲-۹ کاربردهای الگوریتم ژنتیک

حل مسائل سخت
برخی کاربردهای هنری شامل ترکیبات صدا و تصویر و مولتی مدیا
آنالیز و بهینه سازی سیستم های دینامیکی غیر خطی