65.9K
CodeProject 正在变化。 阅读更多。
Home

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

asef
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.96/5 (48投票s)

2005年10月19日

5分钟阅读

viewsIcon

361972

downloadIcon

14619

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

遗传算法，理论

关于遗传算法的书籍和网络资源非常多。我能做的最好的事情就是引用我喜欢的网站上的一些精彩描述。

“遗传算法是进化计算的一部分，进化计算是一个快速发展的领域，属于人工智能。正如你所猜到的，遗传算法的灵感来源于达尔文的进化论。简单地说，通过遗传算法解决问题的方法是‘进化’出来的。”

就像任何其他优化算法一样，GA始于定义优化变量。它也像其他优化算法一样，通过测试收敛性来结束。GA组件的流程图如图1所示。

图 1 - GA组件的流程

定义成本函数和成本

每个问题都有一个成本函数。例如，在变量空间中显示的具有峰谷的三维曲面的最大值。成本，一个适应度值，被分配给每个解决方案。

染色体和基因

基因是0到n-1之间的数字。染色体是这些基因的数组。它可以是一个答案。每一代种群都有确定数量的染色体。

创建随机初始种群

初始种群是从随机选择的染色体中创建的。收敛所需的代数取决于随机初始种群。

解码染色体并找到成本

要找到分配给每个染色体的成本，需要定义一个成本函数。调用成本函数的结果称为成本值。最后，每一代成本值的平均值收敛到期望的答案。

交配和下一代

那些具有更高适应度（更低成本）值的染色体被用来产生下一代。后代是父代和母代的产物，其构成是它们的基因组合（这个过程称为“交叉”）。如果新一代包含一个产生输出足够接近或等于期望答案的染色体，那么问题就解决了。如果不是这种情况，那么新一代将经历与它们的父代相同的过程。这将一直持续到找到解决方案。

关于八皇后问题

在国际象棋中，一个皇后可以水平、垂直或对角线任意移动。棋盘有8行8列。标准的8x8皇后问题是如何在一个普通的棋盘上放置8个皇后，使得它们中的任何一个都不能在一步之内攻击到其他任何一个。在这里，我们使用遗传算法来解决n（n介于8到30之间）皇后问题。

使用代码

我们首先描述变量和函数

变量

  • int ChromosomeMatrix[30][1000]：这个变量是一个介于0到ChessBoardLenght-1之间的数字矩阵。例如，如果ChessBoardLength=8，ChromosomeMatrix可以是{4,6,0,2,7,5,3,1}，这样第一个数字定义了第一行皇后的位置，第二个数字定义了第二行皇后的位置，以此类推。
  • int CostMatrix[1000]：对于每个染色体矩阵，都定义了一个成本值。最佳值为0，表示没有皇后可以攻击到另一个。
  • int CrossOverMatrix[30][1000]：为了从父代生成子代，需要一个交叉矩阵，它决定了必须从两个父代中选择哪个基因。
  • int Population、int Iteration、float Mutationrate：这些变量是遗传算法的参数。
  • int ChessBoardLength：这决定了棋盘有多少行和多少列。
  • int area[30][30]：这个变量是一个棋盘矩阵。

函数

void CGAQueen::Clear()
{
    // to Reset All cells 
    for (int i=0;i<ChessBorad;i++)
        for (int j=0;j<ChessBorad;j++)
            area[i][j]=0;
}

此函数用于用0清除棋盘（area[][]）。

void CGAQueen::InitialPopulation() 
{
    int random;
    bool bCheck;
    for (int index=0;index<=Population-1;index++)
        for (int a=0;a<ChessBorad;a++)
        {
            random=rand();
            bCheck=1;
            for (int b=0;b<a;b++)
            if (random%ChessBorad==ChromosomeMatrix[b][index])
                bCheck=0;
            if (bCheck)
                ChromosomeMatrix[a][index]=random%ChessBorad;
            else
                a--;
        }
}

此函数用于生成初始种群。这个生成是纯粹随机的。使用此函数，ChromosomeMatrix[][]用0到ChessBoardLength-1之间的随机数填充。ChromosomeMatrix的数量等于Population。

void CGAQueen::FillArea(int index)
{
    Clear();
    for (int i=0;i<ChessBoradLenght;i++)
        area[i][ChromosomeMatrix[i][index]]=1;
}

此函数用于用一个染色体填充棋盘。例如，如果ChromosomeMatrix = {3,6,8,5,1,4,0,7,9,2}，第一个数字定义了第一行皇后的列，第二个数字定义了第二行皇后的列，依此类推。图2显示了棋盘——此处ChessBoardLength=10。

