{CodeGate}

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

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

  1. آشنایی با arraylist
  2. حلقه For
  3. متد در جاوا
  4. Constructor در جاوا
  5. While در جاوا
  6. آرایه در جاوا
  7. Setter و getter در جاوا
  8. If در جاوا
  9. شی گرایی در جاوا
  10. مسئله هشت وزیر

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

الگوریتم‌های ژنتیک (به انگلیسی: Genetic Algorithm)، (با نماد اختصاری GA) تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتم‌های تکامل است که از تکنیک‌های زیست‌شناسی فرگشتی مانند وراثت و جهش استفاده می‌کند. این الگوریتم برای اولین بار توسط جان هالند معرفی شد(ویکیپدیا).

ما در این آموزش به توضیح الگوریتم ژنتیک نمیپردازیم اما توضیحاتی که برای درک کد لازم است را خوهیم گفت.

الگوریتم ژنتیک با مجموعه‌ای ‌از جواب برای مسئله خاص(در اینجا هشت وزیر) شروع میشود. به این جواب ها جمعیت نیز گفته میشود. پس ما جمعیتی داریم که پاسخهای مسئله هشت وزیر در آن است(پاسخ های ما یعنی چیدن هشت وزیر درون شطرنج). در مرحله بعد ما با استفاده از جمعیت اولیه جمعیت جدیدی میسازیم. برای ساخت جمعیت جدید از عملگرهای الگوریتم ژنتیک استفاده میکنیم. ساخت جمعیت جدید را تا جایی ادامه میدهیم که به جواب مورد نظر خود برسیم. در مسئله هشت وزیر جواب مورد نظر ما تعداد برخورد وزیرها است که باید صفر شود.

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

در آموزش حل مسئله هشت وزیر با الگوریتم ژنتیک در جاوا به توضیح عملگرهای آن میپردازیم. ما در تولید جمعیت جدید دو عملگر را انجام میدهیم:

  1. Crossover: فرض کنید دو جواب از جمعیت ما به صورت زیر باشد:

11010000

00001111

کاری که این عملگر انجام میدهد ادغام این دو است و جواب به صورت زیر میشود:

1101111

ما 4 عدد اول از جواب اول و 4 عدد دوم از جواب دوم گرفتیم.

  1. Mutate: این عملگر بسیار ساده است. تغییر یکی از جواب های ما به صورت اتفاقی مثلا در جواب های بالا یکی از 1 های ما به صفر تبدیل شود.در هشت وزیر یعنی جابجایی دو وزیر به صورت اتفاقی.

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

قبل از  حل مسئله هشت وزیر با الگوریتم ژنتیک در جاوا در مورد ایده کلی کد توضیح میدهیم سپس پیاده سازی آن را با هم میبینیم. ما باید جمعیتی داشته باشیم از جواب های خود!! جوابهای ما در مسئله هشت وزیر، نحوه چینش هشت وزیر است پس هر یک از جواب های ما صفحه شطرنجی است که هشت وزیر در آن قرار دارد. برای پیاده سازی ما کلاسی به نام Board داریم که همان صفحه شطرنج ما است و کلاس دیگری به نام Queen داریم. این کلاس همان وزیر های است که در صفحه Board قرار میدهیم. پس هر Board یک آرایه از Queen دارد.

حال که ما صفحه شطرنج خود را ساختیم برای حل مسئله هشت وزیر با الگوریتم ژنتیک در جاوا باید الگوریتم ژنتیک را بنویسیم. برای این کار کلاسی به نام NqueenGenetic نوشتیم. در این کلاس ما Arraylist از جنس Board داریم که همان جمعیت ماست. در بالا توضیح دادیم که الگوریتم ژنتیک دو عملگر Crossover و mutate در خود دارد. در کلاس NqueenGenetic این دو عملگر را پیاده سازی می‌کنیم.

