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

Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency for Many Objectives

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2024年第5期28卷 1442-1454页

作者： Zheng, Weijie Doerr, Benjamin Harbin Inst Technol Shenzhen Int Res Inst Artificial Intelligence Sch Comp Sci & Technol Shenzhen 518055 Peoples R China Inst Polytech Paris Ecole Polytech CNRS Lab Informat F-91128 Palaiseau France

The nondominated sorting genetic algorithm II (NSGA-II) is one of the most prominent algorithms to solve multiobjective optimization problems. Despite numerous successful applications, several studies have shown that the NSGA-II is less effective for larger numbers of objectives. In this work, we use mathematical runtime analyses to rigorously demonstrate and quantify this phenomenon. We show that even on the simple m-objective generalization of the discrete OneMinMax benchmark, where every solution is Pareto optimal, the NSGA-II also with large population sizes cannot compute the full Pareto front (objective vectors of all Pareto optima) in subexponential time when the number of objectives is at least three. The reason for this unexpected behavior lies in the fact that in the computation of the crowding distance, the different objectives are regarded independently. This is not a problem for two objectives, where any sorting of a pairwise incomparable set of solutions according to one objective is also such a sorting according to the other objective (in the inverse order).

关键词： Many-objective optimization nondominated sorting genetic algorithm II (NSGA-II) runtime analysis theory of computing Many-objective optimization nondominated sorting genetic algorithm II (NSGA-II) runtime analysis theory of computing

来源：评论

学校读者我要写书评

暂无评论

Why Do Students Struggle in CS theory Courses So Much?

引用

ACM TRANSACTIONS ON computing EDUCATION 2024年第1期25卷 1-5页

作者： Edward, Ryan US Mil Acad West Point Dept Elect Engn & Comp Sci West Point NY 10996 USA

theory courses are required within CS curricula because of their far-reaching impacts on what makes the CS field special, namely what limits there are for computers. Students nearly universally find this course frustrating and challenging as it often requires formal proofs and reasoning. We in the CER community have long had issue with determining where the underlying cognitive barriers are with students in these courses, and how to address them. Various strategies-such as in-class examples, lecture techniques, course structure adjustments, and visual aids-have been explored. However, none have led to substantial progress in identifying the core issues. In this opinion article I give my hypothesis as to what I believe the central fundamental issue is, and that it has not yet been explored within a CER setting. If we as a community want to bridge the gaps students have within formal courses like theory, we need to face it head-on. CCS Concepts: center dot Social and professional topics-computing education;center dot theory of computation-Computability;Formal languages and automata theory;Complexity classes

关键词： theory of computing formal languages computer science education

来源：评论

学校读者我要写书评

暂无评论

Mathematical runtime analysis for the non-dominated sorting genetic algorithm II (NSGA-II)

引用

ARTIFICIAL INTELLIGENCE 2023年 325卷

作者： Zheng, Weijie Doerr, Benjamin Harbin Inst Technol Int Res Inst Artificial Intelligence Sch Comp Sci & Technol Shenzhen Peoples R China Inst Polytech Paris Ecole Polytech Lab Informat LIX CNRS Palaiseau France

The non-dominated sorting genetic algorithm II (NSGA-II) is the most intensively used multi-objective evolutionary algorithm (MOEA) in real-world applications. However, in contrast to several simple MOEAs analyzed also via mathematical means, no such study exists for the NSGA-II so far. In this work, we show that mathematical runtime analyses are feasible also for the NSGA-II. As particular results, we prove that with a population size four times larger than the size of the Pareto front, the NSGA-II with two classic mutation operators and four different ways to select the parents satisfies the same asymptotic runtime guarantees as the SEMO and GSEMO algorithms on the basic ONEMINMAx and LEADINGONESTRAILINGZEROES benchmarks. However, if the population size is only equal to the size of the Pareto front, then the NSGA-II cannot efficiently compute the full Pareto front: for an exponential number of iterations, the population will always miss a constant fraction of the Pareto front. Our experiments confirm the above findings.(c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons .org /licenses /by-nc -nd /4 .0/).

关键词： NSGA-II Runtime analysis Multi-objective optimization theory of computing

来源：评论

学校读者我要写书评

暂无评论

Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives

引用

EVOLUTIONARY COMPUTATION 2023年第4期31卷 337-373页

作者： Zheng, Weijie Doerr, Benjamin Harbin Inst Technol Int Res Inst Artificial Intelligence Sch Comp Sci & Technol Shenzhen Peoples R China Inst Polytech Paris Ecole Polytech CNRS Lab Informat LIX Palaiseau France