图 2 - 棋盘ChromosomeMatrix={ 3,6,8,5,1,4,0,7,9,2}

int CGAQueen::CostFunc(int index)
{
    int costValue=0;
    int m,n;
    int i,j;
    for(i=0;i<ChessBoradLenght;i++)
    {    
        j=ChromosomeMatrix[i][index];
        m=i+1;
        n=j-1;
        while(m<ChessBoradLenght    && n>=0)
        {
            if(area[m][n]==1)
                costValue++; 
            m++;
            n--;
        }

        m=i+1;
        n=j+1;
        while(m<ChessBoradLenght && n<ChessBoradLenght )
        {        
            if(area[m][n]==1)
                costValue++;            
            m++;
            n++;
        }
        m=i-1;
        n=j-1;
        while(m>=0 && n>=0)
        {        
            if(area[m][n]==1)
                costValue++; 
            m--;
            n--;
        }
        m=i-1;
        n=j+1;
        while(m>=0 && n<ChessBoradLenght)
        {        
            if(area[m][n]==1)
                costValue++;            
            m--;
            n++;
        }
    }
    return costValue;
}

此函数用于确定每个ChromosomeMatrix[][]的成本值，并将其保存在CostMatrix[]中。例如，对于染色体 = { 2,6,9,3,5,0,4,1,7,8 }，成本值为2。（见图3。）

图 3 - 由于这两只皇后互相攻击，成本值为2。

void CGAQueen::PopulationSort()
{
    bool k=1;
    int Temp;
    while (k)
    {
        k=0;
        for (int i=0;i<=Population-2;i++)
        {
            if (CostMatrix[i]>CostMatrix[i+1])    
            {
                Temp=CostMatrix[i];
                CostMatrix[i]=CostMatrix[i+1];
                CostMatrix[i+1]=Temp;
                
            for (int j=0;j<ChessBoradLenght;j++)
            {
                Temp=ChromosomeMatrix[j][i];
                ChromosomeMatrix[j][i]=ChromosomeMatrix[j][i+1];
                ChromosomeMatrix[j][i+1]=Temp;
            }            
            k=1;
            }
        }
    }
}

此函数用于根据成本值对新一代进行排序。最佳（最小值）放在顶部，最差（最大值）放在底部。

void CGAQueen::GenerateCrossOverMatrix()
{
    int randomCrossOver;
    for (int index=0;index<=Population-1;index++)
        for (int a=0;a<ChessBoradLenght;a++)
        {
            randomCrossOver=rand();
            CrossOverMatrix[a][index]=randomCrossOver%2;
        }
}

此函数用于生成交叉矩阵。该矩阵包含0和1。

void CGAQueen::Mating()
{
    int TempMatrix[30][2];
    int TempMatrix0[30],TempMatrix1[30];
    int Temp,j,k;

    …
}

此函数用于使用CrossOverMatrix从父代生成子代。这是实现此功能的一种方法。基因从p0和p1中提取。一个基因从一个父代中提取并附加到后代（子代）染色体中。在另一个父代中删除相应的基因（参见图4）。重复此步骤，直到两个父代染色体都为空，并且后代包含所有涉及的基因。

图 4 交叉方法

void CGAQueen::ApplyMutation()
{
    int randomChromosome;
    int randomGen0,randomGen1;
    int Temp;
    int NumberOfMutation=int(MutationRate*(Population-1)*ChessBoradLenght);
    for(int k=0;k<=NumberOfMutation;k++)
    {
        randomChromosome=0;
        while((randomChromosome=rand()%Population)==00;
        randomGen0=rand()%ChessBoradLenght;
        while((randomGen1=rand()%ChessBoradLenght)==randomGen0);
        Temp=ChromosomeMatrix[randomGen0][randomChromosome];
        ChromosomeMatrix[randomGen0][randomChromosome]=
          ChromosomeMatrix[randomGen1][randomChromosome];
        ChromosomeMatrix[randomGen0][randomChromosome]=Temp;
    }
}

此函数用于对当前一代应用变异。首先，选择一个随机染色体，但排除列表中的第一个（最佳）染色体。然后，选择此染色体的两个随机基因并相互替换。增加变异的数量会增加算法在当前染色体空间区域之外搜索的自由度。

我们提供了一个演示，供您体验遗传算法。

玩得开心。

© . All rights reserved.