GA написано на Java

Ответ 1

Ниже приведен полный контур GA. Я удостоверился, что вы очень подробно, поэтому его можно легко закодировать на 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

Обратите внимание, что в настоящее время вам не хватает функции фитнеса (зависит от домена). Кроссовер будет простым одноточечным кроссовером (поскольку вы используете двоичное представление). Мутация может быть простым переворотом в случайном порядке.

ИЗМЕНИТЬ: Я реализовал вышеупомянутый псевдокод в Java с учетом вашей текущей структуры кода и обозначений (помните, что я больше похожи на c/С++, чем на java). Обратите внимание, что это не самая эффективная или полная реализация, я признаю, что написал ее довольно быстро:

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

Population.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();
    }
}

Ответ 2

Почему бы не использовать платформу с открытым исходным кодом, такую ​​как JGAP: http://jgap.sf.net

Ответ 3

Я реализовал этот алгоритм, создав "совокупный массив пригодности" и бинарный поиск, тем самым уменьшая необходимость повторения каждого элемента в массиве во время выбора:

• Для размера популяции N создайте накопительный фитнес-массив: arr [N].
• Установить arr [0]: = computeFitness (индивидуально [0]).
• Затем для каждого последующего элемента: X, arr [X] = arr [X-1] + computeFitness (индивидуальный [X]).
• Генерировать случайное число между 0 и arr [N] (т.е. полное соответствие).
• Используйте двоичный поиск (например, Collections.binarySearch), чтобы найти соответствующий индекс в совокупном массиве пригодности и использовать этот индекс для выбора индивидуума.

Обратите внимание, что вам нужно всего лишь создать фитнес-массив в начале фазы воспроизведения и затем повторно использовать его несколько раз для выполнения выбора в O (log N). p >

Отметим, что выбор турниров намного проще реализовать!

Ответ 4

Концепция, которую вы ищете, называется "выбор колесика рулетки". У вас еще нет установленной функции фитнеса (вы можете подразумевать, что пригодность каждого человека является интегральным значением его хромосомы), но когда вы делаете общий план:

•  
• Совокупность всей совокупности.  
• Получите случайное число (назовите его x) между 0 и суммарной пригодностью.  
• Итерации через население. Для каждого участника:
  • Вычтите член-член из x.
  • Если x теперь меньше или равно нулю, выберите текущий элемент.

Существуют и другие эквивалентные реализации, но общая идея состоит в том, чтобы выбрать элементы с вероятностью, пропорциональной их пригодности.

Изменить: Несколько заметок о функциях фитнеса. Представление хромосомы (в вашем случае как 32-битное целое) не зависит от функции пригодности, используемой для ее оценки. Например, двоичные кодировки обычно обрабатывают хромосому как набор битовых полей, упакованных в интегральное значение соответствующего размера. После этого кроссовер и мутация могут быть выполнены с помощью соответствующих операций маскирования бит. Если вам интересно, я могу опубликовать простой код GA, который у меня есть (в C и Python), который использует побитовые операции для реализации этих функций. Я не уверен, насколько вам комфортно с этими языками.

Ответ 5

Я сделал расширяемую реализацию в java, в которой операторы и индивидуальная структура хорошо определены интерфейсами, которые работают вместе. Github repo здесь https://github.com/juanmf/ga

Он имеет стандартную реализацию для каждого оператора и примерную реализацию задачи с конкретной индивидуальной/демографической структурой и измерителем пригодности. Примерная задача Реализация - найти хорошую футбольную команду с игроками среди 20 команд и ограничение бюджета.

Чтобы адаптировать его к вашей текущей проблеме, вам необходимо обеспечить реализацию этих интерфейсов:

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;

В pkg juanmf.grandt у вас есть примеры классов реализации проблемы и способы их публикации, как показано в нижеприведенном фрагменте кода.

Чтобы опубликовать ваши реализации, вам просто нужно вернуть соответствующие классы из этого Spring beans:

/**
 * 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();
    }
} 

Оператор-перекрестье имеет две реализации для одного и того же метода: один последовательный и один параллельный, который намного превосходит по порядку.

Можно указать условие останова. Если ни один не указан, он имеет условие остановки по умолчанию, которое останавливается после 100 поколений без каких-либо улучшений (здесь вы должны быть осторожны с элитаристами, чтобы не потерять лучшее из каждого поколения, чтобы эффективно активировать это условие остановки).

Итак, если кто-то захочет попробовать, я буду рад помочь. Любой желающий может предлагать предложения, а еще лучше реализовать оператор: D или любой улучшающий запрос на тягу.

Ответ 6

Эти другие вопросы, касающиеся выбора колеса рулетки, должны помочь:

• Алгоритм выбора колесика рулетки
• Выбор рулетки в генетических алгоритмах

В первом, Я пытался объяснить, как работает рулетка. Во втором, Jarod Elliott предоставил некоторый псевдокод. В сочетании с Adamski описанием эффективной реализации их должно быть достаточно, чтобы что-то работало.

Ответ 7

Просто стоит упомянуть. Выбор колеса рулетки (как указано в псевдокоде) не будет работать для задач минимизации - он, однако, действителен для задач максимизации.

Из-за того, как выбирается наиболее подходящий человек, случай минимизации не будет выполняться. Подробности приведены в: Computational Intelligence: 2nd edition