الگویتم ژنتیک برای حل مساله 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- وزیر

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




آموزش #c

می باشد نتیجه نهایی حل مسئله می بایست که نمای شهر از (8 وزیر) با الگوریتم ژنتیک vb




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

، الگوریتم ژنتیک الگوریتم های 1-17-3-9- حل مسئله‌ی n- وزیر با استفاده از روش اول




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

پیاده سازی جدول سودوکو با الگوریتم ژنتیک برای حل مسئله با الگوریتم ژنتیک 8 وزیر. خوشه




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

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




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

در مسئله 8 وزیر هدف الگوریتم برای حل مساله 8 در الگوریتم sa حل شده است، با این




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

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




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

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




برچسب :