遗传编程运行Tricks

遗传编程实际运行Tricks

本篇依据Python中的DEAP库来给出一些在实际运行遗传编程程序中的技巧。

Bloat 和 Bloat Control

Bloat会显著降低模型的泛化性能，因此有必要在运行过程中对GP添加上Bloat Control。

• Parsimony Pressure
  Parsimony Pressure指的是在个体的raw fitness后面添加一项罚函数，用于惩罚个体的大小：
  \[f_{Par}(i) =f(i) - C_p × Size(i)\] \(C_p\)为Parsimony Pressure的系数，在gplearn中被默认设置为0.01.
  实验表明Parsimony Pressure的Train和Test结果虽然有提升，但是非常微弱甚至没有。原因可能是在进化的初期Parsimony的惩罚导致了具有大size的有效信息流失。

• Static Limit
  这种方法是检查Genetic Operator产生的亲本后代是否超过了设置的高度/大小限制，如果超过则退回这一次Genetic Operation。
  在Deap中Static Limit有两种：限制高度和限制大小，（设置为限制高度17为最原始的论文版本的静态控制），这两种限制的表现差别并不是特别大。
  实验发现GP在合理的阈值下的泛化能力和训练准确度都有非常明显的提升，且GP的性能与阈值设定非常有关系。阈值作为超参数，个人经验是先设置比较大的阈值观察和standard GP的性能对比，再逐步改小阈值，找到比Standard GP好-比Standard GP差的阈值范围。
  另外，在合理的阈值下，观察到GP的搜索在达到阈值之后的提升速度会放慢，这个和一部分genetic operation被静态限制判定为非法有关；但是另一些时候GP的搜索在达到阈值之后的泛化能力有所提升。

  另外，特别注意，在DEAP中Static Limit依赖装饰器实现：
  

  toolbox.decorate("mate", gp.staticLimit(operator.attrgetter('height'), max_value=25))
  toolbox.decorate("mutate", gp.staticLimit(operator.attrgetter('height'), max_value=25))

  1. 这个装饰器只对Genetic Operator生效，对产生个体的方法expr无效。
     
  2. 装饰器在使用时必须有返回变量接收装饰器的结果，否则装饰器不起作用：
     正确的方法：
     

     for i in range(1, len(offspring), 2):
        if random.random() < mate_rate:
            offspring[i - 1], offspring[i] = toolbox.mate(offspring[i - 1],offspring[i])
            del offspring[i - 1].fitness.values, offspring[i].fitness.values

     错误的写法：
     

     for i in range(1, len(offspring), 2):
        if random.random() < mate_rate:
            toolbox.mate(offspring[i - 1],offspring[i])
            del offspring[i - 1].fitness.values, offspring[i].fitness.values

     在没有变量接收的情况下genetic operator依然对offspring起作用，但是装饰器的工作原理是接收原来函数的结果处理后传出到变量，因此上面错误的写法中装饰器不起作用。但是，实际运行下来发现在第二种写法下装饰器有小概率会正常工作，导致实验结果不准确。

超参数调整

虽然GP对合理范围内的Crossover和Mutation Rate不会过于敏感，但是种群大小和Primitive Set中的函数会影响GP的精度和泛化能力。

• crossover和mutation的方法
  如果将GP视为是一个Generate-Trail-Screen模式的爬山算法，那么理论上crossover和mutation的方法足够多可以让种群产生足够多样化的后代来让选择进行筛选。因此如果要想更快地让GP进行搜索，可以采用多种crossover和mutation联用的方案，但是使用的mutation和crossover方法越多，有效信息的积累越容易被扰乱。一种推荐的方法是遵循Koza的标准GP中的设置：将所有的crossover和mutation并行进行（需要设计某种机制保证种群大小不变，以维持进化压力和计算量），如此则是对现有个体改动一次便判断一次这个改动是否是有利的，更有助于有效信息的积累。

