Genetic algorithm to find the maximum binary number of a given length

Question

I have written some codes in java implementing simplest genetic algorithm. The code finds (or rather tries to) the maximum value possible for a user-defined number of bits. For example, for 16 bit chromosomes, the code tries to get 2¹⁶-1. I have never had my code reviewed by any one good, so the thing I am looking for is quite obvious: how can I improve my code?

So here goes the code:

Gene.java

public class Gene {

    private int value;

    public Gene() {
        value = Math.random() < 0.5 ? 0 : 1;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        if (value != 0 && value != 1) {
            throw new IllegalArgumentException("value must be either 0 or 1");
        }
        this.value = value;
    }

    public void mutate() {
        value = 1 - value;
    }

    @Override
    public String toString() {
        return String.valueOf(value);
    }
}

Chromosome.java

import java.util.ArrayList;
import java.util.List;

public class Chromosome implements Comparable {

    private ArrayList<Gene> genes;
    private final int chromosomeLength;

    public Chromosome(int length) {
        this.genes = new ArrayList<>();

        this.chromosomeLength = length > 0 ? length : 16;

        for (int i = 0; i < chromosomeLength; i++) {
            this.genes.add(i, new Gene());
        }
    }

    public List<Gene> getGenes() {
        return genes;
    }

    public void setGenes(ArrayList<Gene> genes) {
        this.genes = genes;
    }

    public List<Gene> getAllele(int fromIndex, int toIndex) {
        return new ArrayList<>(genes.subList(fromIndex, toIndex));
    }

    public void setAllele(int fromIndex, List<Gene> allele) {

        int lastIndex = fromIndex + allele.size();
        if (lastIndex > chromosomeLength) {
            throw new IndexOutOfBoundsException("the allele exceeds beyond the size of the chromosome");
        }
        for (int i = fromIndex, j = 0; i < lastIndex; i++, j++) {
            genes.get(i).setValue(allele.get(j).getValue());
        }
    }

    public int getChromosomeLength() {
        return chromosomeLength;
    }

    public void setGeneAt(int index, Gene gene) {
        genes.set(index, gene);
    }

    public Gene getGeneAt(int index) {
        return genes.get(index);
    }

    public int value() {
        return Integer.parseInt(this.toString(), 2);
    }

    @Override
    public String toString() {
        StringBuilder chromosome = new StringBuilder("");
        genes.stream().forEach((Gene g) -> chromosome.append(g));
        return chromosome.toString();
    }

    @Override
    public int compareTo(Object anotherChromosome) {
        Chromosome c = (Chromosome) anotherChromosome;
        return this.value() - c.value();
    }
}

GenePool.java

import java.util.ArrayList;
import java.util.Arrays;


public class GenePool {

    private final ArrayList<Chromosome> genePool;
    private final int genePoolSize;
    private final int chromosomeLength;
    private final double crossOverRate;
    private final double mutationRate;
    private int[] crossPoints;

    public GenePool(int numOfChromosome, int chromosomeLength, double crossOverRate, double mutationRate) {

        this.genePoolSize = numOfChromosome;
        this.chromosomeLength = chromosomeLength > 0 ? chromosomeLength : 16;
        this.crossOverRate = crossOverRate;
        this.mutationRate = mutationRate;

        crossPoints = new int[1];
        crossPoints[0] = this.chromosomeLength / 2;

        genePool = new ArrayList<>();
        for (int i = 0; i < numOfChromosome; i++) {
            genePool.add(new Chromosome(chromosomeLength));
        }
    }

    public int getGenePoolSize() {
        return genePoolSize;
    }

    public Chromosome getChromosomeAt(int index) {
        return genePool.get(index);
    }

    public void setChromosomeAt(int index, Chromosome c) {
        genePool.set(index, c);
    }

    public int getChromosomeLength() {
        return chromosomeLength;
    }

    public int[] getCrossPoints() {
        return crossPoints;
    }

    public void setCrossPoints(int[] crossPoints) {
        if (crossPoints != null) {
            this.crossPoints = crossPoints;

            Arrays.sort(this.crossPoints);
            if (this.crossPoints[0] < 1 || this.crossPoints[crossPoints.length - 1] >= this.chromosomeLength) {
                throw new IllegalArgumentException("values in the crossPoints array must be\n\tbetween 1 "
                        + "and chromosomeLength-1 inclusive");
            }
        }
    }

