7
\$\begingroup\$

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

    }

}
\$\endgroup\$
2
\$\begingroup\$

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.)

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – John Coleman Aug 22 '17 at 15:06
  • \$\begingroup\$ 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. \$\endgroup\$ – Ray Aug 22 '17 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.