遗传算法理解与代码实战（二）- demo（python+deap）

前文介绍了遗传算法，并且手动python代码进行了实践，但是在遇到复杂的问题时（遗传算法理解与代码实战（三）会介绍），手写代码很麻烦，所以需要借助专门的遗传算法库来实现，这里我们选择deap库

1、DEAP简介

1.1 核心模块

在DEAP库中，algorithms、base、creator和tools是核心模块，它们提供了构建和运行进化算法所需的各种组件和工具。下面是对这些模块的简要介绍和使用方法：

creator

creator模块用于创建新的类，这些类可以用于表示个体、适应度、策略等。通过使用creator.create函数，可以定义具有特定属性和方法的类。
使用方法：

from deap import creator
# 创建一个表示个体的新类
creator.create("Individual", list, fitness=creator.FitnessMax)
# 创建一个表示适应度的新类
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
# 创建一个具有特定属性和方法的类
creator.create("MyClass", object, attr1=value1, attr2=value2)

base

base模块提供了进化算法的基本工具和组件，如种群、个体、适应度等。它还提供了遗传操作的基本函数，如选择、交叉和变异。
使用方法：

from deap import base
# 创建一个个体类
ind_class = base.Toolbox()
# 注册一个个体创建函数
ind_class.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_float, n=5)
# 创建一个种群类
pop_class = base.Toolbox()
# 注册一个种群创建函数
pop_class.register("population", tools.initRepeat, list, ind_class.individual)

tools

tools模块提供了许多有用的工具和函数，用于执行遗传操作、统计信息收集、可视化等。
使用方法：

from deap import tools
# 注册一个评估函数
toolbox.register("evaluate", my_evaluation_function)
# 注册一个选择函数
toolbox.register("select", tools.selTournament, tournsize=3)
# 注册一个交叉函数
toolbox.register("mate", tools.cxTwoPoint)
# 注册一个变异函数
toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=1, indpb=0.1)
# 创建一个统计数据对象
stats = tools.Statistics(key=lambda ind: ind.fitness.values)
stats.register("avg", np.mean)
stats.register("min", np.min)
stats.register("max", np.max)
# 创建一个名人堂对象，用于存储最佳个体
hof = tools.HallOfFame(1)

algorithms

algorithms模块提供了各种预定义的进化算法，如简单遗传算法（eaSimple）、遗传编程（eaGP）等。这些算法可以轻松地与toolbox中的组件结合使用。
使用方法：

from deap import algorithms
# 创建一个初始种群
pop = toolbox.population(n=50)
# 运行简单遗传算法
pop, logbook = algorithms.eaSimple(pop, toolbox, cxpb=0.7, mutpb=0.1, ngen=50, stats=stats, halloffame=hof, verbose=True)
# 打印最佳个体
print("Best individual: ", hof[0])

1.2 核心组件

DEAP的核心组件包括：

个体（Individual）：表示问题的一个潜在解决方案。
种群（Population）：个体的集合，表示一代中的所有解决方案。
适应度（Fitness）：评估个体质量的手段，通常是一个或多个数值。
选择（Selection）：从种群中选择个体以繁殖后代的过程。
交叉（Crossover）：交换两个个体的部分基因以创建新的后代。
变异（Mutation）：改变个体基因的过程，以增加种群的多样性。

1.3 主体流程

使用DEAP（Distributed Evolutionary Algorithms in Python）库进行建模的流程通常包括以下几个步骤：

