Genetic Algorithm: Simple Implementation In Java(Binary)

Link Copied To Clipboard !

binary_genetic_algorithm_in_java Algorithms

Genetic Algorithm is the popular evolutionary algorithm based on biological genetics and natural selection. It is typically used in the problems where the goal is to find an optimal best possible solution by performing some genetic operations like crossover and mutation over fittest and selected parents of existing population.

Let’s not talk much about the algorithm and get into the actual part of implementing a very simple binary GA algorithm in java. Before diving into the coding part, let’s first understand what we are trying to achieve and make a plan about how we are going to implement that on code.

What is binary genetic algorithm ?

Binary Genetic Algorithm is similar to other types of genetic algorithms except in binary GA, each chromosome of a population is represented by sequences of zeros and ones, meaning that a gene can have a value of either zero ‘0’ or one ‘1’. The chromosomes of population are all subjected to the genetic operations viz: Selection, Crossover, Mutation in order to improve the fitness of population and achieve the expected goal.

What are we trying to do ?

We are trying to get an individual(chromosome) with certain number of genes to have all genes equal to ones(1s). Simply, we will initialize the population with random chromosome sequences. The population will have certain number of chromosomes. Then, by calculating the fitness, we will know whether the solution exists in the population. If not, we will perform crossover and mutation on them and make the new population of improved genetics eliminating least fittest ones ( Survival of the fittest ).

How to implement simple binary genetic algorithm in Java ?

To implement binary genetic algorithm, we will need a Population class, an Individual or Chromosome class, a Gene class, an Algorithm class as a wrapper and a Main class to execute the algorithm. We will begin to code from the atomic gene level. Create a class Gene.java with a variable number. We need bother getter and setter for this variable as we might want to get or set the value in future. The Gene class looks like this :

package np.com.bsubash.ga.binary;

/**
 * @author subash
 * @since Mar 27, 2021
 */
public class Gene {
	private int number;

	public Gene(int number) {
		this.number = number;
	}

	public void setNumber(int number) {
		this.number = number;
	}

	public int getNumber() {
		return number;
	}

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

The toString() method returns the value of number variable which can be used in console displaying later. Now, since we make a gene, we now make a chromosome. A chromosome is simply a sequence of genes. I will name a class as Individual.java because I am gonna name the array variable to chromosome ( array of gene ) . The idea is that given a chromosome size, we should be able to initialize an Individual with random sequence of genes. The code looks like:

package np.com.bsubash.ga.binary;

/**
 * @author subash
 * @since Mar 27, 2021
 */
public class Individual {
	private Gene[] chromosome;
	private double fitness = -1;

	public Individual(Gene[] chromosome) {
		this.chromosome = chromosome;
	}

	public Individual(int chromosomeSize) {
		this.chromosome = new Gene[chromosomeSize];
		this.initRandomIndividual();
	}

	public Gene[] getChromosome() {
		return this.chromosome;
	}

	public void setFitness(double fitness) {
		this.fitness = fitness;
	}

	public double getFitness() {
		return fitness;
	}

	public void setGene(int index, Gene gene) {
		this.chromosome[index] = gene;
	}

	public Gene getGene(int index) {
		return this.chromosome[index];
	}

	private void initRandomIndividual() {
		if (this.chromosome == null)
			throw new NullPointerException("Chromosome is null !");
		for (int i = 0; i < this.chromosome.length; i++) {
			double rand = Math.random();
			this.setGene(i, new Gene(rand > 0.5 ? 1 : 0));
		}
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (Gene gene : this.chromosome) {
			sb.append(gene.toString());
		}
		return sb.toString();
	}
}

Also, the class has a variable named fitness which will be used to evaluate between other individuals. There is also a method the initialize an individual with random genes. The toString() method returns the string of all genes present in individual’s chromosome.

Now, let’s make a population class. Population is simply a collection of solutions or individuals . It will have limited, fixed number of individuals in it with varying fitness scores. Among all, one with highest fitness is the most acceptable(not the best) solution. The code for Population.java looks like:

package np.com.bsubash.ga.binary;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * @author subash
 * @since Mar 27, 2021
 */
public class Population {
	private Individual[] individuals;
	private double fitness = -1;

	public Population(int populationSize) {
		this.individuals = new Individual[populationSize];
	}

	public Population(int populationSize, int chromosomeSize) {
		this.individuals = new Individual[populationSize];

		for (int i = 0; i < populationSize; i++) {
			this.individuals[i] = new Individual(chromosomeSize);
		}
	}

	public Individual[] getIndividuals() {
		return individuals;
	}

	public double getFitness() {
		return fitness;
	}

	public void setFitness(double fitness) {
		this.fitness = fitness;
	}

	public Individual getIndividual(int index) {
		return this.individuals[index];
	}

	public void setIndividual(int index, Individual individual) {
		this.individuals[index] = individual;
	}

	public Individual getFittestIndividual(int offset) {
		// sort the population so that first individual has highest fitness score
		Arrays.sort(this.individuals, new Comparator<Individual>() {
			@Override
			public int compare(Individual a, Individual b) {
				if (a.getFitness() < b.getFitness())
					return 1;
				if (a.getFitness() > b.getFitness())
					return -1;
				return 0;
			}
		});
		return this.individuals[offset];
	}

