Basic concepts and implementation of genetic algorithms (with Java implementation examples)

As shown in the figure above (left), when the genetic algorithm is used, an individual consists of multiple chromosomes, and each chromosome consists of multiple genes. The figure above (right) shows how chromosomes are divided and combined.

The concept of natural selection

The process of natural selection starts with selecting the individuals in the population that are best adapted to the environment. The offspring inherit the characteristics of their parents, and these characteristics will be added to the next generation. If the parents have better fitness, then their offspring will be more likely to survive. This process of natural selection is carried out iteratively, and eventually, we will get a generation consisting of the individuals that are best adapted to the environment.

This concept can be applied to search problems. We consider many solutions to a problem and search for the best one.

The genetic algorithm consists of the following five steps:

1. initialization
2. Individual evaluation (calculating fitness function)
3. Select Operation
4. Crossover operation
5. Mutation Operation

initialization

The process starts with a set of individuals in the population, each of which is a candidate solution to the problem to be solved.

Individuals are characterized by a set of parameters (variables) called genes, which are strung together to form chromosomes (the solution to the problem).

In genetic algorithms, the genome of a single individual is presented as a string, which can usually be encoded using binary (a string of 1s and 0s), i.e., a binary string represents a chromosome string. Therefore, we can say that we encode the characteristics of the gene string or candidate solution in the chromosome.

Populations, chromosomes, and genes

Individual evaluation (calculating fitness function)

Individual evaluation uses the fitness function to evaluate the individual's fitness for the environment (the ability to compete with other individuals). Each individual has a fitness score, and the likelihood of the individual being selected for reproduction depends on its fitness score. The larger the fitness function value, the higher the quality of the solution. The fitness function is the driving force of the evolution of the genetic algorithm and the only criterion for natural selection. Its design should be combined with the requirements of the problem itself.

Select Operation

The purpose of the selection operation is to select the individuals with the best fitness and have them pass on their genes to the next generation. Based on their fitness scores, we select multiple pairs of better individuals (parents). Individuals with high fitness are more likely to be selected for reproduction, that is, to pass on the genes of better parents to the next generation.

Crossover operation

Crossover is the most important phase in the genetic algorithm. For each pair of parents, there is a randomly selected crossover point for the genes.

For example, the intersection point in the following figure is 3.

The offspring are produced by the exchange of genes between the parents before the crossover point.

Genes are exchanged between parents, and the resulting new offspring are then added to the population.

Mutation Operation

In some of the new offspring formed, some of their genes may be affected by low-probability mutation factors. This means that some bits in the binary bit string may flip.

Before and after mutation operation

Mutation operations can be used to maintain diversity within the population and prevent premature convergence.

termination

The algorithm terminates when the population converges (no offspring are produced within the population that are significantly different from the previous generation). In other words, the genetic algorithm provides a set of solutions to the problem.
Case Implementation

The size of the population is constant. When a new generation is formed, the individuals with the worst fitness die to make room for the next generation. The sequence of these stages is repeated over and over again to produce a new generation that is better than the previous one.

Pseudocode for this iterative process:

START
 Generate the initial population
 Compute fitness
 REPEAT
 Selection
 Crossover
 Mutation
 Compute fitness
 UNTIL population has converged
 STOP

Example implementation in Java

Below is a sample implementation of the genetic algorithm in Java, which can be debugged and modified at will. Given a set of five genes, each of which can hold a binary value of 0 or 1. The fitness here is the number of 1s in the genome. If there are five 1s in the genome, the individual's fitness reaches the maximum value. If there are no 1s in the genome, the individual's fitness reaches the minimum value. The genetic algorithm hopes to optimize the fitness and provide a population composed of individuals with the best fitness. Note: In this example, after the crossover and mutation operations, the individual with the best fitness is replaced by a new offspring with the best fitness.

