Como impedir que o algoritmo genético converja em mínimos locais?
Estou tentando criar um solucionador de sudoku 4 x 4 usando o algoritmo genético. Tenho alguns problemas com valores convergentes para mínimos locais. Estou usando uma abordagem classificada e removendo as duas possibilidades de respostas classificadas inferiores e substituindo-as por um cruzamento entre as duas possibilidades de respostas classificadas mais altas. Para obter ajuda adicional para evitar o mininma local, também estou usando mutação. Se uma resposta não for determinada dentro de uma quantidade específica de geração, minha população será preenchida com valores de estado completamente novos e aleatórios. No entanto, meu algoritmo parece ficar parado nos mínimos locais. Como função de condicionamento físico, estou usando:
(Quantidade total de quadrados abertos * 7 (possíveis violações em cada quadrado; linha, coluna e caixa)) - total de violações
população é um ArrayList de matrizes inteiras, em que cada matriz é um possível estado final para o sudoku com base na entrada. A aptidão é determinada para cada matriz da população.
Alguém poderia me ajudar a determinar por que meu algoritmo converge em mínimos locais ou talvez recomende uma técnica a ser usada para evitar mínimos locais. Qualquer ajuda é muito apreciada.
Função de fitness:
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;
}
Função Crossover:
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] + ", ");
}
}
Função de mutação:
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;
}
}