Learning parallel portfolios of algorithms
Learning parallel portfolios of algorithms
复制标题
学习并行算法组合
DOI：
--
复制
发表时间：
2006
影响因子：
1.2
通讯作者：
S. Zilberstein
中科院分区：
文献类型：
--
作者：
Marek Petrik;S. Zilberstein
广泛的组合优化算法已被开发用于复杂的推理任务。通常情况下，没有一个算法优于所有其他算法。这引起了人们对利用算法集合的性能来提高性能的兴趣。我们将展示如何使用并行组合算法（PPA）来实现这一点。PPA是用于解决单个问题的各种算法的集合，所有算法都在单个处理器上并发运行，直到产生解决方案。可以通过将不同份额的处理器时间分配给每个算法来控制组合的性能。我们提出了一种有效的方法，找到一个PPA中的份额分配给每个算法的处理器时间是固定的。找到最佳的静态时间表被证明是一个NP完全问题的一般类的效用函数。我们提出的PPA随机实例的性能上的界限和经验上的性能评估的集合23个国家的最先进的SAT算法。结果表明，在集合中最快的个人算法的显着的性能增益。
A wide range of combinatorial optimization algorithms have been developed for complex reasoning tasks. Frequently, no single algorithm outperforms all the others. This has raised interest in leveraging the performance of a collection of algorithms to improve performance. We show how to accomplish this using a Parallel Portfolio of Algorithms (PPA). A PPA is a collection of diverse algorithms for solving a single problem, all running concurrently on a single processor until a solution is produced. The performance of the portfolio may be controlled by assigning different shares of processor time to each algorithm. We present an effective method for finding a PPA in which the share of processor time allocated to each algorithm is fixed. Finding the optimal static schedule is shown to be an NP-complete problem for a general class of utility functions. We present bounds on the performance of the PPA over random instances and evaluate the performance empirically on a collection of 23 state-of-the-art SAT algorithms. The results show significant performance gains over the fastest individual algorithm in the collection.