One Max 问题¶

这是使用 DEAP 构建的第一个完整示例。它将帮助新用户概览框架的一些可能性，并展示进化算法在一般情况下的潜力。问题本身非常简单，并且在进化计算社区中被广泛使用。我们将创建一个由整数向量组成的个体群体，这些向量随机填充了 0 和 1。然后我们让我们的群体进化，直到其中一个成员只包含 1 而不再有 0。

设置环境¶

为了解决One Max问题，我们需要一些材料。首先，我们必须定义我们的个体，它们将是整数值的列表，并使用它们生成一个种群。然后，我们将添加一些函数和操作符来处理种群的评估和进化，最后将所有内容整合到脚本中。

但首先，我们需要导入一些模块。

import random

from deap import base
from deap import creator
from deap import tools

创建者¶

由于遗传算法中所需个体的实际结构在很大程度上取决于手头的任务，DEAP 不包含任何显式结构。它将提供一种方便的方法来创建属性容器，这些属性与适应度相关联，称为 deap.creator。使用这种方法，我们可以非常简单地创建自定义个体。

creator 是一个类工厂，可以在运行时构建新类。它将首先使用新类的期望名称调用，其次是它将继承的基类，并且还可以添加您希望成为类属性的任何后续参数。这使我们能够从列表到 n 叉树构建任何类型的容器的新复杂结构。

creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)

首先我们将定义类 FitnessMax。它将继承 deap.base 模块中的 Fitness 类，并包含一个名为 weights 的附加属性。请注意 weights 的值为元组 (1.0,)。这样我们将最大化单个目标适应度。我们再怎么强调也不为过，在 DEAP 中，单目标是一个多目标的特例。

接下来我们将创建类 Individual，它将继承类 list 并在其 fitness 属性中包含我们之前定义的 FitnessMax 类。请注意，在创建时，我们定义的所有类都将成为 creator 容器的一部分，并且可以直接调用。

工具箱¶

现在我们将使用自定义类来创建表示个体以及整个种群的类型。

在我们使用过程中，所有对象，包括个体、种群，以及所有函数、操作符和参数，都将存储在一个名为 Toolbox 的 DEAP 容器中。它包含两个用于添加和删除内容的方法，分别是 register() 和 unregister()。

toolbox = base.Toolbox()
# Attribute generator 
toolbox.register("attr_bool", random.randint, 0, 1)
# Structure initializers
toolbox.register("individual", tools.initRepeat, creator.Individual, 
    toolbox.attr_bool, 100)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

在这个代码块中，我们注册了一个生成函数 toolbox.attr_bool() 和两个初始化函数 individual() 和 population()。toolbox.attr_bool() 在调用时，将随机抽取一个介于 0 和 1 之间的整数。另一方面，这两个初始化函数将实例化一个个体或种群。

将工具注册到工具箱仅将别名关联到已存在的函数，并冻结其部分参数。这使我们能够将任意数量的参数固定为特定值，从而在调用方法时只需指定剩余的参数。例如，attr_bool() 生成器由 randint() 函数生成，该函数接受两个参数 a 和 b，满足 a <= n <= b，其中 n 是返回的整数。在这里，我们将 a = 0 和 b = 1 固定。

我们的个体将使用函数 initRepeat() 生成。它的第一个参数是一个容器类，在我们的例子中是我们在上一节中定义的 Individual 类。这个容器将使用作为第二个参数提供的方法 attr_bool() 填充，并将包含100个整数，如使用第三个参数指定的那样。当调用时，individual() 方法将返回一个初始化的个体，该个体包含通过调用 attr_bool() 方法100次返回的内容。最后，population() 方法使用相同的方法，但我们不固定它应包含的个体数量。

评估函数¶

在我们的示例中，评估函数非常简单。我们只需要计算个体中1的数量。

def evalOneMax(individual):
    return sum(individual),

返回值必须是一个长度等于目标数量（权重）的可迭代对象。

遗传算子¶

在 DEAP 中，有两种使用操作符的方法。我们可以直接从 tools 模块调用一个函数，或者像我们已经为初始化方法所做的那样，在工具箱中注册它及其参数。然而，最方便的方法是在工具箱中注册它们，因为这允许我们根据需要轻松地在操作符之间切换。当使用 algorithms 模块时，也使用工具箱方法。请参阅最大值问题：简短版本以获取示例。

在我们的 One Max 问题中，注册进化所需的遗传操作符及其在工具箱中的默认参数，操作如下。

toolbox.register("evaluate", evalOneMax)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)