Multiobjective evolutionary algorithms are successfully applied in many real-world multiobjective optimization problems. As for many other AI methods, the theoretical understanding of these algorithms is lagging far behind their success in practice. In particular, previous theory work considers mostly easy problems that are composed of unimodal *** a first step towards a deeper understanding of how evolutionary algorithms solve multimodal multiobjective problems, we propose the OneJumpZeroJump problem, a bi-objective problem composed of two objectives isomorphic to the classic jump function benchmark. We prove that the simple evolutionary multiobjective optimizer (SEMO) with probability one does not compute the full Pareto front, regardless of the runtime. In contrast, for all problem sizes n and all jump sizes k is an element of[4..n/2-1], the global SEMO (GSEMO) covers the Pareto front in an expected number of Theta((n-2k)n(k)) iterations. For k=o(n), we also show the tighter bound 3/2en(k+1)+/- o(n(k+1)), which might be the first runtime bound for an MOEA that is tight apart from lower-order terms. We also combine the GSEMO with two approaches that showed advantages in single-objective multimodal problems. When using the GSEMO with a heavy-tailed mutation operator, the expected runtime improves by a factor of at least k(Omega(k)). When adapting the recent stagnation-detection strategy of Rajabi and Witt (2022) to the GSEMO, the expected runtime also improves by a factor of at least k(Omega(k)) and surpasses the heavy-tailed GSEMO by a small polynomial factor in k. Via an experimental analysis, we show that these asymptotic differences are visible already for small problem sizes: A factor-5 speed-up from heavy-tailed mutation and a factor-10 speed-up from stagnation detection can be observed already for jump size 4 and problem sizes between 10 and 50. Overall, our results show that the ideas recently developed to aid single-objective evolutionary algorit

关键词： Multiobjective evolutionary algorithms multimodal problems theory of computing runtime analysis

来源：评论

学校读者我要写书评

暂无评论

Towards a generalized theory comprising digital, neuromorphic and unconventional computing

引用

NEUROMORPHIC computing AND ENGINEERING 2021年第1期1卷

作者： Jaeger, Herbert Univ Groningen Bernoulli Inst Math Comp Sci & Artificial Intelligence & Cognit Syst & Groningen Netherlands

The accelerating race of digital computing technologies seems to be steering towards impasses-technological, economical and environmental-a condition that has spurred research efforts in alternative, 'neuromorphic' (brain-like) computing technologies. Furthermore, for decades, the idea of exploiting nonlinear physical phenomena 'directly' for non-digital computing has been explored under names like 'unconventional computing', 'natural computing', 'physical computing', or 'in-materio computing'. In this article I investigate coordinates and conditions for a generalized concept of 'computing' which comprises digital, neuromorphic, unconventional and possible future 'computing' paradigms. The main contribution of this paper is an in-depth inspection of existing formal conceptualizations of 'computing' in discrete-symbolic, probabilistic and dynamical-systems oriented views. It turns out that different choices of background mathematics lead to decisively different understandings of what 'computing' is. However, across this diversity a unifying coordinate system for theorizing about 'computing' can be distilled.

关键词： neuromorphic computing theory of computing unconventional computing non-digital hardware

来源：评论

学校读者我要写书评

暂无评论

Exploring Error Types in Formal Languages Among Students of Upper Secondary Education 24

Exploring Error Types in Formal Languages Among Students of ...

引用

24th Koli Calling

作者： Schmellenkamp, Marko Stanglmair, Dennis Michaeli, Tilman Zeume, Thomas Ruhr Univ Bochum Bochum Germany Tech Univ Munich TUM Sch Social Sci & Technol Munich Germany

ISBN: (纸本)9798400710384

Foundations of formal languages, as subfield of theoretical computer science, are part of typical upper secondary education curricula. There is very little research on the potential difficulties that students at this level have with this subject. In this paper, we report on an exploratory study of errors in formal languages among upper secondary education students. We collect the data by posing exercises in an intelligent tutoring system and analyzing student input. Our results suggest a) instances of non-functional understanding of concepts such as the empty word or a grammar as a substitution system;b) strategic problems such as lack of foresight when deriving a word or confounding formal specifications with real-world knowledge on certain aspects;and c) various syntactic problems. These findings can serve as a starting point for a broader understanding of how and why students struggle with this topic.

关键词： K-12 computing education types of errors theory of computing theoretical computer science formal languages qualitative analysis

来源：评论

学校读者我要写书评

暂无评论

