遗传算法：自然选择的搜索和优化

什么是遗传算法？

在过去的几年里，人工智能 (AI) 引起了极大的轰动。 谷歌、苹果和微软等大公司正在积极研究这个话题。 事实上，人工智能是一个涵盖许多目标、方法、工具和应用程序的保护伞。 遗传算法 (GA) 只是通过许多可能的解决方案进行智能搜索的工具之一。

遗传算法是一种基于自然进化原理的元启发式搜索和优化技术。 它属于更大的一类进化算法。

GA 维护着一组染色体——一组解决该问题的潜在解决方案。 这个想法是，“进化”将在连续几代之后找到问题的最佳解决方案——类似于自然选择。

遗传算法模拟三个进化过程：选择、基因交叉和突变。

与自然选择类似，遗传算法选择的核心概念是适应度。 更适合的染色体有更好的生存机会。 适应度是衡量由染色体表示的解的质量的函数。 本质上，种群中的每条染色体都代表输入参数。 例如，如果您的问题包含两个输入参数，例如交易价格和交易量，则每个染色体在逻辑上将由两个元素组成。 元素如何在染色体中编码是一个不同的话题。

在选择过程中，染色体形成一对父母进行繁殖。 每个孩子都从父母那里获得特征。 基本上，孩子代表了来自其父母的特征的重组：一些特征来自一个父母，一些来自另一个父母。 除了重组之外，一些特征还可以发生变异。

因为更健康的染色体会产生更多的孩子，所以后代的每一代都会有更好的适应度。 在某些时候，一代将包含一个染色体，它代表了我们问题的足够好的解决方案。

GA 功能强大且广泛适用于复杂问题。 有一大类优化问题很难用传统的优化技术解决。 遗传算法是有效的算法，其解决方案是近似最优的。 众所周知的应用包括调度、运输、路由、组技术、布局设计、神经网络训练等等。

付诸实践

我们将看到的示例可以被认为是 GA 的“Hello World”。 这个例子最初是由 J. Freeman 在Simulating Neural Networks with Mathematica中给出的。 我从 Mitsuo Gen 和 Runwei Cheng 的《遗传算法和工程设计》中得到它。

单词匹配问题试图用遗传算法进化一个表达式。 最初，该算法应该从随机生成的字母列表中“猜测”“成为或不是”短语。

由于列表中 13 个位置 [不包括空格] 中的每一个都有 26 个可能的字母，因此我们以纯随机方式得到正确短语的概率为 (1/26)^13=4.03038×10-19，大约为[quintillion] 中的两次机会（Gen & Chong, 1997）。

我们将在这里更广泛地定义问题，使解决方案更加困难。 假设我们不限于英语或特定短语。 我们最终可以处理任何字母，甚至任何一组符号。 我们对语言一无所知。 我们甚至不知道是否有任何语言。

假设我们的对手想到了一个任意的短语，包括空格。 我们知道短语的长度和字母表中符号的数量。 这是我们仅有的知识。 每次猜测后，我们的对手都会告诉我们有多少个字母。

每条染色体都是字母表中符号的索引序列。 如果我们谈论的是英文字母，那么“a”将由 0 表示，“b”由 1 表示，“c”由 2 表示，依此类推。 因此，例如，单词“be”将表示为[4, 1] 。

我们将通过 Java 代码片段演示所有步骤，但理解每个步骤并不需要 Java 知识。

遗传算法核心

