遗传编程

引言

遗传编程（GP）是进化算法或技术的示例，它通过类似于自然生物进化的过程，生成一个能够解决特定问题的程序。这与常规编程不同，常规编程由人类编写代码，而GP则通过选择、交叉和变异来逐步改进程序。其思想是找到并识别一个以程序形式存在的解决方案，该程序能够有效地执行预定的任务或解决问题。

本质上，GP源于随机创建程序种群，然后通过固定的适应度度量来测试其性能，并遵循通过遗传操作进行优化的过程。这种方法使GP能够在广阔的解空间中搜索解决方案，并常常产生一些“跳出框框”的思路。

关键概念和术语

1. 种群（Population）： 在一段时间内开发的候选程序（个体）的集合。在这种方法中，种群中的每个个体都包含对所考虑问题的潜在解决方案。
2. 染色体（程序）： 在GP中，染色体通常代表一个程序。它可以以各种形式构建，包括各种树状结构，其中节点是操作或函数，叶子是输入或常数。
3. 基因（指令）： 无法进一步分解以定义程序的更小组件。树状结构用于此目的，其中基因代表节点和叶子，节点是运算符（加法、乘法等），叶子是终端。
4. 适应度函数（Fitness Function）： 指示程序解决问题效率的指标。适应度函数为每个程序的性能提供反馈，通过使最 fittest 的个体能够繁殖来控制进化过程。
5. 选择（Selection）： 在循环中从现有种群中选择父代和交配后代的个体的过程。GA中使用的一些选择方法包括轮盘赌选择法、锦标赛选择法和秩选择法。
6. 交叉（重组）（Crossover (Recombination)）： 一种通过组合父代程序的片段来创建新程序的算子。在基于树的GP中，这通常涉及父代之间的子树交换，以产生独特的遗传组合。

遗传编程基础

基本组成部分

1. 种群

这里的种群是一组候选程序，它们通过进化过程经历连续的世代。种群中的每个程序都是对所考虑问题的潜在解决方案。

2. 染色体（程序）

在遗传编程中，染色体是对所考虑问题的解决方案的编码。虽然在遗传算法中，染色体通常表示为固定长度的字符串，但在GP中，基因组是计算机程序，通常是树。

• 树表示：节点是实际的函数或可以执行的操作，而叶子是实际的输入或常数。
• 分层结构：便于表示其他复杂的符号和/或动态。

3. 基因（指令）

因此，基因是构成染色体的片段。在遗传编程的上下文中，基因是程序的小个体片段，形式为指令或操作。可以说，在遗传学方面，它们就像生物体的砖块。

• 函数：算术运算（如加法、减法、乘法、除法）、逻辑运算等。
• 终端：要输入程序的数据，或程序常量或变量所取的值。

遗传算子

遗传算子是程序种群在专门为遗传编程设计的环境中进化的过程。它模仿了自然界普遍存在的选择、交叉和变异现象，从父代程序生成子代程序。

1. 选拔

选择是一种从当前种群中挑选最适合繁殖下一代个体的策略，其逻辑是为表现更好的方案提供更多的繁殖机会，同时保留一些变异。

• 轮盘赌选择：程序的选择方式是，其概率与其适应度成正比。
• 锦标赛选择：随机选择一部分程序，然后从中选择最适合的那个。
• 秩选择：然后，程序的选择概率根据适应度秩进行分配。

2. 交叉（重组）

另一方面，交叉是通过合并两个父代程序的片段来创建子代。该算子鼓励程序之间共享有价值的遗传物质，从而可以改进问题的解决方案。

3. 变异

变异对个体程序引入随机变化，即位值的翻转。该算子用于在种群中保持遗传多样性，以扩展搜索空间中的可能性。

遗传编程过程

1. 初始化

种群的准备是遗传编程进化过程的第一阶段。在这种情况下，会创建第一代或种群的潜在解决方案或搜索代理（称为个体或染色体）。它们通常是随机初始化的，以便个体集从尽可能多的不同形式开始进化过程。种群意味着种群的每个成员都是所考虑问题的候选解决方案。

• 种群大小： 种群中个体的数量。这个大小可以决定GP的多样性和计算量的多少和水平。
• 表示： 选择个体的表示方式，通常是树状结构，其中节点是函数或操作，叶子是输入或常数。
• 随机生成： 从随机生成初始种群开始，根据函数和终端，包含尽可能多的变体以找到解决方案。

2. 适应度评估

