HyperGBM之进化搜索算法

HyperGBM学习笔记之进化搜索算法

一、什么是进化搜索算法？

进化搜索算法是一种启发式的搜索算法，它的主要组成部分是：变异，重组，选择(包括父代的选择和淘汰样本的选择)的算法设计模块，针对不同的task，当我们完成变异，重组，选择模块的实现，那进化搜索算法的框架就算是搭建好了。

如下图所示，我们可以清晰的看到进化搜索算法的通用框架是如何设计和工作的

1. 首先是初始化一个种群，称之为Population.
2. 在种群中我们可以选择出父代
3. 通过父代样本的变异&重组操作我们就可以获得子代样本
4. 决定新生成的子代样本是否替换到初始种群中

关于进化算法的变异和选择两个模块的设计和实现，让我联想到了之前比较火的太空育种技术，简单来说就是将种子带入太空，在辐射的作用下，让种子产生基因变异，通过栽种变异后的种子，从而筛选出满足自己要求的种子，大概步骤如下：

step1：第一代种子观察。通过飞行器搭载回来的种子叫做第一代种子，将其全部种下去。第一代植株有时也 会表现出一些生理变异性状，但科研人员只是观察记录下来，不做任何筛选。

step2：第二代种子优选。将经过第一代所收获的种子全部再种下去，长出来的叫第二代种子。再开始进行选择，例如筛选变矮秆的，以便增强抗倒伏性能；筛选穗子变大的，以提高产量；筛选变早熟的，以提早收获期等等。变异是随机的，有的变好，有的变差，根据育种目标进行定向选择。

step3：第三代种子稳定性观察。将第二步筛选的种子继续播种，查看这些突变性状是否真正能够稳定遗传。

step4：群体比较和异地试种。对具有遗传稳定性的种子进行一定规模的群体比较试验，以及多省市异地试种鉴定，以确定其在不同环境下是否都能表现出优良性状。

在进化算法中，变异不需要辐射，我们可以简单的设计算法来改变样本内部的结构参数，将变异后的样本送入我们提前设计好的评估函数，我们可以确定此次变异是否符合预期。变异符合预期的子代样本同样可以参与到下一次变异中，这个过程不断迭代，直至达到全局最优解。

二、HyperGBM中的变异算法实现

在HyperGBM如何定义autoML的搜索空间一文中，我们了解到了HyperGBM通过将我们搜索《最优的预处理+最优模型+最优模型参数+…》转换成一个向量来表示，整个任务就变成了：搜索出最优的一个向量，使我们task的reward最优化。那么这个向量也就成为了进化搜索算法需要变异的个体。

1. 构建进化搜索实例

rs = EvolutionSearcher(search_space, optimize_direction='min', population_size=50, sample_size=5,
                       candidates_size=6)
'''
:param space_fn: callable, required
    A search space function which when called returns a `HyperSpace` instance
:param population_size: int, required
    Size of population
:param sample_size: int, required
    The number of parent candidates selected in each cycle of evolution
:param regularized: bool
    (default=False), Whether to enable regularized
:param candidates_size: int, (default=10)
    The number of samples for the meta-learner to evaluate candidate paths when roll out
:param optimize_direction: 'min' or 'max', (default='min')
    Whether the search process is approaching the maximum or minimum reward value.
'''

在HyperGBM只需要上面这样简单的一句话可以构建一个进化搜索的一个实例，其中有几个比较重要的参数解析如下:

optimize_direction=‘min’ → 进化过程中筛选子代的标准是reward越小越好
population_size=50 → 初始种群大小为50
sample_size=5 → 每次从种群中选择5个样本作为父代
candidates_size=6 → 每次变异产生6个子代

2. 变异算法实现

变异算法的具体实现逻辑参照下面的源码注释即可。

def mutate(self, parent_space, offspring_space):
    assert parent_space.all_assigned
    ##获取父代的参数集合
    parent_params = parent_space.get_assigned_params()
    ##随机产生一个需要变异的参数对应位置
    pos = self.random_state.randint(0, len(parent_params))
    pos = 0
    for i, hp in enumerate(offspring_space.params_iterator):
        if i > (len(parent_params) - 1) or not parent_params[i].same_config(hp):
        	##如果建模算法发生变化，则子代的参数值均由随机值决定
            hp.random_sample()
        else:
        ##如果是需要变异的位置，重新随机生成一个不同于父代的值，
        ##如果是不需要变异的位置，参数值直接从父代继承即可
            if i == pos:
                new_value = hp.random_sample(assign=False)
                while new_value == parent_params[i].value:
                    new_value = hp.random_sample(assign=False)
                hp.assign(new_value)
            else:
                hp.assign(parent_params[i].value)
    return offspring_space

3. 进化搜索算法整体流程

如上图所示，在HyperGBM中，将进化搜索算法和元学习器进行结合使用，每次变异都会产生N个待测子代样本，然后将这些子代样本送入元学习选择出最终的一个最优子代。同时每次从种群中选择一部分的样本作为父代，有效避免了局部最优解的问题。

三、HyperGBM变异算法性能测试

本次实验以kaggle数据集为例，设置population=100，观察前100次随机搜索和后面500次进化搜索算法的得分情况，实验结果如下：
　　　　　
　　　　　
　　　　　　　　

由上图可以看出：

1.对于随机搜索，我们可以搜索到的子模型性能是随机性的，存在性能较好的trial，但同时也存在很多性能不好的trial

2.对于进化搜索，trial的得分下限显著提高了，同时通过红线标注的情况来看，我们可以发现随着次数的增多，局部最优解一直在被突破，且一旦被突破，局部最优解附近的子模型也会不断的被搜索出来，从理论上来说，不考虑时间的情况我们可以得到一个最高分的局部最优解甚至全局最优解。

3.后面500个trials实际不足500个，原因是HyperGBM有一个discriminate机制，对于一些即使全部训练完成后性能也不怎么样的trial会执行一个提前停止的操作，进一步提升整体框架的搜索性能。

我们简单的画出(0,100), (100,200),(200,300)，(300,400)，(400,500)，(500,600)区间trials的最优模型性能，
我们可以看到随着搜索次数的增多，最优性能是在不断上升的，在一些比赛和项目上，相信HyperGBM可以成为一个不错的工具。