检索结果-内蒙古大学图书馆

Automatic algorithm selection for Pseudo-Boolean optimization with given computational time limits

COMPUTERS & OPERATIONS RESEARCH 2025年 173卷

作者： Pezo, Catalina Hochbaum, Dorit Godoy, Julio Asin-Acha, Roberto Univ Calif Berkeley Dept Ind Engn & Operat Res Berkeley CA USA Univ Concepcion Dept Comp Sci Concepcion Chile Univ Tecn Federico Santa Maria Dept Informat Valparaiso Chile

Machine learning (ML) techniques have been proposed to automatically select the best solver from a portfolio of solvers. They have been applied to various problems including Boolean Satisfiability, Traveling Salesperson and Graph Coloring. These techniques are used to implement meta-solvers that receive, as input, the instance of a problem, predict the best-performing solver in the portfolio, and execute it to deliver a solution. Typically, the quality of the solution improves with a longer computational time. This has led to the development of anytime meta-solvers, , which consider both the instance and a user-prescribed computational time limit. Anytime meta-solvers predict the best-performing solver within the specified time limit. In this study, we focus on designing anytime meta-solvers for the NP-hard optimization problem of Pseudo-Boolean Optimization (PBO), which generalizes Satisfiability and Maximum Satisfiability problems. The effectiveness of our approach is demonstrated via extensive empirical study in which our anytime meta-solver, named PBO_MS, improves dramatically on the performance of Mixed Integer Programming solver Gurobi, which is the best-performing single solver in the portfolio. We generalize the anytime meta-solver by predicting a given number p >= 1 of best solvers in the portfolio and then run these, each with equal share of the specified time limit. This anytime p-meta-solver is shown here to outperform both the anytime 1-meta-solver as well as a fixed selection of p solvers by a wide margin.

关键词： algorithm selection PBO Combinatorial optimization ML

来源：评论

学校读者我要写书评

暂无评论

A dynamic AI-based algorithm selection for Virtual Network Embedding

引用

ANNALS OF TELECOMMUNICATIONS 2025年第3-4期80卷 265-281页

作者： Bouroudi, Abdelmounaim Outtagarts, Abdelkader Hadjadj-Aoul, Yassine Nokia Networks Bell Labs Nozay France Univ Rennes INRIA CNRS IRISA Rennes France

With the increasing sophistication and heterogeneity of network infrastructures, the need for Virtual Network Embedding (VNE) is becoming more critical than ever. VNE consists of mapping virtual networks on top of the physical infrastructure to optimize network resource use and improve overall network performance. Considered as one of the most important bricks of network slicing, it has been proven to be an NP-hard problem with no exact solution. Several heuristics and meta-heuristics were proposed to solve it. As heuristics do not provide satisfactory solutions, meta-heuristics allow a good exploration of the solutions' space, though they require testing several solutions, which is generally unfeasible in a real world environment. Other methods relying on deep reinforcement learning (DRL) and combined with heuristics yield better performance without revealing issues such as sticking at local minima or poor space exploration limits. Nevertheless, these algorithms present varied performances according to the employed approach and the problem to be treated, resulting in robustness problems. To overcome these limits, we propose a robust placement approach based on the algorithm selection paradigm. The main idea is to dynamically select the best algorithm from a set of learning strategies regarding reward and sample efficiency at each time step. The proposed strategy acts as a meta-algorithm that brings more robustness to the network since it dynamically selects the best solution for a specific scenario. We propose two selection algorithms. First, we consider an offline selection in which the placement strategies are updated outside the selection period. In the second algorithm, the different agents are updated simultaneously with the selection process, which we call an online selection. Both solutions proved their efficiency and managed to dynamically select the best algorithm regarding acceptance ratio of the deployed services. Besides, the proposed solutions succeed

关键词： Virtual Network Embedding AI Deep reinforcement learning algorithm selection B5G/6 G

来源：评论

学校读者我要写书评

暂无评论

Machine Learning based algorithm selection and Genetic algorithms for serial-batch scheduling

引用

COMPUTERS & OPERATIONS RESEARCH 2025年 173卷

作者： Uzunoglu, Aykut Gahm, Christian Tuma, Axel Augsburg Univ Chair Business Adm Prod & Supply Chain Management D-86135 Augsburg Germany