我们可以从遗传算法的一般实现开始：

 public void find() { // Initialization List<T> population = Stream.generate(supplier) .limit(populationSize) .collect(toList()); // Iteration while (!termination.test(population)) { // Selection population = selection(population); // Crossover crossover(population); // Mutation mutation(population); } }

这是每个 GA 或多或少包含的一组简单步骤。 在初始化步骤，我们生成初始的短语群。 人口的大小由populationSize决定。 短语如何生成取决于supplier的实施。

在迭代步骤中，我们进化种群，直到在while循环的测试中满足终止条件。 终止条件可以包括代数和群体中短语之一的精确匹配。 termination封装了一个精确的实现。

在每次迭代中，我们执行典型的 GA 步骤：

1. 根据染色体适应度对种群进行选择。
2. 通过交叉操作产生新的“一代”。
3. 对某些短语中的某些字母进行重组。

该算法的核心非常简单且与领域无关。 所有问题都是一样的。 您需要调整的是遗传算子的实现。 接下来，我们将仔细研究前面提到的每个 GA 算子。

选择

正如我们已经知道的那样，选择是寻找当前染色体的继任者的过程——这些染色体更适合我们的问题。 在选择过程中，我们需要保证适应度更好的染色体有更好的生存机会。

 private List<T> selection(List<T> population) { final double[] fitnesses = population.stream() .mapToDouble(fitness) .toArray(); final double totalFitness = DoubleStream.of(fitnesses).sum(); double sum = 0; final double[] probabilities = new double[fitnesses.length]; for (int i = 0; i < fitnesses.length; i++) { sum += fitnesses[i] / totalFitness; probabilities[i] = sum; } probabilities[probabilities.length - 1] = 1; return range(0, probabilities.length).mapToObj(i -> { int index = binarySearch(probabilities, random()); if (index < 0) { index = -(index + 1); } return population.get(index); }).collect(toList()); }

这个实现背后的想法如下：人口被表示为数字轴上的结果范围。 总人口在 0 和 1 之间。

染色体所占据的范围与其适应度成正比。 这导致更适合的染色体获得更大的块。 然后我们随机查看一个介于 0 和 1 之间的数字，并找到一个包含该数字的范围。 显然，更大的范围有更高的机会被选择，因此更适合的染色体有更好的生存机会。

因为我们不知道适应度函数的细节，所以我们需要对适应度值进行归一化。 适应度函数由fitness表示，它将染色体转换为表示染色体适应度的任意双精度值。

在代码中，我们找到了种群中所有染色体的适应度，我们还找到了总适应度。 在for循环中，我们对按总适应度缩小的概率进行累积求和。 从数学上讲，这应该导致最终变量的值为 1。由于浮点的不精确性，我们不能保证这一点，所以我们将其设置为 1 只是为了确定。

最后，对于等于输入染色体数的次数，我们生成一个随机数，找到一个包含该数字的范围，然后选择对应的染色体。 您可能会注意到，可能会多次选择同一染色体。

分频器

现在我们需要染色体来“繁殖”。

 private void crossover(List<T> population) { final int[] indexes = range(0, population.size()) .filter(i-> random() < crossoverProbability) .toArray(); shuffle(Arrays.asList(indexes)); for (int i = 0; i < indexes.length / 2; i++) { final int index1 = indexes[2 * i]; final int index2 = indexes[2 * i + 1]; final T value1 = population.get(index1); final T value2 = population.get(index2); population.set(index1, crossover.apply(value1, value2)); population.set(index2, crossover.apply(value2, value1)); } }

使用预定义的概率crossoverProbability ，我们选择父母进行育种。 选择的父母被洗牌，允许任何组合发生。 我们采用一对父母并应用crossover算子。 我们对每一对应用两次操作符，因为我们需要保持种群大小相同。 孩子们在人口中取代了他们的父母。

突变

最后，我们对特征进行重组。

 private void mutation(List<T> population) { for (int i = 0; i < population.size(); i++) { if (random() < mutationProbability) { population.set(i, mutation.apply(population.get(i))); } } }

使用预定义的概率mutationProbability ，我们对染色体执行“突变”。 突变本身由mutation定义。

特定问题的算法配置

现在让我们看看我们需要为我们的通用实现提供什么类型的问题特定参数。

 private BiFunction<T, T, T> crossover; private double crossoverProbability; private ToDoubleFunction<T> fitness; private Function<T, T> mutation; private double mutationProbability; private int populationSize = 100; private Supplier<T> supplier; private Predicate<Collection<T>> termination;

参数分别为：

1. 交叉算子
2. 交叉概率
3. 健身功能
4. 变异算子
5. 突变概率
6. 人口规模
7. 初始种群的染色体供应商
8. 终止功能

这是我们问题的配置：

 new GeneticAlgorithm<char[]>() .setCrossover(this::crossover) .setCrossoverProbability(0.25) .setFitness(this::fitness) .setMutation(this::mutation) .setMutationProbability(0.05) .setPopulationSize(100) .setSupplier(() -> supplier(expected.length)) .setTermination(this::termination) .find()

交叉算子和概率

private char[] crossover(char[] value1, char[] value2) { final int i = (int) round(random() * value1.length); final char[] result = new char(value1.length); System.arraycopy(value1, 0, result, 0, i); System.arraycopy(value2, i, result, i, value2.length - i); return result; }

交叉的概率为 0.25，因此我们预计平均 25% 的染色体将被选择用于交叉。 我们为一对染色体的交叉执行了一个简单的程序。 我们从[0..length]范围内生成一个随机数n ，其中length是染色体的长度。 现在我们通过从一个染色体中取出前n字符和从第二个染色体后的剩余字符来配对选定的对。

健身功能

private double fitness(char[] value) { return range(0, value.length) .filter(i -> value[i] == expected[i]) .count(); }

适应度函数只是计算目标短语和给定染色体之间的匹配次数。

变异算子和概率

private char[] mutation(char[] value) { final char[] result = Arrays.copyOf(value, value.length); for (int i = 0; i < 2; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); int location = (int) round(random() * (value.length - 1)); result[location] = ALPHABET[letter]; } return result; }

