算法自动选择：调研与展望

需积分: 9 19 浏览量更新于2024-07-16 收藏 739KB PDF 举报

"Automated Algorithm Selection: Survey and Perspectives" 这篇学术文章是对算法自动调参领域的全面调查，由Pascal Kerschke、Holger H. Hoos、Frank Neumann、Heike Trautmann等专家共同撰写。它深入探讨了在机器学习（ML）和其他计算问题中如何智能地选择和配置算法，以实现最佳性能。该领域的研究主要关注如何自动从一系列候选算法中挑选出最适合特定问题实例的算法，以避免手动试错和优化过程中的时间和资源浪费。自动化算法选择（Automated Algorithm Selection）是解决计算问题的一个关键策略，尤其是在面对复杂性和计算难度高的问题时。通常，没有单一的算法能在所有实例上都表现出色，而是有一系列算法，各自在不同的场景下具有优势。这种性能互补性为算法选择提供了机会，通过智能策略来决定何时何地使用哪种算法。文章可能会涵盖以下几个方面： 1. **算法配置（Algorithm Configuration）**：这是一个子领域，专注于调整算法参数以优化其在特定问题上的性能。这涉及到构建模型并测试不同参数组合，以找到最优解。 2. **自动调参（Automatic Hyperparameter Tuning）**：与算法配置密切相关，自动调参涉及到寻找最优化模型的超参数设置，如学习率、正则化强度等，以提高模型的泛化能力。 3. **算法自动化配置（Automated Algorithm Configuration）**：这一概念指的是整个过程的自动化，包括算法的选择和参数的配置，旨在为特定问题创建定制的解决方案。 4. **元启发式方法（Metaheuristics）**：在自动算法选择中，元启发式方法常被用来搜索算法空间，如遗传算法、模拟退火和粒子群优化等，它们能够探索和评估大量可能的算法组合。 5. **性能评估与比较**：文章会讨论如何有效地评估和比较不同算法在不同数据集上的表现，以及如何建立公正的基准来衡量自动化选择的有效性。 6. **应用领域**：自动化算法选择的应用广泛，包括但不限于机器学习、优化问题、计算机视觉、自然语言处理等领域，这些领域的问题往往需要快速适应和应对不断变化的数据特性。 7. **未来展望**：作者可能还会讨论当前挑战，如计算成本、可扩展性问题，以及未来的研究方向，如深度学习中的自动化算法选择，或者结合强化学习进行动态算法决策。通过这样的综述，读者可以了解到算法自动选择的最新进展，以及如何将这些技术应用于实际问题，以提高解决问题的效率和效果。这对于研究者、数据科学家和工程师来说是非常有价值的资源，可以帮助他们更好地理解和利用这个领域的成果。

P. Kerschke et al.

moderate computational cost (Hutter, Hoos et al., 2014), and performance predictors

form the basis for one of the main approaches to per-instance algorithm selection. At

the same time, other approaches, such as cost-based classication, exist and also nd use

in state-of-the-art algorithm selection systems, as explained in the following sections.

3 Features for Discrete and Continuous Problems

Linking algorithm performance on an instance i to instance characteristics forms a cen-

tral part of automated algorithm selection and several related problems. For this pur-

pose, automatically computable features f(i) = (f

(i),...,f

(i)) are required, ideally

with the following properties: Firstly, features should be informative, in that they allow

for a sufcient distinction between different instances; they should also be interpretable,

so that feature values enable an expert to gain maximum insight into instance proper-

ties. Furthermore, features should be cheaply computable, so that the advantages gained

by selecting an algorithm based on them is not outweighed by the cost of feature com-

putation. Features should also be generally applicable; that is, they should be effectively

and efciently computable for a broad range of problem instances, rather than being

restricted, for example, to small instance sizes. Finally, the features f

should be comple-

mentary, in that redundant sets of features are not only computationally wasteful, but

can also cause problems when used by certain machine learning algorithms as a basis

for algorithm selection and related problems.

In the following, we provide an overview of commonly used instance features for

several prominent discrete and continuous problems—not only to illustrate what kind

of features are useful in the context of per-instance algorithm selection, but also to draw

attention to an important and somewhat underrated research topic of signicant impor-

tance to tasks beyond algorithm selection. In particular, informative instance features

can provide important insights into strengths and weaknesses of a given algorithm, and

hence play a crucial role in devising improvements. We generally distinguish between

problem-specic features that are closely based on particular aspects of the problem to

be solved, such as the number of clauses in instances of propositional satisability prob-

lems, and generic features that are more broadly applicable, such as high-level statistics

over information gleaned from short “probing” runs of a solver for the given problem.

3.1 Discrete Problems

To give concrete examples, and in light of the importance of problem-specic features,

we will focus on three of the most prominent and well-studied discrete combinatorial

problems: propositional satisability (and related problems), AI planning, and the trav-

elling salesperson problem (TSP).

Propositional satisability and related problems. The propositional satisability problem

(SAT) is to determine whether for a given formula F in propositional logic, containing

Boolean variables X

,...,X

∈{true,false}, there exists an assignment of logical val-

