1. Introduction
1.介绍
The aim of this series is to explain the idea of genetic algorithms and show the most known implementations.
本系列的目的是为了解释遗传算法的理念，并展示最知名的实现方式。
In this tutorial, we’ll describe a very powerful Jenetics Java library that can be used for solving various optimization problems.
在本教程中，我们将描述一个非常强大的Jenetics Java库，可用于解决各种优化问题。
If you feel that you need to learn more about genetic algorithms, we recommend starting with this article.
如果你觉得你需要学习更多关于遗传算法的知识，我们建议你从这篇文章开始。
2. How Does It Work?
2.它是如何工作的？
According to its official documents, Jenetics is a library based on an evolutionary algorithm written in Java. Evolutionary algorithms have their roots in biology, as they use mechanisms inspired by biological evolution, such as reproduction, mutation, recombination, and selection.
根据其官方文件，Jenetics是一个基于进化算法的库，用Java编写。进化算法起源于生物学，因为它们使用了受生物进化启发的机制，如繁殖、变异、重组和选择。
Jenetics is implemented using the Java Stream interface, so it works smoothly with the rest of the Java Stream API.
Jenetics是使用Java Stream接口实现的，因此它可以与Java Stream API的其他部分顺利地工作。
The main features are:
其主要特点是。
- frictionless minimization – there is no need to change or tweak the fitness function; we can just change the configuration of the Engine class and we are ready to start our first application
- dependency free – there are no runtime third-party libraries needed to use Jenetics
- Java 8 ready – full support for Stream and lambda expressions
- multithreaded – evolutionary steps can be executed in parallel
In order to use Jenetics, we need to add the following dependency into our pom.xml:
为了使用Jenetics，我们需要在我们的pom.xml中添加以下依赖。
<dependency>
<groupId>io.jenetics</groupId>
<artifactId>jenetics</artifactId>
<version>3.7.0</version>
</dependency>The latest version can be found in Maven Central.
最新版本可以在Maven中心找到，。
3. Use Cases
3.使用案例
To test all features of Jenetics, we’ll try to solve various well-known optimization problems, starting from the simple binary algorithm and ending with the Knapsack problem.
为了测试Jenetics的所有功能，我们将尝试解决各种著名的优化问题，从简单的二进制算法开始，最后是Knapsack问题。
3.1. Simple Genetic Algorithm
3.1.简单的遗传算法
Let’s assume that we need to solve the simplest binary problem, where we need to optimize the positions of the 1 bits in the chromosome consisting of 0’s and 1’s. First, we need to define the factory suitable for the problem:
让我们假设我们需要解决最简单的二进制问题，我们需要优化由0和1组成的染色体中1位的位置。首先，我们需要定义适合该问题的工厂。
Factory<Genotype<BitGene>> gtf = Genotype.of(BitChromosome.of(10, 0.5));We created the BitChromosome with a length of 10, and the probability of having 1’s in the chromosome equal to 0.5.
我们创建了长度为10的BitChromosome，染色体中出现1的概率等于0.5。
Now, let’s create the execution environment:
现在，让我们来创建执行环境。
Engine<BitGene, Integer> engine
= Engine.builder(SimpleGeneticAlgorithm::eval, gtf).build();The eval() method returns the bit count:
eval()方法返回比特计数。
private Integer eval(Genotype<BitGene> gt) {
return gt.getChromosome().as(BitChromosome.class).bitCount();
}In the final step, we start the evolution and collect the results:
在最后一步，我们开始演变并收集结果。
Genotype<BitGene> result = engine.stream()
.limit(500)
.collect(EvolutionResult.toBestGenotype());The final result will look similar to this:
最后的结果将类似于这样。
Before the evolution:
[00000010|11111100]
After the evolution:
[00000000|11111111]We managed to optimize the position of 1’s in the gene.
我们设法优化了基因中1的位置。
3.2. Subset Sum Problem
3.2.子集之和问题
Another use case for Jenetics is to solve the subset sum problem. In brief, the challenge to optimize is that, given a set of integers, we need to find a non-empty subset whose sum is zero.
Jenetics的另一个用例是解决子集和问题。简而言之，优化的挑战是，给定一个整数集，我们需要找到一个非空的子集，其总和为零。
There are predefined interfaces in Jenetics to solve such problems:
在Jenetics中，有预定义的接口来解决此类问题。
public class SubsetSum implements Problem<ISeq<Integer>, EnumGene<Integer>, Integer> {
// implementation
}As we can see, we implement the Problem<T, G, C>, that has three parameters:
我们可以看到，我们实现了Problem<T, G, C>，它有三个参数。
- <T> – the argument type of the problem fitness function, in our case an immutable, ordered, fixed sized Integer sequence ISeq<Integer>
- <G> – the gene type the evolution engine is working with, in this case, countable Integer genes EnumGene<Integer>
- <C> – the result type of the fitness function; here it is an Integer
In order to use the Problem<T, G, C> interface, we need to override two methods:
为了使用Problem<T, G, C> 接口，我们需要覆盖两个方法。
@Override
public Function<ISeq<Integer>, Integer> fitness() {
return subset -> Math.abs(subset.stream()
.mapToInt(Integer::intValue).sum());
}
@Override
public Codec<ISeq<Integer>, EnumGene<Integer>> codec() {
return codecs.ofSubSet(basicSet, size);
}In the first one, we define our fitness function, whereas the second one is a class containing factory methods for creating common problem encodings, for example, to find the best fixed-size subset from a given basic set, as in our case.
在第一个中，我们定义了我们的健身函数，而第二个是一个包含工厂方法的类，用于创建常见的问题编码，例如，从一个给定的基本集合中找到最佳的固定尺寸子集，就像我们的情况一样。
Now we can proceed to the main part. At the beginning, we need to create a subset to use in the problem:
现在我们可以进入主要部分了。在开始时，我们需要创建一个子集来用于问题。
SubsetSum problem = of(500, 15, new LCG64ShiftRandom(101010));Please note that we are using the LCG64ShiftRandom generator provided by Jenetics. In the next step, we are building the engine of our solution:
请注意，我们使用的是Jenetics提供的LCG64ShiftRandom发生器。在下一步，我们将建立我们解决方案的引擎。
In the next step, we are building the engine of our solution:
在下一步，我们正在建立我们解决方案的引擎。
Engine<EnumGene<Integer>, Integer> engine = Engine.builder(problem)
.minimizing()
.maximalPhenotypeAge(5)
.alterers(new PartiallyMatchedCrossover<>(0.4), new Mutator<>(0.3))
.build();We try to minimize the result (optimally the result will be 0) by setting the phenotype age and alterers used to alter the offspring. In the next step we can obtain the result:
我们通过设置用于改变后代的表型年龄和改变者，试图使结果最小化（最佳情况下，结果将为0）。在下一步，我们可以得到结果。
Phenotype<EnumGene<Integer>, Integer> result = engine.stream()
.limit(limit.bySteadyFitness(55))
.collect(EvolutionResult.toBestPhenotype());Please note that we are using bySteadyFitness() that returns a predicate, which will truncate the evolution stream if no better phenotype could be found after the given number of generations and collect the best result. If we get lucky, and there is a solution to the randomly created set, we’ll see something similar to this:
请注意，我们使用的是bySteadyFitness()，它返回一个谓词，如果在给定的代数后找不到更好的表型，它将截断进化流并收集最佳结果。如果我们运气好，在随机创建的集合中有一个解决方案，我们会看到与此类似的东西。
If we get lucky, and there is a solution to the randomly created set, we’ll see something similar to this:
如果我们运气好，有一个随机创建的集合的解决方案，我们会看到与此类似的东西。
[85|-76|178|-197|91|-106|-70|-243|-41|-98|94|-213|139|238|219] --> 0Otherwise, the sum of subset will be different than 0.
否则，子集的总和将不同于0。
3.3. Knapsack First Fit Problem
3.3.敲击式第一拟合问题
The Jenetics library allows us to solve even more sophisticated problems, such as the Knapsack problem. Briefly speaking, in this problem, we have a limited space in our knapsack, and we need to decide which items to put inside.
Jenetics库允许我们解决更复杂的问题，例如Knapsack问题。简而言之，在这个问题中，我们的背包空间有限，我们需要决定将哪些物品放在里面。
Let’s start with defining the bag size and number of items:
让我们从定义袋子的大小和物品的数量开始。
int nItems = 15;
double ksSize = nItems * 100.0 / 3.0;In the next step, we’ll generate a random array containing KnapsackItem objects (defined by size and value fields) and we’ll put those items randomly inside the knapsack, using the First Fit method:
在下一步，我们将生成一个包含KnapsackItem对象的随机数组（由size和value字段定义），我们将使用First Fit方法，将这些项目随机放入背包内。
KnapsackFF ff = new KnapsackFF(Stream.generate(KnapsackItem::random)
.limit(nItems)
.toArray(KnapsackItem[]::new), ksSize);Next, we need to create the Engine:
接下来，我们需要创建引擎。
Engine<BitGene, Double> engine
= Engine.builder(ff, BitChromosome.of(nItems, 0.5))
.populationSize(500)
.survivorsSelector(new TournamentSelector<>(5))
.offspringSelector(new RouletteWheelSelector<>())
.alterers(new Mutator<>(0.115), new SinglePointCrossover<>(0.16))
.build();There are a few points to note here:
这里有几个要点需要注意。
- population size is 500
- the offspring will be chosen through the tournament and roulette wheel selections
- as we did in the previous subsection, we need also to define the alterers for the newly created offspring
There is also one very important feature of Jenetics. We can easily collect all statistics and insights from the whole simulation duration. We are going to do this by using the EvolutionStatistics class:
Jenetics还有一个非常重要的特点。我们可以轻松地从整个模拟过程中收集所有的统计数据和见解。我们将通过使用EvolutionStatistics类来实现这一点。
EvolutionStatistics<Double, ?> statistics = EvolutionStatistics.ofNumber();Finally, let’s run the simulations:
最后，让我们运行模拟。
Phenotype<BitGene, Double> best = engine.stream()
.limit(bySteadyFitness(7))
.limit(100)
.peek(statistics)
.collect(toBestPhenotype());Please note that we are updating the evaluation statistics after each generation, which is limited to 7 steady generation and a maximum of 100 generations in total. In more detail there are two possible scenarios:
请注意，我们在每一代之后都会更新评估统计，每一代都限制在7个稳定的世代，总共最多100代。更详细地说，有两种可能的情况。
- we achieve 7 steady generations, then the simulation stops
- we cannot get 7 steady generations in less than 100 generations, so the simulation stops due to the second limit()
It’s important to have maximum generations limit, otherwise, the simulations may not stop in a reasonable time.
有最大的世代限制是很重要的，否则，模拟可能不会在合理的时间内停止。。
The final result contains a lot of information:
最后的结果包含了大量的信息。
+---------------------------------------------------------------------------+
| Time statistics |
+---------------------------------------------------------------------------+
| Selection: sum=0,039207931000 s; mean=0,003267327583 s |
| Altering: sum=0,065145069000 s; mean=0,005428755750 s |
| Fitness calculation: sum=0,029678433000 s; mean=0,002473202750 s |
| Overall execution: sum=0,111383965000 s; mean=0,009281997083 s |
+---------------------------------------------------------------------------+
| Evolution statistics |
+---------------------------------------------------------------------------+
| Generations: 12 |
| Altered: sum=7 664; mean=638,666666667 |
| Killed: sum=0; mean=0,000000000 |
| Invalids: sum=0; mean=0,000000000 |
+---------------------------------------------------------------------------+
| Population statistics |
+---------------------------------------------------------------------------+
| Age: max=10; mean=1,792167; var=4,657748 |
| Fitness: |
| min = 0,000000000000 |
| max = 716,684883338605 |
| mean = 587,012666759785 |
| var = 17309,892287851708 |
| std = 131,567063841418 |
+---------------------------------------------------------------------------+This particular time, we were able to put items with a total value of 716,68 in the best scenario. We also can see the detailed statistics of evolution and time.
这个特定的时间，我们能够把总价值为716,68的物品放在最好的情况下。我们还可以看到演变和时间的详细统计。
How to test?
如何测试？
It is a fairly simple process — just open the main file related to the problem and first run the algorithm. Once we have a general idea, then we can start playing with the parameters.
这是一个相当简单的过程–只要打开与问题有关的主文件，首先运行算法。一旦我们有了一个大致的概念，那么我们就可以开始玩参数了。
4. Conclusion
4.结论
In this article, we covered the Jenetics library features based on real optimization problems.
在这篇文章中，我们介绍了基于实际优化问题的Jenetics库功能。
The code is available as a Maven project on GitHub. Please note that we provided the code examples for more optimization challenges, such as the Springsteen Record (yes, it exists!) and Traveling Salesman problems.
该代码可作为Maven项目在GitHub上获得。请注意，我们为更多的优化挑战提供了代码示例，例如Springsteen Record（是的，它存在！）和Traveling Salesman问题。
For all articles in the series, including other examples of genetic algorithms, check out the following links:
对于该系列的所有文章，包括遗传算法的其他例子，请查看以下链接。
- How to Design a Genetic Algorithm in Java
- The Traveling Salesman Problem in Java
- Ant Colony Optimization
- Introduction to Jenetics library (this)