	public void sufflePopulation() {
		List<Individual> list = Arrays.<Individual>asList(this.individuals);
		Collections.shuffle(list);
		list.toArray(this.individuals);
	}

}

The getFittestIndividual(int offset) method returns an individual at given offset in a population, provided the population is sorted in such a way that the first individual has the highest fitness. The sufflePopulation() simply shuffles the individuals in a population.

We have now all the model classes required for the algorithm. Next thing we need is a class( more of a wrapper class ) which will be used to perform genetic algorithm on a problem. This Algorithm.java class will have a variable to set population size, mutation rate, crossover rate and elitism count. We also need the methods for crossover and mutation. The class looks like:

package np.com.bsubash.ga.binary;

/**
 * @author subash
 * @since Mar 28, 2021
 */
public class Algorithm {
	private int popolationSize;
	private double mutationRate, crossoverRate;
	private int elitismCount;

	public Algorithm(int populationSize, double mutationRate, double crossoverRate, int elitismCount) {
		this.popolationSize = populationSize;
		this.mutationRate = mutationRate;
		this.crossoverRate = crossoverRate;
		this.elitismCount = elitismCount;
	}

	public Population initPopulation(int chromosomeLength) {
		return new Population(this.popolationSize, chromosomeLength);
	}

	public void evaluateFitness(Individual individual) {
		int correct = 0;
		for (int i = 0; i < individual.getChromosome().length; i++) {
			if (individual.getGene(i).getNumber() == 1) {
				correct++;
			}
		}
		double fitness = (double) correct / individual.getChromosome().length;
		individual.setFitness(fitness);
	}

	public void evaluateFitness(Population population) {
		double fitness = 0.0;
		for (Individual individual : population.getIndividuals()) {
			evaluateFitness(individual);
			fitness += individual.getFitness();
		}
		population.setFitness(fitness);
	}

	public boolean solutionFound(Population population) {
		return population.getFittestIndividual(0).getFitness() == 1;
	}

	public Individual selectParentUsingRouletteWheel(Population population) {
		Individual[] individuals = population.getIndividuals();
		double wheelPosition = population.getFitness() * Math.random();
		double wheel = 0;
		for (Individual individual : individuals) {
			wheel += individual.getFitness();
			if (wheel >= wheelPosition) {
				return individual;
			}
		}
		return individuals[individuals.length - 1];
	}

	public Population crossover(Population population) {
		Population newPopulation = new Population(population.getIndividuals().length);
		for (int i = 0; i < population.getIndividuals().length; i++) {
			Individual firstParent = population.getFittestIndividual(i);
			// do crossover if not elite
			if (crossoverRate > Math.random() && i > elitismCount) {
				// perform crossover
				Individual secondParent = selectParentUsingRouletteWheel(population);
				Individual offspring = new Individual(firstParent.getChromosome().length);

				for (int j = 0; j < firstParent.getChromosome().length; j++) {
					offspring.setGene(j, Math.random() < 0.5 ? firstParent.getGene(j) : secondParent.getGene(j));
				}
				newPopulation.setIndividual(i, offspring);
			} else {
				// no crossover
				newPopulation.setIndividual(i, firstParent);
			}
		}
		return newPopulation;
	}

	public Population mutate(Population population) {
		Population newPopulation = new Population(population.getIndividuals().length);
		for (int i = 0; i < population.getIndividuals().length; i++) {
			Individual individual = population.getFittestIndividual(i);
			for (int j = 0; j < individual.getChromosome().length; j++) {
				// skip for elite individual
				if (i > elitismCount && Math.random() > mutationRate) {
					Gene mutatedGene = new Gene(1);
					if (individual.getGene(j).getNumber() == 1) {
						mutatedGene.setNumber(0);
					}
					individual.setGene(j, mutatedGene);
				}
			}
			newPopulation.setIndividual(i, individual);
		}
		return newPopulation;
	}
}

The evaluateFitness(Individual individual) calculates and sets the fitness value to corresponding individual and the evaluateFitness(Population population) calculates and sets the fitness value to the whole population. The solutionFound() method returns true if the population has fitness 1 and false otherwise. The parent selection for crossover is done by roulette wheel method ( you can use any method you like, actually depends on what problem you are working on ) . The suitable parent is selected and returned by the method selectParentByRouletteWheel(Population population) . The method crossover(Population population) performs the crossover on old population and returns new population whereas the method mutation(Population population) performs mutation on old population and returns new population. The returned new populations replace the old population in their respective step.

Hurray ! We completed writing the binary genetic algorithm. What’s left is to test the algorithm. Let’s create a class Main.java and put the following code.

package np.com.bsubash.ga.binary;

/**
 * @author subash
 * @since Mar 28, 2021
 */
public class Main {

	public static void main(String[] args) {
		Algorithm alg = new Algorithm(100, 0.001, 0.95, 2);
		Population population = alg.initPopulation(25);
		alg.evaluateFitness(population);
		int generation = 1;

		while (!alg.solutionFound(population)) {
			// evaluate fitness
			alg.evaluateFitness(population);
			
			System.out.println(generation + ": " + population.getFittestIndividual(0) + ": "
					+ population.getFittestIndividual(0).getFitness());
			
			// crossover
			population = alg.crossover(population);
			// mutation
			population = alg.mutate(population);

			generation++;
		}

		System.out.println("-------------------------------");
		System.out.printf("FOUND SOLUTION IN %d GENERATIONS !\n", generation);
		System.out.println("SOLUTION: " + population.getFittestIndividual(0).toString() + ": "
				+ population.getFittestIndividual(0).getFitness());
	}
}

Here, we are using the population size of 100, chromosome length 25, crossover rate 0.01, mutation rate 0.95 and elitism count 2. You can change the values as fits in your problem. While running, you can see the console logs of each generation with respective fitness values. The loop breaks upon finding the solution the best solution with fitness 1, That is individual with all genes ones ( 111111111111111111111111 ).

You can find the whole source code on github here => SOURCE CODE


You May Also Like