الگوریتم ژنتیک : تاثیر روش بازنمایی در شایستگی کروموزوم

چکیده

اگر بخواهیم مساله ای را به کمک #الگوریتم_ژنتیک حل کنیم، در اولین قدم باید تعریفی برای کروموزوم بیابیم. اینکار به کدگذاری و نمایش شهرت دارد (coding & representation). روش های متفاوتی برای #تعریف_کروموزوم ارائه شده است که بنابر مساله مورد نظر می توان از یکی از روش های رایج استفاده نمود ولی علاقه مندان به الگوریتم ژنتیک باید بدانند که در واقع هیچ محدودیتی در روش تعریف کروموزوم وجود ندارد. کاملا محتمل است که روش های رایج تعریف کروموزوم منجر به بازنمایی خوبی نشوند و روش های ابتکاری دانش‌جويان به کسب نتایج بهتری منجر شود. در این مقاله میخواهیم چند روش برای تعریف کروموزم جهت حل مساله n-وزیر ارائه دهیم و نقاط ضعف هر کدام را بیان کنیم. هدف ما آن است که ببینیم روش های مختلف در تعریف کروموزوم می تواند منجر شایستگی های متفاوتی شود.

مقدمه

فرض کنید یک صفحه شطرنج n*n در اختیار داریم. میخواهيم n مهره وزیر را به گونه ای در صفحه شطرنج قرار دهیم که هیچ دو مهره ای با یکدیگر برخورد نداشته باشند. توجه داشته باشید که هر مهره در صفحه شطرنج می تواند در هشت جهت حرکت کند: چهار جهت اصلی (سطری و ستونی) و چهار جهت فرعی (قطری). مثلا در تصویر زیر مشاهده می شود مهره مشخص شده با هیچ مهره دیگری برخورد ندارد.

اما در تصویر زیر میبینیم که چند مهره مهره با یکدیگر برخورد دارند:

تعریف کروموزوم

روش اول (ماتریس بدون محدودیت): می توانیم کروموزوم را بصورت یک ماتریس n*n تعریف کنیم و مقدار هر سلول را نیز برابر True یا False قرار دهیم بطوریکه True به معنی وجود مهره و False به معنی عدم وجود مهره در آن سلول باشد. با این تعریف، کروموزوم زیر برای یک مساله 4*4 قابل تصور است:

در شکل زیر، همه مهره هایی که با سایر مهره‌ها برخورد دارند، به رنگ قرمز نشان داده شده اند. یعنی اولا در سطر اول دو مهره با هم برخورد دارند و ثانیا در ستون دوم نیز دو مهره برخورد دارند و همچنین در ستون سوم نیز دو مهره دیگر با هم برخورد دارند. از آن گذشته، برخی مهره ها بطور قطری با هم برخورد دارند:

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

در این کروموزوم دیگر خبری از برخوردهای سطری نیست چون در هیچ سطری دو کروموزوم وجود ندارد.

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

در این کروموزوم دو مشکل قبلی (برخوردهای سطری و ستونی) وجود ندارد. یعنی دیگر نه از برخوردهای سطری خبری است و نه برخوردهای ستونی. اما یکسری مشکلاتی دیگری قابل مشاهده است. اولا آخرین ستون از سمت چپ (که میشود اولین ستون از سمت راست) فاقد مهره است. یعنی هیچ مهره ای ندارد. در حالیکه طبق تعریف مساله باید n مهره را در یک صفحه n*n قرار می دادیم اما یک صفحه یک مهره کم دارد.

روش چهارم (ستون غیر خالی):

برای رفع مشکل «ستون‌های خالی» باید یک شرط دیگر نیز به تعریف کروموزوم معتبر اضافه کنیم: «هر ستون باید شامل یک مهره (نه کمتر و نه بیشتر) باشد» با اعمال این محدودیت یقین خواهیم داشت که در هر کروموزوم تعداد n مهره در صفحه قرار داده خواهند شد! پس یک کروموزومی که بطور تصادفی و با اعمال محدودیت های فوق مقداردهی شده باشد، میتواند چنین شکلی داشته باشد:

خب در کروموزوم جدید چندین مشکل رفع شده است:

اولا هیچ برخورد سطری بین کروموزوم ها وجود ندارد، ثانیا هیچ برخورد ستونی بین کروموزوم ها وجود ندارد و ثالثا از تعداد n مهره در چینش صفحه استفاده شده است. تنها مشکلی که باقی مانده است، برخورد قطری مهره هاست. «آیا شما می توانید راهکاری ارائه دهید که از برخورد قطری مهره ها جلوگیری شود؟» هرچند کار سختی نیست اما اجازه دهید، حل این مشکل را بر عهده الگوریتم ژنتیک بگذاریم.

