در ادامه مطالبی که تا کنون در مورد الگوریتم های تکاملی نوشته‌ام، می‌خواهم به بررسی چگونگی تشخیص قابل حل بودن یک مسئله با الگوریتم ژنتیک بپردازم.
برای شبیه‌سازی مسائل در Genetic Algorithm، باید به سه سوال اساسی پاسخ گفت:
1. ساختار مسئله چگونه است؟ آیا یک مسئله بهینه‌سازی محسوب می‌شود؟ هدف از حل این مسئله چیست؟
2. آیا پاسخ این مسئله را میتوان به صورت یک کروموزوم یا به عبارتی به شکل آرایه‌ای از متغیرها و پارامتهای مسئله نشان داد؟
3. آیا میتوان روند رسیدن به پاسخ را در یک تابع ارزیابی تعریف نمود؟ آیا این تابع ارزیابی در تمام مراحل اجرای الگوریتم و از نسل آغازین تا نسلهای پایانی معتبر بوده و مقادیر صحیحی برمی‌گرداند؟
معمولاً در صورتی که نتوان به روشنی و صراحت به این سه سوال پاسخ داد، به احتمال زیاد ساختار مسئله مورد نظر با GA تطابق نداشته و الگوریتم ژنتیک گزینه مناسبی جهت حل آن مسئله نخواهد بود. اکثر مسائل کلاسیکی که ناگزیر از جستجوی تمام فضای حالت آنها هستیم در این دسته قرار می‌گیرند، این گونه مسائل عموماً بوسیله روشهای جستجوی سیستماتیکی مثل A* بهتر حل می‌شوند.
برای پاسخ به سوال اول و تشخیص ساختار مسئله، باید آن را به بخشهای کوچکتر و سوالات ساده‌تر تقسیم کنیم. پس از شناسایی سوالهای اصلی، با توجه به صورت آنها میتوان به سادگی نوع مسئله را تشخیص داد. معمولاً در صورت مسائل بهینه‌سازی، از کلماتی مانند «کمترین»، «بیشترین»، «کوتاه‌ترین»، «طولانی‌ترین» و «کم‌هزینه‌ترین» استفاده می‌شود.
پس از شناسایی نوع و ساختار مسئله، می‌بایست روشی برای نمایش پاسخ آن به شکل کروموزوم پیدا کرده و در نهایت تابعی برای ارزیابی کروموزومها طراحی شود.
کروموزومهای مورد استفاده درالگوریتم ژنتیک، با الهام‌گیری از ساختار کروموزومهای حقیقی ساخته می‌شوند. کروموزومهای حقیقی متشکل از زنجیره‌های DNA هستند و این زنجیره‌ها را در واقع میتوان به صورت رشته‌ای از ژنها متصور شد، که هر ژن مانند یکی از پارامترهای مسئله است.
(ادامه مطلب…)
