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

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++) {
}
}

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++) {
}
}

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) {
}
}

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

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

public class GADemo {

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

gp.evolve(100);
}
}

• 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 :) – user3719857 May 3 '16 at 18:37

• 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.
• 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. – Hank D May 4 '16 at 3:40