• crossover 和 Mutation Rate
  标准GP中Crossover Rate需要保持在较高水平，（但较高水平的Crossover Rate会让不好的building blocks有更大概率被继承到下一代，因此选择需要更加严格）
  如果想要搜索速度更快，那么Mutation Rate可以加大，同时增加population size，在这种情况下GP更接近Generate-Trail-Screen的模式，爬山效应会更明显。一般Mutation Rate不超过0.1.

• Primitive Set、Population Size和Fitness Function
  合理限度内Primitves的数量越多，最终解的泛化性能会越好，但是无关的Primitives数量的增加会让搜索空间变得更加复杂，更容易导致GP陷入局部最优。
  Population Size的数量越多，GP越容易搜索到全局最优，但是评估的运算速度和运算量随着Population Size的数量上升会暴增。
  因此，这里推荐的一种做法是首先生成Fitness Landscape，即设置好Primitive Set和fitness function，以及个体的初始高度之后，随机生成较大数量的个体，统计这些个体的size和fitness，以及出现的频率。然后，一边调整这些设置一边观察观察好的fitness在fitness landscape中的占比的变化。
  其中需要特别注意的是，推荐引入Empheral Constants或者是固定的常数，尤其是通过先验知识预判可能出现的常数，比如周期性函数中的\(π\)和指数中的\(e\)。常数具有极高的信息密度，按照genetic operator对结构的偏向性，常数相比于用运算式构建的常数，比如\(x-x\),\(x÷x\)受到disruption的概率更小，并且可以减小node的使用数量，延缓bloat的出现。但是常数不能设置的无理且过多，否则会由于增大了表示空间的维度而拖慢进化。如果根据经验判断目标问题的解并不太可能出现常数的话（比如特征重建等问题），则不要加常数项。
  种群大小则是根据最终调整好的fitness landscape中的好的fitness的出现频率来设置。

• 运行代数
  和所有的机器学习算法一样：运行的代数少算法可能不收敛，运行代数过多可能会导致bloat和过拟合的问题。
  推荐的做法是首先设置一个非常大的运行代数，观察GP的收敛情况，再逐步改小。
  另一种方法是机器学习常用的方法：划分验证集，每一代的最优解在验证集上运行，观察模型在验证集上的表现，根据模型的泛化能力和训练精度及时停止运行代数。
  另外，在相同运行时间内相比于增加运行代数，（这两种方法都是增加总的搜索到个体数目的方法），个人更倾向于增加种群大小。

计算速度

加快运行速度可以在更多的时间内搜索到更多的个体。

• 安全的方法是评估的时候使用python的一些并行计算库，例如multiprocessing来完成，但是一定要记住在重复实验中，每次GP运行完成之后要关闭multiprocessing.pool以保证每次GP的运行都是独立的。另外，使用CPU的并行计算后要严格注意各种记录的更新方法。multiprocessing在windows下只能在if __name__=='__main__'下面使用，各种日志需要通过multiprocessing中字典的衍生类来创建，需要特别注意日志在不同python文件之间的调用情况。

• 将所有的Primitive设计为支持矩阵运算的函数，比如numpy或者pytorch，可以大幅度加快评估过程中带入fitness cases计算的步骤。
  

• 在代码设计中，需要遍历的部分查找的变量使用dict字典类型会比list列表类型更快，因为python中对字典的搜索依赖的是哈希。
  

• 更高阶的做法是，彻底舍弃DEAP库中的gp.complie方法，该方法通过创建lambda函数的字符串然后使用eval函数将该字符串转化为lambda函数，在需要评估的个体更多的时候lambda函数对每一个遇到的个体都要重新计算。因此可以使用堆栈方法（在GeneticForest和gplearn中使用）来评估个体，将fitness cases按照树的结构逐层级调用和带入，并且使用记录器记录调用过的函数，如果出现被调用过的函数则不必计算直接拉记录器中的值。