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

Exploring the role of graph spectra in graph coloring algorithm performance

DISCRETE APPLIED MATHEMATICS 2014年 176卷 107-121页

作者： Smith-Miles, Kate Baatar, Davaatseren Monash Univ Sch Math Sci Clayton Vic 3800 Australia

This paper considers the challenge of recognizing how the properties of a graph determine the performance of graph coloring algorithms. In particular, we examine how spectral properties of the graph make the graph coloring task easy or hard. We address the question of when an exact algorithm is likely to provide a solution in a reasonable computation time, when we are better off using a quick heuristic, and how the properties of the graph influence algorithm performance. A new methodology is introduced to visualize a collection of graphs in an instance space defined by their properties, with an optimal feature selection approach included to ensure that the instance space preserves the topology of an algorithm performance metric. In this instance space we can reveal how different algorithms perform across a variety of instance classes with various properties. We demonstrate the methodology using a sophisticated branch and bound exact algorithm, and the faster heuristic approaches of integer rounding of a linear programming relaxation of the graph coloring formulation, as well as a greedy degree-saturation heuristic. Our results demonstrate that spectral properties of the graph instances can provide useful descriptions of when each of these algorithms will provide the best solution for a given computational effort. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Graph spectra Graph invariants Graph coloring Branch and bound DSATUR LP-relaxation algorithm selection

来源：评论

学校读者我要写书评

暂无评论

Applying machine learning to low-knowledge control of optimization algorithms

引用

COMPUTATIONAL INTELLIGENCE 2005年第4期21卷 372-387页

作者： Carchrae, T Beck, JC Natl Univ Ireland Univ Coll Cork Dept Comp Sci Cork Constraint Computat Ctr Cork Ireland Univ Toronto Dept Mech & Ind Engn Toronto Intelligent Decis Engn Lab Toronto ON Canada

This paper addresses the question of allocating computational resources among a set of algorithms to achieve the best performance on scheduling problems. Our primary motivation in addressing this problem is to reduce the expertise needed to apply optimization technology. Therefore, we investigate algorithm control techniques that make decisions based only on observations of the improvement in solution quality achieved by each algorithm. We call our approach "low knowledge" since it does not rely on complex prediction models, either of the problem domain or of algorithm behavior. We show that a low-knowledge approach results in a system that achieves significantly better performance than all of the pure algorithms without requiring additional human expertise. Furthermore the low-knowledge approach achieves performance equivalent to a perfect high-knowledge classification approach.

关键词： algorithm selection algorithm control machine learning classifiers scheduling

来源：评论

学校读者我要写书评

暂无评论

Bid evaluation in combinatorial auctions: optimization and learning

引用

SOFTWARE-PRACTICE & EXPERIENCE 2009年第13期39卷 1127-1155页

作者： Milano, Michela Guerri, Alessio Univ Bologna DEIS I-40136 Bologna Italy

In combinatorial auctions bidders can post bids on groups of items. The problem of selecting the winning bids, called Winner Determination Problem, is NP-hard. In this paper, we consider an interesting variant of this problem, called Bid Evaluation Problem (BEP), where items are services and are subject to precedence constraints and temporal windows. The BEP has many practical applications, such as, for instance, in transportation routes auctions and in take off and landing time slot allocation problems. We have developed a number of optimization algorithms based on Constraint Programming, on Integer Programming and on the combination of the two techniques. We first show that all algorithms proposed outperform the only commercial system for solving BEP instances called Multi AGent Negotiation Testbed, a more general tool for agent negotiation. Then, we evaluate the developed algorithms and use the decision tree machine learning technique for finding a relation between the instance structure and the solving algorithm and providing an automatic algorithm selection procedure. We show that we can achieve an accuracy of 90% in predicting the best algorithm given the instance to be solved with a significant time saving w.r.t. a single solving technique or a costless, but less accurate, prediction technique. Copyright (C) 2009 John Wiley & Sons, Ltd.

关键词： combinatorial auctions combinatorial optimization decision tree machine learning algorithm selection

来源：评论

学校读者我要写书评

暂无评论

Selecting fast algorithms for the capacitated vehicle routing problem with machine learning techniques

引用

NETWORKS 2024年第4期84卷 465-480页

作者： Asin-Acha, Roberto Espinoza, Alexis Goldschmidt, Olivier Hochbaum, Dorit S. Huerta, Isaias I. Univ Tecn Federico Santa Maria Dept Informat Valparaiso Chile Univ Concepcion Dept Comp Sci Concepcion Chile Riverside Cty Off Educ Riverside CA USA Univ Calif Berkeley Dept Ind Engn & Operat Res Berkeley CA USA

