Pergunta

Estou tentando escrever um algoritmo genético com base em técnicas que eu havia escolhido no livro "Técnicas de AI para programadores de jogos" que usam uma codificação binária e seleção proporcional de fitness (também conhecida como seleção de rodas de roleta) nos genes da população que são gerado aleatoriamente dentro do programa em uma matriz bidimensional.

Recentemente me deparei um pedaço de pseudocódigo e tentaram implementá -lo, mas encontraram alguns problemas com as especificidades do que preciso fazer. Eu verifiquei vários livros e algum código de código aberto e ainda estou lutando para progredir. Entendo que tenho que obter a soma da aptidão total da população, escolher um número aleatório entre a soma e o zero, se o número for maior que os pais para substituí -lo, mas estou lutando com a implementação dessas idéias .

Qualquer ajuda na implementação dessas idéias seria muito apreciada, pois meu Java está enferrujado.

Foi útil?

Solução

A seguir, é apresentado um contorno completo do GA. Fiz questão de ser muito detalhado para que possa ser facilmente codificado para C/Java/Python/..

/* 1. Init population */
POP_SIZE = number of individuals in the population
pop = newPop = []
for i=1 to POP_SIZE {
    pop.add( getRandomIndividual() )
}

/* 2. evaluate current population */
totalFitness = 0
for i=1 to POP_SIZE {
    fitness = pop[i].evaluate()
    totalFitness += fitness
}