变异操作在每条染色体上独立进行。 突变的概率为 0.05，因此我们预计平均 5% 的人口会发生突变。 我们通过选择一个随机字母位置并将其值替换为字母表中的一个随机字母来进行变异。 我们对每个突变的染色体做两次。

供应商

private char[] supplier(int length) { final char[] result = new char(length); for (int i = 0; i < length; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); result[i] = ALPHABET[letter]; } return result; }

供应商通过从字母表中获取随机字母来生成随机短语。 每个短语都有一个恒定的预定义长度。

终止功能

private boolean termination(Collection<char[]> chars) { count++; final Optional<char[]> result = chars.stream() .filter(value -> round(fitness(value)) == expected.length) .findAny(); if (result.isPresent()) { System.out.println("Count: " + count); System.out.println(result.get()); return true; } final boolean terminated = count == 3000; if (terminated) { chars.forEach(System.out::println); } return terminated; }

终止函数计算调用次数，如果完全匹配或生成计数达到 3,000，则返回true 。

执行

现在我们准备测试我们的算法。 如果您多次运行它，您会注意到并非所有运行都成功。 每次迭代的次数都会不同。 这是由于算法的概率性质。 该算法有几个可以改进的地方。 你可以玩交叉和变异概率。

降低数字将导致稳定但缓慢的解决方案。 较少数量的染色体将受到遗传算子的影响，因此解决方案将需要更多的迭代。

增加数字会加快算法的速度，但也会使解变得不稳定。 适合的染色体不仅会被保留，还会受到遗传算子的影响。 因此，他们将失去他们的“好”基因。

找到一个好的平衡点很重要。 增加迭代次数将使算法有更多机会找到解决方案，但另一方面，这将花费更多时间。 您还可以应用不同的交叉和变异方法。 这些运算符的良好选择将大大提高解决方案的质量。

接下来是什么？

我们在这里只介绍了冰山一角。 我们举了一个只有一个输入的例子，输入可以很容易地表示为一条染色体。 遗传算子简单明了。

处理一个现实世界的问题并将遗传算法应用于它是非常有趣的。 您将发现编码真实输入数据的不同方法以及不同的交叉和变异实现。

如果一个问题可以通过一组参数来表达，我们必须猜测这些参数来优化一个度量，我们可以快速设置一个我们可以用来解决它的 GA。

最有趣的问题之一是教授人工神经网络。 我们可以将可优化参数设置为突触强度，并将适应度指标设置为我们的神经网络给出正确答案的输入百分比。 之后，我们可以坐下来让我们的神经网络演变成我们想要的理想解决方案。 或者至少在我们得到足够好的东西之前，因为进化需要时间。