使用遗传算法解决N皇后问题

• 下载 new.zip - 6.9 KB

引言

在本文中，我们描述了一种解决8皇后问题的方案。我的解决方案基于遗传算法，但遗传算法并不是解决这类问题的理想方法。

在我的代码中，首先初始化原始种群（作为染色体）。例如：a={3 1 4 2} 表示第一个皇后在第1行第3列，第二个皇后在第2行第1列，以此类推。

然后从种群中选择最佳的染色体。下一步是从种群中生成一些子代（交叉），并且其中的一些子代会发生变异。在子代和父代之间选择最佳的染色体。

这个循环重复n次（例如，n= 100）。

使用代码

1. 在运行程序之前，你应该理解用于种群大小、表格大小和适应度（对于遗传算法）的变量。

   fixedsize=100;
   tablesize=8;
   fitness=0; 

2. 首先，生成原始种群，以十进制数组的形式表示：例如，(4皇后)：a={3 1 4 2} 表示第一个皇后在第1行第3列，第二个皇后在第2行第1列，以此类推。

   for i=1:fixedsize
       cromo(i,1:tablesize)=randperm(tablesize);
       cromo(i,tablesize+1)=-1;
   end;
   for i=1:fixedsize
       for j=1:tablesize
           for k=j+1:tablesize
               if (cromo(i,j)==cromo(i,k)) || (abs(cromo(i,j)-abs(cromo(i,k))) == abs(j-k))
                   fitness=fitness+1;
               end;
           end;
       end;
       cromo(i,tablesize+1)=fitness;
       fitness=0;
   end;

3. 选择最佳的父代来生成子代：

   cromo=sortrows(cromo,9);

4. 生成子代并使其变异。重复此步骤n次（例如，n=1500）。

    for cnt=1:1500
       if(cromo(1:fixedsize,9)==0)
           level=cnt;
           checkboard(cromo(1,1:tablesize),tablesize,tablesize);
           break;
       end;
       %pm=(1/240)+(0.11375/2^cnt);
       pc=1/cnt ;
       slct=cromo(1:fixedsize,:);
       n=0;
       for i=1:2:fixedsize/2
           u=rand(1);
           if(u<=pc)
               n=n+2;
               child(n-1:n,1:tablesize)=crossover(slct(i:i+9,:),tablesize);
           end;
       end;
       %n=n+1;
       %if(n>0)
       child(:,tablesize+1)=-1;
       
       cromo((fixedsize+1)-length(child):end,:)=[];
       cromo=[cromo;child];
       for i=(fixedsize+1)-length(child):fixedsize
           cromo(i,1:tablesize)=mutation(cromo(i,1:tablesize),tablesize);
       end;
       %end;
       fitness=0;
       for i=1:fixedsize
           for j=1:tablesize
               for k=j+1:tablesize
                   if (cromo(i,j)==cromo(i,k)) || 
                              (abs(cromo(i,j)-abs(cromo(i,k))) == abs(j-k))
                       fitness=fitness+1;
                   end;
               end;
           end;
           cromo(i,tablesize+1)=fitness;
           fitness=0;
       end;
       cromo=sortrows(cromo,9);
   end;

历史

• 版本 1.0。