-3
package chapter2;

public class AllOnesGA {

    public static void main(String[] args) {
        //Cria instância da classe "GeneticAlgorithm"
        GeneticAlgorithm ga = new GeneticAlgorithm(100, 0.01, 0.95, 0);

        //Inicializa a população
        Population population = new Population(50);

        ga.evalPopulation(population);
        int generation = 1;

        while (ga.isTerminationConditionMet(population) == false) {
            //Mostra o fittest indivíduo da população
            System.out.println("Best solution: " + population.getFittest(0).toString());

            //Aplicar crossover
            population = ga.crossoverPopulation(population);

            //Aplicar mutação
            population = ga.mutatePopualtion(population);

            //Avaliar a população
            ga.evalPopulation(population);

            //Incrementa mais uma geração
            generation++;
        }

        System.out.println("Found solution in " + generation + " generations");
        System.out.println("Best solution: " + population.getFittest(0).toString());
    }
}
//Nova Classe

public class GeneticAlgorithm {
    private int populationSize;
    private double crossoverRate;
    private double mutationRate;
    private int elitismCount;

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

    public Population initPopulation(int chromosomeLenght) {
        Population population = new Population(this.populationSize, chromosomeLenght);
        return population;
    }

    public double calcFitness (Individual individual) {
        //Rastreia o número de genes corretos
        int correctGenes = 0;

        //Loop sobre cada gene
        for (int geneIndex = 0; geneIndex < individual.getChromosomeLenght(); geneIndex++) {
            //Adiciona um ponto de fitness para cada "1" encontrado
            if (individual.getGene(geneIndex) == 1) {
                correctGenes += 1;
            }
        }
        //Calculo de fitness
        double fitness = (double) correctGenes / individual.getChromosomeLenght();

        //Armazena fitness
        individual.setFitness(fitness);

        return fitness;
    }

    public void evalPopulation(Population population) {
        double populationFitness = 0;

        for (Individual individual : population.getIndividuals()) {
            populationFitness += calcFitness(individual);
        }

        population.setPopulationFitness(populationFitness);
    }

    public boolean isTerminationConditionMet(Population population) {
        for (Individual individual : population.getIndividuals()) {
            if (individual.getFitness() == 1) {
                return true;
            }
        }
        return false;
    }

    public Individual selectParent(Population population) {
        //Crossover aplicado com o método "Roleta de Cassino"
        //Seleciona os indivíduos
        Individual individuals[] = population.getIndividuals();

        //Gira a roleta
        double populationFitness = population.getPopulationFitness();
        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;
            }
        }

        return individuals[population.size() - 1];       
    }

    public Population crossoverPopulation(Population population) {
        //Cria nova população
        Population newPopulation = new Population(population.size());

        //Loop sobre população atual por fitness
        for (int populationIndex = 0; populationIndex < population.size(); populationIndex++) {
            Individual parent1 = population.getFittest(populationIndex);

            //Aplicar crossover a este indivíduo??
            if (this.crossoverRate > Math.random() && populationIndex > this.elitismCount) {
                //Inicializa offspring
                Individual offspring = new Individual(parent1.getChromosomeLenght());

                //Encontra o 2 segundo par
                Individual parent2 = selectParent(population);

                //Loop sobre o genoma
                for (int geneIndex = 0; geneIndex < parent1.getChromosomeLenght(); geneIndex ++) {
                    //Usa metade dos genes do par 1 e metade dos genes do par 2
                    if (0.5 > Math.random()) {
                        offspring.setGene(geneIndex, parent1.getGene(geneIndex));
                    } else {
                        offspring.setGene(geneIndex, parent2.getGene(geneIndex));
                    }
                }
                //Adiciona offspring a nova população
                newPopulation.setIndividual(populationIndex, offspring);
            } else {
                //Adiciona individuo a nova opulação sem aplicar crossover
                newPopulation.setIndividual(populationIndex, parent1);
            }
        }
        return newPopulation;
    }

    public Population mutatePopualtion(Population population) {
        //Inicializa nova População
        Population newPopulation = new Population(this.populationSize);

        //Loop sobre população atual por fitness
        for (int populationIndex = 0; populationIndex < population.size(); populationIndex++) {
            Individual individual = population.getFittest(populationIndex);

            //Loop sobre cada gene
            for (int geneIndex = 0; geneIndex < individual.getChromosomeLenght(); geneIndex++) {
                //Pula mutação se o indivíduo for elite
                if (populationIndex >= this.elitismCount) {
                    //Esse gene precisa de mutação??
                    if (this.mutationRate > Math.random()) {
                        //Pega novo gene
                        int newGene = 1;
                        if (individual.getGene(geneIndex) == 1) {
                            newGene = 0;
                        }
                        //Mutar o gene
                        individual.setGene(geneIndex, newGene);
                    }
                }
            }
            //Adiciona individuo a nova população
            newPopulation.setIndividual(populationIndex, individual);
        }
        return newPopulation;
    }
