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

An Adaptive Re-evaluation Method for Evolution Strategy under Additive Noise

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Dinu, Catalin-Viorel Patel, Yash J. Bonet-Monroig, Xavier Wang, Hao LIACS Leiden University Leiden Netherlands Applied Quantum Algorithms 〈aQaL〉 group and Instituut-Lorentz Leiden University Leiden Netherlands Honda Research Institute Europe GmbH Offenbach am Main Germany

The Covariance Matrix Adaptation Evolutionary Strategy (CMA-ES) is one of the most advanced algorithms in numerical black-box optimization. For noisy objective functions, several approaches were proposed to mitigate the noise, e.g., re-evaluations of the same solution or adapting the population size. In this paper, we devise a novel method to adaptively choose the optimal re-evaluation number for function values corrupted by additive Gaussian white noise. We derive a theoretical lower bound of the expected improvement achieved in one iteration of CMA-ES, given an estimation of the noise level and the Lipschitz constant of the function’s gradient. Solving for the maximum of the lower bound, we obtain a simple expression of the optimal re-evaluation number. We experimentally compare our method to the state-of-the-art noise-handling methods for CMA-ES on a set of artificial test functions across various noise levels, optimization budgets, and dimensionality. Our method demonstrates significant advantages in terms of the probability of hitting near-optimal function values. Copyright © 2024, The Authors. All rights reserved.

关键词： Budget control

Identifiability of Autonomous and Controlled Open Quantum Systems

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Parvaiz, Waqas Aspman, Johannes Wodecki, Ales Korpas, Georgios Marecek, Jakub Department of Computer Science Czech Technical University Prague Czech Republic Quantum Technologies Group HSBC Lab Emerging Technologies Innovation & Ventures Singapore Archimedes Research Unit on AI Data Science and Algorithms Athena Research and Innovation Center Marousi Greece

Open quantum systems are a rich area of research in the intersection of quantum mechanics and stochastic analysis. By considering a variety of master equations, we unify multiple views of autonomous and controlled open quantum systems and, through considering their measurement dynamics, connect them to classical linear and bilinear system identification theory. This allows us to formulate corresponding notions of quantum state identifiability for these systems which, in particular, applies to quantum state tomography, providing conditions under which the probed quantum system is reconstructible. Interestingly, the dynamical representation of the system lends itself to considering two types of identifiability: the full master equation recovery and the recovery of the corresponding system matrices of the linear and bilinear systems. Both of these concepts are discussed in detail, and conditions under which reconstruction is possible are given. We set the groundwork for a number of constructive approaches to the identification of open quantum systems. Copyright © 2025, The Authors. All rights reserved.

关键词： Stochastic systems

Can a few decide for many? the metric distortion of sortition 24

学校读者我要写书评

暂无评论

Can a few decide for many? the metric distortion of sortitio...

Proceedings of the 41st International Conference on Machine Learning

作者： Ioannis Caragiannis Evi Micha Jannik Peters Department of Computer Science Aarhus University Aarhus Denmark Computer Science Harvard University Cambridge Research Group Efficient Algorithms Faculty IV - Electrical Engineering and Computer Science TU Berlin Berlin Germany

Recent works have studied the design of algorithms for selecting representative sortition panels. However, the most central question remains unaddressed: Do these panels reflect the entire population's opinion? We present a positive answer by adopting the concept of metric distortion from computational social choice, which aims to quantify how much a panel's decision aligns with the ideal decision of the population when preferences and agents lie on a metric space. We show that uniform selection needs only logarithmically many agents in terms of the number of alternatives to achieve almost optimal distortion. We also show that Fair Greedy Capture, a selection algorithm introduced recently by Ebadian & Micha (2024), matches uniform selection's guarantees of almost optimal distortion and also achieves constant ex-post distortion, ensuring a "best of both worlds" performance.

关键词：

Performance of RIS-Assisted Two-Way Communications with Phase Noise

学校读者我要写书评

暂无评论

Performance of RIS-Assisted Two-Way Communications with Ph...

International Conference on Advanced Engineering Theory and Applications, AETA 2022

