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

Reinvestigating the R2 Indicator: Achieving Pareto Compliance by Integration

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Schäpermeier, Lennart Kerschke, Pascal Big Data Analytics in Transportation TU Dresden Germany & ScaDS.AI Dresden Leipzig Germany

In multi-objective optimization, set-based quality indicators are a cornerstone of benchmarking and performance assessment. They capture the quality of a set of trade-off solutions by reducing it to a scalar number. One of the most commonly used set-based metrics is the R2 indicator, which describes the expected utility of a solution set to a decision-maker under a distribution of utility functions. Typically, this indicator is applied by discretizing this distribution of utility functions, yielding a weakly Pareto-compliant indicator. In consequence, adding a nondominated or dominating solution to a solution set may – but does not have to – improve the indicator’s value. In this paper, we reinvestigate the R2 indicator under the premise that we have a continuous, uniform distribution of (Tchebycheff) utility functions. We analyze its properties in detail, demonstrating that this continuous variant is indeed Pareto-compliant – that is, any beneficial solution will improve the metric’s value. Additionally, we provide an efficient computational procedure to compute this metric for bi-objective problems in O(N log N). As a result, this work contributes to the state-of-the-art Pareto-compliant unary performance metrics, such as the hypervolume indicator, offering an efficient and promising alternative. Copyright © 2024, The Authors. All rights reserved.

关键词： Benchmarking

Using Reinforcement Learning for Per-Instance Algorithm Configuration on the TSP

学校读者我要写书评

暂无评论

Using Reinforcement Learning for Per-Instance Algorithm Conf...

2023 IEEE Symposium Series on Computational Intelligence, SSCI 2023

作者： Vinzent Seiler, Moritz Rook, Jeroen Heins, Jonathan Ludger Preub, Oliver Bossek, Jakob Trautmann, Heike University of Twente Data Management and Biometrics Enschede Netherlands Tu Dresden Big Data Analytics in Transportation Dresden Germany Aachen University Chair for Ai Methodology Rwth Aachen Germany University of Münster Data Science: Statistics and Optimization Münster Germany University of Twente Data Science: Statistics and Optimization Enschede Netherlands

ISBN: (纸本)9781665430654

Automated Algorithm Configuration (AAC) usually takes a global perspective: it identifies a parameter configuration for an (optimization) algorithm that maximizes a performance metric over a set of instances. However, the optimal choice of parameters strongly depends on the instance at hand and should thus be calculated on a per-instance basis. We explore the potential of Per-Instance Algorithm Configuration (PIAC) by using Reinforcement Learning (RL). To this end, we propose a novel PIAC approach that is based on deep neural networks. We apply it to predict configurations for the Lin-Kernighan heuristic (LKH) for the Traveling Salesperson Problem (TSP) individually for every single instance. To train our PIAC approach, we create a large set of 100 000 TSP instances with 2 000 nodes each - currently the largest benchmark set to the best of our knowledge. We compare our approach to the state-of-the-art AAC method Sequential Model-based Algorithm Configuration (SMAC). The results show that our PIAC approach outperforms this baseline on both the newly created instance set and established instance sets. © 2023 IEEE.

关键词： Deep Reinforcement Learning Per-Instance Algorithm Configuration Traveling Salesperson Problem

Deep-ELA: Deep Exploratory Landscape Analysis with Self-Supervised Pretrained Transformers for Single- and Multi-Objective Continuous Optimization Problems

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Seiler, Moritz Vinzent Kerschke, Pascal Trautmann, Heike Paderborn University Germany Big Data Analytics in Transportation TU Dresden Germany ScaDS.AI Dresden Leipzig Germany Data Management and Biometrics Group University of Twente Netherlands

