Design a Genetic Algorithm in Java – 在Java中设计一个遗传算法

最后修改: 2017年 2月 11日

中文/混合/英文(键盘快捷键：t)

1. Introduction

1.介绍

The aim of this series is to explain the idea of genetic algorithms.

这个系列的目的是解释遗传算法的想法。

Genetic algorithms are designed to solve problems by using the same processes as in nature — they use a combination of selection, recombination, and mutation to evolve a solution to a problem.

遗传算法旨在通过使用与自然界相同的过程来解决问题–它们使用选择、重组和突变的组合来演化出一个问题的解决方案。

Let’s start by explaining the concept of those algorithms using the simplest binary genetic algorithm example.

让我们先用最简单的二进制遗传算法的例子来解释这些算法的概念。

2. How Genetic Algorithms Work

2.遗传算法的工作原理

Genetic algorithms are a part of evolutionary computing, which is a rapidly growing area of artificial intelligence.

遗传算法是进化计算的一部分，它是人工智能的一个快速增长领域。

An algorithm starts with a set of solutions (represented by individuals) called population. Solutions from one population are taken and used to form a new population, as there is a chance that the new population will be better than the old one.

一个算法从一个解决方案集（由个体代表）开始，称为群体。从一个种群中提取解决方案并用于形成一个新的种群，因为新的种群有可能比旧的种群更好。

Individuals that are chosen to form new solutions (offspring) are selected according to their fitness — the more suitable they are, the more chances they have to reproduce.

被选来形成新解决方案（后代）的个体是根据他们的适合性来选择的–他们越是适合，就越有机会繁殖。

3. Binary Genetic Algorithm

3.二进制遗传算法

Let’s take a look at the basic process for a simple genetic algorithm.

让我们来看看一个简单的遗传算法的基本过程。

3.1. Initialization

3.1.初始化

In the initialization step, we generate a random Population that serves as a first solution. First, we need to decide how big the Population will be and what is the final solution that we expect:

在初始化步骤中，我们生成一个随机的Population，作为第一个解决方案。首先，我们需要决定这个Population有多大，以及我们期望的最终解决方案是什么。

SimpleGeneticAlgorithm.runAlgorithm(50,
  "1011000100000100010000100000100111001000000100000100000000001111");

In the above example, the Population size is 50, and the correct solution is represented by the binary bit string that we may change at any time.

在上面的例子中，人口规模为50，正确的解决方案由二进制位串表示，我们可以在任何时候改变。

In the next step we are going to save our desired solution and create a random Population:

在下一步，我们将保存我们所需的解决方案，并创建一个随机Population。

setSolution(solution);
Population myPop = new Population(populationSize, true);

Now we are ready to run the main loop of the program.

现在我们准备运行程序的主循环。

3.2. Fitness Check

3.2.健身检查

In the main loop of the program, we are going to evaluate each Individual by the fitness function (in simple words, the better the Individual is, the higher value of fitness function it gets):

在程序的主循环中，我们将通过健身函数评价每个个体（简单地说，个体越好，它的健身函数值越高）。

while (myPop.getFittest().getFitness() < getMaxFitness()) {
    System.out.println(
      "Generation: " + generationCount
      + " Correct genes found: " + myPop.getFittest().getFitness());
    
    myPop = evolvePopulation(myPop);
    generationCount++;
}

Let’s start with explaining how we get the fittest Individual:

让我们先解释一下我们如何获得最合适的个体。

public int getFitness(Individual individual) {
    int fitness = 0;
    for (int i = 0; i < individual.getDefaultGeneLength()
      && i < solution.length; i++) {
        if (individual.getSingleGene(i) == solution[i]) {
            fitness++;
        }
    }
    return fitness;
}

As we can observe, we compare two Individual objects bit by bit. If we cannot find a perfect solution, we need to proceed to the next step, which is an evolution of the Population.

正如我们可以观察到的，我们将两个个体对象一点一点地进行比较。如果我们不能找到一个完美的解决方案，我们就需要进行下一步，也就是对种群的进化。

3.3. Offspring

3.3.子孙

In this step, we need to create a new Population. First, we need to Select two parent Individual objects from a Population, according to their fitness. Please note that it is beneficial to allow the best Individual from the current generation to carry over to the next, unaltered. This strategy is called an Elitism:

在这一步，我们需要创建一个新的种群。首先，我们需要从种群中选择两个父系个体对象，根据它们的适配性。请注意，让当前一代中最好的个体不加改变地延续到下一代是有益的。这种策略被称为Elitism：。

if (elitism) {
    newPopulation.getIndividuals().add(0, pop.getFittest());
    elitismOffset = 1;
} else {
    elitismOffset = 0;
}

