遗传算法(Genetic Algorithm)之deap学习笔记(一): 基础概念

遗传算法是通过计算机模拟生物学中的染色体用于解决最优化的一种搜索算法。

使用遗传算法要考虑的因素：

  • 个体表征(Individual representation)

  • 评估和适应度分配(Evaluation and fitness assignment)

  • 选择(Selection)

  • 变化(variation)，比如变异(Mutation)和交叉(Crossover)

  • 停止标准(Stopping criterion)，确定算法何时应该停止，要么是因为达到最佳值，要么是因为优化过程没有进行。

一般来说遗传算法的结构为：

def evolutionary_algorithm():

    population = [] # a list with all the individuals in the population

    population =  initialize_population(pop_size)
    t = 0

    while not stop_criterion( population[t] ):
        fitnesses = evaluate( population[t] )
        populations[t+1] = environmental_selection( population[t], offspring )
        offspring = mating_and_mutation( population[t], fitnesses )
        t = t+1

DEAP是一个用于遗传算法计算的 Python 库：

https://deap.readthedocs.io/en/master/

DEAP GA 的基本特征：

  • deap.creator: 一个允许创建满足进化算法需求的类。

  • deap.base.Toolbox: 包含进化运算符的进化工具箱。可以使用 register() 方法任何与其他函数填充工具箱。

  • deap.base.Fitness([values]): 适应度是用于测量解决方案的质量的一个度量。 如果值作为元组提供，则使用这些值初始化适应度，否则为空（或无效）。 一般应该继承这个类来定义自己的适应度。

个体表征(Individual representation):

首先，定义个体及其特征

import random

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

IND_SIZE = 5

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

toolbox1 = base.Toolbox()
toolbox1.register("attr_float", random.random)
toolbox1.register("individual", tools.initRepeat, creator.Individual,
                 toolbox1.attr_float, n=IND_SIZE)

现在可以构建第一个个体：

ind1 = toolbox1.individual()

打印个体 ind1 并检查其适应性：

print(ind1)
# 应该为类似于这样的信息
# [0.9841619462895895, 0.9475698700500977, 0.05339882337867663, 0.31524481600878207, 0.9304010252473477]
ind1.fitness.valid
# False

个体被打印为为列表并且适应度无效，因为它不包含任何值。

定义个体群体

现在可以在register中注册一个人口来填充个体

toolbox1.register("population", tools.initRepeat, list, toolbox1.individual)

然后用它来创建初始种群。

pop = toolbox1.population(n=20) # 20

第一个个体：

print( pop[0] )
# [0.9945252850424942, 0.7557223153142187, 0.6154978995613851, 0.433930220107276, 0.9700488979770402]

评估和适应度分配(Evaluation and fitness assignment):

看第一个个体的评价，就是算法中评价适应度的部分。 对于某些问题，可以通过许多不同的方式进行评估，其中一些比其他的更好。

在 DEAP 中：

  • 典型的评估函数将一个个体作为参数，并将其适应度作为元组返回。

  • 适应度是一个浮点值列表，并且具有一个有效的属性，可以知道这个个体是否应该被重新评估。

  • 通过将值设置为关联的元组来设置适应度。

例如，下面评估先前创建的个体 ind1 并将其适应度分配给相应的值：

def evaluate(individual):
     a = sum(individual)
    return a,

在 DEAP 中处理单一适应度测量没有什么不同。 评估函数仍必须返回一个元组，因为单测度适应度被视为多测度（多目标）适应度的特例。

如果要评估一个个体，只需调用评估函数即可。 当传递了完整的个体，然后返回到适应度元组，再将其分配给个体适应度值。

ind1 = pop[0]
ind1.fitness.values = evaluate(ind1)
print(ind1.fitness.valid)
# True
print(ind1)
# [0.9945252850424942, 0.7557223153142187, 0.6154978995613851, 0.433930220107276, 0.9700488979770402]
ind1.fitness.values
# (3.769724618002414,)

选择(Selection)

