用Java编写的GA

Question

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

我最近遇到了一段伪代码并尝试实现它，但是在我需要做的具体事情上遇到一些问题。我已经检查了很多书籍和一些开源代码，但仍在努力取得进展。 我知道我必须获得总体适应度的总和，在总和和零之间选择一个随机数，然后如果该数字大于父母则覆盖它，但我正在努力实施这些想法。

任何对实现这些想法的帮助都将非常感激，因为我的 Java 还很生疏。

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

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

---

编辑：
考虑到您当前的代码结构和符号，我已经在 J​​ava 中实现了上述伪代码（请记住，我更喜欢 ac/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();
    }
}

Answer 2

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

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) 时间内执行选择。

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

Answer 4

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

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

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

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

Answer 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 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 运算符对于同一技术有两种实现，一种是顺序实现，一种是并发，其性能远远优于顺序。

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

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

Answer 6

有关轮盘赌选择的其他问题应该有所帮助：

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

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

Answer 7

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

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