线性遗传规划（LGP）
线性遗传规划（LGP）
名称
线性遗传规划（Linear Genetic Programming, LGP）
分类
线性遗传规划是遗传规划（Genetic Programming, GP）的一种变体，属于进化计算（Evolutionary Computation）领域，而进化计算又是计算智能（Computational Intelligence）的一个子领域。LGP 与传统的树式遗传规划以及其他变体（如笛卡尔遗传规划（CGP）和语法演化（GE））密切相关。
- 计算智能
- 进化计算
- 进化算法
- 遗传算法
- 进化策略
- 遗传规划
- 树式遗传规划
- 线性遗传规划
- 笛卡尔遗传规划
- 语法演化
- 进化算法
- 进化计算
策略
表示
在线性遗传规划中，程序被表示为线性的指令序列，类似于机器码或汇编语言。每条指令由一个操作符（函数）和一个或多个操作数（终端）构成。这些指令按顺序执行，前一条指令的输出可作为后一条指令的输入。
初始化
初始种群中的程序通过随机方式生成。每个程序都是从可用的操作符和终端集合中随机选择指令，并将其排列成线性序列而构成。程序长度可以是固定的，也可以是可变的，这取决于具体实现方式。
评估
种群中的每个程序都根据其在给定问题上的表现进行评估。程序的适应度通常通过在一组测试样例上执行该程序，并衡量其解决问题的效果来确定。具体的适应度函数依赖于所求解问题的性质。
选择
在完成种群评估后，采用某种选择机制来选取父代用于繁殖。常见的选择方法包括锦标赛选择，即由一部分个体依据适应度进行竞争；以及适应度比例选择，即个体按与其适应度成比例的概率被选中。
变异算子
线性遗传规划使用两类主要变异算子来生成新程序：交叉和变异。
交叉通过组合两个父代程序中的遗传信息来产生一个或多个子代。在 LGP 中，这通常通过在每个父代中选择一个随机交叉点，并交换该点之后的指令序列来实现。
变异则向程序中引入随机变化。例如，可将某条指令替换为一条随机生成的新指令，交换两条指令的位置，或修改某条指令中的操作数。
替换
在通过选择和变异生成新一代程序后，需要更新种群，即用新生成的程序替换部分或全部现有个体。这可以通过多种替换策略实现，例如世代替换（替换整个种群）或稳态替换（仅替换部分个体）。
过程
数据结构
- 个体：表示种群中的单个程序，由线性指令序列构成。
- 指令：由一个操作符和一个或多个操作数组成。
- 种群：个体的集合。
参数
- 种群规模：种群中个体的数量。
- 最大代数：算法运行的最大迭代代数。
- 交叉率：对一对选中父代应用交叉操作的概率。
- 变异率：对个体应用变异操作的概率。
- 锦标赛规模：参与锦标赛选择的个体数量。
- 指令集：用于构造程序的可用操作符和终端集合。
伪代码
- 使用随机个体初始化种群
- 评估种群中每个个体的适应度
- 当终止条件未满足时（如未达到最大代数）：
- 使用选择机制选择父代（如锦标赛选择）
- 对每一对父代：
- 以概率 crossover_rate 执行交叉，生成子代
- 以概率 mutation_rate 对子代执行变异
- 评估新生成子代的适应度
- 根据替换策略，用子代替换种群中的个体
- 返回找到的最优个体
注意事项
优点
- 表示灵活：LGP 可以表达多种类型的程序，而不受预定义树结构的限制。
- 执行高效：线性程序执行速度较快，因为其不需要对树结构进行解析。
- 模块性：指令可以以不同方式被复用和组合，从而求解复杂问题。
缺点
- 代码膨胀：与其他 GP 变体类似，LGP 也可能出现代码膨胀现象，即程序规模变得不必要地庞大。
- 表达能力受限：某些问题更适合用树结构或图结构表达，而在线性格式下表示这类问题可能较为困难。
- 参数敏感性：LGP 的性能可能对参数选择较为敏感，例如种群规模和变异算子概率。
启发式建议
种群规模
- 选择能够在保证足够多样性的同时使计算成本可控的种群规模。
- 典型的种群规模通常在 50 到 1000 个体之间，具体取决于问题复杂度。
变异算子概率
- 交叉率应设置得足够高，以促进对新程序组合的探索，通常取值在 0.5 到 1.0 之间。
- 变异率宜设置较低，以在不过度破坏优良解的前提下引入小幅变化，通常取值在 0.01 到 0.1 之间。
指令集设计
- 应包含与问题领域相关且具有多样性的操作符和终端。
- 应确保指令集具备求解问题所需的表达能力，但又不过于复杂，否则会降低进化效率。
终止条件
- 应根据可用计算资源和问题复杂度设置最大代数。
- 可考虑采用早停准则，例如当适应度在若干代内不再明显提升时提前终止。
精英保留
- 在每一代中保留少量最优个体，以防止优良解丢失。
- 精英保留有助于加快收敛，并维持进化过程中发现的最佳解。