GeneticTask.java

public class GeneticTask implements Callable<Chromosome> {

    private int generationsNumber = 10;
    private int populationSize;
    private double crossoverProbability = 0.1;
    private double mutationProbability = 0.05;
    private Chromosome[] initPopulation;

    private final Random GENERATOR = new Random();

    public GeneticTask() {
    }

    public GeneticTask insertChromosomes(Chromosome[] chromosomes) {
        setInitPopulation(chromosomes);
        return this;
    }

    public GeneticTask populationSize(int size) {
        setPopulationSize(size);
        return this;
    }
    public GeneticTask generationsNumber(int size) {
        setGenerationsNumber(size);
        return this;
    }

    public GeneticTask crossoverProbability(int crossoverProbability) {
        setCrossoverProbability(crossoverProbability);
        return this;
    }

    public GeneticTask mutationProbability(int mutationProbability) {
        setMutationProbability(mutationProbability);
        return this;
    }

    /**
     * This method validates chromosomes to make sure the necessary conditions are met:
     * - Population size has to be an even number in order to allow the pairing algorithm
     * to work properly.
     * - Every chromosome has to pass the internal validation in order for genetic operations
     * to be produce the accurate result
     * - Crossover probability has to be higher than mutation probability.
     * Widely used probability values vary:
     * from 0.05 to 0.2 for crossover probability
     * from 0.001 to 0.05 for mutation probability
     *
     * In case any condition has been violated, method should throw
     * IllegalArgumentException with an appropriate message
     */
    private void validate() {

        if (populationSize % 2 != 0)
            throw new IllegalArgumentException("Population size has to be an even number!");

        if (mutationProbability > crossoverProbability)
            throw new IllegalArgumentException("ERROR! Crossover probability (<= 0.05) should be lower than mutation probability!");

        for (Chromosome chromosome : initPopulation) {
            if (!chromosome.isValid()) {
                throw new IllegalArgumentException("ERROR! Chromosome " + chromosome + " is invalid");
            }
        }
    }

    /**
     * Method used to generate first parent generation.
     * At this point, fitness values of the chromosomes aren't known.
     *
     * @param chromosomes The chromosomes passed as arguments by user
     * @param populationSize Number of chromosomes to be selected
     * @return Randomly selected chromosomes, without assesing the fitness value
     */
    private Chromosome[] generateFirstPopulation(Chromosome[] chromosomes, int populationSize) {

        Chromosome[] firstPopulation = new Chromosome[populationSize];

        for (int i = 0; i < populationSize; i++) {
            int randomChoice = GENERATOR.nextInt(chromosomes.length);
            firstPopulation[i] = chromosomes[randomChoice];
        }
        return firstPopulation;
    }


    private double[] computeFitnessValues(Chromosome... chromosomes) {

        double[] fitnessValues = new double[chromosomes.length];

        for (int i = 0; i < chromosomes.length; i++) {
            fitnessValues[i] = chromosomes[i].getFitnessValue();
        }
        return fitnessValues;
    }


    /**
     * This method randomly selects a chromosome using
     * the proportional range method.
     * Backward search optimization is applied in order to reduce iteration steps.
     * Example:
     * We divide the total sum of fitness values by 2 and get the middle point
     * If a generated point value is smaller than the middle point, method starts iterating from zero to max value
     * If that point is larger than the middle point, method iterates from max value to zero
     *
     *
     * @param ranges Array of value ranges
     * @param totalFitness A sum of all fitness values
     * @return A chromosome selected using proportional random choice
     */
    private Optional<Chromosome> selectChromosome(ChoiceRange[] ranges, double totalFitness) {

        // make sure entries are in the correct order
        Arrays.parallelSort(ranges);

        //generate random point of choice
        double choice = totalFitness * GENERATOR.nextDouble();

        /*
        * if the point of choice is lower than half of the total range
        * search the range array forward, otherwise search backwards
        */
        if (choice <= totalFitness / 2D) {
            for (ChoiceRange range : ranges) {
                if (choice >= range.start && choice < range.end)
                    return Optional.ofNullable(range.getChromosome());
            }
        } else {
            for (int i = ranges.length - 1; i >= 0; i--) {
                if (choice < ranges[i].end && choice >= ranges[i].start)
                    return Optional.ofNullable(ranges[i].getChromosome());
            }
        }

        return Optional.empty();
    }

