遗传算法：通过自然选择进行搜索和优化

本文概述

• 什么是遗传算法？
• 付诸实践
• 接下来是什么？

什么是遗传算法？

在过去的几年中, 围绕人工智能(AI)的讨论非常热闹。像Google, Apple和Microsoft这样的主要公司都在积极地研究这个话题。实际上, 人工智能是一个涵盖了许多目标, 方法, 工具和应用程序的保护伞。遗传算法(GA)只是通过多种可能的解决方案进行智能搜索的工具之一。

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

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

GA模仿了三个进化过程：选择, 基因交叉和突变。

与自然选择相似, GA选择的核心概念是适应性。更适合的染色体有更好的生存机会。适应度是一种衡量染色体代表的溶液质量的功能。本质上, 种群中的每个染色体代表输入参数。例如, 如果你的问题包含两个输入参数, 例如交易中的价格和数量, 则每个染色体在逻辑上将由两个元素组成。元素如何在染色体内编码是一个不同的话题。

在选择过程中, 染色体形成一对父母进行育种。每个孩子都从父母那里汲取特色。基本上, 孩子代表了父母特征的重新组合：某些特征来自一个父母, 而另一些则来自另一父母。除重组外, 某些特性可能会发生突变。

由于更合适的染色体产生更多的孩子, 因此每个后代都会有更好的适应性。在某个时候, 一代将包含一个代表我们问题的足够好的解决方案的染色体。

Google Analytics(分析)功能强大, 广泛适用于复杂问题。现有的优化技术很难解决一类优化问题。遗传算法是有效的算法, 其解决方案约为最优。众所周知的应用程序包括调度, 运输, 路由, 组技术, 布局设计, 神经网络训练等。

付诸实践

我们将看的示例可以看作是GA的” Hello World”。该示例最初是由J. Freeman在使用Mathematica模拟神经网络中给出的。我是从Mitsuo Gen和Runwei Cheng的遗传算法和工程设计中学到的。

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

由于列表中13个位置(不包括空格)中的每个位置都有26个可能的字母, 因此我们以纯随机方式获得正确短语的概率为(1/26)^ 13 = 4.03038×10-19, 大约为一千亿美元中有两次机会(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或多或少包含的简单步骤集。在初始化步骤中, 我们生成短语的初始填充。人口规模由人口规模决定。生成该短语的方式取决于供应商的实施方式。

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

在每次迭代中, 我们执行典型的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之间的数字, 并找到一个包含该数字的范围。显然, 更大的范围有更高的机会被选择, 因此更合适的染色体有更好的生存机会。

由于我们不了解适应度函数的详细信息, 因此我们需要对适应度值进行标准化。适应度函数由适应度表示, 适应度将染色体转换为代表染色体适应度的任意双倍。

在代码中, 我们找到了种群中所有染色体的适应度, 并且还找到了总适应度。在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, 我们选择父代进行繁殖。选定的父级被混洗, 允许任何组合发生。我们带双父母, 并使用交叉算子。我们对每对应用两次运算符, 因为我们需要保持总体大小不变。孩子们代替了父母。

突变

最后, 我们进行特征的重组。

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, 我们可以对染色体执行”突变”。突变本身由突变定义。

问题特定的算法配置

现在让我们看一下我们需要为通用实现提供哪些类型的特定于问题的参数。

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。

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