导入库和模块：
首先，你需要导入DEAP库以及你将使用的具体模块，如base、creator、tools和algorithms。
定义问题：
- 创建个体类和适应度类。使用creator模块创建适应度类（如FitnessMax或FitnessMin），以及个体类（如Individual），这些类将用于表示遗传算法中的个体和它们的适应度。
- 确定问题的目标是最小化还是最大化，并相应地设置适应度类的权重。
初始化工具箱：
- 使用base.Toolbox类创建一个工具箱实例，工具箱将包含所有用于生成和操作个体的工具。
- 注册基因生成器（如attr_bool、attr_float等），个体生成器（如individual），种群生成器（如population）等。
定义适应度函数：
- 编写一个函数，用于评估个体的适应度。这个函数将接受一个个体作为输入，并返回一个表示其适应度的值（对于FitnessMax，通常是一个正值；对于FitnessMin，通常是一个负值）。
注册遗传操作：
- 使用工具箱注册遗传操作，如选择（select）、交叉（mate）、变异（mutate）等。
- 你可以选择DEAP提供的预定义操作，也可以自定义自己的操作。
实现遗传算法主循环：
- 编写一个主函数（如main），在其中创建初始种群，并执行遗传算法的迭代过程。
- 在每次迭代中，对种群进行选择、交叉、变异，并评估新生个体的适应度。
- 更新种群，并记录所需的统计数据或最佳个体。
分析和可视化结果：
- 在遗传算法运行结束后，分析结果，可能包括最佳个体的适应度、种群的进化趋势等。
- 使用DEAP提供的工具或第三方库（如Matplotlib）进行可视化。
调优和测试：
- 根据结果调整遗传算法的参数，如种群大小、交叉和变异概率等。
- 进行多次实验，以验证算法的稳定性和性能。

2、代码实战

目标函数： $y=x^2$
x的取值范围是[0，31]

我们根据前面的流程来尽心操作

2.1 定义问题

# 定义问题：求最大化问题
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)

2.2 初始化工具箱

# 初始化
toolbox = base.Toolbox()

# 定义如何生成一个属性（即基因），这里使用0到1的随机整数
toolbox.register("attr_bool", random.randint, 0, 1)

# 定义个体如何生成：创建一个个体，其中包含5个基因
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_bool, n=5)

# 定义种群如何生成：种群由个体组成
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

attr_bool：
attr_bool通常用于生成布尔值（True或False）的基因。在遗传算法中，这通常代表个体的一个二进制特征。
例如，你可以使用attr_bool来生成一个由随机布尔值组成的个体，这些值可以表示遗传算法中的二进制字符串。
attr_float：
attr_float用于生成浮点数的基因。这在处理连续优化问题时非常有用，其中个体的特征需要是实数值。
你可以指定浮点数的范围，例如，attr_float(0.0, 1.0)将生成一个在0.0到1.0之间均匀分布的随机浮点数。
tools.initRepeat是一个函数，用于创建一个个体，其中包含重复的基因。这个函数可以接受以下参数：
- container：一个用于创建个体的类或类型。通常，这是使用creator模块定义的个体类。
- func：一个函数，用于生成个体的单个基因。这个函数可以是toolbox.attr_bool、toolbox.attr_float等。
- n：一个整数，表示个体中基因的数量。
- *args：额外的位置参数，将传递给func。
- **kwargs：额外的关键字参数，将传递给func。

toolbox.individual()
[1, 0, 0, 0, 1]

toolbox.population(10)
[[1, 0, 0, 1, 1],
 [1, 0, 1, 0, 0],
 [0, 1, 1, 1, 0],
 [1, 1, 0, 1, 1],
 [1, 0, 1, 0, 1],
 [0, 0, 0, 1, 0],
 [1, 1, 0, 1, 1],
 [0, 1, 1, 1, 1],
 [0, 0, 0, 0, 0],
 [0, 1, 1, 1, 0]]

2.3 定义适应度函数

# 定义适应度函数
def evalOneMax(individual):
    # 将二进制转换为十进制
    x = int("".join(str(i) for i in individual), 2)
    # 计算适应度
    return x**2,
# 将适应度函数与个体评估过程绑定
toolbox.register("evaluate", evalOneMax)

这个与之前一样不过多介绍

2.4 注册遗传操作



# 注册遗传算法操作：交叉、变异、选择
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)

