In this article, we build upon previous work on designing informative and efficient Exploratory Landscape Analysis features for characterizing problems' landscapes and show their effectiveness in automatically con...
详细信息
In this article, we build upon previous work on designing informative and efficient Exploratory Landscape Analysis features for characterizing problems' landscapes and show their effectiveness in automatically constructing algorithmselection models in continuous black-box optimization problems. Focusing on algorithm performance results of the COCO platform of several years, we construct a representative set of high-performing complementary solvers and present an algorithmselection model that, compared to the portfolio's single best solver, on average requires less than half of the resources for solving a given problem. Therefore, there is a huge gain in efficiency compared to classical ensemble methods combined with an increased insight into problem characteristics and algorithm properties by using informative features. The model acts on the assumption that the function set of the Black-Box Optimization Benchmark is representative enough for practical applications. The model allows for selecting the best suited optimization algorithm within the considered set for unseen problems prior to the optimization itself based on a small sample of function evaluations. Note that such a sample can even be reused for the initial population of an evolutionary (optimization) algorithm so that even the feature costs become negligible.
It has long been observed that for practically any computational problem that has been intensely studied, different instances are best solved using different algorithms. This is particularly pronounced for computation...
详细信息
It has long been observed that for practically any computational problem that has been intensely studied, different instances are best solved using different algorithms. This is particularly pronounced for computationally hard problems, where in most cases, no single algorithm defines the state of the art;instead, there is a set of algorithms with complementary strengths. This performance complementarity can be exploited in various ways, one of which is based on the idea of selecting, from a set of given algorithms, for each problem instance to be solved the one expected to perform best. The task of automatically selecting an algorithm from a given set is known as the per-instance algorithmselection problem and has been intensely studied over the past 15 years, leading to major improvements in the state of the art in solving a growing number of discrete combinatorial problems, including propositional satisfiability and AI planning. Per-instance algorithmselection also shows much promise for boosting performance in solving continuous and mixed discrete/continuous optimisation problems. This survey provides an overview of research in automated algorithm selection, ranging from early and seminal works to recent and promising application areas. Different from earlier work, it covers applications to discrete and continuous problems, and discusses algorithmselection in context with conceptually related approaches, such as algorithm configuration, scheduling, or portfolio selection. Since informative and cheaply computable problem instance features provide the basis for effective per-instance algorithmselection systems, we also provide an overview of such features for discrete and continuous problems. Finally, we provide perspectives on future work in the area and discuss a number of open research challenges.
In recent years, feature-based automated algorithm selection using exploratory landscape analysis has demonstrated its great potential in single-objective continuous black-box optimization. However, feature computatio...
详细信息
ISBN:
(纸本)9783031147142;9783031147135
In recent years, feature-based automated algorithm selection using exploratory landscape analysis has demonstrated its great potential in single-objective continuous black-box optimization. However, feature computation is problem-specific and can be costly in terms of computational resources. This paper investigates feature-free approaches that rely on state-of-the-art deep learning techniques operating on either images or point clouds. We show that point-cloud-based strategies, in particular, are highly competitive and also substantially reduce the size of the required solver portfolio. Moreover, we highlight the effect and importance of cost-sensitive learning in automated algorithm selection models.
Massive multiple-input-multiple-output (MIMO) systems support advanced applications with high data rates, low latency, and high reliability in next-generation mobile networks. However, using machine learning in massiv...
详细信息
Massive multiple-input-multiple-output (MIMO) systems support advanced applications with high data rates, low latency, and high reliability in next-generation mobile networks. However, using machine learning in massive MIMO resource allocation is challenging due to quality of service (QoS) and network complexity across layers. This work presents a novel framework for adapting the scheduling and antenna allocation in massive MIMO systems using deep reinforcement learning (DRL). Rather than directly assigning execution parameters, the proposed framework utilizes DRL to select combinations of algorithms based on the current traffic conditions. The DRL model is trained using a specialized Markov decision process (MDP) model with a componentized action structure and is evaluated in realistic traffic scenarios. The results show that the proposed framework increases satisfied users by 7.2% and 12.5% compared to static algorithm combinations and other cross-layer adaptation methods. This demonstrates the effectiveness of the framework in managing and optimizing resource allocation in a flexible and adaptable manner.
In this work we focus on the well-known Euclidean Traveling Salesperson Problem (TSP) and two highly competitive inexact heuristic TSP solvers, EAX and LKH, in the context of per-instance algorithmselection (AS). We ...
详细信息
ISBN:
(纸本)9783030581114;9783030581121
In this work we focus on the well-known Euclidean Traveling Salesperson Problem (TSP) and two highly competitive inexact heuristic TSP solvers, EAX and LKH, in the context of per-instance algorithmselection (AS). We evolve instances with 1 000 nodes where the solvers show strongly different performance profiles. These instances serve as a basis for an exploratory study on the identification of well-discriminating problem characteristics (features). Our results in a nutshell: we show that even though (1) promising features exist, (2) these are in line with previous results from the literature, and (3) models trained with these features are more accurate than models adopting sophisticated feature selection methods, the advantage is not close to the virtual best solver in terms of penalized average runtime and so is the performance gain over the single best solver. However, we show that a feature-free deep neural network based approach solely based on visual representation of the instances already matches classical AS model results and thus shows huge potential for future studies.
Classic automated algorithm selection (AS) for (combinatorial) optimization problems heavily relies on so-called instance features, i.e., numerical characteristics of the problem at hand ideally extracted with computa...
详细信息
ISBN:
(纸本)9781450383523
Classic automated algorithm selection (AS) for (combinatorial) optimization problems heavily relies on so-called instance features, i.e., numerical characteristics of the problem at hand ideally extracted with computationally low-demanding routines. For the traveling salesperson problem (TSP) a plethora of features have been suggested. Most of these features are, if at all, only normalized imprecisely raising the issue of feature values being strongly affected by the instance size. Such artifacts may have detrimental effects on algorithmselection models. We propose a normalization for two feature groups which stood out in multiple AS studies on the TSP: (a) features based on a minimum spanning tree (MST) and (b) a k-nearest neighbor graph (NNG) transformation of the input instance. To this end we theoretically derive minimum and maximum values for properties of MSTs and k-NNGs of Euclidean graphs. We analyze the differences in feature space between normalized versions of these features and their unnormalized counterparts. Our empirical investigations on various TSP benchmark sets point out that the feature scaling succeeds in eliminating the effect of the instance size. Eventually, a proof-of-concept AS-study shows promising results: models trained with normalized features tend to outperform those trained with the respective vanilla features.
The Traveling-Salesperson-Problem (TSP) is arguably one of the best-known NP-hard combinatorial optimization problems. The two sophisticated heuristic solvers LKH and EAX and respective (restart) variants manage to ca...
详细信息
ISBN:
(纸本)9781728169293
The Traveling-Salesperson-Problem (TSP) is arguably one of the best-known NP-hard combinatorial optimization problems. The two sophisticated heuristic solvers LKH and EAX and respective (restart) variants manage to calculate close-to optimal or even optimal solutions, also for large instances with several thousand nodes in reasonable time. In this work we extend existing benchmarking studies by addressing anytime behaviour of inexact TSP solvers based on empirical runtime distributions leading to an increased understanding of solver behaviour and the respective relation to problem hardness. It turns out that performance ranking of solvers is highly dependent on the focused approximation quality. Insights on intersection points of performances offer huge potential for the construction of hybridized solvers depending on instance features. Moreover, instance features tailored to anytime performance and corresponding performance indicators will highly improve automated algorithm selection models by including comprehensive information on solver quality.
Recommendations-as-a-Service (RaaS) ease the process for small and medium-sized enterprises (SMEs) to offer product recommendations to their customers. Current RaaS, however, suffer from a one-size-fits-all concept, i...
详细信息
ISBN:
(纸本)9781450362436
Recommendations-as-a-Service (RaaS) ease the process for small and medium-sized enterprises (SMEs) to offer product recommendations to their customers. Current RaaS, however, suffer from a one-size-fits-all concept, i.e. they apply the same recommendation algorithm for all SMEs. We introduce Darwin & Goliath, a RaaS that features multiple recommendation frameworks (Apache Lucene, TensorFlow, ...), and identifies the ideal algorithm for each SME automatically. Darwin & Goliath further offers per-instance algorithmselection and a white label feature that allows SMEs to offer a RaaS under their own brand. Since November 2018, Darwin & Goliath has delivered more than 1m recommendations with a CTR = 0.5%.
Exploratory landscape analysis (ELA) is a well-established tool to characterize optimization problems via numerical features. ELA is used for problem comprehension, algorithm design, and applications such as automated...
详细信息
ISBN:
(纸本)9783031700675;9783031700682
Exploratory landscape analysis (ELA) is a well-established tool to characterize optimization problems via numerical features. ELA is used for problem comprehension, algorithm design, and applications such as automated algorithm selection and configuration. Until recently, however, ELA was limited to search spaces with either continuous or discrete variables, neglecting problems with mixed variable types. This gap was addressed in a recent study that uses an approach based on target-encoding to compute exploratory landscape features for mixed-variable problems. In this work, we investigate an alternative encoding scheme based on SHAP values. While these features do not lead to better results in the algorithmselection setting considered in previous work, the two different encoding mechanisms exhibit complementary performance. Combining both feature sets into a hybrid approach outperforms each encoding mechanism individually. Finally, we experiment with two different ways of meta-selecting between the two feature sets. Both approaches are capable of taking advantage of the performance complementarity of the models trained on target-encoded and SHAP-encoded feature sets, respectively.
This paper describes a way of building an algorithmselection system for the two-dimensional rectangle packing problem. A list of features was defined, and five heuristics and metaheuristics were selected as solvers. ...
详细信息
ISBN:
(数字)9781665467087
ISBN:
(纸本)9781665467087
This paper describes a way of building an algorithmselection system for the two-dimensional rectangle packing problem. A list of features was defined, and five heuristics and metaheuristics were selected as solvers. The first step involves the extraction of features from the input problem instances. Using those computed features, machine learning regressors will predict the performance of each solver on the instance and, therefore, find the most fitted algorithm for it. Both the predicted execution time and the expected quality of the solution were used as performance metrics for the selection step. The experimental results showed that the built system has a high accuracy in predicting the best algorithm based on the runtime execution and the solution quality. Moreover, the system achieves these results with much lower computational resources than running the actual solvers of the problem.
暂无评论