ues to the variables such that F evaluates to true; such a variable assignment is said to

satisfy F . Typically, the problem is restricted to formulae F in conjunctive normal form

(CNF), i.e., F consists of conjunctions (∧) of so-called clauses, which are disjunctions (∨)

of Boolean variables X

and their negations ¬X

. A CNF-formula F evaluates to true,

if each of its clauses is satised simultaneously. SAT is one of the most prominent and

intensely studied combinatorial decision problems and has important applications in

hard- and software verication (see, e.g., Biere et al., 2009). Given the ties to other com-

binatorial problems, improvements in SAT often also impact widely studied related

Evolutionary Computation Volume 27, Number 1

Automated Algorithm Selection: Survey and Perspectives

problems, such as maximum satisability (MaxSAT) problem, in which the objective is to

nd a variable assignment that maximises the number of satised CNF clauses.

The rst large collection of features for SAT (and thus also MaxSAT) instances was

provided by Nudelman, Leyton-Brown, Hoos et al. (2004). Despite the rather simple

structure of SAT instances, the authors devised nine different feature sets and a total of

91 features, which characterise a given CNF formula from a multitude of perspectives.

Eleven problem size features describe SAT instances based on summary statistics of their

numbers of clauses and variables. A set of variable-clause graph (VCG) features comprises

ten node degree statistics based on a bipartite graph over the variables and clauses of

a given instance. Interactions between the variables are captured by four variable graph

(VG) features; these are the minimum, maximum, mean, and coefcient of variation of

the node degrees for a graph of variables, in which edges connect pairs of variables that

jointly occur in at least one clause. Similarly, the set of clause graph (CG) features con-

tains seven node degree statistics of a graph whose edges connect clauses that have at

least one variable in common, as well as three features based on weighted clustering

coefcients for the clause graph. Thirteen balance features capture the balance between

negated and unnegated variables per clause, their overall occurrences across all clauses,

as well as fractions of unary, binary, and ternary clauses, whereas six further features

quantify the degree to which the given F resembles a Horn formula (a restricted type

of CNF formula, for which SAT can be decided efciently). The solution of a linear pro-

gram representing the given SAT instance provides the basis for six LP-based features.

Finally, there are two sets of so-called probing features, which are based on performance

statistics over short runs of several well-known SAT algorithms (based on DPLL and

stochastic local search, two prominent approaches to solving SAT) and capture the de-

gree to which these make early progress on the given instance.

Some of the feature sets—specically, the CG, VG, and LP-based features, as well

as some of the VCG, balance and DPLL-probing features—are computationally quite

expensive (see, e.g., Xu et al., 2008; Hutter, Hoos et al., 2014) and consequently not al-

ways useful in the context of practical algorithm selection approaches. Similarly, the

algorithm runs for probing features are limited to a very small part of the overall time

budget for solving a given instance, to make sure that sufcient time remains available

for running the selected SAT solver.

A decade later, Hutter, Hoos et al. (2014)—building on the work by Nudelman,

Leyton-Brown, Hoos et al. (2004)—introduced a set of 138 SAT features. While they

removed some features from the earlier sets, much of the set remained the same. The

most signicant changes were an extension of the CG and VG feature sets by ve new

features each, as well as three new feature sets accounting for an additional 48 features.

The VG feature set was extended by so-called diameter features, which capture statis-

tics based on the set of longest shortest paths from one variable to any other one in the

graph. Also, instead of the weighted clustering coefcients based on the CG (as done

by Nudelman, Leyton-Brown, Hoos et al., 2004), Hutter, Hoos et al. (2014) used a set

of clustering coefcients that measure the CG’s “local cliqueness.” Furthermore, they in-

troduced 18 novel clause learning features, which summarise information gathered dur-

ing short runs of a prominent SAT solver, _, that learns conict clauses

during its search for a satisfying assignment (Mahajan et al., 2004). Another 18 fea-

tures are derived from estimates of variable bias obtained from the SAT solver VARSAT

(Hsu and McIlraith, 2009); these features essentially capture statistics over estimates

for the probability for variables to be true, false,orunconstrained in every satisfying as-

signment. Finally, Hutter, Hoos et al. (2014) proposed to use the actual feature costs,

Evolutionary Computation Volume 27, Number 1 11

剩余43页未读，继续阅读

GanD.GanD

粉丝: 3
资源: 90

算法自动选择：调研与展望

Java经典问题算法大全

A Gaussian Firefly Algorithm：高斯萤火虫算法.pdf

基于区域的立体匹配算法-0812.1340.pdf

Could not find artifact org.springframework.boot:spring-boot-starter:pom:2.0.0.M4 in nexus-aliyun

algorithm identifier in public key not recognised：1.2.156.10197.1.301问题如何解决

fatal: unable to access 'https://gitlab.aeke.com/cv-algorithm/aeke-ai.git/': SSL certificate problem: self-signed certificate

Integrity check failed: java.security.NoSuchAlgorithmException: Algorithm HmacPBESHA256 not available

帮我找计算机专业的外文翻译

最新资源