toolbox.register("mate", tools.cxTwoPoint)：
这一行将两点交叉操作（cxTwoPoint）注册到工具箱中，键为"mate"。两点交叉是一种常用的交叉操作，它选择两个交叉点，并交换两个父代个体在这两点之间的基因段来创建两个子代个体。
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)：
这一行将位翻转变异操作（mutFlipBit）注册到工具箱中，键为"mutate"。位翻转变异会随机选择个体的基因位并进行翻转（0变为1，1变为0）。indpb参数是每个基因发生变异的概率，这里是0.05，意味着每个基因有5%的概率发生变异。
toolbox.register("select", tools.selTournament, tournsize=3)：
这一行将锦标赛选择操作（selTournament）注册到工具箱中，键为"select"。锦标赛选择是一种选择方法，它从种群中随机选择一定数量的个体（这里由tournsize参数指定为3个），然后选择其中适应度最高的个体作为父代。这种方法有助于增加种群的多样性并防止过早收敛。

2.5 实现遗传算法主循环

def main():
    random.seed(64)
    # 创建初始种群
    pop = toolbox.population(n=50)

    # CXPB 为交叉概率，MUTPB 为变异概率
    CXPB, MUTPB, NGEN = 0.5, 0.2, 40

    # 初始种群的适应度评估
    fitnesses = list(map(toolbox.evaluate, pop))
    for ind, fit in zip(pop, fitnesses):
        ind.fitness.values = fit

    # 遗传算法循环
    for g in range(NGEN):
        # 选择下一代
        offspring = toolbox.select(pop, len(pop))
        offspring = list(map(toolbox.clone, 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

        # 重新评估变异和交叉后个体的适应度
        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

        # 输出当前代的最佳个体
        fits = [ind.fitness.values[0] for ind in pop]
        length = len(pop)
        mean = sum(fits) / length
        max_fit = max(fits)
        print(f"代 {g}, 最大适应度 {max_fit}")

    best_ind = tools.selBest(pop, 1)[0]
    print("最佳个体是 %s, %s" % (best_ind, best_ind.fitness.values))

# 初始种群的适应度评估
fitnesses = list(map(toolbox.evaluate, pop))
for ind, fit in zip(pop, fitnesses):
    ind.fitness.values = fit

初始化一个种群并计算这个种群中每个个体的适应度，为遗传算法的后续迭代过程做准备。
遍历完成后我们可以打印下种群的数据

for ind in pop:
    print(ind, ind.fitness.values)

[0, 0, 1, 0, 1] (25.0,)
[0, 1, 0, 1, 1] (121.0,)
[0, 0, 0, 1, 1] (9.0,)
[1, 0, 1, 0, 1] (441.0,)
[1, 0, 1, 1, 0] (484.0,)
[1, 0, 1, 0, 1] (441.0,)
[1, 1, 1, 0, 0] (784.0,)
……

toolbox.select(pop, len(pop)) 这行代码的作用是从当前种群（pop）中选择出新的后代种群，选择的数量与当前种群数量（len(pop)）相同。选择过程通常基于个体的适应度，适应度高的个体有更大的概率被选中。
offspring = list(map(toolbox.clone, offspring)) 这行代码的作用是对选中的后代个体进行克隆。在DEAP库中，个体（Individual）是通过列表（list）实现的，而在遗传算法中，为了避免在操作过程中修改原始种群，通常会对选中的个体进行克隆。map(toolbox.clone, offspring) 对 offspring 中的每个个体执行 toolbox.clone 函数，返回一个克隆个体的迭代器。list() 函数将这个迭代器转换为列表，从而得到一个包含克隆个体的新种群。

# 交叉和变异
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

zip(offspring[::2], offspring[1::2]) 创建了一个迭代器，它将 offspring 列表中的个体两两配对。offspring[::2] 表示选择 offspring 列表中的所有偶数索引个体，而 offspring[1::2] 表示选择所有奇数索引个体。这样，每次迭代都会得到一对个体（child1 和 child2）。
if random.random() < CXPB: 检查一个随机数是否小于交叉概率（CXPB）。如果条件为真，则执行交叉操作；否则，不执行交叉，这对个体将保持不变。
toolbox.mate(child1, child2) 调用注册到工具箱中的交叉操作函数（在这个例子中是 tools.cxTwoPoint，两点交叉），对 child1 和 child2 进行交叉，生成新的后代。这个函数会修改 child1 和 child2 的基因（即它们的属性）。
del child1.fitness.values 和 del child2.fitness.values 删除 child1 和 child2 的适应度值。这是因为交叉操作改变了个体的基因，因此它们之前的适应度值不再有效。在后续的代码中，需要重新评估这些个体的适应度。

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

for mutant in offspring: 这个循环遍历所有后代个体（offspring 列表中的每个个体）。
if random.random() < MUTPB: 检查一个随机数是否小于变异概率（MUTPB）。如果条件为真，则对当前遍历到的个体（mutant）执行变异操作；否则，不执行变异，该个体将保持不变。
toolbox.mutate(mutant) 调用注册到工具箱中的变异操作函数，对 mutant 进行变异。在这个例子中，变异操作函数是 tools.mutFlipBit，它随机翻转个体基因中的一个位（bit）。
del mutant.fitness.values 删除 mutant 的适应度值。这是因为变异操作改变了个体的基因，因此它们之前的适应度值不再有效。在后续的代码中，需要重新评估这些个体的适应度。

在这里插入图片描述

# 重新评估变异和交叉后个体的适应度
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

invalid_ind = [ind for ind in offspring if not ind.fitness.valid] 这行代码使用列表推导式创建一个新列表，包含所有适应度无效的个体。在DEAP库中，个体的适应度可以通过 ind.fitness.valid 属性来检查是否有效。如果个体经历了交叉或变异，其适应度通常会标记为无效。
fitnesses = map(toolbox.evaluate, invalid_ind) 使用 map 函数和工具箱中的 evaluate 函数来计算 invalid_ind 列表中所有个体的适应度。toolbox.evaluate 是之前注册的适应度函数，用于评估个体的适应度。
for ind, fit in zip(invalid_ind, fitnesses): 这个循环遍历所有无效个体和它们的适应度值。
- ind.fitness.values = fit 将计算出的适应度值赋给对应的个体。这样，每个经过交叉或变异的个体的适应度就被更新为最新的值。

pop[:] = offspring

  # 输出当前代的最佳个体
  fits = [ind.fitness.values[0] for ind in pop]
  length = len(pop)
  mean = sum(fits) / length
  max_fit = max(fits)
  print(f"代 {g}, 最大适应度 {max_fit}")

这段代码是将新的后代种群（offspring）替换当前的种群（pop），并输出当前种群中最佳个体的适应度。下面是这段代码的详细解释：

pop[:] = offspring 这行代码将新的后代种群（offspring）替换当前的种群（pop）。在Python中，pop[:] 表示对整个种群列表的引用，而 offspring 是通过选择、交叉和变异操作产生的新种群。这行代码实际上是更新了 pop 列表的内容，使其包含新一代的个体。
fits = [ind.fitness.values[0] for ind in pop] 这行代码使用列表推导式来创建一个新列表，包含当前种群（pop）中每个个体的适应度值。在DEAP库中，个体的适应度值通常是一个元组，即使对于单目标优化问题也是如此。因此，ind.fitness.values[0] 用于获取适应度元组中的第一个元素，即实际的适应度值。
length = len(pop) 获取当前种群的大小（个体数量）。
mean = sum(fits) / length 计算当前种群的平均适应度。sum(fits) 计算所有个体适应度的总和，然后除以种群大小（length）得到平均值。
max_fit = max(fits) 找出当前种群中的最佳适应度值。
print(f"代 {g}, 最大适应度 {max_fit}") 这行代码打印出当前代数（g）和种群中的最大适应度值（max_fit）。这是为了监控算法的进度和性能。

代 0, 最大适应度 961.0
代 1, 最大适应度 961.0
代 2, 最大适应度 961.0
代 3, 最大适应度 961.0
代 4, 最大适应度 961.0
代 5, 最大适应度 961.0
代 6, 最大适应度 961.0
代 7, 最大适应度 961.0
代 8, 最大适应度 961.0
代 9, 最大适应度 961.0
最佳个体是 [1, 1, 1, 1, 1], (961.0,)