نحوه انتخاب والد در الگوریتم ژنتیک متفاوت است. در اینجا ما تابع fitness خود را تعداد برخورد وزیرها با هم گذاشتیم. دو والد را از جمعیت طوری انتخاب میکنیم که کمترین تعداد برخورد(fitness) داشته باشد. برای mutate در هر جمعیت یک وزیر را با وزیر دیگر جابجا میکنیم. در اینجا ما 80% جمعیت خود را شامل mutate کردیم(فرضیاتیست که میتوانید تغییر دهید).

کلاس Queen

کد کلاس وزیر های ما به صورت زیر است:

همانطور که میبینید دو متغیر i و j داریم که سطر و ستون وزیر ما درون صفحه شطرنج است.

کلاس Board

کد کلاس Board به صورت زیر است:

در این کلاس سه فیلد داریم که یکی وزیرهای ما است به نام Queen و دیگری تعداد برخورد وزیرها با هم است به نام conflict و آخرین فیلد نیز تعداد وزیرهای وارد شده به صفحه شطرنج ما است به نام lastelement . سه متد در کد کلاس وجود دارد:

  1. Queenconnflict: تعداد برخود وزیرها را می‌شمارد.
  2. Addqueen: وزیری را به سطر i و ستون j اضافه میکند.
  3. GenerateRandomQueen: 8 وزیر را به صورت کاملا اتفاقی در صفحه میچیند(برای سهولت الگوریتم ما در هر ستون یک وزیر چیدیم).

کلاس NqueenGenetic

در ادامه توضیح حل مسئله هشت وزیر با الگوریتم ژنتیک در جاوا ، کلاس NqueenGenetic الگوریتم ژنتیک را پیاده سازی کردیم. دو فیلد داریم یکی تعداد جمعیت ما است و دیگری خود جمعیت. متدهای این کلاس شامل:

  1. Startalgorithm: متدی است که الگوریتم ژنتیک را شروع و تا موقعی که به جواب نرسیدیم این الگوریتم ادامه دارد.
  2. Sortpopulation: متدی برای مرتب کردن جمعیت بر اساس تعداد برخورد آنهاست(برای انتخاب والد استفاده میشود).
  3. Mutate: در این متد ما بر روی 80% جمعیت خود عملگر mutate انجام میدهیم.
  4. Crossover: در این متد ما دو خانه اول جمعیت( جمعیت بر اساس تعداد برخورد مرتب هستند پس دو خانه اول بهترین جمعیت ماست) را به عنوان والد انتخاب کرده سپس دو فرزند را با والدهای گفته شده تولید میکنیم. نحوه تولید فرزند بدین صورت است که 4 وزیر اول از یکی از والدها و 4 وزیر دوم از والد دیگر گرفته میشود(Singlepoint crossover).
  5. Initialpopulation: یک جمعیت اولیه توسط این متد تولید میشود.
  6. Showboard: وقتی جواب مسئله هشت وزیر پیدا شد این متد صفحه شطرنج را نمایش میدهد.

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

برای تست کدهای بالا، کد زیر را بزنید:

محاسبه تعداد برحوردهای وزیرها

همانطور که توضیح داده شد ما در حل مسئله هشت وزیر با الگوریتم ژنتیک در جاوا از تعداد برخورد به عنوان fitness استفاده می‌کنیم. حال برای محاسبه تعداد برخورد اینگونه عمل میکنیم که:

  1. وزیرهای ما در یک ستون نباشند.
  2. وزیرهای ما در یک سطر نباشند.
  3. وزیرهای ما به صورت اریب با هم برخوردی نداشته باشند.

برای برخورد در یک سطر و ستون کار ساده ای در پیش داریم و کافیست سطر و ستونهای وزیر ها را با هم مقایسه کنیم. اما برای محاسبه برخورد اریب کمی کار متفاوت است. روشی که ما استفاده کردیم بدین صورت است که فرض کنید سطر و ستون یکی از وزیرهای ما به صورت i و j نوشتیم. حال معادله زیر را بدست می‌آوریم:

i-j = m

i+j =n

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

پسورد: www.codegate.ir

 

دسته : java, جاوا, حل مسائل با جاوا, ساختمان داده در جاوا

دیدگاه بگذارید

نظر شما چیست؟

مطلع کردن شما از
avatar

wpDiscuz