We present machine learning (ML) methods for automatically selecting a "best" performing fast algorithm for the capacitated vehicle routing problem (CVRP) with unit demands. algorithm selection is to automatically choose among a portfolio of algorithms the one that is predicted to work best for a given problem instance, and algorithm configuration is to automatically select algorithm's parameters that are predicted to work best for a given problem instance. We present a framework incorporating both algorithm selection and configuration for a portfolio that includes the automatically configured "Sweep algorithm," the first generated feasible solution of the hybrid genetic search algorithm, and the Clarke and Wright algorithm. The automatically selected algorithm is shown here to deliver high-quality feasible solutions within very small running times making it highly suitable for real-time applications and for generating initial feasible solutions for global optimization methods for CVRP. These results bode well to the effectiveness of utilizing ML for improving combinatorial optimization methods.

关键词： algorithm selection machine learning vehicle routing

来源：评论

学校读者我要写书评

暂无评论

Performance modeling and algorithm characterization for robust image segmentation

引用

INTERNATIONAL JOURNAL OF COMPUTER VISION 2008年第1期80卷 92-103页

作者： Shah, Shishir K. Univ Houston Dept Comp Sci Houston TX 77204 USA Univ Houston Quantitat Imaging lab Houston TX 77204 USA

This paper presents a probabilistic framework based on Bayesian theory for the performance prediction and selection of an optimal segmentation algorithm. The framework models the optimal algorithm selection process as one that accounts for the information content of an input image as well as the behavioral properties of a particular candidate segmentation algorithm. The input image information content is measured in terms of image features while the candidate segmentation algorithm's behavioral characteristics are captured through the use of segmentation quality features. Gaussian probability distribution models are used to learn the required relationships between the extracted image and algorithm features and the framework tested on the Berkeley Segmentation Dataset using four candidate segmentation algorithms.

关键词： image segmentation performance modeling algorithm characterization algorithm selection

来源：评论

学校读者我要写书评

暂无评论

Knowledge-based control of vision systems

引用

IMAGE AND VISION COMPUTING 1999年第9期17卷 667-683页

作者： Shekhar, C Moisan, S Vincent, R Burlina, P Chellappa, R Univ Maryland Ctr Automat Res College Pk MD 20742 USA INRIA Sophia Antipolis Sophia Antipolis France Univ Massachusetts Dept Comp Sci Amherst MA 01003 USA

We propose a framework for the development of vision systems that incorporate, along with the executable computer algorithms, the problem-solving knowledge required to obtain optimal performance from them. In this approach, the user provides the input data, specifies the vision task to be performed, and then provides feedback in the form of qualitative evaluations of the results obtained. These assessments are interpreted in a knowledge-based framework to automatically select algorithms and set parameters until results of the desired quality are obtained. This approach is illustrated on two real applications, and examples from the knowledge bases developed are discussed in detail. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： vision system knowledge-based control self-tuning algorithm selection parameter tuning

来源：评论

学校读者我要写书评

暂无评论

A Faster Tree-Decomposition Based algorithm for Counting Linear Extensions

引用

algorithmICA 2020年第8期82卷 2156-2173页

作者： Kangas, Kustaa Koivisto, Mikko Salonen, Sami Aalto Univ Dept Comp Sci Espoo Finland Univ Helsinki Dept Comp Sci Helsinki Finland

We investigate the problem of computing the number of linear extensions of a given n-element poset whose cover graph has treewidth t. We present an algorithm that runs in time O(nt+3) for any constant t;the notation hides polylogarithmic factors. Our algorithm applies dynamic programming along a tree decomposition of the cover graph;the join nodes of the tree decomposition are handled by fast multiplication of multivariate polynomials. We also investigate the algorithm from a practical point of view. We observe that the running time is not well characterized by the parameters n and t alone: fixing these parameters leaves large variance in running times due to uncontrolled features of the selected optimal-width tree decomposition. We compare two approaches to select an efficient tree decomposition: one is to include additional features of the tree decomposition to build a more accurate, heuristic cost function;the other approach is to fit a statistical regression model to collected running time data. Both approaches are shown to yield a tree decomposition that typically is significantly more efficient than a random optimal-width tree decomposition.

关键词： algorithm selection Empirical hardness Linear extension Multiplication of polynomials Tree decomposition

来源：评论

学校读者我要写书评

暂无评论

Meta-learning and the new challenges of machine learning

引用

INTERNATIONAL JOURNAL OF INTELLIGENT SYSTEMS 2021年第11期36卷 6240-6272页

