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

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

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

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

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

---

 

جهش در الگوریتم ژنتیک

عمل جهش یک بیت شامل تبدیل عدد صفر به یک و بالعکس است که بر اساس یک احتمال کوچک مثل P_m به صورت بیت به بیت صورت می گیرد. عمل جهش به این ترتیب است که یک عدد تصادفی بین صفر تا یک تولید می شود، اگر عدد تولید شده کوچکتر از P_m باشد مقدار خروجی را برابر درست (True) وگرنه برابر غلط (False) در نظر می گیریم. اگر برای هر بیت مقدار خروجی درست باشدبیت تغییر می کند وگرنه بیت بدون تغییر باقی خواهد ماند.