Optimal Location of Hubs over Networks with Demand Uncertainty: A Fundamental Mathematical Model

Optimal Location of Hubs over Networks with Demand Uncertain...

引用

IEEE International Conference on Fuzzy Systems (FUZZ-IEEE)

作者： Cuzzocrea, Alfredo Gallo, Carmine Fornari, Giulia Gatto, Vittorio Univ Calabria iDEA Lab Arcavacata Di Rende Italy Univ Paris City Paris France ISIRES Turin Italy

ISBN: (纸本)9798350319552;9798350319545

This paper addresses the problem of finding the optimal location for the hubs in a network, under demand uncertainty, and where the allocation of the nodes is treated as a second stage decision. The contribution is represented by a mathematical model that we carved to fit the operational needs of GUROBI Optimizer. The latter allows us to preliminary assessing the performance of the proposed model.

关键词： Network Algorithms theory of computing Optimization Problems

来源：评论

学校读者我要写书评

暂无评论

Optimal Location of Charging Stations for Electric Vehicles: A Theoretically-Sound Heuristic Approach 23

Optimal Location of Charging Stations for Electric Vehicles:...

引用

38th Annual ACM Symposium on Applied computing (ACM SAC)

作者： Cuzzocrea, Alfredo Canade, Luigi Nicolicchia, Riccardo Roldo, Luca Univ Calabria iDEA Lab Arcavacata Di Rende Italy ISIRES Turin Italy

ISBN: (纸本)9781450395175

Due to the increasing awareness of the environmental dangerous effects of greenhouse gases emitted by fossil fuels, electricity is becoming a valid alternative as power source. Therefore, the amount of electric vehicles (EVs) in cities is gradually increasing. However, EVs suffer from driving range limitations compared to the traditional fossil-fuel-based vehicles. Users may need to charge their vehicle away from home and find a sufficient and convenient availability of public charging stations. In this so-delineated scenario, this paper proposes a theoretically-sound heuristic approach.

关键词： Network Algorithms theory of computing Heuristic Algorithms

来源：评论

学校读者我要写书评

暂无评论

A Machine Learning Methodology for Optimal Big Data Processing in Advanced Smart City Environments 23rd

A Machine Learning Methodology for Optimal Big Data Processi...

引用

23rd International Conference on Computational Science and its Applications (ICCSA)

作者： Cuzzocrea, Alfredo Canade, Luigi Nicolicchia, Riccardo Roldo, Luca Univ Calabria IDEA Lab Arcavacata Di Rende Italy Univ Paris City Dept Comp Sci Paris France ISIRES Turin Italy

ISBN: (纸本)9783031368042;9783031368059

This paper introduces a Machine Learning methodology for supporting optimal big data processing in advanced smart city environments. In particular, the proposed work focuses the attention on the issue of efficiently charging Electric Vehicles (EVs) in an urban area, given various specific constraints. Our preliminary evaluation and analysis proofs the quality of our heuristics.

关键词： Network Algorithms theory of computing Heuristic Algorithms

来源：评论

学校读者我要写书评

暂无评论

From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms

引用

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

作者： Zheng, Weijie Doerr, Benjamin Harbin Inst Technol Int Res Inst Artificial Intelligence Sch Comp Sci & Technol Shenzhen 518055 Peoples R China Inst Polytech Paris Ecole Polytech Lab Informat LIX CNRS F-91120 Palaiseau France

Estimation-of-distribution algorithms (EDAs) are optimization algorithms that learn a distribution from which good solutions can be sampled easily. A key parameter of most EDAs is the sample size (population size). Too small values lead to the undesired effect of genetic drift, while larger values slow down the process. Building on a quantitative analysis of how the population size leads to genetic drift, we design a smart-restart mechanism for EDAs. By stopping runs when the risk for genetic drift is high, it automatically runs the EDA in good parameter regimes. Via a mathematical runtime analysis, we prove a general performance guarantee for this smart-restart scheme. For many situations where the optimal parameter values are known, this shows that the restart scheme automatically finds these optimal values, leading to the asymptotically optimal performance. We also conduct an extensive experimental analysis. On four classic benchmarks, the smart-restart scheme leads to a performance close to the one obtainable with optimal parameter values. We also conduct experiments with PBIL (cross-entropy algorithm) on the max-cut problem and the bipartition problem. Again, the smart-restart mechanism finds much better values for the population size than those suggested in the literature, leading to a much better performance.

关键词： Estimation-of-distribution algorithms genetic drift restart strategy ran-domized search heuristics theory of computing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：