Whenever combinatorial optimization problems cannot be solved by exact solution methods in reasonable time, tailor-made algorithms (heuristics, meta-heuristics) are developed. Often, these heuristics exploit structural properties and perform well on selected subsets of the problem space. For example, this is how the two bestknown construction heuristics solve the scheduling problem investigated in this study (i.e., the scheduling of parallel serial-batch processing machines with incompatible job families, restricted batch capacities, arbitrary batch capacity demands, and sequence-dependent setup times). However, when the properties change, the performance of one algorithm might decrease, and another algorithm might have been the better choice. To resolve this issue, we propose using Machine Learning to exploit the strengths of different algorithms and to select the probably best-performing algorithm for each problem instance individually. To that, we investigate a variety of methods from the "learning-to-rank" literature and propose several adaptations. Furthermore, because there is no algorithm for the considered scheduling problem that is capable to explore the entire solution space, we developed two Genetic algorithms for the improvement of initial solutions computed by the selected algorithms. Here, we put special emphasis on ensuring that the solution representation (encoding) reflects the entire solution space and that the operators (e.g., for recombination and mutation) are appropriate to explore and exploit this space completely. Our computational experiments show an average increase of 39.19% in solution quality.

关键词： Serial batching Total weighted tardiness algorithm selection Genetic algorithm Machine learning

来源：评论

学校读者我要写书评

暂无评论

Landscape features in single-objective continuous optimization: Have we hit a wall in algorithm selection generalization?

引用

SWARM AND EVOLUTIONARY COMPUTATION 2025年 94卷

作者： Cenikj, Gjorgjina Petelin, Gasper Seiler, Moritz Cenikj, Nikola Eftimov, Tome Jozef Stefan Inst Comp Syst Dept Ljubljana 1000 Slovenia Jozef Stefan Int Postgrad Sch Ljubljana 1000 Slovenia Paderborn Univ D-33098 Paderborn Germany Tech Univ Munich D-80333 Munich Germany

The process of identifying the most suitable optimization algorithm fora specific problem, referred to as algorithm selection (AS), entails training models that leverage problem landscape features to forecast algorithm performance. A significant challenge in this domain is ensuring that AS models can generalize effectively to novel, unseen problems. This study evaluates the generalizability of AS models based on different problem representations in the context of single-objective continuous optimization. In particular, it considers the most widely used Exploratory Landscape Analysis features, as well as recently proposed Topological Landscape Analysis features, and features based on deep learning, such as DeepELA, TransOptAS and Doe2Vec. Our results indicate that when presented with out-of-distribution evaluation data, none of the feature-based AS models outperform a simple baseline model, i.e., a Single Best Solver.

关键词： algorithm selection Optimization problem landscape features Single-objective optimization Feature analysis

来源：评论

学校读者我要写书评

暂无评论

algorithm selection Framework for Legalization Using Deep Convolutional Neural Networks and Transfer Learning

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2022年第5期41卷 1481-1494页

作者： Netto, Renan Fabre, Sheiny Fontana, Tiago Augusto Livramento, Vinicius Pilla, Laercio L. Behjat, Laleh Guntzel, Jose Luis Univ Fed Santa Catarina Dept Comp Sci & Stat BR-88040900 Florianopolis SC Brazil Univ Fed Santa Catarina Dept Automat & Syst Engn BR-88040900 Florianopolis SC Brazil Lab Rech Informat F-91190 Gif Sur Yvette France Lab Bordelais Rech Informat F-33405 Talence France Univ Calgary Dept Elect & Comp Engn Calgary AB T2N 1N4 Canada

Machine learning (ML) models have been used to improve the quality of different physical design steps, such as timing analysis, clock tree synthesis, and routing. However, so far very few works have addressed the problem of algorithm selection during physical design, which can drastically reduce the computational effort of some steps. This work proposes a legalization algorithm selection framework using deep convolutional neural networks (CNNs). To extract features, we used snapshots of circuit placements and used transfer learning to train the models using pretrained weights of the Squeezenet architecture. By doing so, we can greatly reduce the training time and required data even though the pretrained weights come from a different problem. We performed extensive experimental analysis of ML models, providing details on how we chose the parameters of our model, such as CNN architecture, learning rate, and number of epochs. We evaluated the proposed framework by training a model to select between different legalization algorithms according to cell displacement and wirelength variation. The trained models achieved an average F-score of 0.98 when predicting cell displacement and 0.83 when predicting wirelength variation. When integrated into the physical design flow, the cell displacement model achieved the best results on 15 out of 16 designs, while the wirelength variation model achieved that for 10 out of 16 designs, being better than any individual legalization algorithm. Finally, using the proposed ML model for algorithm selection resulted in a speedup of up to 10x compared to running all the algorithms separately.