import java.util.Random;

 /**
 *
 * @author Vijini
 */

 //Main class
 public class SimpleDemoGA {

 Population population = new Population();
 Individual fittest;
 Individual secondFittest;
 int generationCount = 0;

 public static void main(String[] args) {

 Random rn = new Random();

 SimpleDemoGA demo = new SimpleDemoGA();

 //Initialize population
 demo.population.initializePopulation(10);

 //Calculate fitness of each individual
 demo.population.calculateFitness();

 System.out.println("Generation: " + demo.generationCount + " Fittest: " + demo.population.fittest);

 //While population gets an individual with maximum fitness
 while (demo.population.fittest < 5) {
 ++demo.generationCount;

 //Do selection
 demo.selection();

 //Do crossover
 demo.crossover();

 //Do mutation under a random probability
 if (rn.nextInt()%7 < 5) {
 demo.mutation();
 }

 //Add fittest offspring to population
 demo.addFittestOffspring();

 //Calculate new fitness value
 demo.population.calculateFitness();

 System.out.println("Generation: " + demo.generationCount + " Fittest: " + demo.population.fittest);
 }

 System.out.println("\nSolution found in generation " + demo.generationCount);
 System.out.println("Fitness: "+demo.population.getFittest().fitness);
 System.out.print("Genes: ");
 for (int i = 0; i < 5; i++) {
 System.out.print(demo.population.getFittest().genes[i]);
 }

 System.out.println("");

 }

 //Selection
 void selection() {

 //Select the most fittest individual
 fittest = population.getFittest();

 //Select the second most fittest individual
 secondFittest = population.getSecondFittest();
 }

 //Crossover
 void crossover() {
 Random rn = new Random();

 //Select a random crossover point
 int crossOverPoint = rn.nextInt(population.individuals[0].geneLength);

 //Swap values ​​among parents
 for (int i = 0; i < crossOverPoint; i++) {
 int temp = fittest.genes[i];
 fittest.genes[i] = secondFittest.genes[i];
 secondFittest.genes[i] = temp;

 }

 }

 //Mutation
 void mutation() {
 Random rn = new Random();

 //Select a random mutation point
 int mutationPoint = rn.nextInt(population.individuals[0].geneLength);

 //Flip values ​​at the mutation point
 if (fittest.genes[mutationPoint] == ​​0) {
 fittest.genes[mutationPoint] = 1;
 } else {
 fittest.genes[mutationPoint] = 0;
 }

 mutationPoint = rn.nextInt(population.individuals[0].geneLength);

 if (secondFittest.genes[mutationPoint] == ​​0) {
 secondFittest.genes[mutationPoint] = 1;
 } else {
 secondFittest.genes[mutationPoint] = 0;
 }
 }

 //Get fittest offspring
 Individual getFittestOffspring() {
 if (fittest.fitness > secondFittest.fitness) {
 return fittest;
 }
 return secondFittest;
 }


 //Replace least fittest individual from most fittest offspring
 void addFittestOffspring() {

 //Update fitness values ​​of offspring
 fittest.calcFitness();
 secondFittest.calcFitness();

 //Get index of least fit individual
 int leastFittestIndex = population.getLeastFittestIndex();

 //Replace least fittest individual from most fittest offspring
 population.individuals[leastFittestIndex] = getFittestOffspring();
 }

 }


 //Individual class
 class Individual {

 int fitness = 0;
 int[] genes = new int[5];
 int geneLength = 5;

 public Individual() {
 Random rn = new Random();

 //Set genes randomly for each individual
 for (int i = 0; i < genes.length; i++) {
 genes[i] = rn.nextInt() % 2;
 }

 fitness = 0;
 }

 //Calculate fitness
 public void calcFitness() {

 fitness = 0;
 for (int i = 0; i < 5; i++) {
 if (genes[i] == 1) {
 ++fitness;
 }
 }
 }

 }

 //Population class
 class Population {

 int popSize = 10;
 Individual[] individuals = new Individual[10];
 int fittest = 0;

 //Initialize population
 public void initializePopulation(int size) {
 for (int i = 0; i < individuals.length; i++) {
 individuals[i] = new Individual();
 }
 }

 //Get the fittest individual
 public Individual getFittest() {
 int maxFit = Integer.MIN_VALUE;
 for (int i = 0; i < individuals.length; i++) {
 if (maxFit <= individuals[i].fitness) {
 maxFit = i;
 }
 }
 fittest = individuals[maxFit].fitness;
 return individuals[maxFit];
 }

 //Get the second most fittest individual
 public Individual getSecondFittest() {
 int maxFit1 = 0;
 int maxFit2 = 0;
 for (int i = 0; i < individuals.length; i++) {
 if (individuals[i].fitness > individuals[maxFit1].fitness) {
 maxFit2 = maxFit1;
 maxFit1 = i;
 } else if (individuals[i].fitness > individuals[maxFit2].fitness) {
 maxFit2 = i;
 }
 }
 return individuals[maxFit2];
 }

 //Get index of least fittest individual
 public int getLeastFittestIndex() {
 int minFit = 0;
 for (int i = 0; i < individuals.length; i++) {
 if (minFit >= individuals[i].fitness) {
 minFit = i;
 }
 }
 return minFit;
 }

 //Calculate fitness of each individual
 public void calculateFitness() {

 for (int i = 0; i < individuals.length; i++) {
 individuals[i].calcFitness();
 }
 getFittest();
 }

 }