5

我正在尝试使用遗传算法构建一个 4 x 4 数独求解器。我对收敛到局部最小值的值有一些问题。我正在使用排名方法并删除排名最低的两个答案可能性，并用两个排名最高的答案可能性之间的交叉替换它们。为了额外帮助避免局部最小值，我也在使用突变。如果在特定的生成数量内没有确定答案，我的人口就会充满全新的随机状态值。但是，我的算法似乎陷入了局部最小值。作为健身功能，我正在使用：

（开放方格的总数 * 7（每个方格可能的违规；行、列和框））- 总违规

population是整数数组的 ArrayList，其中每个数组都是基于输入的数独的可能结束状态。为群体中的每个阵列确定适合度。

有人可以帮助我确定为什么我的算法会收敛于局部最小值，或者可能会推荐一种用于避免局部最小值的技术。任何帮助是极大的赞赏。

健身功能：

public int[] fitnessFunction(ArrayList<int[]> population)
{
    int emptySpaces = this.blankData.size();
    int maxError = emptySpaces*7;
    int[] fitness = new int[populationSize];

    for(int i=0; i<population.size();i++)
    {
        int[] temp = population.get(i);
        int value = evaluationFunc(temp);

        fitness[i] = maxError - value;
        System.out.println("Fitness(i)" + fitness[i]);
    }

    return fitness;
}

分频功能：

public void crossover(ArrayList<int[]> population, int indexWeakest, int indexStrong, int indexSecStrong, int indexSecWeak)
{
    int[] tempWeak = new int[16];
    int[] tempStrong = new int[16];
    int[] tempSecStrong = new int[16];
    int[] tempSecWeak = new int[16];

    tempStrong = population.get(indexStrong);
    tempSecStrong = population.get(indexSecStrong);
    tempWeak = population.get(indexWeakest);
    tempSecWeak = population.get(indexSecWeak);
    population.remove(indexWeakest);
    population.remove(indexSecWeak);


    int crossoverSite = random.nextInt(14)+1;

    for(int i=0;i<tempWeak.length;i++)
    {
        if(i<crossoverSite)
        {
            tempWeak[i] = tempStrong[i];
            tempSecWeak[i] = tempSecStrong[i];
        }
        else
        {
            tempWeak[i] = tempSecStrong[i];
            tempSecWeak[i] = tempStrong[i];
        }
    }
    mutation(tempWeak);
    mutation(tempSecWeak);
    population.add(tempWeak);
    population.add(tempSecWeak);

    for(int j=0; j<tempWeak.length;j++)
    {
        System.out.print(tempWeak[j] + ", ");
    }
    for(int j=0; j<tempWeak.length;j++)
    {
        System.out.print(tempSecWeak[j] + ", ");
    }
}

突变功能：

public void mutation(int[] mutate)
{
    if(this.blankData.size() > 2)
    {
        Blank blank = this.blankData.get(0);
        int x = blank.getPosition();

        Blank blank2 = this.blankData.get(1);
        int y = blank2.getPosition();

        Blank blank3 = this.blankData.get(2);
        int z = blank3.getPosition();

        int rando = random.nextInt(4) + 1;

        if(rando == 2)
        {
            int rando2 = random.nextInt(4) + 1;
            mutate[x] = rando2;
        }
        if(rando == 3)
        {
            int rando2 = random.nextInt(4) + 1;
            mutate[y] = rando2;
        }
        if(rando==4)
        {
            int rando3 = random.nextInt(4) + 1;
            mutate[z] = rando3;
        }
    }
4

2 回答 2

10

你看到快速收敛的原因是你的“交配”方法不是很好。你总是从得分最高的两个个体的“交配”中产生两个后代。想象一下，当其中一个新后代与您的顶级个体相同时会发生什么（偶然地，没有交叉和突变，或者至少没有对适应度产生影响）。一旦发生这种情况，前两个人是相同的，这就消除了交叉的有效性。

一种更典型的方法是替换每一代的每一个人。这里有很多可能的变化，但你可以随机选择两个父母加权适应度。

关于人口规模：我不知道数独问题对您的遗传表示和适应度功能有多难，但我建议您考虑数百万个人，而不是几十个人。

如果您正在处理非常困难的问题，那么当您将人口放在二维网格上并从附近的个体中为网格中的每个点选择“父母”时，遗传算法会更有效。您将获得局部收敛，但每个局部都会收敛到不同的解决方案；您会从网格的局部收敛区域之间的边界获得大量变化。

您可能会考虑的另一种技术是多次运行以从随机种群中收敛，并存储每次运行的顶级个体。在你建立了一堆不同的局部最小值基因组之后，从这些顶级个体中建立一个新的随机种群。

于 2014-11-18T04:35:46.100 回答
0

我认为数独是一个排列问题。因此我建议您使用随机排列数来初始化种群，并使用与排列问题兼容的交叉方法。

于 2014-11-24T12:48:34.640 回答