适应度评估是另一个关键阶段，其中种群中的每个个体都会被再次检查，以了解它在解决问题方面的有效性。适应度函数根据特定属性衡量个体的质量或性能。

• 目标函数： 提供由目标函数定义的个体性能的度量。建议将此函数与问题的目标联系起来。
• 评估指标： 在处理种群时，使用目标函数计算每个个体的适应度。度量可以是准确率、错误率或任何其他可选择的度量。
• 基准问题： 应持续使用基准问题或数据集来衡量个体表现的优劣。

3. 选择最fit的个体

这包括识别当前一代种群中的个体，以便作为下一代父母。每个人都希望获得更高的适应度分数，从而增加创造更好一代的机会。

• 选择方法： 使用选择方法，包括轮盘赌选择、锦标赛选择或基于秩的选择。这些方法确保具有更高适应度的个体更有可能被选中。
• 父代选择： 根据分配的适应度分数选择两个个体（父代）进行杂交。体能好的个体比其他个体有优势，尤其是在繁殖方面，因为它们有更高的概率确保其基因能够传递到下一代。
• 幸存者选择： 选择当前一代中的哪些个体将传递到下一代，通常，父代和子代会被结合。

4. 交叉和变异

在产生新个体过程中使用的两个遗传算子是交叉和变异。这些算子会修改种群，并为新的潜在好解决方案创造空间。

• 交叉（重组）： 为了实现这种变化，合成两个父代个体以产生一个或多个子代。实现交叉的一种方法是子树交叉，其中父代树在某些或所有随机区域被交换。

5. 终止条件

遗传编程会创建不同的世代，而世代的周期不幸地会在满足特定条件后停止。这些条件定义了算法何时应退出，即何时找到了合适的解决方案或满足了预定义的停止条件。

• 最大世代数： 定义算法将进行的迭代次数。如果达到此限制，则停止该过程。
• 适应度阈值： 必须设置一个标准，例如最低适应度，当任何个体达到该标准时，过程就会停止。这是可接受的解决方案质量水平的阈值。
• 收敛： 密切关注“原型对原型”接触的出现，这意味着种群中的个体变得非常相似，只有职业是主要的区别。如果目标度量收敛，则可以终止过程。

遗传编程中程序的表示

与GP相比，程序的表示是程序进化和操作的基础。它定义了交叉和变异等遗传算子如何执行。GP中的程序主要由树状结构、线性结构或基于图的结构表示。

1. 基于图的结构

用于表示程序的结构是DAG，它可以共享子表达式并进行更复杂的表示。

• 节点和边： 节点表示操作或值，边表示操作之间的数据流。
• 子表达式重用： 总结来说，有不同的方法可以合并片段，这些片段可以被数据流图的其他部分共享，从而提高其效率。

示例

对于表达式 (x + 3) * (y - 2)，基于图的表示可能看起来像

在这个图中，如果 `+` 和 `-` 操作在整个程序中出现多次，则可以共享它们的节点。

优点

• 效率：重用程序中的子表达式可以帮助提高程序的计算效率。
• 灵活性：总而言之，基于图的结构可以模仿更复杂的依赖关系。

缺点

• 复杂性：基于图的表示可能稍微更难使用和处理。
• 应用遗传算子的难度：交叉和变异操作更复杂，可能需要更高级的算法来确保给定图的完整性。

2. 树状结构

在所有用于遗传编程的字符中，树状结构是最常用的。在这里，程序的格式是组织成树状结构的节点列表，其中操作数和运算符是其节点。

• 根节点： 它是程序开始时使用的参考点。
• 内部节点： 通常用于函数/运算符表示。
• 叶子节点： 这些是终端值或变量类型。

示例

考虑一个简单的数学表达式 (x + 3) * (y - 2)。该表达式的树状表示将如下所示

优点

• 自然表示：当然，许多计算表达式可以用树状结构非常自然地表示。
• 遗传算子的易用性：交叉和变异操作很容易实现。

缺点

• 复杂性：当树变得非常大时，决策会变得复杂，这会导致“膨胀”问题，即树有太多可以修剪的方面。

3. 线性结构

线性结构将程序表示为指令或命令的序列，就像命令式编程语言程序那样，必须按顺序执行一系列指令或命令。

• 指令序列： 程序是按此顺序运行的指令序列。
• 操作数和运算符： 每条指令可以包含运算符以及它应该操作的操作数。

示例

同一个表达式 (x + 3) * (y - 2) 在线性表示中可能表示为

优点

