Vahid_moghaddam
شنبه 29 اردیبهشت 1386, 09:10 صبح
الگوریتمهای تکاملی
در طبیعت تمام موجودات زنده در حال تکاملند. تکامل برای سازگار شدن با محیطی که در حال تغییر است. در واقع موجودات زنده به سمتی حرکت می کنند که به بهترین گونه ها تبدیل شوند. در زندگی طبیعی، اساس تکامل، ژنها هستند. ژنها با قرار گرفتن در کنار یکدیگر، کروموزومها را تشکیل میدهند. به طور خلاصه، برای بوجود آمدن یک موجود جدید از دو موجود والد، کروموزومها و در واقع ژنها با یکدیگر ترکیب میشوند. به عبارت بهتر موجود جدید شامل ژنهایی از والدین خود است که با آرایشی تازه در کنار هم قرار گرفته اند. تقریبا این آرایش به صورت تصادفی شکل میگیرد و در بعضی موجودات، ژنها جهش می یابند و تبدیل به ژنهایی می شوند که در والدین نبوده اند. اگرچه این روند به صورت تصادفی رخ می دهد، موجودات همیشه به سمت بهتر شدن پیش می روند و فرزندان ضعیف به تدریج از چرخه زندگی حذف می شوند.
براساس تئوری داروین که بیان می کند در طبیعت بهترین گونه ها زنده می مانند، الگوریتم هایی بنا شده که آنها را به عنوان الگوریتم ها تکاملی می شناسیم. این الگوریتمها، الگوریتمهای جستجوی تصادفی هستند که تکامل زیست شناسی را تقلید می کنند. این روشها بر جمعیتی از پاسخ های ممکن مساله با در نظر گرفتن اصل زنده ماندن بهترین اعضا، اعمال می شوند تا پاسخهای بهتر و بهتر مساله را تولید کنند. پاسخهای جدید پتانسیل مساله در یک نسل جدید متولد می شوند. در هر نسل مجموعه ای از پاسخهای شدنی با پروسه انتخاب اعضای نسل قبل بر اساس تطابقشان (بهتر بودنشان) و ترکیب آنها با تقلید از آنچه در طبیعت رخ می دهد، بوجود می آیند. این روند، یعنی انتخاب ژنهای بهتر، زنده ماندن ژنهای بهتر و از بین رفتن ژنهای نامناسب، مجموعه پاسخها را با تکرار پروسه به سمت تکامل می برد. در الگوریتمهای تکاملی اتفاقاتی مثل جفت یابی، ترکیب، جهش، مهاجرت و.... شبیه سازی می شوند.
الگوریتمهای تکاملی به سه دسته اصلی تقسیم می شوند:
الگوریتم ژنتیک
استراتژیهای تکاملی
برنامه ریزی تکاملیالگوریتم ژنتیک
الگوریتم ژنتیک یکی از الگوریتمهای تکاملی است که اگرچه به شکلهای مختلفی ارائه شده است اما پایه تمام این شکلها چهار فرایند است که در ادامه به آنها پرداخته می شود. الگوریتم ژنتیک یک بهینه سازی غیر جبری است که مناسب برای توابعی است که بهینه سازی آنها با روشهای جبری کاری طاقت فرسا است. الگوریتم ژنتیک برای مسایلNP-Hard بسیار مناسب می باشد. همچنین این الگوریتمها قادر به حل مسایلی هستند که در فضای حلشان ناپیوستگی وجود دارد. یکی دیگر از مزایای این روش، توانایی اعمال آن به مسایلی است که دارای متغیرهای زیاد می باشند.
از طرف دیگر، الگوریتم ژنتیک ضعفهایی نیز دارد. این روش غیر جبری است بنابراین پاسخ دقیق مساله را نمی یابد و حتی ممکن است برای یک مساله مشخص با هر بار بکارگیری پاسخی متفاوت ارائه دهد. اگرچه تمامی این پاسخها می توانند پاسخهایی باشند که دقت مورد نیاز را برآورده کنند. الگوریتمهای ژنتیک قابل اعمال به تمام مسایل بهینه سازی هستند اما در مسایلی این روشها نسبت به سایر روشها بسیار کندتر عمل می کنند. بنابراین ژنتیک، روشی عمومی برای تمام جستجوها نمی باشد.
با این وجود این الگوریتم (و سایر الگوریتمهای تکاملی) فضای پاسخ را به صورت موازی و خوشه به خوشه و نه به صورت عضو به عضو می کاوند به همین دلیل امکان رخ دادن اپتیمم های محلی از بین می رود. این روشها نیازی به اطلاعات مربوط به مشتقات تابع هدف ندارند. تنها شکل اصلی تابع مورد نیاز می باشد.
چهار فرایند اصلی در الگوریتم ژنتیک عبارتند از
ایجاد جمعیت کروموزومها (تبدیل مجموعه ای از پاسخهای ممکن به شکل کروموزوم و ژن)
انتخاب (جفت یابی) (Selection)
ترکیب (CrossOver)
جهش (Mutation)در شکل (ضمیمه ها، Pic1) چگونگی مراحل الگوریتم ژنتیک، نشان داده شده است.
قبل از ادامه بحث لازم است قسمتی بسیار مهم از الگوریتم ژنتیک، تابع تطابق (تابع هدف) (Fitness function - Objective function) را معرفی کنیم. این تابع شاید قلب الگوریتم ژنتیک باشد. انتخاب اعضاء بهتر یا به عبارتی زنده ماندن ژنهای بهتر با این تابع کنترل می شود. در ادامه به صورت مفصل درباره تابع تطابق صحبت خواهد شد.
در طبیعت تمام موجودات زنده در حال تکاملند. تکامل برای سازگار شدن با محیطی که در حال تغییر است. در واقع موجودات زنده به سمتی حرکت می کنند که به بهترین گونه ها تبدیل شوند. در زندگی طبیعی، اساس تکامل، ژنها هستند. ژنها با قرار گرفتن در کنار یکدیگر، کروموزومها را تشکیل میدهند. به طور خلاصه، برای بوجود آمدن یک موجود جدید از دو موجود والد، کروموزومها و در واقع ژنها با یکدیگر ترکیب میشوند. به عبارت بهتر موجود جدید شامل ژنهایی از والدین خود است که با آرایشی تازه در کنار هم قرار گرفته اند. تقریبا این آرایش به صورت تصادفی شکل میگیرد و در بعضی موجودات، ژنها جهش می یابند و تبدیل به ژنهایی می شوند که در والدین نبوده اند. اگرچه این روند به صورت تصادفی رخ می دهد، موجودات همیشه به سمت بهتر شدن پیش می روند و فرزندان ضعیف به تدریج از چرخه زندگی حذف می شوند.
براساس تئوری داروین که بیان می کند در طبیعت بهترین گونه ها زنده می مانند، الگوریتم هایی بنا شده که آنها را به عنوان الگوریتم ها تکاملی می شناسیم. این الگوریتمها، الگوریتمهای جستجوی تصادفی هستند که تکامل زیست شناسی را تقلید می کنند. این روشها بر جمعیتی از پاسخ های ممکن مساله با در نظر گرفتن اصل زنده ماندن بهترین اعضا، اعمال می شوند تا پاسخهای بهتر و بهتر مساله را تولید کنند. پاسخهای جدید پتانسیل مساله در یک نسل جدید متولد می شوند. در هر نسل مجموعه ای از پاسخهای شدنی با پروسه انتخاب اعضای نسل قبل بر اساس تطابقشان (بهتر بودنشان) و ترکیب آنها با تقلید از آنچه در طبیعت رخ می دهد، بوجود می آیند. این روند، یعنی انتخاب ژنهای بهتر، زنده ماندن ژنهای بهتر و از بین رفتن ژنهای نامناسب، مجموعه پاسخها را با تکرار پروسه به سمت تکامل می برد. در الگوریتمهای تکاملی اتفاقاتی مثل جفت یابی، ترکیب، جهش، مهاجرت و.... شبیه سازی می شوند.
الگوریتمهای تکاملی به سه دسته اصلی تقسیم می شوند:
الگوریتم ژنتیک
استراتژیهای تکاملی
برنامه ریزی تکاملیالگوریتم ژنتیک
الگوریتم ژنتیک یکی از الگوریتمهای تکاملی است که اگرچه به شکلهای مختلفی ارائه شده است اما پایه تمام این شکلها چهار فرایند است که در ادامه به آنها پرداخته می شود. الگوریتم ژنتیک یک بهینه سازی غیر جبری است که مناسب برای توابعی است که بهینه سازی آنها با روشهای جبری کاری طاقت فرسا است. الگوریتم ژنتیک برای مسایلNP-Hard بسیار مناسب می باشد. همچنین این الگوریتمها قادر به حل مسایلی هستند که در فضای حلشان ناپیوستگی وجود دارد. یکی دیگر از مزایای این روش، توانایی اعمال آن به مسایلی است که دارای متغیرهای زیاد می باشند.
از طرف دیگر، الگوریتم ژنتیک ضعفهایی نیز دارد. این روش غیر جبری است بنابراین پاسخ دقیق مساله را نمی یابد و حتی ممکن است برای یک مساله مشخص با هر بار بکارگیری پاسخی متفاوت ارائه دهد. اگرچه تمامی این پاسخها می توانند پاسخهایی باشند که دقت مورد نیاز را برآورده کنند. الگوریتمهای ژنتیک قابل اعمال به تمام مسایل بهینه سازی هستند اما در مسایلی این روشها نسبت به سایر روشها بسیار کندتر عمل می کنند. بنابراین ژنتیک، روشی عمومی برای تمام جستجوها نمی باشد.
با این وجود این الگوریتم (و سایر الگوریتمهای تکاملی) فضای پاسخ را به صورت موازی و خوشه به خوشه و نه به صورت عضو به عضو می کاوند به همین دلیل امکان رخ دادن اپتیمم های محلی از بین می رود. این روشها نیازی به اطلاعات مربوط به مشتقات تابع هدف ندارند. تنها شکل اصلی تابع مورد نیاز می باشد.
چهار فرایند اصلی در الگوریتم ژنتیک عبارتند از
ایجاد جمعیت کروموزومها (تبدیل مجموعه ای از پاسخهای ممکن به شکل کروموزوم و ژن)
انتخاب (جفت یابی) (Selection)
ترکیب (CrossOver)
جهش (Mutation)در شکل (ضمیمه ها، Pic1) چگونگی مراحل الگوریتم ژنتیک، نشان داده شده است.
قبل از ادامه بحث لازم است قسمتی بسیار مهم از الگوریتم ژنتیک، تابع تطابق (تابع هدف) (Fitness function - Objective function) را معرفی کنیم. این تابع شاید قلب الگوریتم ژنتیک باشد. انتخاب اعضاء بهتر یا به عبارتی زنده ماندن ژنهای بهتر با این تابع کنترل می شود. در ادامه به صورت مفصل درباره تابع تطابق صحبت خواهد شد.