算法选择

算法选择（有时也称为每实例算法选择或离线算法选择）是一种元算法技术，在逐个实例的基础上从组合中选择一种算法。它的动机是，在许多实际问题上，不同的算法具有不同的性能特征。也就是说，虽然一种算法在某些情况下表现良好，但在另一些情况下却表现不佳，反之亦然。如果我们能够确定何时使用哪种算法，我们就可以针对每个场景进行优化，并提高整体性能。这就是算法选择所要做的。应用算法选择技术的xxx前提是，存在（或可以构建）一套互补的算法。

布尔可满足性问题（和其他硬组合问题）算法选择的一个著名应用是布尔可满足性问题。在这里，算法组合是一组（互补的）SAT求解器，实例是布尔公式，成本指标是例如平均运行时间或未解决实例的数量。因此，我们的目标是为每个单独的实例选择一个表现良好的SAT求解器。以同样的方式，算法选择可以应用于许多其他的-困难问题（如混合整数编程、CSP、人工智能规划、TSP、MAXSAT、QBF和答案集编程）。在SAT竞赛中获胜的系统有SATzilla、3S和CSHC。

在机器学习中，算法选择更多地被称为元学习。算法组合包括机器学习算法（例如，随机森林、SVM、DNN），实例是数据集，成本指标是例如错误率。因此，目标是预测哪种机器学习算法在每个数据集上的误差小。

算法选择问题主要是通过机器学习技术来解决的。通过用数字特征表示问题实例{displaystylef}，算法的选择可以被看作是对问题实例的选择。的映射，算法选择可以被看作是一个多类分类问题，通过学习实例特征是实例的数字表示。例如，我们可以计算变量的数量、子句的数量、布尔公式的平均子句长度，或者ML数据集的样本数量、特征、类平衡，以获得对其特征的印象。

我们对两种特征进行区分。静态特征在大多数情况下是一些计数和统计（例如SAT中的子句与变量之比）。这些特征从非常便宜的特征（比如变量的数量）到非常复杂的特征（比如关于变量-句子图的统计）。探测特征（有时也被称为里程碑特征）是通过在一个实例上运行一些算法行为分析来计算的（比如一个便宜的决策树算法在ML数据集上的准确性，或者在一个布尔公式上短时间内运行一个随机的局部搜索求解器）。这些特征往往比简单的静态特征成本更高。特征成本取决于所使用的性能指标例如，如果我们使用运行时间作为性能指标，我们就会把计算实例特征的时间计入算法选择系统的性能中。

SAT求解是一个具体的例子，这种特征成本不能被忽视，因为CNF公式的实例特征可以是非常便宜的（例如，对于DIMACs格式的CNF来说，得到变量的数量可以在恒定的时间内完成），也可以是非常昂贵的（例如，图特征可能要花费几十或几百秒）。在这种情况下，在实践中考虑特征计算的开销是很重要的；否则会对算法选择方法的性能产生误导。例如，如果可以非常准确地决定选择哪种算法，但特征是组合算法的运行时间，那么组合方法就没有任何好处。