作者： Tu, Lam-Thanh Nguyen, Tan N. Tran, Phuong T. Van Huynh, Van Trung Duy, Tran Nguyen, Nhat-Tien Voznak, Miroslav Communication and Signal Processing Research Group Faculty of Electrical and Electronics Engineering Ton Duc Thang University Ho Chi Minh city Viet Nam Wireless Communications Research Group Faculty of Electrical and Electronics Engineering Ton Duc Thang University Ho Chi Minh city Viet Nam Modeling Evolutionary Algorithms Simulation and Artificial Intelligence Faculty of Electrical and Electronics Engineering Ton Duc Thang University Ho Chi Minh city Viet Nam Posts and Telecommunications Institute of Technology Ho Chi Minh city Viet Nam VSB—Technical University of Ostrava Ostrava Czech Republic

ISBN: (纸本)9789819987023

The performance of two-way full-duplex communications with the help of reconfigurable intelligent surface (RIS) under phase noise is investigated in this work. Particularly, we study the outage probability, the average rate of each end-user, and the average sum rate of the whole network under both optimal phase-shift and random phase-shift design. Simulation results via the Monte-Carlo method are given to confirm the advantages of the optimal design compared with the random one and to unveil the impact of some essential parameters such as the number of RIS elements, and the number of quantization bits on the system performance. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.

关键词： Phase noise

Online elicitation of necessarily optimal matchings

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Peters, Jannik Research Group Efficient Algorithms TU Berlin Germany

In this paper, we study the problem of eliciting preferences of agents in the house allocation model. For this we build on a recent model of Hosseini et al. (2021)[AAAI’21] and focus on the task of eliciting preferences to find matchings which are necessarily optimal, i.e., optimal under all possible completions of the elicited preferences. In particular, we follow the approach of Hosseini et al. (2021) and investigate the elicitation of necessarily Pareto optimal (NPO) and necessarily rank-maximal (NRM) matchings. Most importantly, we answer their open question and give an online algorithm for eliciting an NRM matching in the next-best query model which is 3/2 -competitive, i.e., it takes at most 3/2 as many queries as an optimal algorithm. Besides this, we extend this field of research by introducing two new natural models of elicitation and by studying both the complexity of determining whether a necessarily optimal matching exists in them, and by giving online algorithms for these models. © 2021, CC BY.

关键词： Pareto principle

Detours in Directed Graphs 39

学校读者我要写书评

暂无评论

Detours in Directed Graphs

39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022

作者： Fomin, Fedor V. Golovach, Petr A. Lochet, William Sagunov, Danil Simonov, Kirill Saurabh, Saket Department of Informatics University of Bergen Norway St. Petersburg Department of V.A. Steklov Institute of Mathematics Russia JetBrains Research Saint Petersburg Russia Algorithms and Complexity Group TU Wien Austria Institute of Mathematical Sciences HBNI Chennai India

ISBN: (纸本)9783959772228

We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour, the task is to decide whether a graph has an (s, t)-path of length at least distG(s, t) + k (where distG(s, t) denotes the length of a shortest path from s to t). Bezáková et al. [7] proved that on undirected graphs the problem is fixed-parameter tractable (FPT) by providing an algorithm of running time 2O(k) · n. Further, they left the parameterized complexity of the problem on directed graphs open. Our first main result establishes a connection between Longest Detour on directed graphs and 3-Disjoint Paths on directed graphs. Using these new insights, we design a 2O(k) · nO(1) time algorithm for the problem on directed planar graphs. Further, the new approach yields a significantly faster FPT algorithm on undirected graphs. In the second variant of Longest Path, namely Longest Path above Diameter, the task is to decide whether the graph has a path of length at least diam(G) + k (diam(G) denotes the length of a longest shortest path in a graph G). We obtain dichotomy results about Longest Path above Diameter on undirected and directed graphs. For (un)directed graphs, Longest Path above Diameter is NP-complete even for k = 1. However, if the input undirected graph is 2-connected, then the problem is FPT. On the other hand, for 2-connected directed graphs, we show that Longest Path above Diameter is solvable in polynomial time for each k ∈ {1, . . ., 4} and is NP-complete for every k ≥ 5. The parameterized complexity of Longest Detour on general directed graphs remains an interesting open problem. © Fedor V. Fomin, Petr A. Golovach, William Lochet, Danil Sagunov, Kirill Simonov, and Saket Saurabh.

