الگوریتم ژنتیک: ساده و جادویی

[آبجی]

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

• الگوریتم ژنتیک
• استراتژیهای تکاملی
• برنامه ریزی تکاملی

الگوریتم ژنتیک
الگوریتم ژنتیک یکی از الگوریتمهای تکاملی است که اگرچه به شکلهای مختلفی ارائه شده است اما پایه تمام این شکلها چهار فرایند است که در ادامه به آنها پرداخته می شود. الگوریتم ژنتیک یک بهینه سازی غیر جبری است که مناسب برای توابعی است که بهینه سازی آنها با روشهای جبری کاری طاقت فرسا است. الگوریتم ژنتیک برای مسایلNP-Hard بسیار مناسب می باشد. همچنین این الگوریتمها قادر به حل مسایلی هستند که در فضای حلشان ناپیوستگی وجود دارد. یکی دیگر از مزایای این روش، توانایی اعمال آن به مسایلی است که دارای متغیرهای زیاد می باشند.
از طرف دیگر، الگوریتم ژنتیک ضعفهایی نیز دارد. این روش غیر جبری است بنابراین پاسخ دقیق مساله را نمی یابد و حتی ممکن است برای یک مساله مشخص با هر بار بکارگیری پاسخی متفاوت ارائه دهد. اگرچه تمامی این پاسخها می توانند پاسخهایی باشند که دقت مورد نیاز را برآورده کنند. الگوریتمهای ژنتیک قابل اعمال به تمام مسایل بهینه سازی هستند اما در مسایلی این روشها نسبت به سایر روشها بسیار کندتر عمل می کنند. بنابراین ژنتیک، روشی عمومی برای تمام جستجوها نمی باشد.
با این وجود این الگوریتم (و سایر الگوریتمهای تکاملی) فضای پاسخ را به صورت موازی و خوشه به خوشه و نه به صورت عضو به عضو می کاوند به همین دلیل امکان رخ دادن اپتیمم های محلی از بین می رود. این روشها نیازی به اطلاعات مربوط به مشتقات تابع هدف ندارند. تنها شکل اصلی تابع مورد نیاز می باشد.
چهار فرایند اصلی در الگوریتم ژنتیک عبارتند از

• ایجاد جمعیت کروموزومها (تبدیل مجموعه ای از پاسخهای ممکن به شکل کروموزوم و ژن)
• انتخاب (جفت یابی) (Selection)
• ترکیب (CrossOver)
• جهش (Mutation)

در شکل (ضمیمه ها، Pic1) چگونگی مراحل الگوریتم ژنتیک، نشان داده شده است.
قبل از ادامه بحث لازم است قسمتی بسیار مهم از الگوریتم ژنتیک، تابع تطابق (تابع هدف) (Fitness function - Objective function) را معرفی کنیم. این تابع شاید قلب الگوریتم ژنتیک باشد. انتخاب اعضاء بهتر یا به عبارتی زنده ماندن ژنهای بهتر با این تابع کنترل می شود. در ادامه به صورت مفصل درباره تابع تطابق صحبت خواهد شد.

[آبجی]

الگوریتم ژنتیک - قسمت دوم
عناصر الگوریتم ژنتیک
الگوریتمهای ژنتیک اگرچه در شکلهای مختلفی وجود دارند اما حداقل شامل چهار قسمت زیر می باشند:

• جمعیتی از جوابهای ممکن که به کروموزوم و ژن تبدیل شده اند.
• عملگر انتخاب
• عملگر ترکیب
• عملگر جهش

طراحی یک الگوریتم ژنتیک برای مساله ای خاص دارای سه مرحله است:

• طراحی شیوه کدگذاری
• طراحی تابع تطابق
• طراحی عملگرهای ژنتیک

در ادامه هر کدام از این عناصر مورد بررسی قرار می گیرد.

[آبجی]

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