用Java编写的GA

Question

我正在尝试编写一个基于遗传算法的程序，使用二进制编码和适应性比例选择（也称为轮盘赌选择），在程序中对随机生成的种群基因的二维数组进行操作。这些技术均来源于《游戏程序员人工智能技术》。

最近我看到了一段伪代码并试图实现它，但是我遇到了一些具体问题。我查阅了许多书籍和开源代码，但仍然很难进展。我知道我必须获得种群总适应度之和，选择介于总和和零之间的随机数，如果该数字大于父代，则覆盖它，但我在这些想法的实现上遇到了困难。

如果我的Java生疏了，任何有关实现这些想法的帮助都将非常感激。

- Mike B

---

我需要在实现我的最终语句方面寻求帮助。我有点知道该怎么做，但是没有其他资源，而且因为互联网上的许多资源都有不同的实现方式，所以我很难找到一个简单的方法来完成我需要做的事情。 - Mike B

为什么不更新您上面的代码，向我们展示您迄今为止所做的工作？此外，为了帮助健身函数，我们需要了解您正在应用此GA算法的领域（近似函数，优化问题等...） - Amro

对的，我现在使用的代码已经上传了。我觉得我开始逐渐理解它了；交叉和变异的代码应该足够简单，我只是想确保我现在所做的是正确的和/或可以更好地完成。 - Mike B

您似乎对适应度函数的作用和设计有些困惑。您必须明白，没有通用的公式，它通常取决于基因组的表示方式以及它们在应用领域中的含义。您当前的实现仅仅是基因组中1的数量，因此答案显然是全部为1或全部为0，具体取决于您是最大化/最小化适应度函数。这就是为什么我一直在问您使用GA的目的是什么，每个基因组编码的是什么。 - Amro

谢谢你的回复。你提供的一切都是我需要的，因为我的GA并不是用于实际使用的。我最近购买了一本关于游戏编程人工智能的好书，它用一些基本的伪代码介绍了这个概念，我想尝试实现它。它并没有很好地介绍这个主题，但是你的解释和代码已经更好地向我展示了它的作用。在这些例子中，这种实现的整个原因是为了让你看到“进化”的过程。 - Mike B

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

- Amro

Answer 2

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

- Klaus

Answer 3

我通过创建“累积适应度数组”和二分查找算法来实现该算法，从而减少了在选择过程中遍历数组的需要：

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）查找累积适应度数组中的适当索引，并使用此索引选择个体。

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

另外，请注意锦标赛选择更容易实现！

- Adamski

Answer 4

我在Java中制作了一个可扩展的实现，其中运算符和个体结构由共同工作的接口定义得很好。Github仓库链接在这里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 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();
    }
} 

交叉操作符有两种实现方式，一种是顺序执行，另一种是并发执行，后者的执行效率远高于前者。

可以指定停止条件。如果没有给出条件，则有一个默认的停止条件，即在100个世代中没有改进就停止（在这里，您必须小心保留精英，以便有效地触发此停止条件）。

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

- juanmf

Answer 5

你要找的概念叫做“轮盘赌选择”。你还没有确定一个适应度函数（你可能是在暗示每个个体的适应度是其染色体的积分值），但当你有了一个一般的计划是：

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

还有其他等效的实现方法，但一般的想法是按比例选择适应度高的成员。

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

- Derrick Turk

---

第三部分是我遇到问题的地方。我有我的种群和它们的基因，我已经给它们每个人一个数字，要么是零，要么是一，并且我有整个种群的总适应度之和。现在我是否需要再次循环相同的事情，如果我这样做，我选择哪个成员？回答你最新的问题，我熟悉C语言，尽管目前我只是在努力解决适应度方法的问题；我对如何处理交叉和突变有一个很好的想法。 - Mike B

抱歉，我再次查看了您的代码。您将每个染色体表示为一个整数数组，每个整数都应该是0或1。第一次浏览时，我假设您将等位基因打包成单个整数的位，这样会更节省空间。适应度函数代表您对“好”个体解决方案（=染色体）的最佳猜测。我的轮盘赌选择伪代码假定适应度应该被最大化而不是最小化，但很容易改变为相反的情况。（待续...） - Derrick Turk

在计算总适应度之后（您当前的“适应度函数”是染色体适应度为其int数组的总和），您将回到种群中。这是我以前用C编写的一个简单的GA演示：<a href="http://codepad.org/f8IJiCu1">http://codepad.org/f8IJiCu1</a>。看一些代码可能会有所帮助，因为算法很难用文字解释。我编写的类似Python版本在这里：<a href="http://codepad.org/8imFTytY">http://codepad.org/8imFTytY</a>。在我看来，这个版本更加简洁。 - Derrick Turk

哎呀，我的URL被搞砸了。C版本在http://codepad.org/f8IJiCu1，Python版本在http://codepad.org/8imFTytY。 - Derrick Turk

Answer 6

值得一提的是，轮盘赌选择（如伪代码中所示）对于最小化问题无效 - 但对于最大化问题有效。

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

- gpampara

Answer 7

以下这些关于轮盘赌选择的问题应该会有所帮助：

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

在第一个链接中，我已经尝试解释了轮盘赌的工作原理。在第二个链接中，Jarod Elliott提供了一些伪代码。结合Adamski对高效实现的描述，这些应该足以让你得到想要的结果。

- Dan Dyer