启发式优化算法的一些调研
启发式优化算法的背景
1. 首先,我们需要有一个目标函数 其中的
,
是一个正整数。然后,目标函数
不一定需要是显式的(所谓显式指的是能够精确写出
的表达式,例如逻辑回归的目标函数,神经网络的目标函数,XGBoost 的目标函数等),隐式的目标函数使用启发式优化算法也是可以研究的(即无法写出
表达式)。
2. 其次,需要计算目标函数 的最大值
或者最小值
。
3. 再次,如果存在多个函数 并且每一个
的值域都在
内。如果目标函数是
希望求该目标函数的最小值,那么意思就是使得每一个
在
的定义域内都相差得不多,也就是这
条曲线几乎重合。
4. 拥有目标函数的目的是寻找最优的 使得它满足
或者
。
5. 在这里的 一般都是连续的特征,而不是那种类别特征。如果是类别的特征,并不是所有的启发式优化算法都适用,但是遗传算法之类的算法在这种情况下有着一定的用武之地。
启发式优化算法的实验方法
1. 论文中的方法:找到一些形状怪异的函数作为目标函数,需要寻找这些函数的全局最大值或者全局最小值。除了全局的最大最小值点之外,这些函数也有很多局部极值点。例如 Rastrigin 函数(Chapter 6,Example 6.1,Search and Optimization by Metaheuristics)
其中, 或者 Easom 函数(Chapter 2,Example 2.1,Search and Optimization by Metaheuristics)
其中,
2. 最朴素的算法:随机搜索法(Random Search)。也就是把 的定义域切分成
份,其中
计算每一个交点的函数取值,然后统计出其最大值或者最小值就可以了。实际中不适用,因为当
的时候,这个是指数级别的计算复杂度。
3. 启发式优化算法:针对某一个目标函数,使用某种启发式优化算法,然后与随机搜索法做对比,或者与其余的启发式优化算法做对比。
4. 在线调优:启发式优化算法大部分都可以做成实时调优的算法,调优的速度除了算法本身的收敛速度之外,还有给定一个 之后,获取到
的时间。
注:可以尝试使用启发式优化算法在线调优推荐系统中的 AUC 或者 CTR。不过 CTR 一般具有波动性,需要几个小时甚至一天的数据才能够统计出一个相对靠谱的取值。同时,如果用户量不够多的话,如果切流量的话,可能会造成一些流量的 CTR 偏高,另外一些流量的 CTR 偏低。并且流量的条数会有上限,一般来说不会超过 100 左右,甚至只有 10 个不同的流量。因此,在其余场景下使用这类方法的时候,一定要注意获取目标函数 value 的时间长度。时间长度越短,能够进行的尝试(探索次数)就会越多,收敛的希望就会越大;反之,时间长度越长,能够进行的尝试(探索次数)就会受到限制,收敛的时间长度就会变长。
启发式优化算法的一些常见算法
以下的内容暂时只涉及最基本的算法,有很多算法的变种暂时不做过多的描述。
粒子群算法(Particle Swarm Optimization)
PSO 算法是有一个粒子群,根据群体粒子和单个粒子的最优效果,来调整每一个粒子的下一步行动方向。假设粒子的个数是 ,每一个粒子
都是
维欧几里德空间里面的点,同时需要假设粒子的速度
。在每一轮迭代中,需要更新两个最值,分别是每一个粒子在历史上的最优值和所有粒子在历史上的最优值,分别记为
(
)和
。在第
次迭代的时候,
在这里,,并且
是
中间的随机数。
注:需要解决的问题是如何设置这 个粒子,也就是构造粒子群的问题。在每次只能够设置调整一次
的时候,可以把时间窗口按照连续的
段来进行切分,在一个时间段内的这
个时间点可以当成
个粒子,然后进行下一轮的迭代即可。
模拟退火(Simulated Annealing)
其核心思想是构造了温度 这个维度,当温度
高的时候,分子运动速度快,能够探索更多的区域;温度
低的时候,分子运动速度慢,能够探索的区域有限。随着时间的迁移,温度
会从一个较大的值逐渐降低到 0。
模拟退火的大体思路是这样的:先设置一个较大的温度值 ,随机初始化
。假设目标函数是
,需要寻找
,然后执行以下的程序:
Repeat:
a. Repeat:
i. 进行一个随机扰动 ;
ii. 计算 ,
如果 ,也就是
,选择
;
否则,按照 的概率来接受
。
b. 令 。
直到 足够小。
遗传算法的个人理解:
- 如何选择合适的
,可以选择 Gaussian 正态分布,并且可以同时修改
的
个维度,也可以每次只修改一个维度或者部分维度的值;
- 一开始在温度
很大的时候,即使
的时候,都会以极大概率接受
,因为此时
。然后一开始都在四处游荡;
- 当温度
逐渐降低的时候,当时
不一定在一个合适的位置,因此,需要记录历史上探索过的满足
最小的值,从历史上的值中选择出一个合适的值继续迭代。因此,在温度下降的时候,如何选择一个合适的值继续迭代可能是一个关键问题。
- 从遗传算法和 PSO 的对比效果来看,因为 PSO 算法会随时记录当前粒子和所有粒子的最优状态,然后在整个种群中,总会有少数粒子处于当前的最优状态,所以 PSO 的效果从实验效果上来看貌似比不记录状态的遗传算法会好一些。
进化策略(Evolutionary Strategies)
ES 和 GA 有一些方法论上面的不同,这个在书上有论述,等撰写了 GA 在一起看这一块的内容。
进化策略(Evolutionary Strategies)的大体流程与遗传算法(Genetic Algorithm) 相似,不同的是 ES 的步骤是交叉/变异(Crossover/Mutation)在前,选择(Selection)在后。
对于经典的进化策略而言,交叉算子(Crossover Operator)可以按照如下定义:两个父代(parents) 和
,那么子代(children)的交叉可以定义为:
这里的相加就是向量之间的相加。
对于经典的进化策略而言,变异算子(Mutation Operator)可以按照如下定义:对于一个向量 ,使用 Gaussian 正态分布可以构造出一个后代如下:
这里的 是基于具体问题的,很难给出一个通用的值。
就经验而谈,ES 算法一般来说比 GA 更加 Robust。在交叉(Crossover)或者变异(Mutation)之后,ES 算法就需要进行选择,通常来说,ES 算法有两种方式,分别是 和
两种策略。这里的
表示人口数量(population size),
表示从人口中产生的后代的数量。
(1)在 策略中,从
人口中通过变异或者交叉得到
个人,然后从这
个人中选择出
个最优的人。
是精英策略,每一次迭代都比上一次要好。
(2)在 策略中,
个最优的人是从
中选择出来的。
传统的梯度搜索法,例如 Newton-Raphson 方法,需要能够计算目标函数 的导数,也就是说目标函数必须可导。但是在 Evolutionary Gradient Search 中,不需要
是可导的,而是使用导数的近似值来计算。
如果是 的方案,它整体来说其实只有一个人口。从当前的点
开始,通过 Gaussian Mutation 的方法可以生成
个后代,记为
。计算它们的函数取值
。那么估算的梯度就可以计算出来:
归一化之后得到
Evolutionary gradient search 生成了两个点,分别是:
这里的 新的个体定义为:
如果
那么
如果
那么
进化策略(ES)包括 gradient search 和 gradient evolution,并且 covariance matrix adaptation(CMA)ES 在一定的限制条件下加速了搜索的效率。
参考资料:
- Search and Optimization by Metaheuristics,Kelin DU, M.N.S. SWAMY,2016年