//Nova Classe

public class Individual {
    private int[] chromosome;
    private double fitness = -1;

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

    public Individual (int chromosomeLenght) {
        this.chromosome = new int [chromosomeLenght];
        for (int gene = 0; gene < chromosomeLenght; gene ++) {
            if (0.5 < Math.random()) {
                this.setGene(gene, 1);
            } else {
                this.setGene(gene, 0);
            }
        }
    }

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

    public int getChromosomeLenght() {
        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 void setFitness(double fitness) {
        this.fitness = fitness;
    }

    public double getFitness() {
        return this.fitness;
    }

    public String toString() {
        String output = "";
        for (int gene = 0; gene < this.chromosome.length; gene++) {
            output += this.chromosome[gene];
        }
        return output;
    }    
//Nova Classe

public class Population {
    private Individual population[];
    private double populationFitness = -1;

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

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

        for (int individualCount = 0; individualCount < populationSize; individualCount++) {
            Individual individual = new Individual(chromosomeLenght);
            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 rnd = new Random();
        for (int i = population.length - 1; i > 0; i--) {
            int index = rnd.nextInt(i + 1);
            Individual a = population[index];
            population[index] = population[i];
            population[i] = a;
        }
    }

Exceção:

Exception in thread "main" java.lang.NullPointerException
        at chapter2.GeneticAlgorithm.calcFitness(GeneticAlgorithm.java:‌​27)
        at chapter2.GeneticAlgorithm.evalPopulation(GeneticAlgorithm.ja‌​va:46)
        at chapter2.AllOnesGA.main(AllOnesGA.java:12) 
C:\Users\edega\AppData\Local\NetBeans\Cache\8.2\executor-sni‌​ppets\run.xml:53: Java returned: 1
FALHA NA CONSTRUÇÃO (tempo total: 0 segundos)

Gostaria de saber o que posso fazer para corrigir este problema.

6

1 Resposta 1

4

O seu erro é porque no main, você cria um objeto do tipo Population usando o construtor que só recebe um int. Esse construtor cria o array de Individual, mas não o preenche com nada, e portanto todas as posições serão nulas.

Quando o evalPopulation é chamado nessa população vazia, o population.getIndividuals() do laço for trará esse array para ser iterado. Desta forma, no laço for do método evalPopulation, a variável individual será null, e isso será passado para calcFitness.

No método calcFitness, uma vez que o individual é null, o individual.getChromosomeLength() na condição de parada do for vai dar um NullPointerException.

Há formas bem simples e rápidas de se resolver isso, mas decidi buscar uma abordagem mais profunda. Seu código até que é razoavelmente bem escrito, mas há uns probleminhas que podem ser arrumados.

A primeira coisa que se nota é que o seu método calcFitness olha para a quantidade de 1's encontrada nos genes do indivíduo. Entretanto, algoritmos genéticos para problemas diferentes usam diferentes formas de avaliar o fitness. Assim sendo, é importante que a forma de calcular o fitness possa ser plugada e/ou definida por quem for utilizar a classe GeneticAlgorithm, assim como são os demais valores dessa classe (populationSize, crossoverRate, mutationRate e elitismCount). Logo, podemos especificar uma interface que diz o que é um cálculo de fitness:

package chapter2;

@FunctionalInterface
public interface FitnessFunction {
    public double getFitness(boolean[] chromosome);
}

Você notou o boolean[] no parâmetro do método? Pois bem, a sua classe Individual trabalha com int[]. Entretanto os ints usados são sempre 0 e 1, logo convém usar boolean[] ao invés de int[].

Parte do problema que levou você a cometer um erro que causou um NullPointerException era o de estar trabalhando com um objeto Population incompleto e não devidamente inicializado. Trabalhar com objetos em estados incompletos ou não-inicializados é uma má prática de programação, mas não se fala o suficiente sobre isso.

Uma arma contra essa classe de problemas é o princípio de que o construtor não deve apenas instanciar o objeto, mas sim devolver uma instância já devidamente inicializada e completamente preenchida.

Uma outra arma contra problemas de trabalhar com objetos inconsistentes é a imutabilidade, pois garante que o objeto assim que criado estará em um estado válido e dele não poderá sair. Caso um objeto em um estado diferente seja desejado, um novo objeto deverá ser criado. A imutabilidade é muito útil em Strings por exemplo, ao garantir que uma referência para "xyz" não possa misteriosamente e repentinamente se tornar em uma referência para "abc".

Juntando esses conceitos, vamos definir a classe Individual como uma classe imutável:

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);
    }
}

