Estoy tratando de construir un solucionador de sudoku 4 x 4 usando el algoritmo genético. Tengo algunos problemas con los valores que convergen a mínimos locales. Estoy usando un enfoque clasificado y elimino las dos posibilidades de respuesta inferiores y las reemplazo con un cruce entre las dos posibilidades de respuesta mejor clasificadas. Para obtener ayuda adicional para evitar el mininma local, también estoy usando la mutación. Si no se determina una respuesta dentro de una cantidad específica de generación, mi población se llena con valores de estado completamente nuevos y aleatorios. Sin embargo, mi algoritmo parece atascarse en los mínimos locales. Como una función física, estoy usando:

(Cantidad total de cuadrados abiertos * 7 (posibles infracciones en cada casilla; fila, columna y recuadro)) - Infracciones totales

población es una ArrayList de matrices enteras en la que cada matriz es un posible estado final para sudoku basado en la entrada. La aptitud se determina para cada conjunto de la población.

¿Alguien podría ayudarme a determinar por qué mi algoritmo converge en mínimos locales o tal vez recomendar una técnica para evitar mínimos locales? Cualquier ayuda es muy apreciada.

Función de la aptitud:

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

Función de cruce:

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] + ", ");
    }
}

Función de mutación:

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