This project is a Java implementation of a Genetic Algorithm, a stochastic optimization algorithm inspired by natural selection and genetics.
The idea behind the Genetic Algorithm is to find the best solution to a problem by mimicking the process of natural selection and genetics. The algorithm starts with a population of individuals, each one representing a possible solution to the problem. Each individual is evaluated and assigned a fitness score, which represents how good the solution is. The individuals with the best fitness scores are selected to reproduce, and the offspring of the reproduction process will be the new population. The process is repeated until a solution is found or a maximum number of generations is reached.
In our case an individual is a string of characters, and the problem is to find a string that matches a given target string. The fitness score of an individual is calculated by counting the number of characters that didn't match the target string. The lower the fitness score, the better the solution. For example, if the target string is Hello World! and the individual is Hello World?, the fitness score will be 1, because the ? character doesn't match the ! character.
- The corresponding Java code is:
public class Individual {
// Chromosome
private List<Character> genes = new ArrayList<>();
// Fitness score
private double fitness;
public void calculateFitness(String target) {
// Initialize fitness to chromosome length
fitness = genes.size();
for(int i = 0; i < genes.size(); i++)
if(genes.get(i).equals(target.charAt(i)))
fitness -= 1;
}
}The selection is the process of choosing the individuals that will reproduce. The individuals with the best fitness scores have a higher chance of being selected, but the individuals with the worst fitness scores also have a chance of being selected. This is done to avoid the algorithm getting stuck in a local minimum.
In our case, the size of the population is fixed, so the selection process consists of sorting the individuals by their fitness scores and keeping the fittest individuals. The fittest individuals will be the parents of the next generation.
- The corresponding Java code is:
public class Population {
private final int populationInitSize;
private List<Individual> individuals = new ArrayList<>();
private Individual firstFittest;
private Individual secondFittest;
public void selection(){
Collections.sort(individuals);
// Keep populationSize fittest individuals
individuals = individuals.subList(0, populationInitSize);
firstFittest = individuals.get(0);
secondFittest = individuals.get(1);
}
}The crossover is the process of creating the offspring of the reproduction process. The offspring will inherit some of the characteristics of their parents. In our case, the offspring will inherit some of the characters of their parents. The crossover is done by choosing a random crossover point and swapping the characters of the parents after that point. For example, if the parents are Hello World! and Hello World?, and the crossover point is 6, the offspring will be Hello World? and Hello World!.
- The corresponding Java code is:
public void crossover(){
// Generate a random crossover point
Random random = new Random();
int crossoverPoint = random.nextInt(individuals.get(0).getGenes().size());
// Create new individuals to store new individuals
Individual individual1 = new Individual(target.length());
Individual individual2 = new Individual(target.length());
System.out.println("Crossover point: " + crossoverPoint);
// Swap first half of genes
for(int i = 0; i <= crossoverPoint; i++){
individual1.getGenes().set(i, secondFittest.getGenes().get(i));
individual2.getGenes().set(i, firstFittest.getGenes().get(i));
}
// Initialize second half of genes
for(int i = crossoverPoint + 1; i < individual1.getGenes().size(); i++){
individual1.getGenes().set(i, firstFittest.getGenes().get(i));
individual2.getGenes().set(i, secondFittest.getGenes().get(i));
}
// Calculate fitness of new individuals
individual1.calculateFitness(target);
individual2.calculateFitness(target);
// Add new individuals to the population
individuals.add(individual1);
individuals.add(individual2);
}The mutation is the process of changing some characteristics of the individuals. There are multiple ways of doing this. In our case, the mutation is done by randomly changing a character of the individual. For example, if the individual is Hello World!, and the mutation point is 6, the individual may become Hello World?.
The mutation is probabilistic, which means that there is a chance that the individual won't be mutated.
- The corresponding Java code of mutation is:
public void mutation(double mutationRate, int mutationType){
// mutationRate is a value between 0 and 1
// It represents the probability of performing mutation on an individual
ArrayList<Individual> newIndividuals = new ArrayList<>();
if(new Random().nextDouble(1) <= mutationRate){
for(Individual individual : individuals) {
if (mutationType == Population.RANDOM_MUTATION)
mutationType = new Random().nextInt(Population.RANDOM_MUTATION);
switch (mutationType) {
case Population.INSERTION_MUTATION:
newIndividuals.add(individual.insertionMutation());
break;
case Population.SWAP_MUTATION:
newIndividuals.add(individual.swapMutation());
break;
case Population.INVERSION_MUTATION:
newIndividuals.add(individual.inversionMutation());
break;
default:
System.out.println("Invalid mutation type");
}
}
}
individuals.addAll(newIndividuals);
}- Mutation by insertion: a random character is inserted in a random position of the individual.
public Individual insertionMutation() {
Random random = new Random();
int nbrGenesInserted = random.nextInt(genes.size());
Individual newIndividual = new Individual(genes.size());
newIndividual.setGenes(new ArrayList<>(genes));
random.ints(nbrGenesInserted, 0, newIndividual.genes.size()).forEach(index -> {
char gnome = CHARACTERS.charAt(random.nextInt(CHARACTERS.length()));
newIndividual.genes.set(index, gnome);
});
return newIndividual;
}- Mutation by swapping: two random characters are swapped.
public Individual swapMutation() {
int firstIndex = new Random().nextInt(genes.size());
int secondIndex = new Random().nextInt(genes.size());
Individual newIndividual = new Individual(genes.size());
newIndividual.genes = new ArrayList<>(genes);
newIndividual.genes.set(firstIndex, genes.get(secondIndex));
newIndividual.genes.set(secondIndex, genes.get(firstIndex));
return newIndividual;
}- Mutation by inversion: a random substring is inverted.
public Individual inversionMutation() {
// Generate two random indices
int firstIndex = new Random().nextInt(genes.size());
int secondIndex = new Random().nextInt(genes.size());
// Create a new individual and copy the genes
Individual newIndividual = new Individual(genes.size());
newIndividual.genes = new ArrayList<>(genes);
if(firstIndex > secondIndex){
int temp = firstIndex;
firstIndex = secondIndex;
secondIndex = temp;
}
// Reverse the genes between the two indices
ArrayList<Character> subList = new ArrayList<>(newIndividual.genes.subList(firstIndex, secondIndex));
Collections.reverse(subList);
newIndividual.genes.subList(firstIndex, secondIndex).clear();
newIndividual.genes.addAll(firstIndex, subList);
return newIndividual;
}public class AGApp {
private static final int MAX_GENERATIONS = 5000;
private static final int POPULATION_SIZE = 100;
private static final String TARGET = "Hello World!";
public static void main(String[] args) {
// Create an initial population
Population population = new Population(POPULATION_SIZE, TARGET);
population.calculateIndFitness();
population.selection();
// Perform evolution
System.out.println("Evolution in progress...");
for (int i = 0; i < MAX_GENERATIONS && population.getFirstFittest().getFitness() != 0; i++) {
population.calculateIndFitness();
population.selection();
population.crossover();
// 0.5 of chance that the mutation will be performed
population.mutation(0.5, Population.INSERTION_MUTATION);
// Display fitness of the fittest individual
System.out.println("Generation: " + (i + 1) + " (Fittest: " + population.getFirstFittest().getFitness() + ") Chromosome: " + population.getFirstFittest().getGenes().toString());
}
// Get first fittest individual
System.out.println("First fittest individual (Fitness: " + population.getFirstFittest().getFitness() + "): " + population.getFirstFittest().getGenes().toString());
}
}