7
\$\begingroup\$

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 216-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);
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Well the only minor thing I think can be improved is if this program is used on a server or in some multithreaded enviroment, you should use ThreadLocalRandom instead of Math.random(), because the second is kind of slow. Hope this helps in some manor :) \$\endgroup\$ – user3719857 May 3 '16 at 18:37
2
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Thanks. If I did use short or int, how would I do the crossover easily? Mutation is quite obvious by using bitwise operations. Also, note that one can choose any different length other than 16 for chromosome length. \$\endgroup\$ – Sнаđошƒаӽ May 4 '16 at 3:28
  • 1
    \$\begingroup\$ You can still iterate, but instead of an index that increments using i++ you have a single - bit mask that increments using i <<= 1, e.g. for(i = 1; i < 1 << 16; i <<= 1) However, with a little imagination, you could find ways to copy whole chunks of a chromosome using & with a mask containing all the bits you want to copy set to 1, then using shift operators to align them the way you want and splice them in using the | operator. \$\endgroup\$ – Hank D May 4 '16 at 3:40
  • \$\begingroup\$ Since you are the only one giving an answer here, I am going to accept it. But I am not convinced that there is no more improvement to be done :-) \$\endgroup\$ – Sнаđошƒаӽ Jun 28 '16 at 5:54

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.