作者： Monteiro, Jose Pedro Ramos, Diogo Carneiro, Davide Duarte, Francisco Fernandes, Joao M. Novais, Paulo Univ Minho Algoritmi Ctr Dept Informat Felgueiras Portugal Politecn Porto CIICESI ESTG Felgueiras Portugal

In the last years, organizations and companies in general have found the true potential value of collecting and using data for supporting decision-making. As a consequence, data are being collected at an unprecedented rate. This poses several challenges, including, for example, regarding the storage and processing of these data. Machine Learning (ML) is also not an exception, in the sense that algorithms must now deal with novel challenges, such as learn from streaming data or deal with concept drift. ML engineers also have a harder task when it comes to selecting the most appropriate model, given the wealth of algorithms and possible configurations that exist nowadays. At the same time, training time is a stronger restriction as the computational complexity of the training model increases. In this paper we propose a framework for dealing with these challenges, based on meta-learning. Specifically, we tackle two well-defined problems: automatic algorithm selection and continuous algorithm updates that do not require the retraining of the whole algorithm to adapt to new data. Results show that the proposed framework can contribute to ameliorate the identified issues.

关键词： meta-learning machine learning algorithm selection streaming machine learning

来源：评论

学校读者我要写书评

暂无评论

Comprehensive algorithm Portfolio Evaluation using Item Response Theory

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2023年第1期24卷 1-52页

作者： Kandanaarachchi, Sevvandi Smith-Miles, Kate CSIROs Data61 Res Way Clayton Vic 3168 Australia Univ Melbourne Sch Math & Stat Parkville Vic 3010 Australia

Item Response Theory (IRT) has been proposed within the field of Educational Psychometrics to assess student ability as well as test question difficulty and discrimination power. More recently, IRT has been applied to evaluate machine learning algorithm performance on a single classification dataset, where the student is now an algorithm, and the test question is an observation to be classified by the algorithm. In this paper we present a modified IRT-based framework for evaluating a portfolio of algorithms across a repository of datasets, while simultaneously eliciting a richer suite of characteristics - such as algorithm consistency and anomalousness - that describe important aspects of algorithm performance. These characteristics arise from a novel inversion and reinterpretation of the traditional IRT model without requiring additional dataset feature computations. We test this framework on algorithm portfolios for a wide range of applications, demonstrating the broad applicability of this method as an insightful algorithm evaluation tool. Furthermore, the explainable nature of IRT parameters yield an increased understanding of algorithm portfolios.

关键词： Item Response Theory algorithm evaluation algorithm portfolios classification ma chine learning algorithm selection instance space analysis explainable algorithm evaluation.

来源：评论

学校读者我要写书评

暂无评论

MAB-OS: Multi-Armed Bandits Metaheuristic Optimizer selection

引用

APPLIED SOFT COMPUTING 2022年第0期128卷

作者： Meidani, Kazem Mirjalili, Seyedali Farimani, Amir Barati Carnegie Mellon Univ Dept Mech Engn Pittsburgh PA 15213 USA Torrens Univ Australia Ctr Artificial Intelligence Res & Optimizat Adelaide SA Australia Yonsei Univ Yonsei Frontier Lab Seoul South Korea Carnegie Mellon Univ Machine Learning Dept Pittsburgh PA USA Carnegie Mellon Univ Dept Biomed Engn Pittsburgh PA USA

Metaheuristic algorithms are derivative-free optimizers designed to estimate the global optima for optimization problems. Keeping balance between exploitation and exploration and the performance complementarity between the algorithms have led to the introduction of quite a few metaheuristic methods. In this work, we propose a framework based on Multi-Armed Bandits (MAB) problem, which is a classical Reinforcement Learning (RL) method, to intelligently select a suitable optimizer for each optimization problem during the optimization process. This online algorithm selection technique leverages on the convergence behavior of the algorithms to find the right balance of explorationexploitation by choosing the update rule of the algorithm with the most estimated improvement in the solution. By performing experiments with three armed-bandits being Harris Hawks Optimizer (HHO), Differential Evolution (DE), and Whale Optimization algorithm (WOA), we show that the MAB Optimizer selection (named as MAB-OS) framework has the best overall performance on different types of fitness landscapes in terms of both convergence rate and the final solution. The data and codes used for this work are available at: https://***/BaratiLab/MAB-OS. (c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://***/licenses/by- nc- nd/4.0/).

关键词： Metaheuristic Optimization Multi-Armed Bandits Reinforcement Learning algorithm selection Adaptive algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：