In order to select two best Individual objects, we are going to apply tournament selection strategy:

为了选择两个最佳个人对象，我们将应用锦标赛选择策略。

private Individual tournamentSelection(Population pop) {
    Population tournament = new Population(tournamentSize, false);
    for (int i = 0; i < tournamentSize; i++) {
        int randomId = (int) (Math.random() * pop.getIndividuals().size());
        tournament.getIndividuals().add(i, pop.getIndividual(randomId));
    }
    Individual fittest = tournament.getFittest();
    return fittest;
}

The winner of each tournament (the one with the best fitness) is selected for the next stage, which is Crossover:

每场比赛的获胜者（体能最好的人）被选入下一阶段，也就是交叉赛。

private Individual crossover(Individual indiv1, Individual indiv2) {
    Individual newSol = new Individual();
    for (int i = 0; i < newSol.getDefaultGeneLength(); i++) {
        if (Math.random() <= uniformRate) {
            newSol.setSingleGene(i, indiv1.getSingleGene(i));
        } else {
            newSol.setSingleGene(i, indiv2.getSingleGene(i));
        }
    }
    return newSol;
}

In the crossover, we swap bits from each chosen Individual at a randomly chosen spot. The whole process runs inside the following loop:

在交叉过程中，我们在一个随机选择的点上交换每个选定的个体的比特。整个过程在以下循环中运行。

for (int i = elitismOffset; i < pop.getIndividuals().size(); i++) {
    Individual indiv1 = tournamentSelection(pop);
    Individual indiv2 = tournamentSelection(pop);
    Individual newIndiv = crossover(indiv1, indiv2);
    newPopulation.getIndividuals().add(i, newIndiv);
}

As we can see, after the crossover, we place new offspring in a new Population. This step is called the Acceptance.

正如我们所看到的，在杂交之后，我们将新的后代放入一个新的种群。这一步骤被称为接受。。

Finally, we can perform a Mutation. Mutation is used to maintain genetic diversity from one generation of a Population to the next. We used the bit inversion type of mutation, where random bits are simply inverted:

最后，我们可以进行一次突变。突变是用来维持一个种群的一代到另一代的遗传多样性。我们使用了位反转类型的突变，其中随机位被简单反转。

private void mutate(Individual indiv) {
    for (int i = 0; i < indiv.getDefaultGeneLength(); i++) {
        if (Math.random() <= mutationRate) {
            byte gene = (byte) Math.round(Math.random());
            indiv.setSingleGene(i, gene);
        }
    }
}

All types of the Mutation and the Crossover are nicely described in this tutorial.

所有类型的突变和交叉都在本教程中得到了很好的描述。

We then repeat steps from subsections 3.2 and 3.3, until we reach a termination condition, for example, the best solution.

然后我们重复第3.2和3.3小节的步骤，直到我们达到一个终止条件，例如，最佳解。

4. Tips and Tricks

4.技巧和窍门

In order to implement an efficient genetic algorithm, we need to tune a set of parameters. This section should give you some basic recommendations how to start with the most importing parameters:

为了实现一个高效的遗传算法，我们需要调整一组参数。本节应该给你一些基本建议，如何从最导入的参数开始。

  • Crossover rate – it should be high, about 80%-95%
  • Mutation rate – it should be very low, around 0.5%-1%.
  • Population size – good population size is about 20-30, however, for some problems sizes 50-100 are better
  • Selection – basic roulette wheel selection can be used with the concept of elitism
  • Crossover and mutation type – it depends on encoding and the problem

Please note that recommendations for tuning are often results of empiric studies on genetic algorithms, and they may vary, based on the proposed problems.

请注意，调整的建议通常是对遗传算法的经验研究结果，它们可能会有所不同，基于所提出的问题。

5. Conclusion

5.结论

This tutorial introduces fundamentals of genetic algorithms. You can learn about genetic algorithms without any previous knowledge of this area, having only basic computer programming skills.

本教程介绍了遗传算法的基本原理。你可以学习遗传算法而不需要任何这方面的知识，只需具备基本的计算机编程技能。

The complete source code for the code snippets in this tutorial is available in the GitHub project.

本教程中代码片段的完整源代码可在GitHub项目中获得，。

Please also note that we use Lombok to generate getters and setters. You can check how to configure it correctly in your IDE in this article.

还请注意，我们使用Lombok来生成getters和setters。你可以在这篇文章中查看如何在你的IDE中正确配置它。

For further examples of genetic algorithms, check out all the articles of our series:

关于遗传算法的进一步例子，请查看我们系列的所有文章。