使用 Python 进行 AI – 遗传算法
使用 Python 进行人工智能 – 遗传算法
Section titled “使用 Python 进行人工智能 – 遗传算法”本章深入探讨 遗传算法 (Genetic Algorithms, GAs)，这是一类受查尔斯·达尔文自然进化论启发的有趣的优化算法。我们将探讨其原理，并使用 DEAP 库在 Python 中实现它们。
什么是遗传算法？
Section titled “什么是遗传算法？”遗传算法是基于搜索的启发式方法，模仿自然选择和遗传过程。它们属于更大的 进化算法 (Evolutionary Algorithms, EAs) 家族。遗传算法特别适合解决传统方法可能难以应对的复杂优化和搜索问题。
遗传算法主要由 John Holland 及其合作者开发，它们在一个潜在解决方案群体（称为 个体 (individuals) 或 染色体 (chromosomes)）上进行操作。通过选择 (selection)、交叉 (crossover)（重组 (recombination)）和 变异 (mutation) 等机制，群体经过多代进化，逐步产生更好的解决方案。
遗传算法中的关键概念：
- 群体 (Population)：问题候选解决方案的集合。
- 染色体 (Chromosome)（个体 (Individual)）：单个候选解决方案，通常表示为基因串（例如，二进制字符串、数字列表）。
- 基因 (Gene)：染色体的基本组成部分，代表解决方案的一部分。
- 适应度函数 (Fitness Function)：评估解决方案（染色体）好坏的函数。适应度越高表示解决方案越好。
- 选择 (Selection)：从当前群体中选择个体作为下一代父代的过程。适应度较高的个体有更高的机会被选中（适者生存）。
- 交叉 (Crossover)（重组 (Recombination)）：结合两个父代染色体的遗传物质以创建后代。这允许探索新的解决方案区域。
- 变异 (Mutation)：随机改变染色体中的一个或多个基因。这增加了群体的多样性，并有助于逃离 局部最优 (local optima)。
遗传算法平衡了 探索 (exploration)（搜索解决方案空间的新区域）和 利用 (exploitation)（专注于目前找到的有前途的区域）。
使用遗传算法解决优化问题
Section titled “使用遗传算法解决优化问题”优化 (Optimization) 通常是通过最大化或最小化 目标函数 (objective function)，从一组可行解中找到最佳解决方案。遗传算法为此提供了一个强大的框架。
优化过程图的文字描述：优化过程可以可视化为一个循环。它始于一个“初始猜测/解决方案”。这个解决方案被输入到“系统模型/目标函数”中，产生“性能指标”。这些指标随后由“优化算法”（如遗传算法）进行分析。算法生成一个“新的/改进的解决方案”，然后作为新的“初始猜测/解决方案”反馈回去，循环继续，直到找到满意的解决方案或满足终止条件。
遗传算法的一般步骤
Section titled “遗传算法的一般步骤”- 初始化 (Initialization)：创建一个由随机候选解组成的初始群体。
- 评估 (Evaluation)：使用适应度函数计算群体中每个个体的适应度。
- 选择 (Selection)：根据个体的适应度选择父代个体。
- 交叉 (Crossover)：对选定的父代对应用交叉算子以创建后代。
- 变异 (Mutation)：以一定概率对后代（有时也对父代）应用变异算子。
- 替换 (Replacement)：形成下一代的新群体，通常通过用新后代（有时也包括上一代中的精英个体）替换部分或全部旧群体。
- 终止 (Termination)：重复步骤 2-6，直到满足终止条件（例如，达到最大代数、达到适应度阈值、连续多代没有改进）。
安装必需的软件包：DEAP
Section titled “安装必需的软件包：DEAP”为了在 Python 中实现遗传算法，我们将使用 DEAP (Distributed Evolutionary Algorithms in Python)，这是一个功能强大且灵活的进化计算库。通过 pip 安装：
pip install deap numpy matplotlib如果你正在使用 Anaconda，也可以尝试：
conda install -c conda-forge deap使用 DEAP 实现遗传算法解决方案
Section titled “使用 DEAP 实现遗传算法解决方案”DEAP 提供了定义个体、群体、遗传算子和进化算法的工具。让我们探索两个示例。
示例 1：OneMax 问题 (最大化二进制字符串中的 1)
Section titled “示例 1：OneMax 问题 (最大化二进制字符串中的 1)”OneMax 问题是遗传算法中的一个经典玩具问题。目标是进化一个二进制字符串（0 和 1 的列表），使其包含尽可能多的 1。对于长度为 N 的字符串，最优解是一个包含 N 个 1 的字符串。
导入必需的 DEAP 组件和其他库：
import randomimport numpy as npimport matplotlib.pyplot as plt
from deap import base, creator, tools, algorithms
# 问题参数NUM_BITS = 45 # 二进制字符串的长度TARGET_SUM = NUM_BITS # 我们想要全为 1
# --- 1. 定义适应度和个体 ---# 创建一个最大化适应度类 (旨在最大化单个目标)。# weights=(1.0,) 表示我们想要最大化第一个 (也是唯一一个) 目标值。creator.create("FitnessMax", base.Fitness, weights=(1.0,))
# 创建一个个体类：一个带有 FitnessMax 属性的位列表。creator.create("Individual", list, fitness=creator.FitnessMax)
# --- 2. 初始化 Toolbox ---# Toolbox 将存储用于生成个体和群体的函数，以及遗传算子。toolbox = base.Toolbox()
# 属性生成器：定义如何创建一个基因 (位)，值为 0 或 1。toolbox.register("attr_bool", random.randint, 0, 1)
# 个体生成器：定义如何创建一个个体 (染色体)。# tools.initRepeat 调用 toolbox.attr_bool NUM_BITS 次来填充个体。toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_bool, NUM_BITS)
# 群体生成器：定义如何创建一个群体 (个体列表)。toolbox.register("population", tools.initRepeat, list, toolbox.individual)
# --- 3. 定义评估 (适应度) 函数 ---# 此函数计算个体的“适应度”。# 对于 OneMax，适应度是二进制字符串中 1 的数量。def evalOneMax(individual): return sum(individual), # 返回一个元组，因为适应度可以是多目标的
# 在 toolbox 中注册评估函数。toolbox.register("evaluate", evalOneMax)
# --- 4. 注册遗传算子 ---# 交叉算子：两个个体如何组合产生后代。# tools.cxTwoPoint 执行两点交叉。toolbox.register("mate", tools.cxTwoPoint)
# 变异算子：个体如何被随机改变。# tools.mutFlipBit 以概率 indpb (独立概率) 翻转位。toolbox.register("mutate", tools.mutFlipBit, indpb=0.05) # 5% 几率翻转每个位
# 选择算子：如何选择个体作为父代。# tools.selTournament 使用锦标赛选择 (tournsize 是每次锦标赛的个体数量)。toolbox.register("select", tools.selTournament, tournsize=3)
# --- 5. 运行遗传算法 ---def run_onemax_ga(): random.seed(42) # 为了保证结果的可重现性
pop_size = 300 population = toolbox.population(n=pop_size)
# 交叉和变异的概率 prob_crossing, prob_mutating = 0.7, 0.2 # CXPB, MUTPB num_generations = 40
print('Evolution process starts')
# 用于跟踪进化过程中的统计数据 stats = tools.Statistics(lambda ind: ind.fitness.values) stats.register("avg", np.mean) stats.register("std", np.std) stats.register("min", np.min) stats.register("max", np.max)
# 使用 DEAP 算法运行 GA (eaSimple 是一个标准算法)。 # halloffame 存储进化过程中发现的最佳个体。 hof = tools.HallOfFame(1) # 存储单个最佳个体 population, logbook = algorithms.eaSimple(population, toolbox, cxpb=prob_crossing, mutpb=prob_mutating, ngen=num_generations, stats=stats, halloffame=hof, verbose=True)
print('\n- Evolution ends -')
best_individual = hof[0] print(f'\nBest individual found: {best_individual}') print(f'Number of ones: {sum(best_individual)}') print(f'Fitness: {best_individual.fitness.values[0]}')
# 绘制统计图 gen = logbook.select("gen") max_fitness_values = logbook.chapters["fitness"].select("max") avg_fitness_values = logbook.chapters["fitness"].select("avg")
plt.figure(figsize=(10,6)) plt.plot(gen, max_fitness_values, label="Maximum Fitness") plt.plot(gen, avg_fitness_values, label="Average Fitness") plt.xlabel("Generation") plt.ylabel("Fitness") plt.title("Fitness over Generations (OneMax Problem)") plt.legend() plt.grid(True) plt.show()
return population, logbook, hof
if __name__ == "__main__": run_onemax_ga()预期输出 (节选，实际输出会显示每一代的统计数据)：
Evolution process startsgen nevals avg std min max0 300 22.41 3.16842 12 311 216 25.3033 2.93396 17 33... (许多代) ...39 207 44.9 0.3 44 4540 221 44.9367 0.24362 44 45
- Evolution ends -
Best individual found: [1, 1, ..., 1] (一个包含 45 个 1 的列表)Number of ones: 45Fitness: 45.0该图将显示两条线：一条表示最大适应度，另一条表示每代的平均适应度。两者通常都会增加，其中最大适应度会达到目标值（本例中为 45）。这表明遗传算法能够找到最优解。
遗传算法的实际应用：优化调度、物流、工程设计、金融建模，以及训练机器学习模型 (例如，超参数调优、特征选择)。
示例 2：符号回归
Section titled “示例 2：符号回归”符号回归 (Symbolic Regression) 是一种 回归分析 (regression analysis)，它搜索数学表达式空间，以找到最适合给定数据集的模型。与拟合参数到预先指定的模型结构（例如，线性回归）的传统回归不同，符号回归进化的是模型本身的结构。遗传编程 (Genetic Programming, GP) 是遗传算法的一种特殊形式，常用于此目的。
目标：进化一个数学函数（例如，y = f(x)），使其最适合一组 (x, y) 数据点。假设我们的目标函数是 y = x^3 - 2*x^2 + x - 5，我们将生成一些围绕它的带噪声数据。
import operatorimport mathimport randomimport numpy as npimport matplotlib.pyplot as plt
from deap import algorithms, base, creator, tools, gp
# --- 1. 定义原语 (函数和终端) ---# 原语是构建符号表达式 (树) 的基本单元。pset = gp.PrimitiveSet("MAIN", 1) # "MAIN" 是名称，1 是元数 (输入数量，例如 'x')pset.addPrimitive(operator.add, 2) # 加法 (2 个参数)pset.addPrimitive(operator.sub, 2) # 减法 (2 个参数)pset.addPrimitive(operator.mul, 2) # 乘法 (2 个参数)def protected_div(left, right): try: return left / right except ZeroDivisionError: return 1 # 如果除以零，返回一个常数pset.addPrimitive(protected_div, 2) # 受保护的除法pset.addPrimitive(operator.neg, 1) # 取反 (1 个参数)# pset.addPrimitive(math.sin, 1) # 正弦 (可选)# pset.addPrimitive(math.cos, 1) # 余弦 (可选)
# 终端：函数的输入 (例如，像 'x' 这样的变量或常量)pset.addEphemeralConstant("rand101", lambda: random.uniform(-1, 1)) # 介于 -1 和 1 之间的随机常数pset.renameArguments(ARG0='x') # 将输入参数重命名为 'x'
# --- 2. 定义适应度和个体 ---creator.create("FitnessMin", base.Fitness, weights=(-1.0,)) # 我们想要最小化误差creator.create("Individual", gp.PrimitiveTree, fitness=creator.FitnessMin)
# --- 3. 初始化 Toolbox ---toolbox = base.Toolbox()# 表达式生成器：定义如何构建树。# gp.genHalfAndHalf 结合全树和生长树以增加多样性。toolbox.register("expr", gp.genHalfAndHalf, pset=pset, min_=1, max_=3) # 树的最小/最大深度
# 个体和群体生成器toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.expr)toolbox.register("population", tools.initRepeat, list, toolbox.individual)
# 将树编译成可调用的 Python 函数的函数toolbox.register("compile", gp.compile, pset=pset)
# --- 4. 定义评估 (适应度) 函数 ---# 生成一些样本数据用于拟合# 目标函数：y = x^3 - 2*x^2 + x - 5NUM_POINTS = 50X_POINTS = np.linspace(-5, 5, NUM_POINTS)Y_TARGET = X_POINTS**3 - 2*X_POINTS**2 + X_POINTS - 5 + np.random.randn(NUM_POINTS) * 2 # 添加一些噪声
def evalSymbReg(individual, points_x, points_y): # 将 GP 树编译成可调用函数 func = toolbox.compile(expr=individual) # 计算预测 y 值与目标 y 值之间的均方误差 (MSE) try: sqerrors = [(func(x) - y)**2 for x, y in zip(points_x, points_y)] return math.fsum(sqerrors) / len(points_y), # 作为元组返回 except (OverflowError, ValueError): return float('inf'), # 对导致错误的表达式进行惩罚
toolbox.register("evaluate", evalSymbReg, points_x=X_POINTS, points_y=Y_TARGET)
# --- 5. 注册遗传算子 (GP 特有) ---toolbox.register("select", tools.selTournament, tournsize=3)toolbox.register("mate", gp.cxOnePoint) # 树的单点交叉toolbox.register("expr_mut", gp.genFull, min_=0, max_=2) # 变异可以生成小的子树toolbox.register("mutate", gp.mutUniform, expr=toolbox.expr_mut, pset=pset)
# 限制树高度的装饰器 (以防止臃肿)toolbox.decorate("mate", gp.staticLimit(key=operator.attrgetter("height"), max_value=17))toolbox.decorate("mutate", gp.staticLimit(key=operator.attrgetter("height"), max_value=17))
# --- 6. 运行遗传编程算法 ---def run_symbolic_regression_gp(): random.seed(60)
pop_size = 500 population = toolbox.population(n=pop_size) hof = tools.HallOfFame(1)
stats_fit = tools.Statistics(lambda ind: ind.fitness.values) stats_size = tools.Statistics(len) # 树的大小 (节点数量) mstats = tools.MultiStatistics(fitness=stats_fit, size=stats_size) mstats.register("avg", np.mean) mstats.register("std", np.std) mstats.register("min", np.min) mstats.register("max", np.max)
prob_crossing, prob_mutating = 0.8, 0.15 num_generations = 50
print('Symbolic Regression GP process starts') population, logbook = algorithms.eaSimple(population, toolbox, prob_crossing, prob_mutating, num_generations, stats=mstats, halloffame=hof, verbose=True)
print('\n- GP Evolution ends -') best_individual = hof[0] print(f'\nBest individual found (tree structure):\n{best_individual}') print(f'Fitness (MSE): {best_individual.fitness.values[0]}')
# 将最佳树转换为字符串以便阅读 best_func_str = str(best_individual) print(f'As a string: {best_func_str}')
# 绘制适应度和大小随代数的变化图 gen = logbook.select("gen") min_fitness_values = logbook.chapters["fitness"].select("min") avg_fitness_values = logbook.chapters["fitness"].select("avg") avg_size_values = logbook.chapters["size"].select("avg")
fig, ax1 = plt.subplots(figsize=(12,7)) line1 = ax1.plot(gen, min_fitness_values, "b-", label="Minimum Fitness (MSE)") ax1.plot(gen, avg_fitness_values, "g-", label="Average Fitness (MSE)", alpha=0.5) ax1.set_xlabel("Generation") ax1.set_ylabel("Fitness (MSE)", color="b") ax1.tick_params(axis='y', labelcolor='b') ax1.set_yscale('log') # 对适应度分析通常很有用
ax2 = ax1.twinx() line2 = ax2.plot(gen, avg_size_values, "r-", label="Average Tree Size") ax2.set_ylabel("Average Size", color="r") ax2.tick_params(axis='y', labelcolor='r')
lns = line1 + line2 labs = [l.get_label() for l in lns] ax1.legend(lns, labs, loc="center right") plt.title("Symbolic Regression: Fitness and Size over Generations") plt.grid(True) plt.show()
# 绘制最佳个体的拟合图 func_best = toolbox.compile(expr=best_individual) Y_PRED = [func_best(x) for x in X_POINTS] plt.figure(figsize=(10,6)) plt.scatter(X_POINTS, Y_TARGET, color='blue', label='Target Data (noisy)') plt.plot(X_POINTS, Y_PRED, color='red', linewidth=2, label='GP Evolved Function') plt.xlabel('x') plt.ylabel('y') plt.title('Symbolic Regression: Best Evolved Function vs Target Data') plt.legend() plt.grid(True) plt.show()
return population, logbook, hof
if __name__ == "__main__": run_symbolic_regression_gp()预期输出 (节选)：
Symbolic Regression GP process startsgen nevals avg std min max avg std min max0 500 1.11e+06 7.41e+06 12.01 1.01e+08 4.952 1.76492 2 71 412 2.31e+05 2.29e+06 9.65 4.64e+07 5.86 2.72186 2 14... (许多代) ...49 413 205.133 1071.76 2.0101 2.22e+04 12.604 6.0282 2 3150 421 24.2023 135.434 2.0095 2901.17 12.55 6.1135 2 30
- GP Evolution ends -
Best individual found (tree structure):(Example: mul(sub(mul(x, x), x), x)) <-- 这是一个占位符，实际的树会更复杂Fitness (MSE): (例如，2.0095)As a string: (例如，'mul(sub(mul(x, x), x), x)') <-- 树的实际字符串表示形式第一张图将显示适应度（MSE，理想情况下应下降）和平均树大小随代数的变化。第二张图将显示原始的带噪声数据点以及由 GP 进化的函数，展示了它如何很好地拟合数据。进化的函数可能不是恰好等于 x^3 - 2*x^2 + x - 5，但可能是一个接近的近似值，或者是一个也能很好地拟合数据的不同函数形式。
符号回归是科学和工程领域自动化模型发现的强大工具。
更多学习资源：
- DEAP 文档: https://deap.readthedocs.io/en/master/
- 遗传编程实地指南 (作者 Poli, Langdon, McPhee)：一本全面的资源，通常可在网上获取。
- 进化计算导论 (作者 Eiben and Smith)：一本涵盖遗传算法和其他进化算法的教科书。