عناصر الگوریتم ژنتیک
الگوریتمهای ژنتیک اگرچه در شکلهای مختلفی وجود دارند اما حداقل شامل چهار قسمت زیر می باشند:
طراحی یک الگوریتم ژنتیک برای مساله ای خاص دارای سه مرحله است:
- جمعیتی از جوابهای ممکن که به کروموزوم و ژن تبدیل شده اند.
- عملگر انتخاب
- عملگر ترکیب
- عملگر جهش
در ادامه هر کدام از این عناصر مورد بررسی قرار می گیرد.
- طراحی شیوه کدگذاری
- طراحی تابع تطابق
- طراحی عملگرهای ژنتیک
جمعیت
مفهوم جمعیت در الگوریتم ژنتیک شبیه به چیزی است که در زندگی طبیعی وجود دارد. برای مساله گزاره هایی وجود دارند که می توانند به عنوان پاسخ، چه درست، چه غلط در نظرگرفته شوند. به این گزاره ها پاسخهای ممکن یا شدنی می گوییم. مثلا اگر مساله یافتن ماکزیمم یک تابع در مجموعه اعداد صحیح باشد، تمام اعداد صحیح می توانند به عنوان پاسخ شدنی مساله در نظر گرفته شوند.
در الگوریتم ژنتیک به عنوان اولین مرحله لازم است مجموعه ای از جوابهای شدنی به عنوان جمعیت اولیه ایجاد شود. اعضای این مجموعه معمولا به صورت تصادفی انتخاب می شوند اما در الگوریتمهای بهینه، از قیدهایی استفاده می شود تا جمعیت پراکندگی بیش از حد نداشته باشد. تعداد اعضای جمعیت به نوع مساله بستگی دارد. در واقع تعداد اعضا، پارامتری است که با تغییر آن می توان دقت جوابها و سرعت همگرایی جستجو را بهبود بخشید. در برخی مسایل یک جمعیت 8 عضوی کاملا مناسب است در حالی که در برخی یک جمعیت 100 عضوی نیز کافی نیست. بر اساس تجربه بهتر است تعداد اعضای جمعیت عددی بین 10 تا 160 باشد.
بعد از انتخاب جمعیت، لازم است اعضای آن به شکل کروموزوم درآیند. هر کروموزوم آرایشی از چند ژن است. در مرحله تبدیل (کدگذاری) (Encoding) ، جوابها به ژنها تبدیل می شوند. روشهای مختلفی برای کدگذاری وجود دارد. انتخاب روش وابسته به نوع مساله ای است که به آن پرداخته می شود. نکته قابل ذکر در تبدیل جوابها به کروموزوم ها این است که طول کروموزوم ها باید برابر و ثابت باشد یعنی اگر یک جواب از مجموعه به کروموزومی با n ژن تبدیل شد، طول تمام کروموزومهای دیگر نیز باید n باشد. طول کروموزومها را نوع کدگذاری، جنس پاسخها و محدوده پاسخها تعیین می کند. کروموزومها در الگوریتم ژنتیک باید به گونه ای باشند که دقیقا تمام مشخصات پاسخ را در خود ذخیره کنند. مثلا اگر مساله با اعداد حقیقی کار می کند، کروموزوم باید شامل اطلاعات مربوط به علامت عدد، تعداد رقمهای اعشاری، محدوده عدد و ... باشد. مهمترین نوع کدگذاری، کدگذاری باینری است.
جمعیت
ادامه در فایل ضمیمه
انتخاب در الگوریتم ژنتیک
انتخاب چرخ رولت
انتخاب ترتیبی، بولتزمن، حالت پایدار و رقابتی
ترکیب و انواع آن در GAs
قوانین ایجاد تاپیک در تالار
پاسخ با نقل قول