Ich versuche, einen 4 x 4-Sudoku-Löser mithilfe des genetischen Algorithmus zu erstellen. Ich habe einige Probleme mit Werten, die sich den lokalen Minima annähern. Ich benutze einen rangierten Ansatz und entferne die unteren zwei rangierten Antwortmöglichkeiten und ersetze sie durch einen Übergang zwischen den beiden ranghöchsten Antwortmöglichkeiten. Als zusätzliche Hilfe zur Vermeidung von lokalem Mininma verwende ich auch Mutation. Wenn eine Antwort nicht innerhalb einer bestimmten Anzahl von Generationen ermittelt wird, wird meine Population mit völlig neuen und zufälligen Zustandswerten gefüllt. Mein Algorithmus scheint jedoch in lokalen Minima zu stecken. Als Fitnessfunktion benutze ich:

(Gesamtanzahl offener Felder * 7 (mögliche Verstöße an jedem Feld; Zeile, Spalte und Feld)) - Gesamtanzahl der Verstöße

Populatio ist eine ArrayList von Integer-Arrays, in denen jedes Array ein möglicher Endstatus für Sudoku ist, der auf der Eingabe basiert. Die Fitness wird für jedes Array in der Population bestimmt.

Wäre jemand in der Lage, mich bei der Ermittlung der Konvergenz meines Algorithmus für lokale Minima zu unterstützen, oder würde er möglicherweise eine Technik empfehlen, mit der lokale Minima vermieden werden können? Jede Hilfe wird sehr geschätzt.

Fitnessfunktion

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

Crossover-Funktion:

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

Mutationsfunktion:

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