• 简洁性：当计划时，线性结构是最有价值的结构类型，因为它更容易阅读和遵循。
• 空间效率：线性表示可以比树状结构更节省空间。

缺点

• 对某些问题不够自然：不幸的是，有些问题无法通过按顺序应用最合适的操作来解决。
• 复杂的遗传算子：使用交叉和变异比使用树状结构稍微复杂一些。

遗传编程中的适应度评估

性能评估是GP中的一个重要步骤，因为它揭示了程序在解决预定义问题方面的效率。此过程有助于对种群中的每个成员的兼容性进行评级，以指导下一代程序的创建过程。

目标函数

• 目标函数也称为适应度函数，它是用于评估单个程序的一个特定标准。
• 目标函数取决于所研究的问题，并代表程序性能相对于目标的数值度量。
• 目标函数将问题特征（由其需求给出）映射为评估找到的解决方案质量的数值。
• 它提供了一种对个体进行排序并确定哪些程序更适合转移到下一代的方法。

目标函数类型

• 单目标函数： 当存在一个标准来找到“最佳”解决方案时使用，该标准基于一个标准，例如分类中的不准确性或回归问题中的误差。
• 多目标函数： 当同时需要最大化或最小化两个或多个目标时使用，例如准确性和计算时间。

度量适应度

适应度的计算使目标函数能够为种群中的每个个体确定适应度分数。它规定了谁应该在每个种群中拥有更多的后代。

1. 评估过程

• 每个个体通过在测试用例或数据点或两者上运行来测试。
• 这会参考目标函数得出结论，将结果与期望结果进行比较。

2. 适应度指标

• 准确率：从比例和比率的计算中得出，预测准确率表示为正确预测数与尝试的相应预测总数之比。
• 错误率：例如均方误差或平均绝对误差，它们是相对的。
• 复杂性：还应注意，一些问题考虑解决方案的简洁性；也就是说，它们对“更大的”程序施加时间惩罚。

遗传编程的应用

1. 符号回归

符号回归是一类回归分析，它搜索数学表达式的空间，旨在为一组数据找到合适的模型。符号回归不同于研究人员先验选择的模型结构的经典回归方法。

2. 自动化系统设计和控制

GP可以生成人类工程师通常开发的系统设计和控制策略。GP通过虚拟测试它们的功能来修改控制器或设计规范。适应度函数的作用是确定设计或控制策略的效率。

• 机器人学： 机器人运动和响应的最优控制方案。
• 工程： 例如，在汽车行业，可以设计曲线和形状以获得更符合空气动力学的汽车造型，或在赛车电路开发中。
• 自动化： 为工业构建控制器以提高运营效率和可靠性。

3. 图像和信号处理

GP开发用于对图片或信号执行操作的程序，例如过滤、检测边缘甚至提取特征。适应度函数是评估处理后结果的手段。

• 图像增强： 去除图像中的瑕疵，使图像或物体更清晰，甚至增强图像对比度。
• 特征提取： 选择医学图像中器官的特征以进行诊断。
• 信号分类： 例如，在通信中用于信号类型的分类或识别时间序列模型。

4. 金融建模

GP应用于金融领域，用于识别市场模式、预测其行为、创建交易策略甚至优化投资组合。GP使用历史金融信息来调整交易规则、未来价值模型和投资组合分配方案。适应度函数（即要最大化的函数）衡量所寻求解决方案的有效性、盈利性甚至风险调整后的回报。

• 算法交易： 整合新的交易算法，以更优的方法在市场上进行交易。
• 风险管理： 分析和预测金融风险，以制定更好的风险管理策略。
• 投资组合优化： 以使回报最高、风险最低的方式投资资源的过程。

5. 生物信息学

GP可以解决许多与生物信息学相关的问题，包括数据挖掘、模拟生物系统和理解遗传模式。GP调整模型或模式来分析生物信息或模拟生物功能。适应度函数估计每个解决方案与期望结果或其他与问题相关的生命方面的接近程度。

• 基因表达分析： 如上所述，它是一种识别技术，用于揭示调控网络和基因之间的关系。
• 蛋白质结构预测： 根据氨基酸序列预测蛋白质的整体三维构象。
• 进化研究： 模拟种群变化以理解遗传多样性和自然选择的计算机模型。

结论

遗传编程（GP）是一种通用且效率极高的算法，适用于各种目的，包括符号回归、设计必需的系统和算法，以及图像分析、金融建模、生物信息学等众多领域。遵循这一思路，GP利用自然进化过程来为复杂问题寻找最佳替代方案，方法是适应现有解决方案。