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

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

مقدمه

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

معرفی الگوریتم ژنتیک

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

• الگوریتم های ژنتیک (Genetic Algorithms)
• برنامه نویسی ژنتیک (Genetic Programming)
• استراتژی های تکاملی (Evolutionary Strategies)
• برنامه نویسی تکاملی (Evolutionary Programming)

به جز الگوریتم ژنتیک باقی این ها از حوصله بحث خارج است و میتوانید در کتابی تحت عنوان Introduction to Evolutionary Computing این مفاهیم را کامل مطالعه کنید. در الگوریتم ژنتیک جواب یا جواب های کاندید مسئله را که در یک قالب کروموزوم مانند کد گزاری میشوند به عنوان خروجی بر میگرداند. در این الگوریتم اوپراتور هایی تحت عنوان اوپراتور های بازترکیب یا Recombination Operators تعریف میشوند و به وسیله این ها روی کروموزوم ها تغییراتی اعمال خواهد شد. معمولا از این الگوریتم برای مسائل بهینه سازی، برای مثال بهینه سازی یک تابع هدف در مسائل مختلف نیز استفاده میشود. دامنه مسائلی که این الگوریتم در آن ها کاربرد دارد بسیار زیاد است و هنوز از موضوعات داغ به حساب می آید.

این الگوریتم معمولا با تولید یک جمعیت اولیه با رعایت محدودیت های مسئله به صورت تصادفی آغاز به کار می کند. در مرحله بعد از بین این جمعیت که منظورمان کروموزوم ها است، با روش های مختلفی بر اساس یک تابع Fitness که میزان خوب بودن هر کروموزوم را اندازه گیری میکند، چند تا از آن ها به عنوان والد برای جفت گیری انتخاب میشوند. البته اینطور نیست که همیشه کروموزوم های خوب تولید مثل کنند، بلکه تنها به آن ها شانس بیشتری برای انتخاب شدن (Selection) داده میشود و ممکن است یک کروموزوم نا مناسب با اینکه شانس کمتری داشته، بر اساس نحوه انتخاب هایمان که شامل روش های مختلفی است، انتخاب شود. بعد از انتخاب والدین و تولید فرزند که این هم روش های زیادی دارد، با احتمالی در فرزندان یک جهش ژنتیکی ایجاد میکنیم، ممکن است جهشی هم انجام نشود. در مرحله بعد با معیاری فرزندان را در جمعیت جای می دهیم و به اندازه تعداد فرزندان تعدادی کروموزوم را حذف کنیم (Survival Selection).

الگوریتم ژنتیک و مسئله هشت زیر

برای بیان این مسئله در قالب این الگوریتم ما هر کروموزوم را یک آرایه هشت تایی در نظر گرفته ایم که اندیس های این آرایه معرف ستون های خانه شطرنج و هر مقدار در این آرایه شماره سطر می باشند. مقادیر این آرایه غیر تکراری و جایگشتی از اعداد یک تا هشت هستند. در اینجا ما جمعیت اولیه را 100 در نظر گرفته ایم اما به دلخواه میتواند هر عددی انتخاب شود. فقط این نکته باید توجه شود که تعداد جایگشت های متفاوت 8 عدد 40320 می باشد و جمعیت اولیه باید مقداری کمتر از این  تعداد باشد. 

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

برای هر یک از این دو فرزند نیز به احتمال 80 درصد جهش انجام میشود. برای جهش دادن فرزندان دو اندیس رندم انتخاب شده و مقدار موجود در این اندیس ها با هم جابجا میشوند. سپس کل جمعیت به ترتیب تابع سودمندی مرتب شده و دو کروموزوم آخر که جز بدترین ها هستند را با فرزندان جابجا میکنیم.

پیاده سازی

در این قسمت به مبحث شیرین پیاده سازی میرسیم. در ادامه با توجه به توضیحاتی که داده شد توابع مورد نیاز پیاده سازی شده و تک تک آن ها را توضیح مختصری میدهیم.

Init

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

Print_chrom

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

one_queen_penalty

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

configuration_penalty

این تابع مقدار کل تهدیدها در یک کروموزوم را با محسابه این مقدار هر یک از وزیر ها (ژن ها) به کمک تابع one_queen_penalty و جمع آن ها، بر میگرداند.

chrom_fitness_calculator

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

selection

این تابع 5 کروموزوم را به صورت رندم برای تولید مثل انتخاب میکند. ورودی آن لیست جمعیت کل و تعداد والد برای انتخاب می باشد.

get_two_parents

این تابع دو والد از کروموزوم های انتخاب شده در تابع selection با سودمندی ماکزیمم را بر میگرداند.

cross_over

این تابع عمل تولید 2 فرزند با دو والد انتخاب شده توسط تابع get_two_parents را با روش ذکر شده انجام میدهد.

mutation و mutate

این دو تابع مسئول انجام عمل جهش با روش ذکر شده در فرزندان تولید شده هستند. تابع mutation دو فرزند را گرفته و برای هر کدام یک احتمال تولید میکند. اگر زیر 80 درصد باشد با تابع mutate یک جهش در فرزند ایجاد میکند در غیر اینصورت جهشی ایجاد نمیشود.

survival_selection

این تابع نیز با روش ذکر شده در لیست جمعیت کل، فرزندان تولید شده را جایگزین میکند.

پارامتر ها

• pop_size : تعداد جمعیت اولیه
• select_random : تعداد کروموزومی که بصورت رندم برای انتخاب والدین، انتخاب میشوند.
• mutation_prob : احتمال جهش
• rounds : تعداد تکرار الگوریتم

نتیجه نهایی

الگوریتم با توجه به جمعیت انتخاب شده بعد از یک تا بیشتر از 200 تکرار میتواند به جواب برسد. در یکی از اجرا های این الگوریتم بعد از 214 تکرار به جواب رسیدیم.

• ده کروموزوم برتر:

[(4, 1, 5, 8, 2, 7, 3, 6), (6, 3, 1, 2, 5, 8, 4, 7),

 (6, 3, 1, 4, 8, 5, 2, 7), (6, 3, 1, 2, 5, 8, 4, 7),

 (6, 4, 7, 3, 8, 2, 5, 1), (6, 3, 5, 2, 8, 1, 7, 4),

 (1, 3, 6, 2, 5, 8, 4, 7), (4, 7, 5, 8, 2, 1, 3, 6),

 (7, 6, 3, 5, 8, 1, 4, 2), (4, 2, 5, 8, 1, 7, 6, 3)]

• کروموزوم برتر و جواب مسئله

(4, 1, 5, 8, 2, 7, 3, 6)

• شکل این کروموزوم در صفحه شطرنج

برای دانلود فایل کد ها اینجا را کلیک کنید.

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

خوب و خوش باشید.