通用资料收集

Genetic Programming初步了解

GP与遗传算法（GA）的主要不同：GP的个体是完整的数学表达式或者计算机程序，而经典的GA的个体限定为参数组合、字符串。

两大类：基于树的（Tree-based GP / Koza-style GP）、基于图的（Cartesian GP）

Tree-based GP

基于树的GP中，个体可以用一个抽象语法树（AST）表示：

  • 叶节点（终结符、零参数函数，terminal set）：表示输入变量或常量，如{x, y, 3}

  • 内部节点（函数，function set）：表示简单的算子，如{+,-,x,/,min,max}

    • 上面列举的都是二元算子，由他们的线性组合我们可以推断出表达式的解空间一定是连续的；通过引入IF这样一个三元算子：IF ProgOut > 0 THEN CLASS1 ELSE CLASS2（即第一个儿子的结果大于0，整棵树返回CLASS1，否则返回CLASS2），可以引入间断的解空间。
  • 一个GP系统的primitive set = function set + terminal set

基于树的GP在进化时会限制深度，深度的定义与数据结构中树的深度定义一致。

种群初始化方法（Population Initialization）

最简单的两种：grow/full以及它们的混合形式：ramped half-and-half

  • grow方法（成长方法，算法简记为长到不能长为止）：

    • 从function set随机取一个作为root；
    • 对随后的所有候选位置，从primitive set中随机取一个占位；如果已经到达限制深度只能从terminal set中随机取；
    • 停止条件：没有新的可选位置；

  • full方法（相比grow方法，多样性有所下降）：

    • 从function set随机取一个作为root；
    • 在到达深度限制前，从function set中随机取；到达深度限制时从primitive set中取；
    • 停止条件：到达深度限制；

  • ramped half-and-half方法：

    • 一个population中一半的个体grow，一半的个体full，深度限制由单一值扩展为限制范围。

适应度评估（Fitness Evaluation）

与遗传算法一致

环境选择（Environmental Selection）

与遗传算法一致，主要有tournament selection和轮盘赌选择法；

遗传算子（Genetic Operator）

可以与遗传算法类比，但相较遗传算法在线性的染色体上进行Genetic Operation不同，对Tree-based的个体而言遗传算子的设计要略微复杂一些：

  1. Crossover：

    1. subtree-crossover（两个父体得到一个子体）：对两个待交叉个体A、B，对每一个父体选择一个crossover point，复制A为$A_{copy}$，将B的以crossover point为root的子树记为$ B_{subtree\_copy}$，并用$ B_{subtree\_copy}$替换$A_{copy}$中以杂交点为root的子树。

    image-20210123220135343

    1. one-point crossover（两个父体得到两个子体）：

    同样也要对两个待交叉个体各自选择crossover point，并相互交换以各自crossover point为root的子树，与遗传算法中的crossover类似。

    image-20210123220322078

  2. Mutation：替换以随机选择的mutation point为root的子树为一个随机生成的子树。

image-20210123221535497

  1. Copy(Reproduction)：父体不做变化，直接复制到下一代。

思考如何直接使用Genetic Programming解决图像分类？

由于基于图的GP很容易让人联想到神经网络的data flow，因此已经有很多工作例如A Genetic Programming Approach to Designing Convolutional Neural Network Architectures在使用GP探索NN的结构了，与使用遗传算法探索NN有相似之处。

那么，如何将图像的像素级数据直接运用到Genetic Programming上并实现图像分类的效果呢？基本思路大致如下：在不能使用NN的情况下，利用原始的手工提取特征的方法提取到的特征作为terminal set中的输入变量，对GP的输出按照分类标签划分范围（如正数代表Class 1，负数代表Class 2），以分类accuracy作为个体适应度。

手工提取特征的方法多种多样，简单的可以直接取固定区域的像素的统计数据作为特征，如均值方差；复杂的可以运用在深度学习广泛运用前CV领域常用的手工算子：HOG、SVM、Haar；

经典工作（按发表时间排序）

  • Classification Strategies for Image Classification in Genetic Programming（2003）：分类策略上的创新：针对GP的返回值运用了动态的映射选择方法，而非固定边界值的选择，即$return\_value <->predict\_label$之间的映射不再固定。

    • SRS：为N个classification生成N-1个边界值，在进化全过程保持不变；
    • Centred Dynamic Range Selection (CDRS)：首先按SRS生成固定边界并完成评估，对种群中每个个体得到了相应的适应度，定义class center为：$ \text { Center }_{c}=\frac{\sum_{p=1}^{M} \sum_{\mu_{c}=1}^{L}\left(W_{p} \times \text { Result }_{p \mu_{c}}\right)}{\sum_{p=1}^{M} \sum_{\mu_{c}=1}^{L} W_{p}} $，其中M是种群个体数，L是对类别c的训练样本数，$W_p$是反映个体在种群中重要程度的指标，可以由$W_p = \text{fitness}_p + 50\%$计算得到。最后重新确定类别的范围为相邻class center所包括的数值，并按新计算的范围重新评估每个个体。
  • Genetic Programming for Image Classification with Unbalanced Data（2009）：适应度评估函数上的创新：使用accuracy评估图像分类不能很好处理标签不平衡数据；同时特征选择也更加多样，以PEDESTRIAN数据集为例，文章在36x19的图像上手动划分区域并计算对应区域的统计特征。
  • An Effective Feature Learning Approach Using Genetic Programming with Image Descriptors for Image Classification（2020）：function set上的创新，不再局限于{+,-,x,/,if}，引入了CV领域常见手工特征算子。其他工作包括使用min-max正则化处理特征；

当然，如果拓宽视野，让分类任务不局限在只通过GP完成，那还有这些工作：

  • Evolutionary Deep Learning: A Genetic Programming Approach to Image Classification
  • An Evolutionary Deep Learning Approach Using Genetic Programming with Convolution Operators for Image Classification

使用DEAP框架解决GP图像分类问题

Demo: Genetic-Programming-MNIST

特征、标签划分都用的很暴力的方法，效果自然也很差，暂且当做一个玩具吧！

Last modification：April 25th, 2023 at 09:59 pm
© 允许规范转载
If you think my article is useful to you, please feel free to appreciate