Essa classe acima merece algumas explicações, vez que algumas coisas do seu código original que nela não estavam foram parar lá dentro e além disso, a estrutura é significativamente diferente da sua classe original. O principal motivo para isso são os métodos invejosos.

Um método invejoso é um método que "queria" estar dentro de uma classe, mas está em outra. Ou seja, é um método que foi colocado na classe errada. Idealmente, um método representa uma operação realizada sobre a classe que o contém. Porém um método invejoso que "tem inveja" de uma outra classe, ao invés de representar uma operação sobre a classe que o contém, representa uma operação sobre uma outra classe.

No seu código original, praticamente tudo o que está na classe GeneticAlgorithm são métodos que queriam estar na classe Population. Já o método calcFitness queria estar na classe Individual. Os métodos crossoverPopulation e mutatePopualtion têm inveja da classe Population, mas dentro dos laços for de ambos, é possível extrair-se um trecho em cada que têm inveja de Individual. Após a extração desses trechos e a mudança deles para a classe Individual, temos os métodos cross e newMutant na classe Individual.

Outra coisa a se notar é a imutabilidade de Individual. Observe que o construtor é privado, todos os campos são final e a classe é final. Isso é para garantir que quando o objeto é instanciado, ele já terá sido completamente inicializado e não poderá ser alterado. Observe que o cálculo do fitness é feito dentro do próprio construtor, o que elimina a necessidade de você ter que chamar um método setFitness ou calcFitness no objeto posteriormente. A necessidade de que um setFitness ou calcFitness tenha que ser chamado após a conclusão da execução do construtor demonstra que o objeto não havia sido construído por inteiro e que esse método servia para terminar de construí-lo. Assim sendo, o melhor lugar para calcular o fitness é no construtor (cálculo esse delegado ao FitnessFunction).

Uma mutação (método mutate) em um Individual consiste na criação de um outro Individual com um cromossomo um pouco diferente. Um cruzamento entre dois Individuals (método cross) também cria um novo Individual sem alterar nenhum dos dois pais. Do seu construtor original que recebia um int, fiz o método randomIndividual. O fato do construtor ser privado garante que é impossível criar-se instâncias de Individual por alguma forma que não seja por meio de um desses três métodos, o que garante que as regras de criação do Individual são respeitadas.

Além disso, como efeito colateral da eliminação da inveja de métodos, a classe Individual tem menos necessidade de expôr getters ou outros métodos para serem utilizados por outras classes, e como efeito o encapsulamento é melhorado, acoplamento entre classes é reduzido e a coesão da classe é aumentada. Isso possibilitou a remoção do método getChromosome() e a redução da visibilidade do getGene de public para private.

Utilize a classe StringBuilder para criar Strings complexas. Ficar concatenando Strings dentro de um loop é uma má-prática de programação, pois cria um monte de objetos intermediários String desncessários que consomem memória e têm que ter os seus conteúdos copiados cada vez que alguma coisa for concatenada, prejudicando o desempenho. Neste ponto, o fato de StringBuilder não ser imutável é uma vantagem.

Um caso análogo a esse, onde a mutabilidade é utilizada é nos métodos randomIndividual, mutate e cross, que se aproveitam da mutabilidade dos arrays para garantir um bom desempenho e só instanciar o Individual uma única vez no final. Se não fosse assim, ou teríamos que sacrificar a imutabilidade de Individual ou teríamos que instanciar vários Individuals intermediários cada qual com um gene diferente do anterior, e tendo que copiar várias e várias vezes os cromossomos.

Por fim, o último detalhe a se notar na classe Individual, é que só precisamos de uma instância de Random. Logo, ela é mantida em uma variável private static final.

Retirando tanta coisa referente à classe GeneticAlgorithm por causa de métodos invejosos levaria a classe Population a precisar de vários dos valores que estão em GeneticAlgorithm. Para evitar criar um acoplamento forte entre essas classes, criei a classe 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;
    }
}

