如何防止遗传算法收敛于局部最小值？

Question

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

(开放平方的总金额*7(每个方格可能违反;行,列和方框)) - 违规总数

population是整数数组的ArrayList,其中每个数组都是基于输入的sudoku可能的结束状态.确定人群中每个阵列的适应度.

有人能够帮助我确定为什么我的算法会收敛于局部最小值,或者可能会建议使用一种技术来避免局部最小值.任何帮助是极大的赞赏.

健身功能:

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;
        }
    }

Answer 1

你看到快速收敛的原因是你的"交配"方法不是很好.你总是从前两位得分人的"交配"中产生两个后代.想象一下当一个新的后代与你的顶级个体相同时会发生什么(偶然,没有交叉和没有突变,或者至少没有一个对健康产生影响).一旦发生这种情况,前两个人是相同的,这消除了交叉的有效性.

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

关于人口规模:我不知道数据有多难给出你的基因表现和健身功能,但我建议你考虑数百万个人,而不是几十个人.

如果您正在研究真正难以解决的问题,那么当您将人口置于二维网格并为附近的个体中的每个点选择"父母"时,遗传算法会更有效.您将获得本地融合,但每个地方都将融合在不同的解决方案上; 你会从网格的局部融合区域之间的边界产生大量的变化.

您可能会想到的另一种技术是从随机群体中多次收敛并存储每次运行中的顶级个体.在构建了一堆不同的局部最小基因组后,从那些顶级个体中构建一个新的随机群体.