用 Java 编写的 GA

GA written in Java

提问by Mike B

I am attempting to write a Genetic Algorithm based on techniques I had picked up from the book "AI Techniques for Game Programmers" that uses a binary encoding and fitness proportionate selection (also known as roulette wheel selection) on the genes of the population that are randomly generated within the program in a two-dimensional array.

我正在尝试根据我从“游戏程序员的人工智能技术”一书中学到的技术编写遗传算法，该算法对人口的基因使用二进制编码和适应度比例选择（也称为轮盘选择）程序内随机生成的二维数组。

I recently came across a piece of pseudocodeand have tried to implement it, but have come across some problems with the specifics of what I need to be doing. I've checked a number of books and some open-source code and am still struggling to progress. I understand that I have to get the sum of the total fitness of the population, pick a random number between the sum and zero, then if the number is greater than the parents to overwrite it, but I am struggling with the implementation of these ideas.

我最近遇到了一段伪代码并试图实现它，但遇到了一些关于我需要做的细节的问题。我检查了一些书籍和一些开源代码，但仍在努力进步。我知道我必须得到人口总适应度的总和，在总和和零之间选择一个随机数，然后如果这个数字大于父母就覆盖它，但我正在努力实现这些想法.

Any help in the implementation of these ideas would be very much appreciated as my Java is rusty.

由于我的 Java 已经生锈，因此非常感谢在实现这些想法方面的任何帮助。

采纳答案by Amro

The following is a complete outline of the GA. I made sure to be very detailed so it can be easily coded to C/Java/Python/..

以下是 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

Note that currently you're missing a fitness function (depends on the domain). The crossover would be a simple one point crossover (since you are using a binary representation). Mutation could be a simple flip of a bit at random.

请注意，目前您缺少适应度函数（取决于域）。交叉将是一个简单的单点交叉（因为您使用的是二进制表示）。突变可能是一个简单的随机翻转。

---

---

EDIT: I have implemented the above pseudocode in Java taking into consideration your current code structure and notations (keep in mind i am more of a c/c++ guy than java). Note this is in no way the most efficient or complete implementation, I admit I wrote it rather quickly:

编辑：考虑到您当前的代码结构和符号，我已经在 J​​ava 中实现了上述伪代码（请记住，我更喜欢 ac/c++ 而非 java）。请注意，这绝不是最有效或最完整的实现，我承认我写得相当快：

Individual.java

个人.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

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

回答by Derrick Turk

The concept you're looking for is called "roulette wheel selection." You don't have an established fitness function yet (you may be implying that the fitness of each individual is the integral value of its chromosome), but when you do a general plan is:

您正在寻找的概念称为“轮盘选择”。您还没有确定的适应度函数（您可能暗示每个个体的适应度是其染色体的积分值），但是当您做一个总体计划时：

1. Sum the fitness of the entire population.
2. Get a random number (call it x) between 0 and the total fitness.
3. Iterate through the population. For each member:
   1. Subtract the member's fitness from x.
   2. If x is now less or equal to zero, select the current member.

1. 对整个种群的适应度求和。
2. 获取一个介于 0 和总适应度之间的随机数（称为 x）。
3. 遍历人口。对于每个成员：
   1. 从 x 中减去成员的适应度。
   2. 如果 x 现在小于或等于 0，则选择当前成员。

There are other equivalent implementations, but the general idea is to select members with a probability proportional to their fitness.

还有其他等效的实现，但总体思路是选择具有与其适应度成正比的概率的成员。

Edit: A few notes on fitness functions. The representation of a chromosome (in your case as a 32-bit integer) is independent of the fitness function used to evaluate it. For example, binary encodings typically treat the chromosome as a set of bitfields packed into an integral value of appropriate size. Crossover and mutation can then be accomplished by the appropriate bit-masking operations. If you're interested, I can post some simple GA code I have laying around (in C and Python) which uses bitwise operations to implement these functions. I'm not sure how comfortable you are with these languages.

编辑：关于健身功能的一些说明。染色体的表示（在您的情况下为 32 位整数）与用于评估它的适应度函数无关。例如，二进制编码通常将染色体视为一组位字段，这些位字段打包成适当大小的整数值。然后可以通过适当的位掩码操作来完成交叉和变异。如果您有兴趣，我可以发布一些简单的 GA 代码（在 C 和 Python 中），这些代码使用按位运算来实现这些功能。我不确定您对这些语言是否满意。

回答by Adamski

I have implemented this algorithm by creating a "cumulative fitness array" and binary search, thus reducing the need to iterate through each elementin the array during the selection:

我通过创建一个“累积适应度数组”和二分搜索来实现这个算法，从而减少了在选择过程中遍历数组中每个元素的需要：

