چگونه یک مسئله را با الگوریتم ژنتیک حل کنیم؟

در ادامه مطالبی که تا کنون در مورد الگوریتم های تکاملی نوشته‌ام، می‌خواهم به بررسی چگونگی تشخیص قابل حل بودن یک مسئله با الگوریتم ژنتیک بپردازم.
برای شبیه‌سازی مسائل در Genetic Algorithm، باید به سه سوال اساسی پاسخ گفت:

1.  ساختار مسئله چگونه است؟ آیا یک مسئله بهینه‌سازی محسوب می‌شود؟ هدف از حل این مسئله چیست؟

2.  آیا پاسخ این مسئله را می‌توان به صورت یک کروموزوم یا به عبارتی به شکل آرایه‌ای از متغیرها و پارامتهای مسئله نشان داد؟

3.  آیا می‌توان روند رسیدن به پاسخ را در یک تابع ارزیابی تعریف نمود؟ آیا این تابع ارزیابی در تمام مراحل اجرای الگوریتم و از نسل آغازین تا نسلهای پایانی معتبر بوده و مقادیر صحیحی برمی‌گرداند؟

معمولاً در صورتی که نتوان به روشنی و صراحت به این سه سوال پاسخ داد، به احتمال زیاد ساختار مسئله مورد نظر با GA تطابق نداشته و الگوریتم ژنتیک گزینه مناسبی جهت حل آن مسئله نخواهد بود. اکثر مسائل کلاسیکی که ناگزیر از جستجوی تمام فضای حالت آنها هستیم در این دسته قرار می‌گیرند، این گونه مسائل عموماً بوسیله روشهای جستجوی سیستماتیکی مثل A* بهتر حل می‌شوند.

برای پاسخ به سوال اول و تشخیص ساختار مسئله، باید آن را به بخشهای کوچکتر و سوالات ساده‌تر تقسیم کنیم. پس از شناسایی سوالهای اصلی، با توجه به صورت آنها می‌توان به سادگی نوع مسئله را تشخیص داد. معمولاً در صورت مسائل بهینه‌سازی، از کلماتی مانند «کمترین»، «بیشترین»، «کوتاه‌ترین»، «طولانی‌ترین» و «کم‌هزینه‌ترین» استفاده می‌شود.

پس از شناسایی نوع و ساختار مسئله، می‌بایست روشی برای نمایش پاسخ آن به شکل کروموزوم پیدا کرده و در نهایت تابعی برای ارزیابی کروموزومها طراحی شود.

کروموزومهای مورد استفاده درالگوریتم ژنتیک، با الهام‌گیری از ساختار کروموزومهای حقیقی ساخته می‌شوند. کروموزومهای حقیقی متشکل از زنجیره‌های DNA هستند و این زنجیره‌ها را در واقع می‌توان به صورت رشته‌ای از ژنها متصور شد، که هر ژن مانند یکی از پارامترهای مسئله است.

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

برای ساخت کروموزوم در زبان برنامه‌نویسی، باید یکی از روشهای استاندارد کد‌گذاری ژنها در الگوریتم ژنتیک را انتخاب کنیم. روش‌های کدگذاری رایج به شرح ذیل هستند:

دودویی
روش کدگذاری دودویی یا رشته‌بیتی  قدیمی‌ترین روش نمایش مقدار ژنها بوده که از زمان پیدایش الگوریتم ژنتیک مورد استفاده قرار می‌گرفته است. در این روش مقدار هر کدام از ژنها به عددی دودویی تبدیل شده و کروموزوم به شکل آرایه‌ای عددی از اعداد مبنای دو (بیتهای 0 و 1) نمایش داده می‌شود.

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

نقطه ضعف مهم دیگری که در این روش کدگذاری به چشم می‌خورد، مصرف زیاد حافظه برای نگهداری آرایه بیتی است، چرا که در زبانهای برنامه‌نویسی سطح بالا کوچکترین نوع داده‌ای که برای نگهداری اعداد می‌تواند مورد استفاده قرار بگیرد، نوع Byte با بازه عددی 0 تا 255 است که به ازای هر متغیر، 1 بایت حافظه مصرف می‌کند. بنابراین اگر برای نمایش هر بیت در آرایه بیتی، از یک متغیر نوع Byte استفاده شده باشد، 1 بیت آن مصرف شده و 7 بیت دیگر به هدر رفته است.
برای حل این مشکل می‌توان در مسائلی که دارای تعداد متغیرهای زیاد و بازه عددی بزرگی هستند از همپوشانی بیتی استفاده کرده تا مصرف حافظه به حداقل برسد.

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

کاراکتری
در روش کاراکتری یا جایگشتی به جای مقدار هر ژن از یک کاراکتر A تا Z استفاده می‌شود. این شیوه کد‌گذاری تا حدی نمادین بوده و به دلیل محدودیت بازه مقادیر ژنها، فقط در موارد خاصی که استفاده از این روش ساده‌تر باشد، مورد استفاده قرار می‌گیرد.
به عنوان مثال ممکن است در پیاده‌سازی یک عملگر ترکیب یا جهش خاص، به دفعات از عمل حذف و اضافه ژنها به قسمتهای مختلف کروموزوم استفاده شده باشد. در این صورت با استفاده از نوع داده String به عنوان آرایه کاراکتری، به دلیل انعطاف‌پذیری بیشتری که نسبت به یک آرایه عددی ایستا دارد، به سادگی می‌توان کاراکترها را از رشته حذف یا به هر قسمت از آن اضافه نمود.

اندیسی
در این روش ابتدا یک کروموزوم را به عنوان مرجع و به یکی از روشهای عددی یا کاراکتری تولید می‌نماییم. سپس برای ساخت کروموزومهای دیگر، به جای درج مقادیر واقعی، اندیس مکان ژن مورد نظر در کروموزوم مرجع را درج می‌نماییم. از این روش زمانی استفاده می‌شود که مقادیر مورد انتظار برای ژنها ثابت بوده و فقط ترتیب قرارگیری آنها در کنار یکدیگر تغییر کند.
در صورتی که این شرط برقرار باشد، استفاده از روش اندیسی بهینه‌تر و سریعتر از روشهای دیگر است.

ماتریسی
این روش هم مانند روش اندیسی از یک کروموزوم مرجع استفاده می‌کند. در این روش برای مشخص نمودن ترتیب قرارگیری اندیس ژنها در کروموزوم، از یک ماتریس اولویت استفاده می‌شود. به عبارتی هر کروموزوم شامل یک ماتریس N×N بیتی برای نمایش اولویت N ژن موجود در کروموزوم مرجع است.

در قسمت آینده به بررسی چگونگی طراحی یک تابع ارزیابی (Fitness Function) کارا و بهینه برای مسائل مختلف خواهم پرداخت. ارزیابی بهینه، مهمترین بخش از حل مسائل با الگوریتم ژنتیک محسوب می‌شود.

جهت توضیحات بیشتر به کتاب “پیاده‌سای و حل مسائل کاربردی با الگوریتم ژنتیک” رجوع نمایید.

About محمد شمس

برنامه‌نویس، طراح انیمیشن و علاقمند به هوش مصنوعی

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *


8 × 6 =