    /**
     * Used to select chromosome population for current iteration(generation)
     *
     * @param chromosomes   Pool used to select reproductive chromosomes
     * @param fitnessValues Corresponding fitness values used in proportional selection
     * @return An array of reproductive chromosomes
     */
    private Chromosome[] selectParentPopulation(Chromosome[] chromosomes, double[] fitnessValues) {
        double totalFitness = 0;
        double startStep = 0;

        // Compute sum of fitness values
        for (double fitnessValue : fitnessValues) {
            totalFitness += fitnessValue;
        }

        // Assign array of ranges and add corresponding chromosome to each one
        ChoiceRange[] ranges = new ChoiceRange[chromosomes.length];
        for (int i = 0; i < chromosomes.length; i++) {
            ranges[i] = new ChoiceRange(chromosomes[i], Math.nextAfter(startStep, totalFitness), startStep + fitnessValues[i]);
            startStep += fitnessValues[i];
        }

        Chromosome parentGeneration[] = new Chromosome[populationSize];

        //Generate parent generation
        for (int i = 0; i < populationSize; i++) {
            parentGeneration[i] = selectChromosome(ranges, totalFitness).get();
        }

        return parentGeneration;
    }

    /**
     * Calls chromosome's crossover() and mutate() methods
     * if probability conditions are satisfied:
     * Example:
     * Crossover probability equals 0.1.
     * If random double generator returns double number that is
     * either equal or smaller than 0.1, crossover() method is called.
     * Same applies for mutation.
     *
     * @param chromosomes Chromosomes selected to be reproduced
     * @return Children chromosomes, known as new parent generation
     */
    private Chromosome[] performGeneticOperations(Chromosome[] chromosomes) {

        for (int i = 0; i < chromosomes.length; i += 2) {

            if (GENERATOR.nextDouble() <= crossoverProbability) {
                chromosomes[i] = chromosomes[i].crossover(chromosomes[i + 1]);
                chromosomes[i + 1] = chromosomes[i + 1].crossover(chromosomes[i]);
            }
            if (GENERATOR.nextDouble() <= mutationProbability) {
                chromosomes[i] = chromosomes[i].mutate(chromosomes[i + 1]);
                chromosomes[i + 1] = chromosomes[i + 1].mutate(chromosomes[i]);
            }
        }
        return chromosomes;
    }

    private Chromosome bestChromosome(Chromosome[] chromosomes) {
        Arrays.parallelSort(chromosomes);
        return chromosomes[chromosomes.length - 1];
    }

    /**
     * This is the core method of GeneticTask class.
     * It performs the "basic genetic algorithm" part:
     * select population -> crossover & mutate chromosomes -> repeat
     * Number of iterations (generations) is set to 10 by default, it can be changed
     * by calling populationSize(number) method.
     *
     * @return The final population after performing all iterations
     */
    private Chromosome[] getEvolvedGeneration() {

        validate();

        Chromosome[] population = generateFirstPopulation(initPopulation, populationSize);
        System.out.println(Arrays.toString(population));
        double[] fitnessValues;

        for (int i = 0; i < generationsNumber; i++) {
            fitnessValues = computeFitnessValues(population);
            population = selectParentPopulation(population, fitnessValues);
            performGeneticOperations(population);
            System.out.println(Arrays.toString(population));
        }

        return population;
    }

    @Override
    public Chromosome call() throws Exception {
        Chromosome[] evolvedCandidates = getEvolvedGeneration();

        return bestChromosome(evolvedCandidates);
    }

    public void setCrossoverProbability(double crossoverProbability) {
        this.crossoverProbability = crossoverProbability;
    }

    public void setMutationProbability(double mutationProbability) {
        this.mutationProbability = mutationProbability;
    }


    public void setInitPopulation(Chromosome[] initPopulation) {
        this.initPopulation = initPopulation;
    }

    public void setPopulationSize(int populationSize) {
        if (populationSize > 0) {
            this.populationSize = populationSize;
        } else {
            throw new IllegalArgumentException("A size of a population must be larger than 0!");
        }
    }


    public void setGenerationsNumber(int generations) {

        if (generations > 0) {
            this.generationsNumber = generations;
        } else {
            throw new IllegalArgumentException("A number of iterations must be larger than 0!");
        }
    }


    private class ChoiceRange implements Comparable<ChoiceRange> {
        private Chromosome chromosome;

        public Chromosome getChromosome() {
            return chromosome;
        }

        public void setChromosome(Chromosome chromosome) {
            this.chromosome = chromosome;
        }

        public ChoiceRange(Chromosome chromosome, double start, double end) {
            this.start = start;
            this.end = end;
            setChromosome(chromosome);
        }

        double start;
        double end;

        @Override
        public int compareTo(ChoiceRange o) {
            return Double.valueOf(start).compareTo(o.start);
        }
    }
}