关键词： algorithm selection convolutional neural network (CNN) machine learning (ML) multirow legalization physical design

来源：评论

学校读者我要写书评

暂无评论

algorithm selection in Adversarial Settings: From Experiments to Tournaments in StarCraft

引用

IEEE TRANSACTIONS ON GAMES 2019年第3期11卷 238-247页

作者： Tavares, Anderson Rocha Vieira, Daniel Kneipp S. Negrisoli, Tiago Chaimowicz, Luiz Univ Fed Minas Gerais Lab Multidisciplinary Res Games BR-31270901 Belo Horizonte MG Brazil

algorithm selection-the mapping of problem instances to algorithms-has been successfully applied to a variety of complex theoretical and practical problems, including computer games. In this paper, we extend the traditional framework, which considers a single decision maker, to adversarial settings, by modeling algorithm selection as a normal-form game. In this "game of algorithm selection," agents select algorithms to play a computer game on their behalf. The game's payoff matrix stores the relative performance among algorithms. We also consider nonstationary scenarios, where algorithms can learn from previous matches. We apply this approach to real-time strategy game StarCraft, using hots developed for the game as our algorithms. Our experiments suggest that minimax-Q is a suitable method for algorithm selection in both stationary and nonstationary conditions. We proceed by implementing our approach in MegaBot, a fully capable StarCraft bot. MegaBot showed robustness to nonstationarity, competing in the difficult scenario of StarCraft AI tournaments. MegaBot successfully learns how to select algorithms, exhibiting increasing win rates with tournament progress. In 2016, its debut year, it left 60% of opponents behind in two out of three tournaments. In 2017, however, MegaBot faced difficulties as its algorithm portfolio got outdated compared to newer entries.

关键词： algorithm selection game theory real-time strategy (RTS) games StarCraft

来源：评论

学校读者我要写书评

暂无评论

algorithm selection: A quantitative optimization-intensive approach

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 1999年第5期18卷 524-532页

作者： Potkonjak, M Rabaey, JM Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA Univ Calif Berkeley Dept EECS Berkeley CA 94720 USA

Implementation platform selection is an important component of hardware-software codesign process which selects, for a given computation, the most suitable implementation platform. In this paper, we study the complementary component of hardware-software codesign, algorithm selection. Given a set of specifications for the targeted application, algorithm selection refers to choosing the most suitable completely specified computational structure for a given set of design goals and constraints, among several functionally equivalent alternatives. While implementation platform selection has been recently widely and vigorously studied, the algorithm selection problem has not been studied in computer-aided design domain until now. We first introduce the algorithm selection problem, and then analyze and classify its degrees of freedom. Next, we demonstrate an extraordinary impact of algorithm selection for achieving high throughput, and low-cost implementations. We define the algorithm selection problem formally and prove that throughput and area optimization using algorithm selection are computationally intractable problems. We also propose a relaxation-based heuristic for throughput optimization. Finally, we present an algorithm for cost optimization using algorithm selection. The effectiveness of methodology and proposed algorithms is illustrated using real-life examples.

关键词： algorithm selection area optimization system-level synthesis throughput optimization

来源：评论

学校读者我要写书评

暂无评论

algorithm selection for software validation based on graph kernels

引用

AUTOMATED SOFTWARE ENGINEERING 2020年第1-2期27卷 153-186页

作者： Richter, Cedric Huellermeier, Eyke Jakobs, Marie-Christine Wehrheim, Heike Paderborn Univ Paderborn Germany Tech Univ Darmstadt Dept Comp Sci Darmstadt Germany