روش پنجم (آرایه یک بعدی):

بیایید مرور کنیم که از ابتدا تا کنون چه کردیم. برای تعریف کروموزوم از یک ماتریس استفاده کردیم. سپس برای رفع برخی اشکالات چند محدودیت بر روی ماتریس اعمال کردیم و هم اکنون به ماتریسی با همراه 3 محدودیت (سطری، ستونی و جایگشتی) رسیدیم. با توجه به اینکه ماتریس جدید (پس از اعمال محدودیت) تفاوت های زیادی با ماتریس اولیه دارد، شاید بتوان روش دیگری برای کدینگ و نمایش کروموزوم تعریف کرد. چرا از ماتریس استفاده کنیم؟ میتوان از یک آرایه یک بعدی، که معادل همان ماتریس است، استفاده نمود. بیاییم صفحه شطرنج n*n را بصورت n ستون کنار هم نگاه کنیم که در هر ستون فقط و فقط یک مهره قرار دارد. پس می توانیم یک آرایه n عنصر تعریف کنیم و مقدار عددی هر عنصر آرایه را برابر با شماره سطری تعریف کنیم که در آن سطر مهره ای قرار دارد. نگاه کنید:

آرایه فوق برابر ماتریس زیر است. سلول دوم آرایه یک بعدی برابر چهار است یعنی در صفحه شطرنج، مهره ای که در ستون دوم قرار دارد، باید در سطر چهارم قرار گیرد. همچنین مقدار سلول چهارم از آرایه یک بعدی برابر دو است، یعنی در صفحه شطرنج، مهره ای که در ستون چهارم قرار دارد، باید در سطر دوم قرار گیرد

بنابراین مشاهده می کنیم که بجای استفاده از ماتریس (یا همان آرایه دو بعدی) می توان از آرایه یک بعدی استفاده کرد. اگر بخواهیم از زاویه دیگری به این مساله نگاه کنیم، می بینیم که اگر بخواهیم برای تعریف کروموزوم از ماتریس استفاده کنیم، خطاهای متعددی ممکن است بروز کند در حالیکه اگر روش تعریف کروموزوم را از ماتریس به یک آرایه یک بعدی تغییر دهیم، عملا امکان رخداد خیلی از خطاها وجود نخواهد داشت. مثلا امکان تعریف دو مهره در یک ستون وجود ندارد.

سوال: آیا حق داریم کروموزوم آرایه ای را بصورت زیر مقدار دهی کنیم؟

بنابر فرضیات قبل (عدم وجود چند کروموزوم در یک سطر) این کروموزوم معتبر نیست چون در ستون های اول و دوم، هر دو مهره در یک سطر قرار دارند یعنی چیزی شبیه به ماتریس زیر:

خب حالا چکار کنیم که هرگز در یک سطر دو مهره قرار نداشته باشند؟ در واقع چطور باید محدودیت های ذکر شده را در این آرایه یک بعدی اعمال کنیم؟ خیلی ساده! با استفاده از جایگشت اعداد 1 تا n می توانیم این محدودیت را در کروموزوم اعمال کنیم. یعنی هنگام مقداردهی به آرایه یک بعدی، از جایگشت اعداد 1 تا n استفاده خواهیم کرد. یعنی چینشی از اعداد 1 تا n که اولا در آنها عدد تکراری وجود نداشته باشند و ثانیا (و طبیعتا) شامل تمام اعداد 1 تا n باشند. با اینکار اولا هیچ ستونی بدون مهره نمی ماند وثانیا در هیچ سطری دو مهره قرار نخواهد گرفت.

در شکل زیر چهار کروموزوم متفاوت را که حاصل جایگشت اعداد 1 تا چهار هستند را مشاهده می کنید:

خلاصه:

در الگوریتم ژنتیک روش کدینگ کروموزوم میتواند یک مساله قابل حل را به یک مساله غیر قابل حل تبدیل کند و برعکس! در این مقاله خواستیم نشان دهیم که چطور روش های مختلف نمایش کروموزوم برای حل مساله هشت وزیر می تواند شایستگی کروموزوم را تحت تاثیر قرار دهد. روش ارائه ماتریسی، مستعد خطاهای متعددی مانند برخوردهای سطری و ستونی است. اعمال محدودیت «یک مهره در یک ستون» و «یک مهره در یک سطر» منجر به کاهش برخورد مهرها و افزایش شایستگی می شود. همچنین بجای استفاده از اعداد تصادفی می توان از جایگشت اعداد استفاده نمود تا به کروموزوم هایی با شایستگی بالاتری رسید.

اطلاعات بیشتر در کانال تلگرام فرصت یادگیری: https://t.me/ForsatAcademy