    public Chromosome[] crossOver(Chromosome c1, Chromosome c2) {

        Chromosome[] offsprings = new Chromosome[2];
        offsprings[0] = new Chromosome(c1.getChromosomeLength());
        offsprings[1] = new Chromosome(c1.getChromosomeLength());

        Chromosome[] parentChromosomes = {c1, c2};

        int selector = 0;
        for (int i = 0, start = 0; i <= crossPoints.length; i++) {

            int crossPoint = i == crossPoints.length ? c1.getChromosomeLength() : crossPoints[i];

            offsprings[0].setAllele(start, parentChromosomes[selector].getAllele(start, crossPoint));
            offsprings[1].setAllele(start, parentChromosomes[1 - selector].getAllele(start, crossPoint));
            selector = 1 - selector;
            start = crossPoint;
        }
        return offsprings;
    }

    public void mutateGenePool() {

        int totalGeneCount = genePoolSize * chromosomeLength;

        System.out.println("Mutating genes:");
        for (int i = 0; i < totalGeneCount; i++) {
            double prob = Math.random();
            if (prob < mutationRate) {
                System.out.printf("Chromosome#: %d\tGene#: %d\n", i / chromosomeLength, i % chromosomeLength);
                genePool.get(i / chromosomeLength).getGeneAt(i % chromosomeLength).mutate();
            }
        }
        System.out.println("");
    }

    public int getLeastFitIndex() {
        int index = 0;
        int min = genePool.get(index).value();
        int currentValue;
        for (int i = 1; i < genePoolSize; i++) {
            currentValue = genePool.get(i).value();
            if (currentValue < min) {
                index = i;
                min = currentValue;
            }
        }
        return index;
    }

    public void saveFittest(ArrayList<Chromosome> offsprings) {
        // sort in ascending order
        offsprings.sort(null);

        offsprings.stream().forEach((offspring) -> {
            int leastFitIndex = getLeastFitIndex();
            if (offspring.value() > genePool.get(leastFitIndex).value()) {
                genePool.set(leastFitIndex, offspring);
            }
        });
    }

    public void evolve(int noOfGeneration) {

        for (int generation = 1; generation <= noOfGeneration; generation++) {

            System.out.println("Generation :" + generation);
            ArrayList<Integer> selection = new ArrayList<>();

            for (int i = 0; i < genePoolSize; i++) {
                if (Math.random() <= crossOverRate) {
                    selection.add(i);
                }
            }

            if (selection.size() % 2 == 1) {
                selection.remove(selection.size() - 1);
            }

            ArrayList<Chromosome> offsprings = new ArrayList<>();
            for (int i = 0; i < selection.size(); i += 2) {
                int index1 = selection.get(i);
                int index2 = selection.get(i + 1);
                offsprings.addAll(Arrays.asList(crossOver(genePool.get(index1), genePool.get(index2))));
            }

            System.out.println("Before saving the offsprings");
            displayChromosomes(genePool, "GenePool");
            displayChromosomes(offsprings, "Offsprings");

            saveFittest(offsprings);

            System.out.println("Before mutation:");
            displayChromosomes(genePool, "GenePool");

            mutateGenePool();

            System.out.println("After mutation:");
            displayChromosomes(genePool, "GenePool");

            System.out.println("\n\n");
        }
    }

    public void displayChromosomes(ArrayList<Chromosome> geneList, String name) {
        System.out.println(name);
        if (geneList.isEmpty()) {
            System.out.println("Empty list");
        }

        geneList.stream().forEach((c) -> {
            System.out.println(c + " -> " + c.value());
        });
        System.out.println("");
    }
}

GADemo.java

public class GADemo {

    public static void main(String[] args) {
        GenePool gp = new GenePool(10, 0, 0.25, 0.01);

        gp.evolve(100);
    }
}

Answer 1

I can offer a few points.

• It seems like a Gene is essentially a single bit, having only 2 values, so a Chromosome, having no more than 16 Genes, could be modeled as a short or an int, using 16 bits to represent the values of the genes.
• Avoid using concrete collection types like ArrayList except when creating them. It makes code less maintainable since you can't change the implementation type without hunting through the code. See Chromosome.setGenes()
• myCollection.forEach() is more efficient than myCollection.stream().forEach()
• quite often, when I see people jump straight to forEach, I find that they are missing opportunities to leverage the power of the Stream api. One thing I do is look at what is in the forEach() and if I see the block split cleanly by an if{} statement, I see a place where Stream.filter() should be used.