while not end_condition (best fitness, #iterations, no improvement...)
{
    // build new population
    // optional: Elitism: copy best K from current pop to newPop
    while newPop.size()<POP_SIZE
    {
        /* 3. roulette wheel selection */
        // select 1st individual
        rnd = getRandomDouble([0,1]) * totalFitness
        for(idx=0; idx<POP_SIZE && rnd>0; idx++) {
            rnd -= pop[idx].fitness
        }
        indiv1 = pop[idx-1]
        // select 2nd individual
        rnd = getRandomDouble([0,1]) * totalFitness
        for(idx=0; idx<POP_SIZE && rnd>0; idx++) {
            rnd -= pop[idx].fitness
        }
        indiv2 = pop[idx-1]

        /* 4. crossover */
        indiv1, indiv2 = crossover(indiv1, indiv2)

        /* 5. mutation */
        indiv1.mutate()
        indiv2.mutate()

        // add to new population
        newPop.add(indiv1)
        newPop.add(indiv2)
    }
    pop = newPop
    newPop = []

    /* re-evaluate current population */
    totalFitness = 0
    for i=1 to POP_SIZE {
        fitness = pop[i].evaluate()
        totalFitness += fitness
    }
}

// return best genome
bestIndividual = pop.bestIndiv()     // max/min fitness indiv

Observe que atualmente você está perdendo uma função de condicionamento físico (depende do domínio). O crossover seria um crossover simples de um ponto (já que você está usando uma representação binária). A mutação pode ser um pouco simples de um pouco aleatoriamente.

EDITAR: Eu implementei o pseudocódigo acima em Java, levando em consideração sua estrutura e nota de código atual (lembre -se de que sou mais do cara AC/C ++ do que Java). Observe que isso não é de forma alguma a implementação mais eficiente ou completa, admito que escrevi rapidamente:

Individual.java

import java.util.Random;

public class Individual
{
    public static final int SIZE = 500;
    private int[] genes = new int[SIZE];
    private int fitnessValue;

    public Individual() {}

    public int getFitnessValue() {
        return fitnessValue;
    }

    public void setFitnessValue(int fitnessValue) {
        this.fitnessValue = fitnessValue;
    }

    public int getGene(int index) {
        return genes[index];
    }

    public void setGene(int index, int gene) {
        this.genes[index] = gene;
    }

    public void randGenes() {
        Random rand = new Random();
        for(int i=0; i<SIZE; ++i) {
            this.setGene(i, rand.nextInt(2));
        }
    }

    public void mutate() {
        Random rand = new Random();
        int index = rand.nextInt(SIZE);
        this.setGene(index, 1-this.getGene(index));    // flip
    }

    public int evaluate() {
        int fitness = 0;
        for(int i=0; i<SIZE; ++i) {
            fitness += this.getGene(i);
        }
        this.setFitnessValue(fitness);

        return fitness;
    }
}

População.java

import java.util.Random;

public class Population
{
    final static int ELITISM_K = 5;
    final static int POP_SIZE = 200 + ELITISM_K;  // population size
    final static int MAX_ITER = 2000;             // max number of iterations
    final static double MUTATION_RATE = 0.05;     // probability of mutation
    final static double CROSSOVER_RATE = 0.7;     // probability of crossover

    private static Random m_rand = new Random();  // random-number generator
    private Individual[] m_population;
    private double totalFitness;

    public Population() {
        m_population = new Individual[POP_SIZE];

        // init population
        for (int i = 0; i < POP_SIZE; i++) {
            m_population[i] = new Individual();
            m_population[i].randGenes();
        }

        // evaluate current population
        this.evaluate();
    }

    public void setPopulation(Individual[] newPop) {
        // this.m_population = newPop;
        System.arraycopy(newPop, 0, this.m_population, 0, POP_SIZE);
    }

    public Individual[] getPopulation() {
        return this.m_population;
    }

    public double evaluate() {
        this.totalFitness = 0.0;
        for (int i = 0; i < POP_SIZE; i++) {
            this.totalFitness += m_population[i].evaluate();
        }
        return this.totalFitness;
    }

    public Individual rouletteWheelSelection() {
        double randNum = m_rand.nextDouble() * this.totalFitness;
        int idx;
        for (idx=0; idx<POP_SIZE && randNum>0; ++idx) {
            randNum -= m_population[idx].getFitnessValue();
        }
        return m_population[idx-1];
    }

    public Individual findBestIndividual() {
        int idxMax = 0, idxMin = 0;
        double currentMax = 0.0;
        double currentMin = 1.0;
        double currentVal;

        for (int idx=0; idx<POP_SIZE; ++idx) {
            currentVal = m_population[idx].getFitnessValue();
            if (currentMax < currentMin) {
                currentMax = currentMin = currentVal;
                idxMax = idxMin = idx;
            }
            if (currentVal > currentMax) {
                currentMax = currentVal;
                idxMax = idx;
            }
            if (currentVal < currentMin) {
                currentMin = currentVal;
                idxMin = idx;
            }
        }

        //return m_population[idxMin];      // minimization
        return m_population[idxMax];        // maximization
    }

    public static Individual[] crossover(Individual indiv1,Individual indiv2) {
        Individual[] newIndiv = new Individual[2];
        newIndiv[0] = new Individual();
        newIndiv[1] = new Individual();

        int randPoint = m_rand.nextInt(Individual.SIZE);
        int i;
        for (i=0; i<randPoint; ++i) {
            newIndiv[0].setGene(i, indiv1.getGene(i));
            newIndiv[1].setGene(i, indiv2.getGene(i));
        }
        for (; i<Individual.SIZE; ++i) {
            newIndiv[0].setGene(i, indiv2.getGene(i));
            newIndiv[1].setGene(i, indiv1.getGene(i));
        }

        return newIndiv;
    }


    public static void main(String[] args) {
        Population pop = new Population();
        Individual[] newPop = new Individual[POP_SIZE];
        Individual[] indiv = new Individual[2];

        // current population
        System.out.print("Total Fitness = " + pop.totalFitness);
        System.out.println(" ; Best Fitness = " + 
            pop.findBestIndividual().getFitnessValue());

        // main loop
        int count;
        for (int iter = 0; iter < MAX_ITER; iter++) {
            count = 0;

            // Elitism
            for (int i=0; i<ELITISM_K; ++i) {
                newPop[count] = pop.findBestIndividual();
                count++;
            }

            // build new Population
            while (count < POP_SIZE) {
                // Selection
                indiv[0] = pop.rouletteWheelSelection();
                indiv[1] = pop.rouletteWheelSelection();

                // Crossover
                if ( m_rand.nextDouble() < CROSSOVER_RATE ) {
                    indiv = crossover(indiv[0], indiv[1]);
                }

                // Mutation
                if ( m_rand.nextDouble() < MUTATION_RATE ) {
                    indiv[0].mutate();
                }
                if ( m_rand.nextDouble() < MUTATION_RATE ) {
                    indiv[1].mutate();
                }

                // add to new population
                newPop[count] = indiv[0];
                newPop[count+1] = indiv[1];
                count += 2;
            }
            pop.setPopulation(newPop);

            // reevaluate current population
            pop.evaluate();
            System.out.print("Total Fitness = " + pop.totalFitness);
            System.out.println(" ; Best Fitness = " +
                pop.findBestIndividual().getFitnessValue()); 
        }

        // best indiv
        Individual bestIndiv = pop.findBestIndividual();
    }
}

Outras dicas

Por que não usar uma estrutura de código aberto como o JGAP: http://jgap.sf.net

Eu implementei este algoritmo criando uma "matriz cumulativa de fitness" e Pesquisa binária, portanto reduzindo a necessidade de iterar em cada elemento Na matriz durante a seleção:

  1. Para o tamanho da população n, crie uma matriz cumulativa de fitness: arr [n].
  2. Definir arr [0]: = ComputeFitness (individual [0]).
  3. Então, para cada elemento subsequente: x, arr [x] = arr [x-1] + computefitness (individual [x]).
  4. Gerar um número aleatório entre 0 e arr [n] (ou seja, a aptidão total).
  5. Use uma pesquisa binária (por exemplo, coleções.

Observe que você só precisa criar a matriz de fitness no início da fase de reprodução e pode reutilizá-la várias vezes para realizar seleções em O (log n) Tempo.

Como um aparte, observe que a seleção de torneios é muito mais fácil de implementar!

O conceito que você está procurando é chamado de "seleção de rodas de roleta". Você ainda não tem uma função de condicionamento físico estabelecido (pode estar implicando que a aptidão de cada indivíduo é o valor integral de seu cromossomo), mas quando você faz um plano geral é:

  1. Soma a aptidão de toda a população.
  2. Obtenha um número aleatório (ligue para x) entre 0 e a aptidão total.
  3. Itera através da população. Para cada membro:
    1. Subtraia a aptidão do membro de x.
    2. Se x agora estiver menor ou igual a zero, selecione o membro atual.

Existem outras implementações equivalentes, mas a idéia geral é selecionar membros com uma probabilidade proporcional à sua aptidão.

Editar: algumas notas sobre funções de fitness. A representação de um cromossomo (no seu caso como um número inteiro de 32 bits) é independente da função de aptidão usada para avaliá-lo. Por exemplo, as codificações binárias normalmente tratam o cromossomo como um conjunto de campos de bits embalados em um valor integral do tamanho apropriado. Crossover e mutação podem ser realizados pelas operações apropriadas de mascaramento de bits. Se você estiver interessado, posso postar algum código GA simples que tenho (em C e Python) que usa operações bit -netwise para implementar essas funções. Não tenho certeza de como você está confortável com esses idiomas.

Fiz uma implementação extensível em Java, na qual os operadores e a estrutura individual são bem definidos por interfaces que funcionam juntas. Repo Github aqui https://github.com/juanmf/ga

Possui uma implementação padrão para cada operador e um exemplo de implementação de problemas com uma estrutura individual/populacional específica e um medidor de condicionamento físico. O exemplo de implementação do problema é encontrar o bom time de futebol com jogadores entre 20 equipes e uma restrição de orçamento.

Para adaptá -lo ao seu problema atual, você precisa fornecer implementações dessas interfaces:

juanmf.ga.structure.Gen;
juanmf.ga.structure.Individual;
juanmf.ga.structure.IndividualFactory; 
juanmf.ga.structure.Population;  // Has a basic implementation already
juanmf.ga.structure.PopulationFactory;

Dentro pkg juanmf.grandt Você tem o exemplo de classes de implementação de problemas e como publicá -las, conforme mostrado no snippet de código abaixo.

Para publicar suas implementações, você só precisa devolver as classes adequadas deste feijão da primavera:

/**
 * Make sure @ComponentScan("pkg") in juanmf.ga.App.java includes this class' pkg 
 * so that these beans get registered.
 */
@Configuration
public class Config {

    @Bean(name="individualFactory")
    public IndividualFactory getIndividualFactory() {
        return new Team.TeamFactory();
    }

    @Bean(name="populationFactory")
    public PopulationFactory getPopulationFactory() {
        return new Team.TeamPopulationFactory();
    }

    @Bean(name="fitnessMeter")
    public FitnessMeter getFitnessMeter() {
        return new TeamAptitudeMeter();
    }
}

O operador cruzado possui duas implementações para a mesma técnica, uma sequencial e uma simultânea que supera de longe sequencial.

A condição de parada pode ser especificada. Se nenhum for fornecido, ele possui uma condição de parada padrão que pare após 100 gerações sem melhorias (aqui você deve ter cuidado com o elitista, para não perder o melhor de cada geração, a fim de acionar essa condição de parada com eficiência).

Então, se alguém estiver disposto a tentar, ficaria feliz em ajudar. Qualquer um é bem -vindo para oferecer sugestões e implementações melhores e melhores: D ou qualquer solicitação de tração em melhoria.

Essas outras perguntas sobre a seleção de rodas de roleta devem ajudar:

No primeiro, Eu tentei explicar Como funciona a roda de roleta. No segundo, Jarod Elliott forneceu algum pseudocódigo. Combinado com Descrição de Adamski de uma implementação eficiente, estes devem ser suficientes para fazer algo funcionando.

Apenas um ponto que vale a pena mencionar. A seleção da roda da roleta (como indicado no código pseudo) não funcionará para problemas de minimização - no entanto, é válido para problemas de maximização.

Devido à maneira pela qual o indivíduo mais adequado é selecionado, o caso de minimização não será realizado. Os detalhes são fornecidos em: Inteligência computacional: 2ª edição

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top