Your mistake is because in main, you create an object of the type Population using the constructor that only receives one int. This constructor creates the array of Individual, but does not fill it with anything, and therefore all positions will be null.
When the evalPopulation is called in this empty population, the population.getIndividuals() of the loop for will bring this array to be iterated. This way, in the loop for of the method evalPopulation, the variable individual will be null, and this will be passed on to calcFitness.
In the method calcFitness, since the individual is null, the individual.getChromosomeLength() in the stopping condition of the for will give a NullPointerException.
There are very simple and quick ways to solve this, but I decided to look for a deeper approach. Your code until it is reasonably well written, but there are a few little problems that can be arranged.
The first thing you notice is that your method calcFitness looks at the amount of 1’s found in the individual’s genes. However, genetic algorithms for different problems use different ways to evaluate fitness. Therefore, it is important that the way to calculate the fitness can be plugged in and/or defined by those using the class GeneticAlgorithm, as are the other values of this class (populationSize, crossoverRate, mutationRate and elitismCount). So we can specify an interface that says what a fitness calculation is:
package chapter2;
@FunctionalInterface
public interface FitnessFunction {
public double getFitness(boolean[] chromosome);
}
Did you notice the boolean[] in the method parameter? Well, your class Individual works with int[]. Meanwhile the intused s are always 0 and 1, so it is convenient to use boolean[] instead of int[].
Part of the problem that caused you to make a mistake that caused a NullPointerException was to be working with an object Population incomplete and not properly initialized. Working with objects in incomplete or uninitialized states is a bad programming practice, but not enough is said about it.
A weapon against this class of problems is the principle that the constructor should not only instantiate the object, but return an already properly initialized and fully filled instance.
Another weapon against the problems of working with inconsistent objects is immutability, because it ensures that the object created will be in a valid state and cannot leave it. If an object in a different state is desired, a new object must be created. Immutability is very useful in Strings, for example, by ensuring that a reference to "xyz" cannot mysteriously and suddenly become a reference to "abc".
Putting these concepts together, let’s define the class Individual as an immutable class:
package chapter2;
import java.util.Random;
public final class Individual {
private static final Random RND = new Random();
private final boolean[] chromosome;
private final double fitness;
private final FitnessFunction fitnessCalc;
private Individual(FitnessFunction fitnessCalc, boolean[] chromosome) {
this.chromosome = chromosome;
this.fitnessCalc = fitnessCalc;
this.fitness = fitnessCalc.getFitness(chromosome);
}
public static Individual randomIndividual(FitnessFunction fitnessCalc, int chromosomeLenght) {
boolean[] chromosome = new boolean[chromosomeLenght];
for (int gene = 0; gene < chromosomeLenght; gene++) {
chromosome[gene] = RND.nextInt(2) == 0;
}
return new Individual(fitnessCalc, chromosome);
}
public static Individual cross(Individual parent1, Individual parent2) {
boolean[] chromosome = new boolean[parent1.getChromosomeLenght()];
for (int geneIndex = 0; geneIndex < chromosome.length; geneIndex++) {
//Usa metade dos genes do parent1 e metade dos genes do parent2.
Individual parent = RND.nextInt(2) == 0 ? parent1 : parent2;
chromosome[geneIndex] = parent.getGene(geneIndex);
}
return new Individual(parent1.fitnessCalc, chromosome);
}
public Individual newMutant(double mutationRate) {
// Cria os cromossomos do novo indivíduo inicialmente como uma cópia do cromossomo deste indivíduo.
boolean[] newChromosome = chromosome.clone();
// Percorre os cromossomos do novo indivíduo e troca alguns genes aleatoriamente, respeitando a taxa de mutação.
for (int geneIndex = 0; geneIndex < chromosome.length; geneIndex++) {
if (mutationRate > RND.nextDouble()) {
newChromosome[geneIndex] ^= true;
}
}
// Cria o novo indivíduo com o novo cromossomo mutado.
return new Individual(fitnessCalc, newChromosome);
}
private int getChromosomeLenght() {
return this.chromosome.length;
}
private boolean getGene(int offset) {
return this.chromosome[offset];
}
public double getFitness() {
return this.fitness;
}
@Override
public String toString() {
char[] c = new char[chromosome.length];
for (int geneIndex = 0; geneIndex < chromosome.length; geneIndex++) {
c[geneIndex] = chromosome[geneIndex] ? '1' : '0';
}
return new String(c);
}
}
This class above deserves some explanations, since some things of its original code that were not there were inside and besides, the structure is significantly different from its original class. The main reason for this is the envious methods.
A jealous method is a method that "wanted" to be within one class, but is in another. That is, it is a method that has been placed in the wrong class. Ideally, a method represents an operation performed on the class containing it. But a jealous method that "envies" another class, rather than representing an operation on the class that contains it, represents an operation on another class.
In its original code, virtually everything in the class GeneticAlgorithm are methods that wanted to be in class Population. Already the method calcFitness wanted to be in class Individual. The methods crossoverPopulation and mutatePopualtion are envious of class Population, but within the bonds for of both, it is possible to extract a passage in each one that is envious of Individual. After the extraction of these sections and their change to the class Individual, we have the methods cross and newMutant in class Individual.
Another thing to note is the immutability of Individual. Note that the constructor is private, all fields are final and the class is final. This is to ensure that when the object is instantiated, it has already been fully initialized and cannot be changed. Note that the fitness calculation is done within the builder itself, which eliminates the need for you to have to call a method setFitness or calcFitness on the subject. The need for a setFitness or calcFitness has to be called after completion of the constructor’s execution demonstrates that the object had not been built entirely and that this method served to finish building it. Therefore, the best place to calculate fitness is in the builder (calculation this delegate to FitnessFunction).
A mutation (method mutate) in a Individual is the creation of another Individual with a slightly different chromosome. A cross between two Individuals (method cross) also creates a new Individual without altering either parent. From its original builder it received a int, did the method randomIndividual. The fact that the constructor is private ensures that it is impossible to create instances of Individual in any way other than by means of one of these three methods, which ensures that the rules for the creation of the Individual are respected.
Moreover, as a side effect of eliminating envy of methods, the class Individual has less need to expose getters or other methods to be used by other classes, and as an effect encapsulation is improved, class coupling is reduced and the class cohesion is augmented. This made it possible to remove the method getChromosome() and reducing the visibility of getGene of public for private.
Use the class StringBuilder to create Stringcomplex s. Stay concatenating Strings within a loop is a bad programming practice as it creates a lot of intermediate objects String Mismatches that consume memory and have to have their contents copied every time something is concatenated, impairing performance. At this point, the fact of StringBuilder nay unchanging is an advantage.
A similar case where mutability is used is in the methods randomIndividual, mutate and cross, that take advantage of the mutability of arrays to ensure a good performance and only instantiate the Individual once at the end. Otherwise, or we would have to sacrifice the immutability of Individual or we would have to instantiate several Individuals intermediate each with a different gene from the previous one, and having to copy the chromosomes several times.
Finally, the last detail to notice in the class Individual, is that we only need one instance of Random. Therefore, it is maintained in a variable private static final.
Taking away so much of the class GeneticAlgorithm because of envious methods would lead to class Population need several of the values that are in GeneticAlgorithm. To avoid creating a strong coupling between these classes, I created the class GeneticAlgorithmParameters:
package chapter2;
public final class GeneticAlgorithmParameters {
private final double crossoverRate;
private final double mutationRate;
private final int elitismCount;
private final int populationSize;
private final int chromosomeLength;
private final FitnessFunction fitnessCalc;
public GeneticAlgorithmParameters(
double crossoverRate,
double mutationRate,
int elitismCount,
int populationSize,
int chromosomeLength,
FitnessFunction fitnessCalc)
{
this.crossoverRate = crossoverRate;
this.mutationRate = mutationRate;
this.elitismCount = elitismCount;
this.populationSize = populationSize;
this.chromosomeLength = chromosomeLength;
this.fitnessCalc = fitnessCalc;
}
public double getCrossoverRate() {
return crossoverRate;
}
public double getMutationRate() {
return mutationRate;
}
public int getElitismCount() {
return elitismCount;
}
public int getPopulationSize() {
return populationSize;
}
public int getChromosomeLength() {
return chromosomeLength;
}
public FitnessFunction getFitnessCalc() {
return fitnessCalc;
}
}
This class does not have much special about it, but it is to be noted that it is immutable. It represents the parameters with which your genetic algorithm operates: what is the population, what is the size of chromosomes, what is the fitness function, mutation rate, etc.
Now, let’s go to class Population:
package chapter2;
import java.util.ArrayList;
import java.util.List;
public final class Population {
private final int generationNumber;
private final GeneticAlgorithmParameters parameters;
private final List<Individual> individuals;
private final double populationFitness;
private Population(
int generationNumber,
GeneticAlgorithmParameters parameters,
List<Individual> individuals)
{
// Seta vários dos atributos desta população.
this.generationNumber = generationNumber;
this.parameters = parameters;
this.individuals = individuals;
// Ordena os indivíduos por fitness.
individuals.sort((o1, o2) -> (int) Math.signum(o2.getFitness() - o1.getFitness()));
// Calcula o fitness da população.
this.populationFitness = individuals.stream().mapToDouble(Individual::getFitness).sum();
}
public static Population randomPopulation(GeneticAlgorithmParameters parameters) {
// Cria uma lista inicialmente vazia dos indivíduos que serão gerados.
List<Individual> individuals = new ArrayList<>(parameters.getPopulationSize());
// Coloca na lista vários indivíduos gerados aleatoriamente.
for (int individualCount = 0; individualCount < parameters.getPopulationSize(); individualCount++) {
Individual individual = Individual.randomIndividual(
parameters.getFitnessCalc(),
parameters.getChromosomeLength());
individuals.add(individual);
}
// Cria uma população na geração 1 com os indivíduos gerados.
return new Population(1, parameters, individuals);
}
public Individual getFittest() {
// Retorna o primeiro indivíduo (o que tem o melhor fitness).
return individuals.get(0);
}
public int getGenerationNumber() {
return generationNumber;
}
public boolean isTerminationConditionMet() {
return individuals.stream().anyMatch(individual -> individual.getFitness() == 1);
}
private Individual selectParent() {
// Crossover aplicado com o método "Roleta de Cassino".
// Gira a roleta.
double rouletteWheelPosition = Math.random() * populationFitness;
// Encontra o indivíduo para o crossover.
double spinWheel = 0;
for (Individual individual : individuals) {
spinWheel += individual.getFitness();
if (spinWheel >= rouletteWheelPosition) {
return individual;
}
}
// Se a roleta não parou em nenhum indivíduo, escolhe o último.
return individuals.get(individuals.size() - 1);
}
public Population crossover() {
// Cria uma lista inicialmente vazia dos indivíduos que serão gerados.
List<Individual> newIndividuals = new ArrayList<>(parameters.getPopulationSize());
// Loop sobre população atual por fitness.
int populationIndex = 0;
for (Individual parent1 : individuals) {
// Aplicar crossover a este indivíduo?
if (parameters.getCrossoverRate() > Math.random() && populationIndex > parameters.getElitismCount()) {
// Encontra o par para realizar o crossover.
Individual parent2 = selectParent();
// Realiza o crossover e cria um novo indivíduo.
Individual offspring = Individual.cross(parent1, parent2);
// Adiciona o novo indivíduo gerado à lista da nova população.
newIndividuals.add(offspring);
} else {
// Adiciona o indivíduo à lista da nova população sem aplicar crossover.
newIndividuals.add(parent1);
}
}
// Cria uma nova população da geração seguinte com os indivíduos gerados.
return new Population(generationNumber + 1, parameters, newIndividuals);
}
public Population mutate() {
// Cria uma lista inicialmente vazia dos indivíduos que serão gerados.
List<Individual> newIndividuals = new ArrayList<>(parameters.getPopulationSize());
// Loop sobre população atual por fitness.
int populationIndex = 0;
for (Individual individual : individuals) {
// Faz mutação se o indivíduo não for elite.
Individual newIndividual = populationIndex >= parameters.getElitismCount()
? individual.newMutant(parameters.getMutationRate())
: individual;
// Adiciona o indivíduo a nova população.
newIndividuals.add(newIndividual);
// Conta um indivíduo a fim de podermos contar quantos
// estão na elite e quantos sofrerão mutação.
populationIndex++;
}
// Cria uma nova população da geração seguinte com os indivíduos gerados.
return new Population(generationNumber + 1, parameters, newIndividuals);
}
@Override
public String toString() {
return "Generation " + generationNumber
+ ", best fitness " + getFittest().getFitness()
+ ", individuals " + individuals.toString();
}
}
The first thing to notice here is that I use List<Individual> instead of Individual[]. That in itself already diminishes the possibility of you having one NullPointerException because the list will never have null elements even when newly instantiated, unlike what happens with the array. When using lists instead of array, you also have to worry less about tracking the size. With lists, there is also much less need to keep counting and calculating positions of elements.
The class Population is immutable and should be instantiated with the definitive list of individuals. The method setIndividual of its original class was eliminated as it was used only to fill the Population newly created. That is, the method setIndividual served to finish building the object that the constructor left incomplete, exactly what we seek to eliminate. The constructor is also private and instances can only be created by methods mutate, cross and randomPopulation, and the first two are concerned with increasing the number of generation (the last one creates generation 1). The lists used by these three methods are also mutable while being filled in, being treated as immutable when this list is passed to the constructor of Population.
In addition, the builder of Population already orders individuals according to fitness, so that this operation is no longer a construction step of the object that the builder did not do. With the calculation of populationFitness, we also have the same situation again (which made the method disappear evalPopulation). And on top of that, note that the code for these two activities (sort and measure the fitness of the population) is much simpler using Java 8’s lambda syntax. lambda is also used to simplify the isTerminationConditionMet.
As for the generation number, I had the impression that this was something I was jealous of the class Population, and so I put it in there. Another effect of improving encapsulation was that the method getFittest now no longer need the parameter int, only the highest fitness individual needs to be accessed externally.
Part of your class AllOnesGA consisted of the genetic algorithm itself, which is the algorithm that produces as many generations of populations as needed, evaluates them, crossover them and mutations. This was then moved to the class GeneticAlgorithm, that has remained so:
package chapter2;
public class GeneticAlgorithm {
private final GeneticAlgorithmParameters params;
public GeneticAlgorithm(GeneticAlgorithmParameters params) {
this.params = params;
}
public Population run(int maxGenerations) {
// Inicializa a população.
Population population = Population.randomPopulation(params);
System.out.println("Start population: " + population);
// Produz tantas gerações quanto forem necessárias até que o número
// máximo de gerações tenha sido atingido ou uma solução ideal tenha
// sido encontrada.
while (population.getGenerationNumber() < maxGenerations
&& !population.isTerminationConditionMet())
{
// Aplica o crossover (conta uma nova geração).
population = population.crossover();
System.out.println("New population: " + population);
// Aplica mutação (conta uma segunda nova geração).
population = population.mutate();
System.out.println("New population: " + population);
}
return population;
}
}
Note that in this class there is nothing of its original class. What was in the original class were envious methods that are now in the right place, and what was left here was behavior that was envious for not being here.
The only thing is that he ends up counting a generation to the crossover and another for the mutate, time with each iteration of the while, each of these creates a new Population which implies two generations for iteration of the while.
Finally, note that there is a parameter maxGenerations to avoid the method getting stuck in an infinite loop or a solution taking days, months, or years to come out. Upon reaching the maximum number of iterations, the last generated population is returned (which should be headed by the individual with the highest fitness ever found).
And finally your class AllOnesGA:
package chapter2;
public class AllOnesGA {
// Função de avaliação de fitness de teste.
// O valor máximo dela é quando todos os valores do cromossomo são verdadeiros.
// Esta função é apenas para exemplificar, pois numa aplicação real, o valor
// ótimo do cromossomo é difícil de ser determinado e a implementação desta
// função seria bem complicada e difícil de otimizar manualmente ou por uso
// de técnicas mais ortodoxas.
private static double simpleFitness(boolean[] chromosome) {
// Rastreia o número de genes corretos.
int correctGenes = 0;
// Loop sobre cada gene.
for (boolean b : chromosome) {
// Adiciona um ponto de fitness para cada true encontrado.
if (b) correctGenes++;
}
// Cálculo de fitness.
return (double) correctGenes / chromosome.length;
}
public static void main(String[] args) {
double crossoverRate = 0.05;
double mutationRate = 0.01;
int elitismCount = 3;
int populationSize = 80;
int chromosomeCount = 15;
int maxGenerations = 10000;
// Cria os parâmetros do algoritmo genético (inclusive a função de fitness).
GeneticAlgorithmParameters params = new GeneticAlgorithmParameters(
crossoverRate,
mutationRate,
elitismCount,
populationSize,
chromosomeCount,
AllOnesGA::simpleFitness);
// Cria instância do algoritmo genético com os parâmetros dados (inclusive a função de fitness).
GeneticAlgorithm ga = new GeneticAlgorithm(params);
// Executa o algoritmo genético até obter a população final.
Population finalPopulation = ga.run(maxGenerations);
// Mostra a população final.
System.out.println("Final population: " + finalPopulation);
Individual fittest = finalPopulation.getFittest();
System.out.println("Best solution: " + fittest + " - Fitness: " + fittest.getFitness());
}
}
The method simpleFitness is your original fitness method, which checks to see if all genes are true. Other fitness calculation methods can be used depending on the specific problem in which you will seek a solution with genetic algorithms.
The method main He doesn’t have a lot of secrets either. It creates the parameters of the genetic algorithm (can change them to play at will), instantiates the genetic algorithm, executes it and shows the result.
To conclude, remember that:
The ternary operator is your friend if you know how to use it, and it can eliminate those ifs boring where what is in the block of if is almost the same as what is in the block of else, avoiding duplication of code.
If you’re going to use an expression in the form blablabla == false, being blablabla an expression of the kind bololean, use only !blablabla instead. The same goes for blablabla == true, just use blablabla.
Use blablabla ^= true; is a trick to reverse a value of type boolean. Very useful when writing blablabla = !blablabla is bad when the expression blablabla becomes a very complex expression such as newChromosome[geneIndex] class Individual. For example, newChromosome[geneIndex] ^= true; is simpler than newChromosome[geneIndex] = !newChromosome[geneIndex].
I think in all classes except the first, you forgot to put the
package chapter2;and the}at the end of class.– Victor Stafusa
Reading the error line, an object is being used that has
nullon the line27, now just try to figure out why this object hasnull– Isac
I’m working on this code. Your project is really cool, it just had some silly mistakes and details to improve.
– Victor Stafusa
I already have an answer ready. I voted to reopen the question.
– Victor Stafusa
If you could pass me the corrected code, I’d be grateful!
– André Spironello
This question is being debated at the goal: https://pt.meta.stackoverflow.com/q/6237/132
– Victor Stafusa