In many recent works, the potential of Exploratory Landscape Analysis (ELA) features to numerically characterize, in particular, single-objective continuous optimization problems has been demonstrated. These numerical features provide the input for all kinds of machine learning tasks on continuous optimization problems, ranging, i.a., from High-level Property Prediction to Automated Algorithm Selection and Automated Algorithm Configuration. Without ELA features, analyzing and understanding the characteristics of single-objective continuous optimization problems is — to the best of our knowledge — very limited. Yet, despite their usefulness, as demonstrated in several past works, ELA features suffer from several drawbacks. These include, in particular, (1.) a strong correlation between multiple features, as well as (2.) its very limited applicability to multiobjective continuous optimization problems. As a remedy, recent works proposed deep learning-based approaches as alternatives to ELA. In these works, e.g., point-cloud transformers were used to characterize an optimization problem’s fitness landscape. However, these approaches require a large amount of labeled training data. Within this work, we propose a hybrid approach, Deep-ELA, which combines (the benefits of) deep learning and ELA features. Specifically, we pre-trained four transformers on millions of randomly generated optimization problems to learn deep representations of the landscapes of continuous single- and multi-objective optimization problems. Our proposed framework can either be used out-of-the-box for analyzing single- and multi-objective continuous optimization problems, or subsequently fine-tuned to various tasks focussing on algorithm behavior and problem understanding. © 2024, CC BY.

关键词： Self-supervised learning

Dancing to the State of the Art? How Candidate Lists Influence LKH for Solving the Traveling Salesperson Problem

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Heins, Jonathan Schäpermeier, Lennart Kerschke, Pascal Whitley, Darrell Big Data Analytics in Transportation TU Dresden Germany ScaDS.AI Dresden/Leipzig Dresden Germany Department of Computer Science Colorado State University Fort Collins United States

Solving the Traveling Salesperson Problem (TSP) remains a persistent challenge, despite its fundamental role in numerous generalized applications in modern contexts. Heuristic solvers address the demand for finding high-quality solutions efficiently. Among these solvers, the Lin-Kernighan-Helsgaun (LKH) heuristic stands out, as it complements the performance of genetic algorithms across a diverse range of problem instances. However, frequent timeouts on challenging instances hinder the practical applicability of the solver. Within this work, we investigate a previously overlooked factor contributing to many timeouts: The use of a fixed candidate set based on a tree structure. Our investigations reveal that candidate sets based on Hamiltonian circuits contain more optimal edges. We thus propose to integrate this promising initialization strategy, in the form of POPMUSIC, within an efficient restart version of LKH. As confirmed by our experimental studies, this refined TSP heuristic is much more efficient – causing fewer timeouts and improving the performance (in terms of penalized average runtime) by an order of magnitude – and thereby challenges the state of the art in TSP solving. Copyright © 2024, The Authors. All rights reserved.

关键词： Genetic algorithms

A COLLECTION OF DEEP LEARNING-BASED FEATURE-FREE APPROACHES FOR CHARACTERIZING SINGLE-OBJECTIVE CONTINUOUS FITNESS LANDSCAPES

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Seiler, Moritz Vinzent Prager, Raphael Patrick Kerschke, Pascal Trautmann, Heike Data Science: Statistics and Optimization University of Münster Germany Big Data Analytics in Transportation Tu Dresden Germany University of Twente Netherlands

Exploratory Landscape Analysis is a powerful technique for numerically characterizing landscapes of single-objective continuous optimization problems. Landscape insights are crucial both for problem understanding as well as for assessing benchmark set diversity and composition. Despite the irrefutable usefulness of these features, they suffer from their own ailments and downsides. Hence, in this work we provide a collection of different approaches to characterize optimization landscapes. Similar to conventional landscape features, we require a small initial sample. However, instead of computing features based on that sample, we develop alternative representations of the original sample. These range from point clouds to 2D images and, therefore, are entirely feature-free. We demonstrate and validate our devised methods on the BBOB testbed and predict, with the help of Deep Learning, the high-level, expert-based landscape properties such as the degree of multimodality and the existence of funnel structures. The quality of our approaches is on par with methods relying on the traditional landscape features. Thereby, we provide an exciting new perspective on every research area which utilizes problem information such as problem understanding and algorithm design as well as automated algorithm configuration and selection. © 2022, CC BY.

关键词： Optimization

MOLE: DIGGING TUNNELS THROUGH MULTIMODAL MULTI-OBJECTIVE LANDSCAPES

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Schäpermeier, Lennart Grimme, Christian Kerschke, Pascal Big Data Analytics in Transportation TU Dresden Dresden Germany Statistics and Optimization Group University of Münster Münster Germany

