حل مسئله n وزیر با استفاده از الگوریتم ژنتیک
همانطور که می دانیم معمای n وزیر معمای چیدن n وزیر به صورتی است که هیچکدام از وزیر ها نتوانند به دیگری حمله کنند، یافتن راه حل این مسئله به صورت دستی بسیار سخت می باشد، به همین دلیل از الگوریتم ژنتیک برای حل این مسئله استفاده می شود، در حقیقت با تولید مقادیر اولیه شروع کرده و با وراثت و ... کروموزوم های جدید (حالات جدید) تولید کرده و به همین ترتیب ادامه می دهیم تا به جواب مسئله برسیم.
* منظور از مقادیر اولیه همان حالت اولیه است.
البته تعداد کروموزوم ها هر چه قدر بیشتر باشد، مسلما سریعتر به جواب خواهیم رسید، در عوض به حافظه بیشتری نیاز خواهیم داشت. این مسئله را با استفاده از کدهای نرم افزار ریاضی متلب (Matlab) پیاده سازی کرده ام که البته هنوز بهینه نمی باشد، برای مسئله 8 وزیر پاسخ می دهد اما برای مسئله 9 وزیر تنها یک پاسخ دریافت کردم، البته نسخه اولیه این الگوریتم برای مسئله 8 وزیر تنها یک پاسخ داده بود که بعدا مسئله بهینه و پاسخ های بیشتری داد.
بعدا نسخه های بهینه تری نیز در وبلاگ قرار داده خواهد شد، دوستان و همکلاسی های محترم هم در صورتی که الگوریتم بهینه تری نوشته اند، لطفا اطلاع دهند تا در وبلاگ قرار داده شده و از تجربه و علم آنها نیز استفاده کنیم.
برای دانلود سورس کد حل مسئله n وزیر با استفاده از الگوریتم ژنتیک و نرم افزار متلب کلیک نمایید. (نسخه جدید در پایین قابل دانلود می باشد)
ویرایش:
همانطور که می دانیم الگوریتم ژنتیک کاملا تصادفی می باشد، از طرفی بدلیل اینکه مجموعه ای از نظریه تکامل هست و از وراثت و والد و ... تبعیت می کند، در نتیجه بعد از گذشت زمان به جواب مسئله نزدیک تر خواهیم شد، در پایین نمودار الگوریتم ژنتیک برای حل مسئله n وزیر را ترسیم کرده ایم. همانطور که مشاهده می کنید، در اوایل از جواب مسئله بسیار دور هستیم اما بعد از گذشت مدت زمانی به پاسخ مسئله که همان صفر هست رسیده ایم.
در حالت کلی نمودار به صورت نزولی می باشد، هر چند بدلیل اینکه الگوریتم ژنتیک تصادفی است، در برخی از x ها، y افزایش یافته و یا ثابت مانده است.
سورس کد الگوریتم ژنتیک برای حل مسئله n وزیر نسبت به کد قبلی که در اسلاید قابل مشاهده هست بهینه تر شده است، در پایین فایل مربوطه را جهت دانلود قرار داده ایم.
دانلود اسلابد حل مسئله n وزیر با استفاده از الگوریتم ژنتیک
دانلود سورس کد الگوریتم ژنتیک برای حل مسئله n وزیر
سعید محمدی اقدم