关键词： Directed graphs

Untangling Circular Drawings: algorithms and Complexity 32

学校读者我要写书评

暂无评论

Untangling Circular Drawings: Algorithms and Complexity

32nd International Symposium on algorithms and Computation, ISAAC 2021

作者： Bhore, Sujoy Li, Guangping Nöllenburg, Martin Rutter, Ignaz Wu, Hsiang-Yun Indian Institute of Science Education and Research Bhopal India Algorithms and Complexity Group TU Wien Austria Universität Passau Germany Research Unit of Computer Graphics TU Wien Austria

ISBN: (纸本)9783959772143

We consider the problem of untangling a given (non-planar) straight-line circular drawing δG of an outerplanar graph G = (V, E) into a planar straight-line circular drawing by shifting a minimum number of vertices to a new position on the circle. For an outerplanar graph G, it is clear that such a crossing-free circular drawing always exists and we define the circular shifting number shift◦(δG) as the minimum number of vertices that need to be shifted to resolve all crossings of δG. We show that the problem Circular Untangling, asking whether shift◦(δG) ≤ K for a given integer K, is NP-complete. Based on this result we study Circular Untangling for almost-planar circular drawings, in which a single edge is involved in all the crossings. In this case we provide a tight upper bound shift◦(δG) ≤ ⌊n2 ⌋ - 1, where n is the number of vertices in G, and present a polynomial-time algorithm to compute the circular shifting number of almost-planar drawings. © Sujoy Bhore, Guangping Li, Martin Nöllenburg, Ignaz Rutter, and Hsiang-Yun Wu.

关键词： Computational complexity

Multi tree operators for genetic programming to identify optimal energy flow controllers 21

学校读者我要写书评

暂无评论

Multi tree operators for genetic programming to identify opt...

2021 Genetic and Evolutionary Computation Conference, GECCO 2021

作者： Kefer, Kathrin Hanghofer, Roland Kefer, Patrick Stöger, Markus Hofer, Bernd Affenzeller, Michael Winkler, Stephan Fronius International GmbH Thalheim Austria Research and Develoment Fh OO7die Forschungs und Entwicklungs GmbH Research Group Heuristic and Evolutionary Algorithms Laboratory Hagenberg Austria Research and Develoment Fh Oö Forschungs und Entwicklungs GmbH Research Group Asic Wels Austria

ISBN: (纸本)9781450383516

Genetic programming is known to be able to find nearly optimal solutions for quite complex problems. So far, the focus was more on solution candidates that hold just one symbolic regression tree. For complex problems like controlling the energy flows of a building in order to minimize its energy costs, this is often not sufficient. This is why this work presents a solution candidate implementation in HeuristicLab where they hold multiple symbolic regression trees. Additionally, also new crossover and mutation operators were implemented as the existing ones cannot handle multiple trees in one solution candidate. The first type of operators applies them on all trees in the solution candidate, whereas the second one only applies them to one of the trees. It is found that applying the mutator to only one of the trees significantly reduces the training duration. Applying the crossover to one of the trees instead of all needs longer training times but can also achieve better results. © 2021 ACM.

关键词： Genetic programming

Can a Few Decide for Many? The Metric Distortion of Sortition

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Caragiannis, Ioannis Micha, Evi Peters, Jannik Department of Computer Science Aarhus University Aarhus Denmark Computer Science Harvard University Cambridge United States Research Group Efficient Algorithms Faculty IV - Electrical Engineering and Computer Science TU Berlin Berlin Germany

Recent works have studied the design of algorithms for selecting representative sortition panels. However, the most central question remains unaddressed: Do these panels reflect the entire population's opinion? We present a positive answer by adopting the concept of metric distortion from computational social choice, which aims to quantify how much a panel's decision aligns with the ideal decision of the population when preferences and agents lie on a metric space. We show that uniform selection needs only logarithmically many agents in terms of the number of alternatives to achieve almost optimal distortion. We also show that Fair Greedy Capture, a selection algorithm introduced recently by Ebadian & Micha (2024), matches uniformselection's guarantees of almost optimal distortion and also achieves constant ex-post distortion, ensuring a "best of both worlds" performance. © 2024, CC BY.

关键词：