如何防止遗传算法收敛于局部最小值？
我正在尝试使用遗传算法构建一个4 x 4数独求解器。 我有一些问题，价值收敛到局部最小值。 我正在使用排名方法并删除最后两个排名的答案可能性，并用两个排名最高的答案可能性之间的交叉替换它们。 为了避免局部mininma的额外帮助，我也使用变异。 如果在特定的生成量内未确定答案，则我的人口中充满了全新的随机状态值。 但是，我的算法似乎陷入局部最小值。 作为健身function，我正在使用：
（开放平方的总金额* 7（每个方格可能违规;行，列和方框）） – 违规总数
population是整数数组的ArrayList，其中每个数组都是基于输入的sudoku的可能结束状态。 确定人群中每个arrays的适应度。
有人能够帮助我确定为什么我的算法会收敛于局部最小值，或者可能会推荐一种技术来避免局部最小值。 任何帮助是极大的赞赏。
健身function：
public int[] fitnessFunction(ArrayList 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; } 交叉function：
public void crossover(ArrayList 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] + ", "); } }
突变function：
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; } }
你看到快速收敛的原因是你的“交配”方法不是很好。 你总是通过排名前两位得分人的“交配”产生两个后代。 想象一下当一个新的后代与你的顶级个体相同时会发生什么（偶然，没有交叉和没有突变，或者至少没有一个对健身产生影响）。 一旦发生这种情况，前两个人是相同的，这消除了交叉的有效性。
更典型的方法是在每一代中替换每个人。 这里有很多可能的变化，但你可以随机选择两个父母加权适应度。
关于人口规模：我不知道数独有多少给你的基因表现和健身function，但我建议你考虑数百万个人，而不是几十个人。
如果您正在处理非常棘手的问题，那么当您将人口置于二维网格并为附近的个体中的每个点选择“父母”时，遗传算法会更有效。 您将获得本地融合，但每个地区将融合在不同的解决方案上; 你会从网格的局部融合区域之间的边界产生大量的变化。
您可能会想到的另一种技术是从随机群体中多次收敛并存储每次运行中的最高个体。 在构建了一堆不同的局部最小基因组后，从这些顶级个体中构建一个新的随机群体。
我认为数独是一个排列问题。 因此，我建议你使用随机排列数来初始化人口，并使用兼容排列问题的交叉方法。