1. For population size N create cumulative fitness array: arr[N].
2. Set arr[0] := computeFitness(individual[0]).
3. Then, for each subsequent element: X, arr[X] = arr[X-1] + computeFitness(individual[X]).
4. Generate a random number between 0 and arr[N] (i.e. the total fitness).
5. Use a binary search (e.g. Collections.binarySearch) to locate the appropriate index in the cumulative fitness array, and use this index to select the individual.

1. 对于种群大小 N，创建累积适应度数组：arr[N]。
2. 设置 arr[0] := computeFitness(individual[0])。
3. 然后，对于每个后续元素：X，arr[X] = arr[X-1] + computeFitness(individual[X])。
4. 生成一个介于 0 和 arr[N] 之间的随机数（即总适​​应度）。
5. 使用二分搜索（例如 Collections.binarySearch）在累积适应度数组中定位适当的索引，并使用该索引选择个体。

Note that you only need to create the fitness array at the start of the reproduction phase, and can then re-use it multiple times to perform selections in O(log N)time.

请注意，您只需要在复制阶段开始时创建适应度数组，然后可以多次重复使用它以在O(log N)时间内执行选择。

As an aside, note that tournament selection is far easier to implement!

顺便说一句，请注意锦标赛选择更容易实现！

回答by Dan Dyer

These other questions about roulette wheel selection should help:

这些关于轮盘选择的其他问题应该会有所帮助：

• Roulette wheel selection algorithm
• Roulette selection in genetic algorithms

• 轮盘选择算法
• 遗传算法中的轮盘赌选择

In the first one, I've tried to explainhow the roulette wheel works. In the second, Jarod Elliott has provided some pseudocode. Combined with Adamski's description of an efficient implementation, these should be sufficient to get something working.

在第一个中，我试图解释轮盘赌是如何工作的。第二部分，Jarod Elliott 提供了一些伪代码。结合Adamski 对高效实现的描述，这些应该足以让某些事情发挥作用。

回答by gpampara

Just a point worth mentioning. The Roulette wheel selection (as indicated in the pseudo-code) will not work for minimization problems - it is, however, valid for maximization problems.

只是值得一提的一点。轮盘选择（如伪代码中所示）不适用于最小化问题 - 然而，它适用于最大化问题。

Due to the manner in which the most fit individual is selected, the minimization case will not hold. Details are provided in: Computational Intelligence: 2nd edition

由于选择最适合个体的方式，最小化情况将不成立。详细信息见：计算智能：第 2 版

回答by Klaus

Why not use an open-source Framework like JGAP: http://jgap.sf.net

为什么不使用像 JGAP 这样的开源框架：http://jgap.sf.net

回答by juanmf

I made an extensible implementation in java, in which operators and individual structure is well defined by interfaces that work together. Github repo here https://github.com/juanmf/ga

我在 java 中做了一个可扩展的实现，其中操作符和单个结构由一起工作的接口很好地定义。这里的 Github 仓库https://github.com/juanmf/ga

It has a standard implementation for each operator, and an example problem implementation with a particular Individual/Population structure and a Fitness meter. The example problem Implementation is to find the a good soccer team with players among 20 teams and a budget restriction.

它对每个操作员都有一个标准实现，以及一个具有特定个人/人口结构和健身计的示例问题实现。示例问题实现是在 20 支球队和预算限制中找到一支优秀的足球队。

To adapt it to your current problem you need to provide implementations of these 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;

In pkg juanmf.grandtyou have the example problem implementation classes, and how to publish them, as shown in the code snippet below.

在pkg juanmf.grandt您有示例问题实现类，以及如何发布它们，如下面的代码片段所示。

To publish you implementations you just have to return the proper classes from this Spring beans:

要发布您的实现，您只需要从这个 Spring bean 返回正确的类：

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

Crosser operator has two implementations for the same technique, one sequential and one concurrent which outperforms sequential by far.

Crosser 运算符有两种实现相同的技术，一种是顺序的，一种是并发的，其性能远远优于顺序。

Stop condition can be specified. If none is given, it has a default stop condition that stops after 100 generations with no improvements (here you must be careful with elitist, not to loose the best of each generation so as to trigger this stop condition effectively).

可以指定停止条件。如果没有给出，它有一个默认的停止条件，在 100 代之后停止，没有任何改进（在这里你必须小心精英，不要失去每一代的最好的，以便有效地触发这个停止条件）。

So if anyone is willing to give it a try, I'd be glad to help. Anyone is welcome to offer suggestions, and better yet operator implementations :D or any improving pull request.

因此，如果有人愿意尝试一下，我很乐意提供帮助。欢迎任何人提供建议，以及更好的操作员实现 :D 或任何改进的拉取请求。