تابع برازش مسئله ۸ وزیر – قسمت دوم

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

Function FitnessFunction8Queen(Chromosome)
{
Sum = 0;
Sum = Sum + Count (Column Q1 ==  Column other Queen);
Sum = Sum + Count (Column Q2 ==  Column other Queen);
Sum = Sum + Count (Column Q3 ==  Column other Queen);
Sum = Sum + Count (Column Q4 ==  Column other Queen);
Sum = Sum + Count (Column Q5 ==  Column other Queen);
Sum = Sum + Count (Column Q6 ==  Column other Queen);
Sum = Sum + Count (Column Q7 ==  Column other Queen);
Sum = Sum + Count (Column Q8 ==  Column other Queen);
Return Sum;
}

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

حل مسئله ۸ وزیر با الگوریتم ژنتیک : حرکت های مجاز وزیر در صفحه شطرنج

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

این مورد رو باید چطوری پیاده سازی کنیم؟

بزارید با یک مثال پیش بریم. شکل زیر رو در نظر بگیرید. برای سادگی کار ما خونه های شطرنج رو شماره گذاری کردیم.

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

فرض کنید یک وزیر در خونه  (۳,۶) هستش. خوب ۴ خونه های مورب در مرحله اول میشه

• خونه (۲,۷): رابطه این با خونه  (۳,۶) چیه؟ اگر دقت کنید اگر از سطر یکی کم کنیم (۳-۱) برابر ۲ میشه و اگر به ستون یکی اضافه کنیم (۶+۱) میشه ۷٫ پس یک قانون رو پیدا کردیم

• خونه (۲,۵) : رابطه این با خونه  (۳,۶) چیه؟ اگر دقت کنید اگر از سطر یکی کم کنیم (۳-۱) برابر ۲ میشه و اگر از ستون یکی کم کنیم (۶-۱) میشه ۵٫ پس یک قانون دیگه رو پیدا کردیم

• خونه (۷,۴): رابطه این با خونه (۳,۶) چیه؟ اگر دقت کنید اگر به سطر یکی اضافه کنیم (۳+۱) برابر ۴ میشه و اگر به ستون یکی اضافه کنیم (۶+۱) میشه ۷٫ پس یک دیگه قانون رو پیدا کردیم

• خونه (۵,۴): رابطه این با خونه (۳,۶) چیه؟ اگر دقت کنید اگر به سطر یکی اضافه کنیم (۳+۱) برابر ۴ میشه و اگر از ستون یکی کم کنیم (۶-۱) میشه ۵٫ پس یک قانون رو پیدا کردیم

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

•    خونه (۲,۷): ۱ = |۳-۲| = |۶-۷|
•    خونه (۲,۵): ۱ = |۳-۲| = |۶-۵|
•    خونه (۷,۴): ۱ = |۳-۴| = |۶-۷|
•    خونه (۵,۴): ۱ = |۳-۴| = |۶-۵|

خوب برای خونه های ردیف دو باید چکار کرد؟ خونه های که در شکل زیر نمایش داده شده است.

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

به این موضوع فکر کنید تا مطلب بعدی به این سوال جواب بدیم.