Esta classe não tem muito de especial sobre ela, mas é de se notar que ela é imutável. Ela representa os parâmetros com o qual o seu algoritmo genético opera: qual é a população, qual é o tamanho dos cromossomos, qual é a função de fitness, a taxa de mutação, etc.

Agora, vamos à classe 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();
    }
}

A primeira coisa a se notar aqui é que uso List<Individual> ao invés de Individual[]. Isso daí por si só já diminui a possibilidade de você ter um NullPointerException porque a lista nunca terá elementos nulos mesmo quando recém-instanciada, diferente do que ocorre com o array. Ao usar listas ao invés de array, você também passa a ter que se preocupar bem menos em rastrear o tamanho. Com listas, também há bem menos necessidade de ficar se contando e calculando posições de elementos.

A classe Population é imutável, devendo ser instanciada já com a lista definitiva de indivíduos. O método setIndividual da sua classe original foi eliminado, pois ele era usado apenas para preencher o Population recém-criado. Ou seja, o método setIndividual servia para terminar de construir o objeto que o construtor deixou incompleto, exatamente o que buscamos eliminar. O construtor também é privado e instâncias só podem ser criadas pelos métodos mutate, cross e randomPopulation, sendo que os dois primeiros se preocupam em aumentar o número da geração (o último cria a geração 1). As listas utilizadas por esses três métodos também são mutáveis enquanto estão sendo preenchidas, sendo tratadas como imutáveis quando essa lista é passada ao construtor de Population.

Além disso, o construtor de Population já ordena os indivíduos de acordo com o fitness, para que essa operação não seja mais uma etapa de construção do objeto que o construtor não fez. Com o cálculo do populationFitness, também temos novamente a mesma situação (o que fez sumir o método evalPopulation). E ainda por cima, perceba que o código para essas duas atividades (ordenar e medir o fitness da população) fica bem mais simples usando a sintaxe de lambda do Java 8. O lambda também é usado para simplificar o isTerminationConditionMet.

Quanto ao número de geração, tive a impressão de que isso era algo que tinha inveja da classe Population, e por isso coloquei aí dentro. Outro efeito da melhora do encapsulamento foi que o método getFittest agora não precisa mais do parâmetro int, apenas o indivíduo de maior fitness precisa ser acessado externamente.

Parte da sua classe AllOnesGA consistia no algoritmo genético propriamente dito, que é o algoritmo que produz tantas gerações quantas forem necessárias de populações, as avalia, faz crossover e mutações. Isso daí foi movido para a classe GeneticAlgorithm, que ficou assim:

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 que dessa classe não há nada da sua classe original. O que havia na classe original eram métodos invejosos que agora estão no lugar certo, e o que ficou aqui foi um comportamento que era invejoso por não estar aqui.

O único porém é que ele acaba contando uma geração para o crossover e uma outra para o mutate, vez que a cada iteração do while, cada um desses cria um novo Population o que implica em duas gerações por iteração do while.

Por fim, nota-se que há um parâmetro maxGenerations para evitar que o método fique preso em um loop infinito ou que uma solução demore dias, meses ou anos para sair. Ao atingir o número máximo de iterações, é retornada a última população gerada (que deve ser encabeçada pelo indivíduo com o maior fitness já encontrado).

E finalmente a sua classe 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());
    }
}

O método simpleFitness é o seu método de fitness original, que verifica se todos os genes são verdadeiros. Outros métodos de cálculo de fitness podem ser usados dependendo do problema específico no qual você vai buscar uma solução com algoritmos genéticos.

O método main também não possui muitos segredos. Ele cria os parâmetros do algoritmo genético (pode alterá-los para brincar a vontade), instancia o algoritmo genético, executa ele e mostra o resultado.

Para finalizar, lembre-se que:

  • O operador ternário é seu amigo se você souber utilizá-lo, e ele pode te eliminar aqueles ifs chatos onde o que está no bloco do if é quase igual ao que está no bloco do else, evitando duplicações de código.

  • Se você for utilizar uma expressão na forma blablabla == false, sendo blablabla uma expressão do tipo bololean, use apenas !blablabla ao invés disso. O mesmo vale para blablabla == true, basta usar simplesmente blablabla.

  • Usar blablabla ^= true; é um truque para inverter um valor do tipo boolean. Muito útil quando escrever blablabla = !blablabla fica ruim quando a expressão blablabla se transforma em uma expressão bem complexa tal como o newChromosome[geneIndex] da classe Individual. Por exemplo, newChromosome[geneIndex] ^= true; fica mais simples do que newChromosome[geneIndex] = !newChromosome[geneIndex].

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .