算法

The algorithms 模块旨在包含一些特定的算法，以便执行非常常见的进化算法。这里使用的方法更多是为了方便而不是参考，因为每个进化算法的实现可能会有无限的变化。该模块中的大多数算法使用在工具箱中注册的运算符。通常，使用的关键词是 mate() 用于交叉，mutate() 用于变异，select() 用于选择，以及 evaluate() 用于评估。

鼓励您编写自己的算法，以便让它们做您真正希望它们做的事情。

完整算法

这些是完全封装的算法，它们在一定程度上局限于非常基本的进化计算概念。除了它们的参数外，所有算法还接受一个初始化的 Statistics 对象来维护进化的统计数据，一个初始化的 HallOfFame 来保存出现在种群中的最佳个体，以及一个布尔值 verbose 来指定是否记录进化过程中发生的事情。

deap.algorithms.eaSimple(population, toolbox, cxpb, mutpb, ngen[, stats, halloffame, verbose])[源代码]

该算法重现了 [Back2000] 第7章中介绍的最简单的进化算法。

参数:

  • population – 个人名单。

  • toolbox – 一个包含进化操作符的 Toolbox。

  • cxpb – 两个个体交配的概率。

  • mutpb – 个体突变的概率。

  • ngen – 代数。

  • stats – 一个 Statistics 对象，可以就地更新，可选。

  • halloffame – 一个 HallOfFame 对象，将包含最佳个体，可选。

  • verbose – 是否记录统计数据。

返回:

最终人口

返回:

一个包含进化统计数据的 Logbook

该算法接收一个种群，并使用 varAnd() 方法就地进化它。它返回优化的种群和一个包含进化统计数据的 Logbook。日志簿将包含代数、每代的评估次数以及如果提供了 Statistics 作为参数时的统计数据。cxpb 和 mutpb 参数传递给 varAnd() 函数。伪代码如下

evaluate(population)
for g in range(ngen):
    population = select(population, len(population))
    offspring = varAnd(population, toolbox, cxpb, mutpb)
    evaluate(offspring)
    population = offspring

如上伪代码所述，算法如下进行。首先，它评估具有无效适应度的个体。其次，它进入代际循环，其中选择过程被应用以完全替换父代种群。该算法的1:1替换比率**要求**选择过程是随机的，并且多次选择相同的个体，例如，selTournament() 和 selRoulette()。第三，它应用 varAnd() 函数来生成下一代种群。第四，它评估新个体并计算该种群的统计数据。最后，当完成 ngen 代时，算法返回一个包含最终种群和进化记录 Logbook 的元组。

备注

使用非随机选择方法将导致没有选择，因为操作符从 n 个个体中选择 n 个。

此函数期望在工具箱中注册 toolbox.mate()、toolbox.mutate()、toolbox.select() 和 toolbox.evaluate() 别名。

[Back2000]

Back, Fogel 和 Michalewicz, “进化计算 1 : 基本算法和操作”, 2000.

deap.algorithms.eaMuPlusLambda(population, toolbox, mu, lambda_, cxpb, mutpb, ngen[, stats, halloffame, verbose])[源代码]

这是 \((\mu + \lambda)\) 进化算法。

参数:

  • population – 个人名单。

  • toolbox – 一个包含进化操作符的 Toolbox。

  • mu – 选择下一代的个体数量。

  • lambda_ – 每一代要产生的子代数量。

  • cxpb – 后代通过交叉产生的概率。

  • mutpb – 后代通过突变产生的概率。

  • ngen – 代数。

  • stats – 一个 Statistics 对象，可以就地更新，可选。

  • halloffame – 一个 HallOfFame 对象，将包含最佳个体，可选。

  • verbose – 是否记录统计数据。

返回:

最终人口

返回:

一个包含进化统计数据的 Logbook。

该算法接收一个种群，并使用 varOr() 函数对其进行原地进化。它返回优化后的种群和一个包含进化统计数据的 Logbook。日志簿将包含代数、每代的评估次数以及如果作为参数提供了 Statistics 的统计数据。cxpb 和 mutpb 参数传递给 varOr() 函数。伪代码如下

evaluate(population)
for g in range(ngen):
    offspring = varOr(population, toolbox, lambda_, cxpb, mutpb)
    evaluate(offspring)
    population = select(population + offspring, mu)

首先，对适应度无效的个体进行评估。其次，进化循环通过从种群中产生 lambda_ 后代开始，后代由 varOr() 函数生成。然后对后代进行评估，并从后代和种群中选择下一代种群。最后，当完成 ngen 代时，算法返回一个包含最终种群和进化记录的 Logbook 的元组。

此函数期望在工具箱中注册 toolbox.mate()、toolbox.mutate()、toolbox.select() 和 toolbox.evaluate() 别名。此算法使用 varOr() 变异。

deap.algorithms.eaMuCommaLambda(population, toolbox, mu, lambda_, cxpb, mutpb, ngen[, stats, halloffame, verbose])[源代码]

这是 \((\mu~,~\lambda)\) 进化算法。

参数:

  • population – 个人名单。

  • toolbox – 一个包含进化操作符的 Toolbox。

  • mu – 选择下一代的个体数量。

  • lambda_ – 每一代要产生的子代数量。

  • cxpb – 后代通过交叉产生的概率。

  • mutpb – 后代通过突变产生的概率。

  • ngen – 代数。

  • stats – 一个 Statistics 对象，可以就地更新，可选。

  • halloffame – 一个 HallOfFame 对象，将包含最佳个体，可选。

  • verbose – 是否记录统计数据。

返回:

最终人口

返回:

一个包含进化统计数据的 Logbook

该算法接收一个种群，并使用 varOr() 函数对其进行原地进化。它返回优化后的种群和一个包含进化统计数据的 Logbook。日志簿将包含代数、每代的评估次数以及如果作为参数提供了 Statistics 的统计数据。cxpb 和 mutpb 参数传递给 varOr() 函数。伪代码如下

evaluate(population)
for g in range(ngen):
    offspring = varOr(population, toolbox, lambda_, cxpb, mutpb)
    evaluate(offspring)
    population = select(offspring, mu)

首先，评估适应度无效的个体。其次，进化循环通过从种群中产生 lambda_ 后代开始，后代由 varOr() 函数生成。然后评估后代，并从 仅 后代中选择下一代种群。最后，当完成 ngen 代时，算法返回一个包含最终种群和进化记录的 Logbook 的元组。

备注

当 lambda:mu 比率为 1 比 1 时，必须小心，因为非随机选择将导致根本没有选择，因为操作符从 mu 的池中选择 lambda 个体。

此函数期望在工具箱中注册 toolbox.mate()、toolbox.mutate()、toolbox.select() 和 toolbox.evaluate() 别名。此算法使用 varOr() 变异。

deap.algorithms.eaGenerateUpdate(toolbox, ngen[, stats, halloffame, verbose])[源代码]

该算法实现了 [Colette2010] 中提出的 ask-tell 模型，其中 ask 称为 generate，tell 称为 update。

参数:

  • toolbox – 一个包含进化操作符的 Toolbox。

  • ngen – 代数。

  • stats – 一个 Statistics 对象，可以就地更新，可选。

  • halloffame – 一个 HallOfFame 对象，将包含最佳个体，可选。

  • verbose – 是否记录统计数据。

返回:

最终人口

返回:

一个包含进化统计数据的 Logbook

该算法使用 toolbox.generate() 函数生成个体，并使用 toolbox.update() 函数更新生成方法。它返回优化的种群和一个包含进化统计数据的 Logbook。如果提供了 Statistics 作为参数，日志簿将包含代数、每代的评估次数以及统计数据。伪代码如下

for g in range(ngen):
    population = toolbox.generate()
    evaluate(population)
    toolbox.update(population)

此函数期望在工具箱中注册 toolbox.generate() 和 toolbox.evaluate() 别名。

[Colette2010]

Collette, Y., N. Hansen, G. Pujol, D. Salazar Aponte 和 R. Le Riche (2010). 关于优化器的面向对象编程 - Scilab 中的示例。在 P. Breitkopf 和 R. F. Coelho 编辑的《计算力学中的多学科设计优化》中，Wiley, pp. 527-565;

变体

变体是算法中较小的部分，可以单独使用来构建更复杂的算法。

deap.algorithms.varAnd(population, toolbox, cxpb, mutpb)[源代码]

进化算法的一部分，仅应用变异部分（交叉 和 突变）。修改后的个体其适应度被视为无效。个体被克隆，因此返回的种群与输入种群无关。

参数:

  • population – 一个需要变动的个人名单。

  • toolbox – 一个包含进化操作符的 Toolbox。

  • cxpb – 两个个体交配的概率。

  • mutpb – 个体突变的概率。

返回:

一个由不同个体组成的列表，这些个体与其父母无关。

变异过程如下。首先，使用 toolbox.clone() 方法复制父代种群 \(P_\mathrm{p}\)，并将结果放入子代种群 \(P_\mathrm{o}\) 中。对 \(P_\mathrm{o}\) 进行第一次遍历，以配对连续的个体。根据交叉概率 cxpb，个体 \(\mathbf{x}_i\) 和 \(\mathbf{x}_{i+1}\) 使用 toolbox.mate() 方法进行配对。生成的子代 \(\mathbf{y}_i\) 和 \(\mathbf{y}_{i+1}\) 替换 \(P_\mathrm{o}\) 中的相应父代。对生成的 \(P_\mathrm{o}\) 进行第二次遍历，以概率 mutpb 对每个个体进行变异。当个体发生变异时，它将替换 \(P_\mathrm{o}\) 中未变异的版本。最终的 \(P_\mathrm{o}\) 被返回。

这种变体因其倾向于对个体同时应用交叉和变异操作而命名为 And。请注意，这两个操作并非系统性地应用，生成的个体可以仅由交叉产生，仅由变异产生，或由交叉和变异共同产生，以及根据给定的概率进行复制。两个概率都应在 \([0, 1]\) 范围内。

deap.algorithms.varOr(population, toolbox, lambda_, cxpb, mutpb)[源代码]

进化算法的一部分，仅应用变异部分（交叉、变异 或 复制）。修改后的个体其适应度被视为无效。个体被克隆，因此返回的种群与输入的种群独立。

参数:

  • population – 一个需要变动的个人名单。

  • toolbox – 一个包含进化操作符的 Toolbox。

  • lambda_ – 要生成的子项数量

  • cxpb – 两个个体交配的概率。

  • mutpb – 个体突变的概率。

返回:

最终人口。

变化如下。在每次 lambda_ 迭代中，它会从三种操作中选择一种：交叉、变异或复制。如果是交叉操作，则从父代种群 \(P_\mathrm{p}\) 中随机选择两个个体，这些个体通过 toolbox.clone() 方法克隆，然后使用 toolbox.mate() 方法进行交配。只有第一个子代被添加到子代种群 \(P_\mathrm{o}\) 中，第二个子代被丢弃。如果是变异操作，则从 \(P_\mathrm{p}\) 中随机选择一个个个体，克隆后使用 toolbox.mutate() 方法进行变异。产生的变异体被添加到 \(P_\mathrm{o}\) 中。如果是复制操作，则从 \(P_\mathrm{p}\) 中随机选择一个个个体，克隆后添加到 \(P_\mathrm{o}\) 中。

这种变异被称为 Or ，因为后代永远不会同时通过交叉和变异操作产生。两种概率之和应在 \([0, 1]\) 范围内，繁殖概率为 1 - cxpb - mutpb。

协方差矩阵自适应进化策略

一个提供协方差矩阵自适应进化策略支持的模块。

class deap.cma.Strategy(centroid, sigma[, **kargs])[源代码]

一种策略，将跟踪CMA-ES算法的基本参数（[Hansen2001]）。

参数:

  • centroid – 一个可迭代对象，指示进化从哪里开始。

  • sigma – 分布的初始标准差。

  • parameter – 一个或多个参数传递给策略，如下表所述，可选。

参数

默认

详情

lambda_

int(4 + 3 * log(N))

每一代产生的子代数量，N 是个体的尺寸（整数）。

mu

int(lambda_ / 2)

从 lambda 子节点中保留的父节点数量（整数）。

cmatrix

identity(N)

将被采样的分布的初始协方差矩阵。

weights

"superlinear"

降低速度，可以是 "superlinear"、"linear" 或 "equal"。

cs

(mueff + 2) / (N + mueff + 3)

步长累积常数。

damps

1 + 2 * max(0, sqrt(( mueff - 1) / (N + 1)) - 1) + cs

步长阻尼。

ccum

4 / (N + 4)

协方差矩阵的累积常数。

ccov1

2 / ((N + 1.3)^2 + mueff)

秩一更新的学习率。

ccovmu

2 * (mueff - 2 + 1 / mueff) / ((N + 2)^2 + mueff)

用于秩-μ更新的学习率。
[Hansen2001]

Hansen 和 Ostermeier, 2001. 完全去随机化的进化策略中的自适应。进化计算

computeParams(params)[源代码]

计算取决于 \(\lambda\) 的参数。如果在进化过程中 \(\lambda\) 发生变化，则需要再次调用。

参数:

params – 手动设置的参数的字典。

generate(ind_init)[源代码]

从当前策略生成一个类型为 ind_init 的 \(\lambda\) 个体种群。

参数:

ind_init – 一个能够从列表初始化个体的函数对象。

返回:

个人名单。

update(population)[源代码]

从 种群 中更新当前的协方差矩阵策略。

参数:

population – 用于更新参数的个体列表。

class deap.cma.StrategyOnePlusLambda(parent, sigma[, **kargs])[源代码]

一种使用 \(1 + \lambda\) 范式的CMA-ES策略（[Igel2007]）。

参数:

  • parent – 一个可迭代对象，指示进化从哪里开始。父对象需要一个适应度属性。

  • sigma – 分布的初始标准差。

  • lambda – 从父代产生的后代数量。（可选，默认为1）

  • parameter – 一个或多个参数传递给策略，如下表所述。（可选）

其他参数可以如下一表所述提供

[Igel2007]

Igel, Hansen, Roth, 2007. 协方差矩阵自适应

多目标优化。 进化计算 春季;15(1):1-28

computeParams(params)[源代码]

计算取决于 \(\lambda\) 的参数。如果在进化过程中 \(\lambda\) 发生变化，则需要再次调用。

参数:

params – 手动设置的参数的字典。

generate(ind_init)[源代码]

从当前策略生成一个类型为 ind_init 的 \(\lambda\) 个体种群。

参数:

ind_init – 一个能够从列表初始化个体的函数对象。

返回:

个人名单。

update(population)[源代码]

从 种群 中更新当前的协方差矩阵策略。

参数:

population – 用于更新参数的个体列表。

class deap.cma.StrategyMultiObjective(population, sigma[, **kargs])[源代码]

基于论文 [Voss2010] 的多目标CMA-ES策略。它与标准的CMA-ES策略类似，采用生成-更新方案。

参数:

  • population – 一个初始的个体种群。

  • sigma – 整个系统的初始步长。

  • mu – 进化中使用的父代数量。如果未提供，则默认为 population 的长度。（可选）

  • lambda – 每代要产生的后代数量。（可选，默认为1）

  • indicator – 要使用的指示函数。（可选，默认为 hypervolume()）

其他参数可以如下一表所述提供

[Voss2010]

Voss, Hansen, Igel, “改进了步长适应的MO-CMA-ES”, 2010.

generate(ind_init)[源代码]

从当前策略生成一个类型为 ind_init 的 \(\lambda\) 个体种群。

参数:

ind_init – 一个能够从列表初始化个体的函数对象。

返回:

一个具有私有属性 _ps 的个体列表。最后一个属性对于更新函数至关重要，它表明该个体是后代，并指示其父代的索引。

update(population)[源代码]

从 群体 中更新当前的协方差矩阵策略。

参数:

population – 用于更新参数的个体列表。