# Genetic Algorithm for N-queens is very slow

Using Genetic Algorithm to solve N-Queens problem where N=22. My program is functional and is capable of solving N-Queen problems up to around where N=15, but everything after that is absurdly slow. The goal of my program is to reach a speed where it can solve N=22 in a reasonable time. The only thing that I can think of that is slowing my program down is the sorting algorithm I am currently using, which is bubble sort. But even after the switch to QuickSort there was no improvement. I switched back to bubble sort so that I can isolate and find the main issue that is slowing my program down.

I know there are many different ways to implement the Genetic Algorithm, but I did mine based off Wikipedia.

import java.util.Random;

public class GeneticAlgorithm {

private Random random;

public GeneticAlgorithm() {
random = new Random();

Chromosome[] population = generatePopulation();

if (checkInitialPop(population) != null) {
System.out.println("Initial board has solution");
printBoard(checkInitialPop(population).state);
} else {
while (true) {
normalizeFitnessFunction(population);
sortPopulation(population);
Chromosome x = selectChromosome(population);
Chromosome y = selectChromosome(population);
Chromosome z = crossOver(x, y);
//Replace least fit Chromosome with child
population[population.length - 1] = z;
if (getFitnessFunction(z.state) == 253) {
System.out.println("Solved");
printBoard(z.state);
break;
}
}
}
}

//Checks initial population for goal state
private Chromosome checkInitialPop(Chromosome[] population) {
for (int i = 0; i < population.length; i++) {
if (getFitnessFunction(population[i].state) == 253) {
return population[i];
}
}
return null;
}

//Generates population of Chromosomes
private Chromosome[] generatePopulation() {
Chromosome[] population = new Chromosome;
for (int i = 0; i < population.length; i++) {
population[i] = new Chromosome(generateState());
}
return population;
}

//Generates a random state for N-Queens board
private int[] generateState() {
int[] state = new int;
for (int i = 0; i < state.length; i++) {
state[i] = random.nextInt(15);
}
return state;
}

//Makes all fitness
private void normalizeFitnessFunction(Chromosome[] population) {
int accFit = 0;
for (int i = 0; i < population.length; i++) {
accFit += getFitnessFunction(population[i].state);
}

for (int i = 0; i < population.length; i++) {
population[i].fitness = (double) getFitnessFunction(population[i].state) / (double) accFit;
}
}

//Bubble Sort (Descending order)
private void sortPopulation(Chromosome[] population) {
int n = population.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < (n - i) - 1; j++) {
if (population[j].fitness < population[j + 1].fitness) {
Chromosome temp = population[j];
population[j] = population[j + 1];
population[j + 1] = temp;
}
}
}
}

//Genetic Algorithm Roulette Wheel Selection
private Chromosome selectChromosome(Chromosome[] population) {
double x = random.nextDouble();
double accFit = 0;

for (int i = 0; i < population.length; i++) {
accFit += population[i].fitness;
}

double value = x * accFit;

for (int i = 0; i < population.length; i++) {
value -= population[i].fitness;
if (value <= 0) {
return population[i];
}
}

return population[population.length - 1];
}

//Crosses over two Chromosomes to make child
private Chromosome crossOver(Chromosome x, Chromosome y) {
int point = random.nextInt(x.state.length);
int[] state = new int[x.state.length];
for (int i = 0; i < point; i++) {
state[i] = x.state[i];
}

for (int i = point; i < y.state.length; i++) {
state[i] = y.state[i];
}

// Mutation
double mutateRate = random.nextDouble();
if (mutateRate <= 0.05) {
state[random.nextInt(state.length)] = random.nextInt(state.length);
}

return new Chromosome(state);
}

//Gets # of queens in conflict and subtracts from 253
private int getFitnessFunction(int[] state) {
int h = 0;
int offset = 0;
// For each col
for (int i = 0; i < state.length; i++) {
// For each row
for (int j = i + 1; j < state.length; j++) {
// If queen in same row
if (state[i] == state[j]) {
h += 1;
}
// For Diagonals
offset = j - i;
// If Another queen in diagonal
if (state[i] == state[j] - offset || state[i] == state[j] + offset) {
h += 1;
}
}
}
return 253 - h;
}

private void printBoard(int[] state) {
if (state != null) {
int[][] temp = new int[state.length][state.length];

for (int i = 0; i < state.length; i++) {
for (int j = 0; j < state.length; j++) {
temp[i][j] = 0;
}
}

for (int i = 0; i < state.length; i++) {
int col = i;
int row = state.length - 1 - state[i];
temp[row][col] = 1;

}

for (int i = 0; i < temp.length; i++) {
System.out.println("");
for (int j = 0; j < temp.length; j++) {
if (temp[i][j] == 1) {
System.out.print("Q ");
} else {
System.out.print("- ");
}
}
}

}
}

private class Chromosome {

double fitness;
int[] state;

public Chromosome(int[] state) {
this.state = state.clone();
}

}

}


## 1 Answer

You could encode the chromosome better. Currently, you can create a state=[1, 5,1,...], which is clearly an invalid state. Instead, make the state a permutation of [1,2,...n]. This will eliminate MANY unfit genes.

The mutation operator is just swapping two random positions. And you don't need to do the crossover. (This is typically how we encode the traveling salesman problem.)

• There are ways to crossover two permutations so that the result is a permutation (e.g. PMX, partially matched crossover) so it would be possible to still do it as a genetic rather than simple evolutionary algorithm, but +1 for identifying what is probably the core problem with the code. – John Coleman Aug 22 '17 at 15:06
• PMX is pretty cool. But IMHO, i generally advise against any form of crossover because it doesn't help the algorithm and is an unnecessary complication. – Ray Aug 22 '17 at 17:57