Recent advances in the visualization of continuous multimodal multi-objective optimization (MMMOO) landscapes brought a new perspective to their search dynamics. Locally efficient (LE) sets, often considered as traps for local search, are rarely isolated in the decision space. Rather, intersections by superposing attraction basins lead to further solution sets that at least partially contain better solutions. The Multi-Objective Gradient Sliding Algorithm (MOGSA) is an algorithmic concept developed to exploit these superpositions. While it has promising performance on many MMMOO problems with linear LE sets, closer analysis of MOGSA revealed that it does not sufficiently generalize to a wider set of test problems. Based on a detailed analysis of shortcomings of MOGSA, we propose a new algorithm, the Multi-Objective Landscape Explorer (MOLE). It is able to efficiently model and exploit LE sets in MMMOO problems. An implementation of MOLE is presented for the bi-objective case, and the practicality of the approach is shown in a benchmarking experiment on the Bi-Objective BBOB testbed. Copyright © 2022, The Authors. All rights reserved.

关键词： Multiobjective optimization

Physical Layer Security: Learning-Aided Attack Detection based on 5G NR SRS

学校读者我要写书评

暂无评论

Physical Layer Security: Learning-Aided Attack Detection bas...

IEEE Conference on Communications and Network Security (CNS)

作者： Jonas Ninnemann Felix Rauschert Paul Schwarzbach Pascal Kerschke Oliver Michler Chair of Transport Systems Information Technology Faculty of Transport and Traffic Sciences “Friedrich List” TUD Dresden University of Technology Chair of Big Data Analytics in Transportation Faculty of Transport and Traffic Sciences “Friedrich List” TUD Dresden University of Technology

ISBN: (数字)9798350375961

ISBN: (纸本)9798350375978

Physical layer security (PLS) constitutes a crucial foundation for future trustworthy networks, particularly in scenarios involving low-resource devices, low-latency, and high-mobility applications. The effectiveness of PLS can be significantly enhanced through the integration of jamming and anomaly detection mechanisms that exploit the inherent randomness of the wireless channel and leverage machine learning (ML) techniques. Our approach capitalizes on 5G new radio (NR) sounding reference signal (SRS) measurements to facilitate accurate channel estimation and its corresponding SNR estimation, thereby enabling the identification of anomalous behavior that may be indicative of a potential attack. For the learning-aided detection, various features are extracted from the estimated channel state information (CSI), particularly the channel impulse response (CIR) of the 5G NR SRS. Through the training of an ML classification model on a comprehensive dataset of SRS measurements collected in our laboratory, we achieved a detection accuracy above 90%, investigated feature importance, and demonstrated the viability of this approach in bolstering PLS in future wireless networks.

关键词： Training Accuracy 5G mobile communication Wireless networks Channel estimation Physical layer security Feature extraction Low latency communication Jamming Channel impulse response

Hybridizing Target- and SHAP-encoded Features for Algorithm Selection in Mixed-variable Black-box Optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Dietrich, Konstantin Prager, Raphael Patrick Doerr, Carola Trautmann, Heike Big Data Analytics in Transportation TU Dresden Germany ScaDS.AI Dresden Germany Data Science: Statistics and Optimization University of Münster Germany Sorbonne Université CNRS LIP6 Paris France Machine Learning and Optimisation Paderborn University Germany Data Management and Biometrics Group University of Twente Netherlands

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 algorithm selection 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. Copyright © 2024, The Authors. All rights reserved.

关键词： Optimization

Using Reinforcement Learning for Per-Instance Algorithm Configuration on the TSP

学校读者我要写书评

暂无评论

Using Reinforcement Learning for Per-Instance Algorithm Conf...

IEEE Symposium Series on Computational Intelligence (SSCI)

作者： Moritz Vinzent Seiler Jeroen Rook Jonathan Heins Oliver Ludger Preuß Jakob Bossek Heike Trautmann Data Science: Statistics and Optimization University of Münster Münster Germany Data Management and Biometrics University of Twente Enschede Netherlands Big Data Analytics in Transportation TU Dresden Dresden Germany Chair for AI Methodology RWTH Aachen University Aachen Germany Data Science: Statistics and Optimization University of Twente Enschede Netherlands

关键词：