一个算法开发者,可能会幻想进入这样一个境界:算法只用开发一次,但是可以到处部署交付。这种ROI无穷大的壮丽景象,不光开发者很喜欢,老板们更喜欢。
但是,早在1997年,IBM两位学者就给这个幻想泼下一盆冷水,他们在一篇论文里证明了一个结论,就是著名的「没有免费午餐定理」。在那篇论文里,他们说道(大意):「如果算法在某一类问题上性能特别好,那在其它问题上就会很糟糕」。
所以,现实中一个算法的表现,在有的场景里面性能非常好,但在有的场景里面却非常糟糕,有些客户能收到惊喜,而有些客户可能会受到惊吓。对于这些受到惊吓的客户,他们场景里的需求该怎么交付呢?
聪明的开发者们在算法中引入了算法参数,使用不同的算法参数来代表不同场景里面的关键特征,这使得算法具备了适应多种场景的能力。通过小心地配置这些算法参数,我们可能会让算法的实际性能达到或超出期待的水平,这样也许就能够实现一次算法开发,然后通过参数配置达成在多个场景里面进行交付的效果。
以求解优化问题为例,求解器里就内置了很多参数,这些参数的引入,使得求解器拥有了支持多种不同场景的潜力。对于有些场景,求解器默认的参数就能很好地适应;但在一些新场景里,默认参数可能不再与场景匹配,甚至会明显拖慢求解效率。这时候,我们可以将新场景的优化模型输入到调参器,让它寻找与场景更匹配的求解器参数配置,这样就能充分释放求解器在新场景中的潜力。
调参器背后的算法模拟了人类认识问题然后解决问题的过程,它通过观测参数对应的输出(性能)数据来拟合或学习参数与输出之间隐含的数量关系,再根据学习到的关系,来推测最有潜力的参数,然后对这个参数进行验证。如此反复,不断积累关于输入输出之间关系的知识,从而作出更优的推测。
这类算法在未知的数量关系上进行优化,所以通常也称之为黑盒优化算法,因为在优化过程中没有梯度信息可以利用,所以也称为无梯度优化算法。
我们测试了一个算例,这个算例来自混合整数规划的标准测试集 MIPLIB2017,它有2万多个变量,近400个约束。使用Cbc直接进行求解,需要24000秒,而使用CPLEX进行求解,只需要46秒——不愧是商用求解器,效率是开源求解器的512倍。
而使用我们的调参器(MindOpt Tuner)推荐的参数,Cbc的求解耗时居然下降到了20秒,足足提速1200倍。从24000秒到20秒,1200倍提速!也就是说,在这个问题上,使用调参器推荐的参数,开源的Cbc一举反超CPLEX,实现2.3倍的效率领先。
我们对MIPLIB2017中的240个算例进行了测试,如果把每个模型的求解时间放开到3万秒,Cbc只能算出106个模型,而使用我们的调参器推荐的参数,解出了121个模型,最大加速倍数,达到1226倍,106个算例的平均求解时间从4209秒下降到1196秒平均加速倍数达到 17.85 倍。
所以,对于你设计的算法或程序,倘若一时性能不如意,千万不要妄自菲薄,不调一下参数,你咋知道它不会使出惊世骇俗的洪荒之力呢?
调参器本质上是在对输入输出关系进行学习,并在此之上进行推理,因此,除了对求解器进行参数优化,只要我们的算法或程序能对输入进行响应,我们就能借助调参器(或者说黑盒优化算法)找到最符合我们需求的输入。
如果把矿石的投料配比作为参数,我们可以通过冶炼化学反应过程的模拟器,来计算某一配比下铁水的成份和冶炼的成本,接入调参器,我们就能得到能满足成份要求且成本最低的配比方案。
如果把药物的分子结构作为参数,我们可以把生物化学反应的模拟程序接入调参器,我们就能得到最有潜力的药物成份。
如果把工件加工顺序作为参数,我们可以通过生产仿真程序来推演订单交付的准时率,把仿真模型接入调参器,我们就能得到交付最及时的生产计划。
总之,如果某个业务场景可以进行模拟验证,那么调参器就可以帮助我们找到最佳的答案。