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

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

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

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

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

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

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

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

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

11010000

00001111

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

1101111

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

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

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

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

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

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

کلاس Queen

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

public class Queen {

     private int i;
     private int j;
     public int getI() {
          return i;
     }
     public int getJ() {
          return j;
     }
     public void setI(int i) {
          this.i = i;
     }
     public void setJ(int j) {
          this.j = j;
     }
     public Queen(int i, int j) {
          super();

          this.i =(i<8)?i:1;
          this.j = (j<8)?j:1;
     }


}

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

کلاس Board

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

public class Board {
     Queen[] queen = new Queen[8];
     int lastelement = 0;
     int conflict;

     public int getConflict() {
          return conflict;
     }

     public void setConflict(int conflict) {
          this.conflict = conflict;
     }

     public void addQueen(int i, int j) {
          if (lastelement < 8) {
              queen[lastelement] = new Queen(i, j);
              lastelement++;
          } else {
              JOptionPane.showMessageDialog(null,
                        "board must have 8 queen!!!!!");
          }
     }

     public void GenerateRandomQueen() {
          for (int i = 0; i < queen.length; i++) {
              Random random = new Random();
              queen[i] = new Queen(random.nextInt(8), i);
          }
     }

     public int Queenconnflict() {
          int num_of_conflict = 0;
          for (int i = 0; i < 8; i++) {
              Queen temp = queen[i];
              int diagonal_1 = temp.getI() - temp.getJ();
              int diagonal_2 = temp.getI() + temp.getJ();
              for (int j = i + 1; j < queen.length; j++) {
                   if ((queen[j].getI() - queen[j].getJ() == diagonal_1
                             || queen[j].getI() + queen[j].getJ() == diagonal_2
                             || queen[j].getJ() == temp.getJ() || queen[j]
                                  .getI() == temp.getI())) {
                        num_of_conflict++;
                   }
              }
          }
          setConflict(num_of_conflict);
          return num_of_conflict;
     }

}

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

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

کلاس NqueenGenetic

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

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

public class NqueenGenetic {

     ArrayList<Board> population;
     int population_size;

     public NqueenGenetic(int population_size) {
          super();
          population = new ArrayList<>();
          this.population_size = population_size;
     }

     public void startAlgorithm() {
          initialpopulation();
          int iteration = 0;
          while (true) {
              iteration++;
              System.out.println(iteration);
              sortpopulation();
              crossover();
              mutation();

          }

     }

     private void sortpopulation() {
          for (int i = 0; i < population_size; i++) {
              for (int j = 0; j < population_size - 1; j++) {
                   if (population.get(j).conflict > population.get(j + 1).conflict) {
                        Collections.swap(population, j, j + 1);
                   }
              }
          }

     }

     private void mutation() {
          for (int i = 0; i < .8 * population_size; i++) {
              Random rand = new Random();
              int changequeen = rand.nextInt(8);
              int changequeen2 = rand.nextInt(8);
               population.get(i).queen[changequeen].setI(rand.nextInt(8));
               population.get(i).queen[changequeen2].setI(rand.nextInt(8));
          }
     }

     private void crossover() {
          Board parent = population.get(0);
          Board parent2 = population.get(1);
          Board child = new Board();
          for (int j = 0; j < 8; j++) {
              if (j < 4) {
                   child.addQueen(parent.queen[j].getI(), j);
              } else {
                   child.addQueen(parent2.queen[j].getI(), j);

              }

          }
          child.Queenconnflict();
          if (child.conflict == 0) {

              showboard(child);
              System.exit(1);
          }
          Board child2 = new Board();
          for (int j = 0; j < 8; j++) {
              if (j < 4) {
                   child2.addQueen(parent2.queen[j].getI(), j);
              } else {
                   child2.addQueen(parent.queen[j].getI(), j);

              }

          }

          child2.Queenconnflict();
          if (child2.conflict == 0) {

              showboard(child2);
              System.exit(1);
          }

          population.set(population_size-1, child);
          population.set(population_size-2, child2);


     }

     private void showboard(Board child) {

          for (int i = 0; i < 8; i++) {
              for (int j = 0; j < 8; j++) {
                   int row = child.queen[j].getI();
                   int column = child.queen[j].getJ();
                   if (i == row && j == column) {
                        System.out.print("Q ");
                   } else {
                        System.out.print("- ");
                   }
              }
              System.out.println();
          }

     }
     private void initialpopulation() {
          for (int i = 0; i < population_size; i++) {
              Board board = new Board();
              board.GenerateRandomQueen();
              board.Queenconnflict();
              population.add(board);
          }

     }

}

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

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

     public static void main(String[] args) {
          new NqueenGenetic(30).startAlgorithm();

     }

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

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

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

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

i-j = m

i+j =n

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