通过 deap.operators 模块中可用的选择运算符在种群中进行选择。

选择运算符通常将一个可迭代的个体容器和要选择的个体数量作为第一个参数。 它返回一个列表，其中包含对所选个体的引用。

首先，我们必须评估每个个体的适应度。 我们只想评估发生变化的个体的适应性，但是初始种群中没有个体的适应度是已知的，因此我们必须首先评估所有个体。

fitnesses = list(map(evaluate, pop))

这为我们提供了与群体中每个个体对应的适应度值列表。 接下来，我们将适应度分配给每个个体。可以使用 zip将具有相应适应度的个体排列起来。

for ind, fit in zip(pop, fitnesses):
    ind.fitness.values = fit

在下面的代码中，我们使用一种方法来选择人口中排名前 2 的个体。

selected = tools.selBest(pop, 2)

检查是否成功地选择了群体中位置为 0 的个体

pop[0] in selected
# False

因此，我们最终得到一份“选定”个体的列表，这些个体可能能够繁殖到下一代。

变异(Mutation)

deap.tools 模块中有多种变异算子。每个突变都有自己的特点，可以应用于不同类型的个体。

要对第一个个体应用突变（此处为高斯突变(gaussian mutation)），只需应用所需的函数即可。

pop[0]
# [0.9945252850424942,
# 0.7557223153142187,
# 0.6154978995613851,
# 0.433930220107276,
# 0.9700488979770402]

tools.mutGaussian(pop[0], mu=0.0, sigma=0.2, indpb=0.2)
# ([1.106753515634373,
#  0.34892623294563724,
#  0.6154978995613851,
#  0.6722066739974353,
#  1.4913149064117197],)

Mu 和 sigma 是高斯曲线的项，indpb 是每个基因突变的独立概率。

我们还需要删除个体的 fitness.value，因为它已经发生变化，需要在下次我们需要它的适应性时重新评估。

del pop[0].fitness.values

DEAP 中的变异运算符具有破坏性，并会就地突变原始个体。 因此，如果要保留原始父突变前，就必须提前复制。 我们可以使用toolbox中的克隆功能克隆一个个体。

mutant = toolbox1.clone(pop[0])
tools.mutGaussian(mutant, mu=0.0, sigma=0.2, indpb=0.2)
del mutant.fitness.values

交叉(Crossover)

deap.tools 模块中有多种交叉算子。每个算子都有自己的特点，可能适用于不同类型的个体。与变异一样，交叉具有破坏性，因此通常需要先复制个体。

下面是克隆种群中前两个个体然后将它们相互交叉的示例

child1, child2 = [ toolbox1.clone(ind) for ind in (pop[0], pop[1]) ]
tools.cxOnePoint(child1, child2)
del child1.fitness.values
del child2.fitness.values

和变异一样，因为我们对个体做了改变，所以需要删除它们的 fitness.values 以便下次重新评估它们。

通常需要设置一个交叉的概率：

cxProb = 0.6

if random.random() < cxProb:
    child1, child2 = [ toolbox1.clone(ind) for ind in (pop[0], pop[1]) ]
    tools.cxOnePoint(child1, child2)
    del child1.fitness.values
    del child2.fitness.values

将运算符和toolbox一起使用

toolbox基本上有两种方法，register() 和 unregister()，用于在toolbox中添加或删除。

比如：

def evaluateInd(individual):
    return result,

toolbox1.register("mate", tools.cxOnePoint)
toolbox1.register("mutate", tools.mutGaussian, mu=0, sigma=1, indpb=0.2)
toolbox1.register("select", tools.selTournament, tournsize=3)
toolbox1.register("evaluate", evaluateInd)

现在可以通过调用toolbox来调用：比如mutate，它将使用注册时的默认参数

mutant = toolbox1.clone(pop[0])
toolbox1.mutate(mutant)
del mutant.fitness.values

这个笔记简单的介绍了DEAP中遗传算法的结构，后续会继续更新更深层的学习内容。