algorithm selection is the task of choosing an algorithm from a given set of candidate algorithms when faced with a particular problem instance. algorithm selection via machine learning (ML) has recently been successfully applied for various problem classes, including computationally hard problems such as SAT. In this paper, we study algorithm selection for software validation, i.e., the task of choosing a software validation tool for a given validation instance. A validation instance consists of a program plus properties to be checked on it. The application of machine learning techniques to this task first of all requires an appropriate representation of software. To this end, we propose a dedicated kernel function, which compares two programs in terms of their similarity, thus making the algorithm selection task amenable to kernel-based machine learning methods. Our kernel operates on a graph representation of source code mixing elements of control-flow and program-dependence graphs with abstract syntax trees. Thus, given two such representations as input, the kernel function yields a real-valued score that can be interpreted as a degree of similarity. We experimentally evaluate our kernel in two learning scenarios, namely a classification and a ranking problem: (1) selecting between a verification and a testing tool for bug finding (i.e., property violation), and (2) ranking several verification tools, from presumably best to worst, for property proving. The evaluation, which is based on data sets from the annual software verification competition SV-COMP, demonstrates our kernel to generalize well and to achieve rather high prediction accuracy, both for the classification and the ranking task.

关键词： algorithm selection Software validation Machine learning Graph kernels Verification Testing

来源：评论

学校读者我要写书评

暂无评论

algorithm selection for SMT MachSMT: Machine Learning Driven algorithm selection for SMT Solvers

引用

INTERNATIONAL JOURNAL ON SOFTWARE TOOLS FOR TECHNOLOGY TRANSFER 2023年第2期25卷 219-239页

作者： Scott, Joseph Niemetz, Aina Preiner, Mathias Nejati, Saeed Ganesh, Vijay 200 Univ Ave Waterloo ON Canada 450 Jane Stanford Way Stanford CA 94305 USA

This paper presents MachSMT, an algorithm selection tool for Satisfiability Modulo Theories (SMT) solvers. MachSMT supports the entirety of the SMT-LIB language and standardized SMT-LIB theories, and is easy to extend with support for new theories. MachSMT deploys machine learning methods to construct both empirical hardness models and pairwise ranking comparators over state-of-the-art SMT solvers. Given an input formula in SMT-LIB format, MachSMT leverages these learnt models to output a ranking of solvers based on predicted runtimes. We provide an extensive empirical evaluation of MachSMT to demonstrate the efficiency and efficacy of MachSMT over three broad usage scenarios on theories and theory combinations of practical relevance (e.g., bit-vectors, (non)linear integer and real arithmetic, arrays, and floating-point arithmetic). First, we deploy MachSMT on state-of-the-art solvers in SMT-COMP 2019 and 2020. We observe MachSMT frequently improves on the best performing solvers in the competition, winning 57 divisions outright, with up to a 99.4% improvement in PAR-2 score. Second, we evaluate MachSMT to select configurations from a single underlying solver. We observe that MachSMT solves 898 more benchmarks and up to a 93.4% improvement in PAR-2 score across 23 configurations of the SMT solver cvc5. Last, we evaluate MachSMT on domain-specific problems, namely network verification with simple domain-specific features, and observe an improvement of 77.3% in PAR-2 score.

关键词： SMT solvers Machine learning algorithm selection

来源：评论

学校读者我要写书评

暂无评论

algorithm selection on a meta level

引用

MACHINE LEARNING 2023年第4期112卷 1253-1286页

作者： Tornede, Alexander Gehring, Lukas Tornede, Tanja Wever, Marcel Huellermeier, Eyke Paderborn Univ Heinz Nixdorf Inst D-33098 Paderborn Germany Univ Munich LMU D-80538 Munich Germany

The problem of selecting an algorithm that appears most suitable for a specific instance of an algorithmic problem class, such as the Boolean satisfiability problem, is called instance-specific algorithm selection. Over the past decade, the problem has received considerable attention, resulting in a number of different methods for algorithm selection. Although most of these methods are based on machine learning, surprisingly little work has been done on meta learning, that is, on taking advantage of the complementarity of existing algorithm selection methods in order to combine them into a single superior algorithm selector. In this paper, we introduce the problem of meta algorithm selection, which essentially asks for the best way to combine a given set of algorithm selectors. We present a general methodological framework for meta algorithm selection as well as several concrete learning methods as instantiations of this framework, essentially combining ideas of meta learning and ensemble learning. In an extensive experimental evaluation, we demonstrate that ensembles of algorithm selectors can significantly outperform single algorithm selectors and have the potential to form the new state of the art in algorithm selection.

关键词： algorithm selection Meta learning Ensemble learning Bagging Boosting Stacking

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：