如何防止遗传算法收敛于局部最小值？ [英] How to prevent genetic algorithm from converging on local minima?

问题描述

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

I am trying to build a 4 x 4 sudoku solver by using the genetic algorithm. I have some issues with values converging to local minima. I am using a ranked approach and removing the bottom two ranked answer possibilities and replacing them with a crossover between the two highest ranked answer possibilities. For additional help avoiding local mininma, I am also using mutation. If an answer is not determined within a specific amount of generation, my population is filled with completely new and random state values. However, my algorithm seems to get stuck in local minima. As a fitness function, I am using:

（开放式广场的总金额* 7（每个广场可能违规;行，列和方框）） - 违规总数

(Total Amount of Open Squares * 7 (possible violations at each square; row, column, and box)) - total Violations

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

population is an ArrayList of integer arrays in which each array is a possible end state for sudoku based on the input. Fitness is determined for each array in the population.

是否有人能够帮助我确定为什么我的算法收敛于局部最小值或者可能建议使用一种技术来避免当地最低点。非常感谢任何帮助。

Would someone be able to assist me in determining why my algorithm converges on local minima or perhaps recommend a technique to use to avoid local minima. Any help is greatly appreciated.

健身功能：

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

推荐答案

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

The reason you see rapid convergence is that your methodology for "mating" is not very good. You are always producing two offspring from "mating" of the top two scoring individuals. Imagine what happens when one of the new offspring is the same as your top individual (by chance, no crossover and no mutation, or at least none that have an effect on the fitness). Once this occurs, the top two individuals are identical which eliminates the effectiveness of crossover.

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

A more typical approach is to replace EVERY individual on every generation. There are lots of possible variations here, but you might do a random choice of two parents weighted fitness.

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

Regarding population size: I don't know how hard of a problem sudoku is given your genetic representation and fitness function, but I suggest that you think about millions of individuals, not dozens.

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

If you are working on really hard problems, genetic algorithms are much more effective when you place your population on a 2-D grid and choosing "parents" for each point in the grid from the nearby individuals. You will get local convergence, but each locality will have converged on different solutions; you get a huge amount of variation produced from the borders between the locally-converged areas of the grid.

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

Another technique you might think about is running to convergence from random populations many times and store the top individual from each run. After you build up a bunch of different local minima genomes, build a new random population from those top individuals.

这篇关于如何防止遗传算法收敛于局部最小值？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！