حل مسئله Maze با استفاده از الگوریتم ژنتیک

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

هدف در این مسئله اتخاذ ترتیبی از تصمیمات به منظور رسیدن به حالت هدف از حالت شروع می باشد. 

روش های متفاوتی جهت حل مسئله Maze وجود دارد، که الگوریتم ژنتیک یکی از این روش هاست که جواب تقریبا بهینه را بدست می آورد.

در این مطلب قصد داریم حل مسئله Maze  را با استفاده از الگوریتم ژنتیک توضیح دهیم. الگوریتم های ژنتیک،  روش اکتشافی از دسته الگوریتم های تکاملی هستند که بر اساس اصل داروین و با استفاده از انتخاب طبیعی است. الگوریتم ژنتیک در دهه 1960 توسط "جان هالند" بیان شد. 

---

  

 

روش حل مسئله

1. ایجاد Maze

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

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

بازنمایی سلول نمونه در قسمت بالا نشان داده شده است. درها در سمت چپ و پایین نشان داده شده است و برچسب به صورت "1" نشان داده شده است.

از این برچسب در ایجاد ساختار maze و همچنین برای نمایش تعداد درهای موجود در سلول در طی فرآیند جستجوی مسیر بهینه استفاده می شود. ساختار maze با استفاده از فرآیند مطابق شکل 3 به روز می شود.

در صورت وجود مسیر از سلول شروع تا سلول پایان  ، "1" برمی گردد ، در غیر این صورت "0" برمی گردد که نشانگر عدم دسترسی به مسیر است.

1.2 مرحله دوم: برچسب گذاری مسیر

سلولهای شروع (S) و پایان (F) بطور تصادفی انتخاب می شوند،S>=0 و n>=F. سلول شروع با برچسب 1 آغاز می شود. با استفاده از الگوریتم Flood_Fill (S، 0) برای هر سلول متصل به درب (مقدار = 1). اگر برچسب زدن به سلول پایان (0 ، F) نیز انجام شود ، مقدار 1 را برمی گرداند ، در غیر این صورت از Flood_Fill (F، n) با برچسب 2 استفاده کنید . شکل 4 حالت بازگشت (1) را نشان می دهد.

در صورتی که مقدار صفر برگردانده شود، فرآیند ادغام برچسب ها برای ایجاد maze اتخاذ می شود.

1.3 مرحله سوم: ادغام برچسب ها

در این فرآیند ، ردیابی برچسب با استفاده از الگوریتم flood_fill برای وجود دیواره ها بین سلول ها انجام می شود. اگر دیواری در بین سلولها با برچسب های مختلف قرار داشته باشد و یکی از برچسب ها "1" باشد، با سلولی که مقدار برچسب آن"1" باشد، ادغام می شود. این روند ادامه دارد تا سلول با برچسب 2 با سلولی که مقدار برچسب آن یک است، ادغام شود. روند پیوستن به برچسب ها در شکل 7 و 8 نشان داده شده است.

شکل 7 و شکل 8 فرآیند پیوستن به برچسبها را در صورت عدم اشتراک گذاری و به اشتراک گذاری دیواری توسط برچسب Start و Finish ، به ترتیب ، در نتیجه بازگشت (0) از مرحله 1 نشان می دهد.

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

1. ایجاد جمعیت تصادفی اولیه.
2. برازش افراد در جمعیت را محاسبه کنید.
3. مراحل بعدی را تا رسیدن به معیارهای خاتمه تکرار کنید.

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

مراحل زیر قسمت های مهم فرآیند الگوریتم ژنتیک را معرفی می کند.

2.1  ساختار و نگاشت کروموزوم (Chromosome structure and mapping)

کروموزوم برای نشان دادن حرکت مسیر از یک سلول به سلول دیگر از اعداد  0 تا 3  استفاده می کند. شکل 6 نمایانگر کروموزوم و معادل آن برای نمایش کروموزوم است.

2.2  تابع برازش (Fitness function)

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

که در آن FV تابع برازش، CC سلول جاری، SC سلول شروع، FC سلول پایانی می باشد.

2.3  عملگر ادغام (Cross Over)

عملگر ادغام در شکل 9 نمایش داده شده است. دو تا از والدین از جمعیت انتخاب می شوند و دو فرزند به وسیله عملگرهای جمع و منها بر روی ژن های مربوطه تولید می شوند. اولین فرزند نتیجه عملگر جمع و دومی نتیجه عملگر منها می باشد.

"n module 4"(باقیمانده تقسیم بر 4) بر روی تمام ژن های مربوط به فرزندان اعمال شده تا اعداد در بازه 0 تا 3 تولید شوند.

2.4  عملگر جهش(Mutation)

نمونه ای از جهش بیت تصادفی در شکل 10 نشان داده شده است. یک عدد تصادفی (0-3) در مکان انتخابی تصادفی در کروموزوم جایگزین می شود.

نتیجه:

مدل پیشنهادی پیاده سازی شده است و نتایج حاصل از مجموعه داده های مورد استفاده با موفقیت نشان داده می شوند. به نظر می رسد عملگرModulo در تولید بهترین نتایج مؤثر است. به نظر می رسد که عملگر جهش در تولید کروموزوم جدید برای جلوگیری از مشکلات بهینه محلی مفید است. زمینه استفاده بیشتر از روشها برای ساختار maze پیچیده تر با ساختار هندسی متفاوت نسبت به ساختار مستطیل وجود دارد.

نتیجه پیاده سازی maze با پیچیدگی های متفاوت در شکل زیر نشان داده شده است.

دانلود مقاله اصلی