I hope you are doing well.
I am writing a simple genetic algorithm in Java. However, I am encountering an issue with elitism. When I try to preserve the best individuals, I observe abnormal behavior in the results. Specifically, after a few iterations, the fitness values start from a higher value than the one preserved from the previous generation.
Could you please help me understand why this is happening?
As for following snippet
public class SphereFunction {
public static void main(String[] args) {
// for (int x = 0; x < 10; x++) {
// System.out.println("nn" + x + "nnn");
GeneticAlgorithm ga = new GeneticAlgorithm(100, 0.5, 0.85, 2, 5);
Population population = ga.initPopulation(40);
//Evaluate population
ga.evalPopulation(population);
//Initiate Elite population
Population elite = ga.initElitismPopulation(population);
//ga.elitismPopulation(population, elite);
int generation = 0;
while (!ga.isTerminationConditionMet(generation, 75)) {
// Print fittest individual from population
//System.out.println("Best solution: " + population.getFittest(population.size() - 1).getFitness() + ", " + population.getFittest(population.size() - 2).getFitness());
/* Preserve Elitism **/
ga.elitismPopulation(population, elite);
ga.updatePopulationWithElite(population, elite);
/* crossover **/
//population = ga.sirCrossover(population);
population = ga.sirMultiPointCrossover(population);
/* mutation **/
population = ga.sirMutate(population);
/* update population with preserve**/
//ga.updatePopulationWithElite(population, elite);
// Evaluate population
ga.evalPopulation(population);
generation++;
}
Population mergedPopulation = ga.mergePopulation(population, elite);
System.out.println("nFound solution in " + generation + " generations");
System.out.println("Best Solution for (" + population.getFittest(population.size() - 1).getFitness() + ") " + population.getIndividual(population.size() - 1));
//System.out.println("Worst Solution for (" + population.getIndividual(0).getFitness() + ") " + population.getIndividual(0));
// System.out.println("Best Solution for (" + population.getIndividual(population.size() - 1).getFitness() + ") " + population.getIndividual(population.size() - 1));
System.out.println("Best Solution for merged population (" + mergedPopulation.getFittest(mergedPopulation.size() - 1).getFitness() + ") " + mergedPopulation.getIndividual(mergedPopulation.size() - 1));
}
}
public class Individual {
private int[] chromosome;
private double fitness = -1;
public Individual(int[] chromosome) {
this.chromosome = chromosome;
}
public Individual(int chromosomeLength) {
this.chromosome = new int[chromosomeLength];
for (int gene = 0; gene < chromosomeLength; gene++) {
if (0.5 < Math.random()) {
this.setGene(gene, 1);
} else {
this.setGene(gene, 0);
}
}
}
public int[] getChromosome() {
return this.chromosome;
}
public int getChromosomeLength() {
return this.chromosome.length;
}
public void setGene(int offset, int gene) {
this.chromosome[offset] = gene;
}
public int getGene(int offset) {
return this.chromosome[offset];
}
public double getFitness() {
return this.fitness;
}
public void setFitness(double fitness) {
this.fitness = fitness;
}
public String toString() {
String output = "";
for (int gene = 0; gene < this.chromosome.length; gene++) {
output += this.chromosome[gene];
}
return output;
}
}
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
public class Population {
private Individual population[];
private double populationFitness = -1;
public Population(int populationSize) {
this.population = new Individual[populationSize];
}
public Population(int populationSize, int chromosomeLength) {
this.population = new Individual[populationSize];
for (int individualCount = 0; individualCount < populationSize; individualCount++) {
Individual individual = new Individual(chromosomeLength);
this.population[individualCount] = individual;
}
}
public Individual[] getIndividuals() {
return this.population;
}
public Individual getFittest(int offset) {
Arrays.sort(this.population, new Comparator<Individual>() {
@Override
public int compare(Individual o1, Individual o2) {
if (o1.getFitness() > o2.getFitness()) {
return -1;
} else if (o1.getFitness() < o2.getFitness()) {
return 1;
}
return 0;
}
});
return this.population[offset];
}
public void setPopulationFitness(double fitness) {
this.populationFitness = fitness;
}
public double getPopulationFitness() {
return this.populationFitness;
}
public int size() {
return this.population.length;
}
public Individual setIndividual(int offset, Individual individual) {
return population[offset] = individual;
}
public Individual getIndividual(int offset) {
return population[offset];
}
public void shuffle() {
Random ran = new Random();
for (int i = population.length - 1; i > 0; i--) {
int index = ran.nextInt(i + 1);
Individual a = population[index];
//System.out.println(Arrays.toString(a.getChromosome()) + " " + a.getFitness());
population[index] = population[i];
population[i] = a;
}
}
public void sortPopulation() {
Arrays.sort(this.population, (o1, o2) -> {
if (o1.getFitness() > o2.getFitness()) {
return -1;
} else if (o1.getFitness() < o2.getFitness()) {
return 1;
}
return 0;
});
}
public void sortAscPopulation() {
Arrays.sort(this.population, (o1, o2) -> {
if (o1.getFitness() < o2.getFitness()) {
return -1;
} else if (o1.getFitness() > o2.getFitness()) {
return 1;
}
return 0;
});
}
}
import java.util.Random;
public class GeneticAlgorithm {
private int populationSize;
private double mutationRate;
private double crossoverRate;
private int elitismCount;
protected int tournamentSize;
public GeneticAlgorithm(int populationSize, double mutationRate, double crossoverRate, int elitismCount, int tournamentSize) {
this.populationSize = populationSize;
this.mutationRate = mutationRate;
this.crossoverRate = crossoverRate;
this.elitismCount = elitismCount;
this.tournamentSize = tournamentSize;
}
public int getElitismCount() {
return elitismCount;
}
public Population initPopulation(int chromosomeLength) {
Population population = new Population(this.populationSize, chromosomeLength);
return population;
}
public double calcFitness(Individual individual) {
int numSegments = 5; // Example: Divide chromosome into 5 segments
int segmentLength = individual.getChromosomeLength() / numSegments;
double totalFitness = 0.0;
// Iterate over segments and calculate fitness for each
for (int i = 0; i < numSegments; i++) {
// Extract the segment from the chromosome
int startIndex = i * segmentLength;
int endIndex = (i + 1) * segmentLength;
String segment = individual.toString().substring(startIndex, endIndex);
// Convert the segment to an integer value
int segmentValue = Integer.parseInt(segment, 2);
// int lb = -100000000;
// int ub = 100000000;
int lb = -50;
int ub = 50;
// double scaledValue = lb + (double) (segmentValue / ((1 << segment.length()) - 1)) * (ub - lb);
double scaledValue = lb + (double) (segmentValue / Math.pow(2, segmentLength)) * (ub - lb);
// Apply fitness function to the segment (example fitness function)
double segmentFitness = Math.pow(scaledValue, 2); // Example fitness function: Square of the segment value
// Add segment fitness to total fitness
totalFitness += segmentFitness;
}
// Store total fitness in the individual
individual.setFitness(totalFitness);
return totalFitness;
}
public void evalPopulation(Population population) {
double populationFitness = 0;
// Loop over population evaluating individuals and suming population
// fitness
for (Individual individual : population.getIndividuals()) {
populationFitness += calcFitness(individual);
}
//System.out.println("populationFitness = " + populationFitness);
population.setPopulationFitness(populationFitness);
}
public boolean isTerminationConditionMet(int generationCount, int maxGeneration) {
return (generationCount >= maxGeneration);
}
// Implementing roulette wheel selection
public Individual selectParent(Population population) {
//Get individuals
Individual individuals[] = population.getIndividuals();
//Spin roulette wheel
double populationFitness = population.getPopulationFitness();
double rouletteWheelPosition = Math.random() * populationFitness;
// Find parent
double spinWheel = 0;
for (Individual individual : individuals) {
spinWheel += individual.getFitness();
if (spinWheel >= rouletteWheelPosition) {
return individual;
}
}
return individuals[population.size() - 1];
}
public Individual tournamentSelectParent(Population population) {
// Create tournament
Population tournament = new Population(this.tournamentSize);
// Add random individuals to the tournament
population.shuffle();
for (int i = 0; i < this.tournamentSize; i++) {
Individual tournamentIndividual = population.getIndividual(i);
tournament.setIndividual(i, tournamentIndividual);
}
return tournament.getFittest(tournamentSize - 1);
}
public Population sirMultiPointCrossover(Population population) {
// Create new population
Population newPopulation = new Population(population.size());
// Iterate over pairs of parents
for (int populationIndex = 0; populationIndex < population.size() / 2; populationIndex++) {
int secondPopulationIndex = populationIndex + population.size() / 2;
// Get the parents for crossover
Individual parent1 = population.getIndividual(populationIndex);
Individual parent2 = tournamentSelectParent(population);
// System.out.println("nparent1 = " + parent1.toString());
// System.out.println("parent2 = " + parent2.toString());
int chromosomeLength = parent1.getChromosomeLength();
// int swapPoint1 = (int) ((Math.random() * (chromosomeLength / 3)) + 1);
// System.out.println("swapPoint1: " + swapPoint1);
// int swapPoint2 = (int) ((Math.random() * (chromosomeLength / 2)));
// System.out.println("swapPoint2: " + swapPoint2);
/*هنا لمن ضفنا نقطة التبديل الثانية الى نقطة التبديل الاولى كام ينطيني نتائج افضل**/
int swapPoint1 = (int) ((Math.random() * (chromosomeLength / 2)) + 1);
//System.out.println("swapPoint1: " + swapPoint1);
int swapPoint2 = swapPoint1 + (int) ((Math.random() * (chromosomeLength / 2)));
//System.out.println("swapPoint2: " + swapPoint2);
// Apply crossover to this individual?
if (this.crossoverRate > Math.random()) {
Individual offspring1 = new Individual(parent1.getChromosomeLength());
Individual offspring2 = new Individual(parent1.getChromosomeLength());
// Loop over genome
for (int geneIndex = 0; geneIndex < parent1.getChromosomeLength(); geneIndex++) {
// Use half of parent1's genes and half of parent2's genes
if (geneIndex < swapPoint1) {
//System.out.println("if geneIndex = " + geneIndex);
offspring1.setGene(geneIndex, parent1.getGene(geneIndex));
//System.out.print(offspring1.getGene(geneIndex));
offspring2.setGene(geneIndex, parent2.getGene(geneIndex));
//System.out.print("parent2.getGene = ");
} else if (geneIndex < swapPoint2) {
// if (geneIndex == swapPoint1) {
// System.out.print("**");
// }
offspring1.setGene(geneIndex, parent2.getGene(geneIndex));
//System.out.print(offspring1.getGene(geneIndex));
offspring2.setGene(geneIndex, parent1.getGene(geneIndex));
} else {
// if (geneIndex == swapPoint2) {
// System.out.print("**");
// }
//System.out.println("else geneIndex = " + geneIndex);
offspring1.setGene(geneIndex, parent1.getGene(geneIndex));
//System.out.print(offspring1.getGene(geneIndex));
offspring2.setGene(geneIndex, parent2.getGene(geneIndex));
}
}
// Add offspring to new population
newPopulation.setIndividual(populationIndex, offspring1);
newPopulation.setIndividual(secondPopulationIndex, offspring2);
} else {
// Add individual to new population without applying crossover
newPopulation.setIndividual(populationIndex, parent1);
newPopulation.setIndividual(secondPopulationIndex, parent2);
}
}
return newPopulation;
}
public Population sirMutate(Population population) {
// Initialize new population
Population newPopulation = new Population(this.populationSize);
//Loop over current population
for (int populationIndex = 0; populationIndex < population.size(); populationIndex++) {
Individual individual = population.getIndividual(populationIndex);
for (int geneIndex = 0; geneIndex < individual.getChromosomeLength(); geneIndex++) {
//Does this gene need mutation?
if (this.mutationRate > Math.random()) {
// Get new gene
int newGene = 1;
if (individual.getGene(geneIndex) == 1) {
newGene = 0;
}
//Mutate gene
individual.setGene(geneIndex, newGene);
}
}
//Add individual to population
newPopulation.setIndividual(populationIndex, individual);
}
//Return mutated population
return newPopulation;
}
public Population initElitismPopulation(Population population) {
// Create elitismPopulation
Population elitismPopulation = new Population(this.elitismCount);
// // Add the best individuals to the elitismPopulation
//population.sortAscPopulation();
for (int i = 0; i < this.elitismCount; i++) {
Individual elitismIndividual = population.getIndividual(i);
elitismPopulation.setIndividual(i, elitismIndividual);
}
return elitismPopulation;
}
public Population elitismPopulation(Population population, Population eliti) {
System.out.println("nn)*************************************");
for (Individual individual : eliti.getIndividuals()) {
System.out.println("Elite Individual: " + individual + ", Fitness: " + individual.getFitness());
}
System.out.println("*************************************");
// Iterate through each individual in the population
for (Individual individual : population.getIndividuals()) {
double fitness = individual.getFitness();
double bestFitness = eliti.getIndividual(0).getFitness();
double secondBestFitness = eliti.getIndividual(1).getFitness();
// Compare the fitness of the current individual with the elite individuals
if (fitness < bestFitness) {
eliti.setIndividual(1, eliti.getIndividual(0));
eliti.setIndividual(0, individual);
bestFitness = fitness;
secondBestFitness = eliti.getIndividual(1).getFitness();
System.out.println("Updated elites: [" + eliti.getIndividual(0).getFitness() + ", " + eliti.getIndividual(1).getFitness() + "]");
} else if (fitness < secondBestFitness && fitness != bestFitness) {
eliti.setIndividual(1, individual);
secondBestFitness = fitness;
System.out.println("Updated second best elite: " + eliti.getIndividual(1).getFitness());
}
}
System.out.println("Final elites:");
for (Individual individual : eliti.getIndividuals()) {
System.out.println("Elite Individual: " + individual + ", Fitness: " + individual.getFitness());
}
System.out.println("*************************************");
return eliti;
}
// public Population elitismPopulation(Population population, Population eliti) {
//
// System.out.println("*************************************");
// for (Individual individual : eliti.getIndividuals()) {
// System.out.println("Elite Individual: " + individual + ", Fitness: " + individual.getFitness());
// }
// System.out.println("*************************************");
// // Iterate through each individual in the population
// for (Individual individual : population.getIndividuals()) {
// double fitness = individual.getFitness();
// double bestFitness = eliti.getIndividual(0).getFitness();
// double secondBestFitness = eliti.getIndividual(1).getFitness();
//
// // Compare the fitness of the current individual with the elite individuals
// if (fitness < bestFitness) {
// System.out.println("Hello");
// // If the fitness of the current individual is lower than the fittest elite individual,
// // shift the elite individuals and make the current individual the fittest
// eliti.setIndividual(1, eliti.getIndividual(0));
// eliti.setIndividual(0, individual);
// System.out.println("Updated elites: [" + individual.getFitness() + ", " + bestFitness + "]");
// } else if (fitness < secondBestFitness && fitness != bestFitness) {
// eliti.setIndividual(1, individual);
// System.out.println("Updated second best elite: " + individual.getFitness());
// }
// }
// return eliti;
// }
public void updatePopulationWithElite(Population population, Population elitism) {
// Random rand = new Random();
//
// for (int i = 0; i < elitism.size(); i++) {
// Individual individual = elitism.getIndividual(i);
// int index = rand.nextInt(population.size());
// population.setIndividual(index, individual);
//
// }
}
public Population elitismPopulation2(Population population, Population eliti) {
// Iterate through each individual in the population
for (Individual individual : population.getIndividuals()) {
// Compare the fitness of the current individual with the elite individuals
if (individual.getFitness() < eliti.getIndividual(0).getFitness()) {
// If the fitness of the current individual is lower than the fittest elite individual,
// shift the elite individuals and make the current individual the fittest
eliti.setIndividual(2, eliti.getIndividual(1));
eliti.setIndividual(1, eliti.getIndividual(0));
eliti.setIndividual(0, individual);
} else if (individual.getFitness() < eliti.getIndividual(1).getFitness() && individual.getFitness() != eliti.getIndividual(0).getFitness()) {
// If the fitness of the current individual is lower than the second fittest elite individual,
// replace the second fittest with the current individual
eliti.setIndividual(2, eliti.getIndividual(1));
eliti.setIndividual(1, eliti.getIndividual(0));
} else if (individual.getFitness() < eliti.getIndividual(2).getFitness() && individual.getFitness() != eliti.getIndividual(0).getFitness() && individual.getFitness() != eliti.getIndividual(1).getFitness()) {
// If the fitness of the current individual is lower than the second fittest elite individual,
// replace the second fittest with the current individual
eliti.setIndividual(2, individual);
}
}
// Print the updated elite individuals
// for (Individual individual : eliti.getIndividuals()) {
// System.out.println("Elite Individual: " + individual + ", Fitness: " + individual.getFitness());
// }
return eliti;
}
public Population mergePopulation(Population population, Population eliti) {
int sizeOfNewPopulation = this.elitismCount + this.populationSize;
Population mergedPopulation = new Population(sizeOfNewPopulation);
for (int i = 0; i < this.populationSize; i++) {
Individual individual = population.getIndividual(i);
mergedPopulation.setIndividual(i, individual);
}
int j = 0;
for (int i = this.populationSize; i < sizeOfNewPopulation; i++) {
Individual individual = eliti.getIndividual(j);
mergedPopulation.setIndividual(i, individual);
j++;
}
return mergedPopulation;
}
}
I have tried to trace the code but there is one bug where my data get overflow by someting I don’t know
New contributor
Sermad SAAD is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.