基于栈的遗传规划（SBGP）
2026/3/21约 1544 字大约 5 分钟
基于栈的遗传规划（SBGP）
名称
基于栈的遗传规划（Stack-based Genetic Programming, SBGP），又称栈式表示遗传规划（Genetic Programming with Stack-Based Representation）、栈表示遗传规划（Stack-Based Representation Genetic Programming）
分类
基于栈的遗传规划是遗传规划（Genetic Programming, GP）的一种变体，其采用基于栈的程序表示方式。它与其他遗传规划变体，如线性遗传规划（LGP）和语法引导遗传规划（GGGP）密切相关。
- 人工智能
- 机器学习
- 计算智能
- 进化计算
- 遗传规划
- 基于栈的遗传规划
- 遗传规划
- 进化计算
- 计算智能
- 机器学习
策略
在基于栈的遗传规划中，候选解被表示为作用于栈数据结构的一系列指令。每条指令可以是向栈中压入一个值、对栈顶值执行某种操作，或以其他方式对栈进行操作（例如复制或删除元素）。
交叉、变异等遗传算子作用于这些指令序列，以生成新的候选解。交叉通常通过在两个父代解之间交换指令子序列来实现，而变异则可以通过替换、插入或删除某条指令来完成。
评估
在评估一个候选解时，需要按顺序执行其指令，并在每一步更新栈状态。最终根据栈的结束状态，或栈中某个特定值，来确定该解在所求问题上的适应度。
选择与变异
与其他遗传规划方法类似，基于栈的遗传规划使用由多个候选解构成的种群，并在多代演化过程中不断改进。通常采用锦标赛选择或适应度比例选择等机制来选取父代个体，再对这些父代应用遗传算子生成新解，并将其加入种群中，以替换适应度较低的个体。
过程
- 初始化种群
- 随机生成一个由栈式程序构成的种群
- 评估种群中每个程序的适应度
- 当终止条件未满足时，重复以下过程：
- 从种群中选择父代
- 对所选父代应用遗传算子
- 通过交换父代之间的指令子序列执行交叉
- 通过替换、插入或删除子代中的指令执行变异
- 评估新生成子代的适应度
- 用新子代替换种群中适应度较低的个体
- 返回找到的最优解
数据结构
- 指令：可在栈上执行的操作（如压栈、加法、乘法、复制、交换）
- 程序：表示候选解的一段指令序列
- 栈：在程序执行过程中用于存储和操作中间值的数据结构
- 种群：候选解（程序）的集合
参数
- 种群规模：种群中候选解的数量
- 最大程序长度：程序（指令序列）允许的最大长度
- 交叉率：对一对选中父代应用交叉算子的概率
- 变异率：对子代应用变异算子的概率
- 锦标赛规模：参与锦标赛选择的个体数量（若采用该选择方式）
- 精英保留数：每一代中未经改变直接保留下来的最优解数量
注意事项
优点
- 表示灵活：基于栈的表示方式允许进化出长度和结构可变的复杂程序
- 评估高效：栈式程序的执行通常较快，因为无需解析或解释复杂的语法树
- 可扩展性强：可以方便地向指令集中加入新指令，以扩展进化程序的能力
缺点
- 膨胀：程序可能在适应度并未明显提升的情况下变得过于庞大和复杂，从而增加计算开销
- 冗余：栈式程序中可能包含对问题求解没有贡献的冗余或无效指令
- 表达能力受限：相较于其他遗传规划表示方式，有些问题可能更难用基于栈的表示来表达或求解
启发式建议
指令集设计
- 应包含覆盖问题领域所需操作的多样化指令集
- 应在栈操作类指令（如复制、交换）与计算类指令（如算术、逻辑运算）之间保持平衡
- 可考虑加入问题特定指令，以提高进化程序的效率和求解效果
种群初始化
- 可采用渐增半半初始化方法（ramped half-and-half），生成在程序规模和结构上具有多样性的初始种群
- 应设置合理的初始最大程序长度，以防止生成过于庞大的初始程序
遗传算子概率
- 应根据问题复杂度以及探索与开发之间所需的平衡来调整交叉率和变异率
- 较高的交叉率有助于组合有用的程序子序列，而较高的变异率有助于探索新的指令和结构
选择与精英保留
- 可采用中等规模的锦标赛选择（如 5–7），以平衡选择压力与种群多样性
- 可使用精英保留策略，在代际间保留少量最优解（如 1–5 个），以防优良解因随机因素而丢失
膨胀控制
- 应设置最大程序长度限制，以防程序规模无界增长
- 可采用简约压力（parsimony pressure）或多目标方法，在适应度相同的情况下偏向更小、更简洁的程序
- 可考虑使用简化或编辑算子，以删除进化程序中的冗余或低效指令
参数调优
- 可通过系统实验，或采用自动化参数调优方法（如网格搜索、进化算法），寻找适用于具体问题的最佳参数组合
- 应在不同参数设置下进行多次运行并监测算法表现，以识别能够稳定产生较好结果的鲁棒配置