# 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[1000];
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[15];
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();
}

}

}