我正在尝试使用遗传算法构建 4 x 4 数独求解器。我对值收敛到局部最小值有一些问题。我正在使用排名方法并删除排名底部的两个答案可能性,并将它们替换为排名最高的两个答案可能性之间的交叉。为了获得避免局部最小值的额外帮助,我还使用了突变。如果在特定的一代时间内没有确定答案,我的群体将充满全新的随机状态值。然而,我的算法似乎陷入了局部最小值。作为健身功能,我使用:
(空心方块总数 * 7(每个方块可能存在的违规行为;行、列和方框))- 违规总数
人口是一个整数数组的 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;
}
}