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

توی  این مطلب در مورد تابع برازش یا Fitness Function صحبت کردیم و گفتیم که چندتا تابع برازش رو بررسی میکنیم. تا حالا دو تابع رو بررسی کردیم تابع برازش مسئله کوله پشتی و تابع برازش مسئله فروشنده دوره گرد. در این مطلب قصد داریم تابه برازش مسئله ۸ وزیر رو بررسی کنیم، اگر با این مسئله آشنا نیستید این مطلب رو بخونید.

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

تفسیر کروموزوم مربوط به نمایش فوق به صورت زیر است
وزیر اول در سطر اول در خونه ۵ باشه
وزیر دوم در سطر دوم در خونه ۷ باشه
وزیر سوم در سطر سوم در خونه ۲ باشه
وزیر چهارم در سطر چهارم در خونه ۶ باشه
وزیر پنجم در سطر پنجم در خونه ۳ باشه
وزیر ششم در سطر ششم در خونه ۱ باشه
وزیر هفتم در سطر هفتم در خونه ۸ باشه
وزیر هشتم در سطر هشتم در خونه ۴ باشه

خوب بریم سراغ تابع برازش مسئله ۸ وزیر. تابع برازش باید مشخص کنه که هر جواب چقدر خوب است. خوب بهترین جواب جوابی است که در اون هیچ یک از وزیر ها هم رو نزنن و بدین جواب، جوابی است که همه وزیر ها هم رو بزنن.
در نتیجه تابع برازش مسئله ۸ وزیر، در بهترین حالت (یا همون جواب نهایی مسئله) عدد ۰ رو بر می گردونه و  در بدترین حالت هر وزیر با ۷ تا وزیر دیگه برخورد داره، چون ۸ تا هم وزیر داریم در نتیجه کلا میشه ۷*۸=۵۶ حالت.

خوب حالا ببنیم چطوری باید برخوردها رو حساب کنیم.

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

تا اینجا تابع برازش مسئله ۸ وزیر میشه

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;
}

 خوب تابع بالا یعنی چی:
ورودی تابع: همون طور که گفتیم ورودی تابع برازش کروموزوم است
خروجی تابع: Sum مجموع تعداد برخوردهای وزیر ها با یکدیگر است.
بدنه تابع:  در این تابع مجموع برخوردهای هر یک از وزیران با سایر وزیران محاسبه میشه و در متغیر sum قرار میگیره و در نهایت آن را به عنوان خروجی الگوریتم بر می گردونه.

حالت زیر رو در نظر بگیرید

کروموزوم برای مسئله فوق میشه

خروجی تابع برازش برای کروموزوم بالا برابر با ۴ چرا
وزیر ۱ با وزیر ۶ ام توی این ستون هستن (مقادیر اعداد ژن ۱ و ۶ برابر است)، برخورد اول
وزیر ۳ با وزیر ۸ ام توی این ستون هستن (مقادیر اعداد ژن ۳ و ۸ برابر است)، برخورد دوم
وزیر ۶ با وزیر ۱ ام توی این ستون هستن (مقادیر اعداد ژن ۶ و ۱ برابر است)، برخورد سوم
وزیر ۸ با وزیر ۳ ام توی این ستون هستن (مقادیر اعداد ژن ۸ و ۳ برابر است)، برخورد چهارم

به نظر شما تابع برازش معرفی شده کامل است؟