评估将通过调用别名 evaluate 来执行。在这里不固定其参数是很重要的。我们稍后需要它来将函数应用于我们种群中的每个单独个体。另一方面，变异需要一个参数被固定（每个属性被变异的不依赖概率 indpb）。

进化种群¶

一旦选择了表示形式和遗传算子，我们将定义一个结合所有部分并执行种群进化的算法，直到解决One Max问题。在编程中，将其放在一个函数中是一种良好的风格，通常命名为 main()。

创建人口¶

首先，我们需要实际实例化我们的种群。但这一步可以通过我们之前在工具箱中注册的 population() 方法轻松完成。

def main():
    pop = toolbox.population(n=300)

pop 将是一个由 300 个个体组成的 列表 。由于我们在工具箱中注册 population() 方法时没有指定参数 n ，因此我们可以自由创建任意大小的种群。

接下来要做的是评估我们全新的种群。

    # Evaluate the entire population
    fitnesses = list(map(toolbox.evaluate, pop))
    for ind, fit in zip(pop, fitnesses):
        ind.fitness.values = fit

我们将 map() 评估函数应用于每一个个体，然后分配他们各自的适应度。注意，fitnesses 和 population 中的顺序是一致的。

在我们继续之前，现在是定义一些我们稍后会用到的常量的时候了。

    # CXPB  is the probability with which two individuals
    #       are crossed
    #
    # MUTPB is the probability for mutating an individual
    CXPB, MUTPB = 0.5, 0.2

执行进化¶

人口的进化是我们必须完成的最后一步。回想一下，我们的个体由100个整数组成，我们希望进化我们的种群，直到我们至少有一个个体只包含 1 而没有 0。所以我们所要做的就是获得个体的适应度值。

    # Extracting all the fitnesses of 
    fits = [ind.fitness.values[0] for ind in pop]

并在我们的种群中进化，直到其中一个达到 100 或代数达到 1000。

    # Variable keeping track of the number of generations
    g = 0

    # Begin the evolution
    while max(fits) < 100 and g < 1000:
        # A new generation
        g = g + 1
        print("-- Generation %i --" % g)

进化过程本身将通过选择、交配和变异我们种群中的个体来执行。

在我们的遗传算法简单示例中，第一步是选择下一代。

        # Select the next generation individuals
        offspring = toolbox.select(pop, len(pop))
        # Clone the selected individuals
        offspring = list(map(toolbox.clone, offspring))

这将创建一个后代列表，它是所选个体的完全副本。toolbox.clone() 方法确保我们不使用对个体的引用，而是一个完全独立的实例。这是极其重要的，因为工具箱中的遗传操作符将就地修改提供的对象。

接下来，我们将以一定的概率 CXPB 和 MUTPB 对产生的子代进行交叉（交配）和变异。del 语句将使修改后的子代的适应度失效。

        # Apply crossover and mutation on the offspring
        for child1, child2 in zip(offspring[::2], offspring[1::2]):
            if random.random() < CXPB:
                toolbox.mate(child1, child2)
                del child1.fitness.values
                del child2.fitness.values

        for mutant in offspring:
            if random.random() < MUTPB:
                toolbox.mutate(mutant)
                del mutant.fitness.values

DEAP 中提供的交叉（或配对）和变异操作符通常分别以 2 个或 1 个个体作为输入，并返回 2 个或 1 个修改后的个体。此外，它们在工具箱容器内修改这些个体，我们不需要重新分配它们的结果。

由于我们的一些后代的内容在上一步中发生了变化，我们现在需要重新评估它们的适应性。为了节省时间和资源，我们只映射那些适应性被标记为无效的后代。

        # Evaluate the individuals with an invalid fitness
        invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
        fitnesses = map(toolbox.evaluate, invalid_ind)
        for ind, fit in zip(invalid_ind, fitnesses):
            ind.fitness.values = fit

最后但同样重要的是，我们用后代替换旧的种群。

        pop[:] = offspring

为了检查进化的性能，我们将计算并打印种群中所有个体的适应度的最小值、最大值、平均值以及它们的标准差。

        # Gather all the fitnesses in one list and print the stats
        fits = [ind.fitness.values[0] for ind in pop]

        length = len(pop)
        mean = sum(fits) / length
        sum2 = sum(x*x for x in fits)
        std = abs(sum2 / length - mean**2)**0.5

        print("  Min %s" % min(fits))
        print("  Max %s" % max(fits))
        print("  Avg %s" % mean)
        print("  Std %s" % std)

这一进化过程将一直运行，直到至少有一个个体完全被 1 填满。

在DEAP中，可以使用 Statistics 对象来方便地收集进化统计数据。有关示例，请参见最大值问题：简短版本。

此示例的完整源代码：examples/ga/onemax。