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

صورت مسئله :
در یک صفحه شطرنج n * n ، n وزیر را طوری قرار دهیم که همدیگر را گارد ندهند .

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

نحوه نمایش مسئله :
می دانیم اگر دو وزیر در یک ستون قرار گیرند قطعا به جواب نخواهیم رسید . بنابراین قرار دادن دو وزیر در یک ستون باعث غیرامیدبخش شدن جواب مسئله می شود . برای نمایش مسئله در کروموزوم ها از این ویژگی استفاده کرده و به صورت زیر عمل می کنیم :

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

كد:

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

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

تولید جمعیت اولیه :

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

Fitness ( برازش ) :

برای محاسبه میزان بهینگی جواب تعداد جفت وزیرهایی را که به هم گارد می دهند ، محاسبه می کنیم . برای مسئله 8 وزیر در بدترین حالت هر وزیر با همه وزیر های دیگر گارد می دهد ( فرض کنید همه وزیرها در یک سطر قرار گیرند ) . در این حالت حداکثر تعداد جفت وزیر هایی که به همگدیکر کارد می دهند 28 جفت است :

كد:

7 + 6 + 5 + 4 +3 + 2 + 1

در حالت کلی برای مسئله n وزیر حداکثر تعداد جفت وزیرهایی که به همدیگر گارد می دهند به صورت زیر محاسبه می شود :

كد:

1 + 2 + … + (n-1) = ( n * (n-1 ) ) /2

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

كد:

Fitness[i] =1 – ( Guard(chromosome[i]) / MaxGuards )

حداکثر تعداد گارد ها : MaxGuards

تعداد جفت وزیرهایی که در کروموزوم ام همدیگر را گارد می دهند : Guard(chromosome[i])

Selection ( انتخاب ):

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

Crossover ( ادغام ) :

برای این مسئله از دو روش برای ادغام کروموزوم ها استفاده شده است :
1 ) ادغام تک نقطه ای
2 ) ادغام دو نقطه ای

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

در ادغام دو نقطه ای در دو کروموزوم متوالی ، دو نقطه محوری به تصادف انتخاب می کنیم . سپس ژن های بین این دو نقطه را در دو کروموزوم تعویض می کنیم .

Mutation ( جهش ) :

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

روش Simulated Annealing برای حل مساله n- وزیر

در این مسئله نحوه نمایش مسئله در روش SA نیز همانند نحوه نمایش مسئله در روش الگوریتم ژنتیک می باشد و پارامترهای الگوریتم SA در این برنامه به طور دستی تنظیم می شوند . اما برای تولید حالت همسایه بدین شکل عمل می کنیم که یکی از عناصر آرایه را انتخاب کرده و مقدار آن را تغییر می دهیم .

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

مطالب مشابه :

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

آموزش #c

فهرست عناوین کتاب

پیاده سازی جدول سودوکو با الگوریتم ژنتیک

مسئله هشت وزیر

الگوریتم های متاهیوریستیکی ...

پروژه پایانی - دانشگاه پیام نور

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