Как предотвратить сходимость генетического алгоритма на локальных минимумах?
Я пытаюсь построить решатель судоку 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;
}
}