4.3 Article

More Precise Runtime Analyses of Non-elitist Evolutionary Algorithms in Uncertain Environments

相关参考文献

注意:仅列出部分参考文献,下载原文获取全部文献信息。
Proceedings Paper Computer Science, Cybernetics

Self-adaptation via Multi-objectivisation: A Theoretical Study

Per Kristian Lehre et al.

Summary: The exploration vs exploitation dilemma is about balancing the exploration of new but potentially less fit regions with the focus on regions near the fittest individuals. We propose a self-adaptive evolutionary algorithm that maximizes fitness and mutation rates to efficiently escape local optima.

PROCEEDINGS OF THE 2022 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'22) (2022)

Article Computer Science, Software Engineering

Analysing the Robustness of Evolutionary Algorithms to Noise: Refined Runtime Bounds and an Example Where Noise is Beneficial

Dirk Sudholt

Summary: In this study, we analysed the performance of well-known evolutionary algorithms, the (1 + 1) EA and the (1 + similar to) EA, in the prior noise model. We discovered that the (1 + 1) EA on LeadingOnes is surprisingly sensitive to noise and showed that offspring populations of size similar to = 3.42 log n can effectively deal with much higher noise than previously known.

ALGORITHMICA (2021)

Article Computer Science, Software Engineering

Analysis of Noisy Evolutionary Optimization When Sampling Fails

Chao Qian et al.

Summary: In noisy evolutionary optimization, sampling is a common strategy but may fail with fixed sample sizes. Using parent or offspring populations may be helpful in some cases, while a tailored adaptive sampling strategy can work when neither sampling nor populations are effective.

ALGORITHMICA (2021)

Article Computer Science, Artificial Intelligence

AutoML: A survey of the state-of-the-art

Xin He et al.

Summary: Deep learning techniques have achieved remarkable results in various tasks, but building a high-quality DL system requires human expertise. Automated machine learning is a promising solution that is currently being extensively researched.

KNOWLEDGE-BASED SYSTEMS (2021)

Article Computer Science, Software Engineering

Runtime Analyses of the Population-Based Univariate Estimation of Distribution Algorithms on LeadingOnes

Per Kristian Lehre et al.

Summary: Rigorous runtime analyses were conducted for the UMDA and PBIL algorithms on the LeadingOnes function, with the UMDA algorithm showing an expected runtime of O(n lambda log lambda + n(2) and the PBIL algorithm showing an expected runtime of O(n(2+c)). Despite the independence assumption in probabilistic models, both algorithms demonstrate the ability to effectively handle variable interactions.

ALGORITHMICA (2021)

Proceedings Paper Computer Science, Artificial Intelligence

When Non-Elitism Meets Time-Linkage Problems

Weijie Zheng et al.

Summary: This work analyzes the impact of non-elitism in evolutionary algorithms by comparing the performance of elitist and non-elitist algorithms, finding that the non-elitist (1, lambda) EA is more effective in avoiding local optima and reaching the global optimum, with an expected runtime of O(n(3+c) log n).

PROCEEDINGS OF THE 2021 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'21) (2021)

Proceedings Paper Computer Science, Artificial Intelligence

More Precise Runtime Analyses of Non-elitist EAs in Uncertain Environments

Per Kristian Lehre et al.

Summary: Evolutionary algorithms have shown effectiveness in dealing with uncertainties, particularly at low levels. Non-elitist evolutionary algorithms with large population sizes can better handle higher levels of uncertainties, but may still face challenges in certain fitness uncertainty scenarios.

PROCEEDINGS OF THE 2021 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'21) (2021)

Proceedings Paper Computer Science, Artificial Intelligence

Non-elitist Evolutionary Algorithms Excel in Fitness Landscapes with Sparse Deceptive Regions and Dense Valleys

Duc-Cuong Dang et al.

Summary: This study examines the runtime dependence of evolutionary algorithms on fitness landscape parameters, finding that for specific density and sparsity alpha, there is exponential elitist complexity, but non-elitist algorithms can optimize the problem with a set of sufficient conditions in polynomial time.

PROCEEDINGS OF THE 2021 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'21) (2021)

Proceedings Paper Computer Science, Artificial Intelligence

Self-Adjusting Population Sizes for Non-Elitist Evolutionary Algorithms: Why Success Rates Matter

Mario Alejandro Hevia Fajardo et al.

Summary: Research shows that the ability of parameter control mechanisms in evolutionary algorithms to find and maintain suitable values in non-elitist algorithms depends heavily on the success rate. If the success rate is sufficiently small, the self-adjusting (1, lambda) EA can optimize ONEMAX in O(n) expected generations and O(n log n) expected evaluations; however, if the success rate is too large, the algorithm will have an exponential runtime on ONEMAX.

PROCEEDINGS OF THE 2021 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'21) (2021)

Proceedings Paper Computer Science, Artificial Intelligence

Self-Adjusting Offspring Population Sizes Outperform Fixed Parameters on the Cliff Function

Mario Alejandro Hevia Fajardo et al.

Summary: Research on self-adjusting parameters in evolutionary algorithms has shown that they can outperform fixed parameters. This study focuses on the optimization performance of a self-adjusting (1, lambda) EA on the Cliff function, demonstrating significant improvements over fixed parameters.

PROCEEDINGS OF THE 16TH ACM/SIGEVO CONFERENCE ON FOUNDATIONS OF GENETIC ALGORITHMS (FOGA'21) (2021)

Article Computer Science, Software Engineering

Multiplicative Up-Drift

Benjamin Doerr et al.

Summary: Drift analysis translates the expected progress of evolutionary algorithms into probabilistic guarantees on run time. Research shows that random processes exhibiting (1+delta) multiplicative growth lead to stronger run time guarantees.

ALGORITHMICA (2021)

Review Computer Science, Artificial Intelligence

Evolutionary algorithms and their applications to engineering problems

Adam Slowik et al.

NEURAL COMPUTING & APPLICATIONS (2020)

Article Computer Science, Artificial Intelligence

Self-Adaptation in Nonelitist Evolutionary Algorithms on Discrete Problems With Unknown Structure

Brendan Case et al.

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION (2020)

Proceedings Paper Computer Science, Artificial Intelligence

Does Comma Selection Help To Cope With Local Optima?

Benjamin Doerr

GECCO'20: PROCEEDINGS OF THE 2020 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (2020)

Article Computer Science, Software Engineering

Running Time Analysis of the (1+1)-EA for OneMax and LeadingOnes Under Bit-Wise Noise

Chao Qian et al.

ALGORITHMICA (2019)

Article Computer Science, Software Engineering

Level-Based Analysis of the Univariate Marginal Distribution Algorithm

Duc-Cuong Dang et al.

ALGORITHMICA (2019)

Proceedings Paper Computer Science, Artificial Intelligence

Self-Adjusting Mutation Rates with Provably Optimal Success Rules

Benjamin Doerr et al.

PROCEEDINGS OF THE 2019 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'19) (2019)

Proceedings Paper Computer Science, Artificial Intelligence

Runtime Analysis of the Univariate Marginal Distribution Algorithm under Low Selective Pressure and Prior Noise

Per Kristian Lehre et al.

PROCEEDINGS OF THE 2019 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'19) (2019)

Proceedings Paper Computer Science, Theory & Methods

The Benefits and Limitations of Voting Mechanisms in Evolutionary Optimisation

Jonathan E. Rowe et al.

FOGA'19: PROCEEDINGS OF THE 15TH ACM/SIGEVO CONFERENCE ON FOUNDATIONS OF GENETIC ALGORITHMS (2019)

Article Computer Science, Artificial Intelligence

Level-Based Analysis of Genetic Algorithms and Other Search Processes

Dogan Corus et al.

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION (2018)

Article Computer Science, Artificial Intelligence

On the Effectiveness of Sampling for Evolutionary Optimization in Noisy Environments

Chao Qian et al.

EVOLUTIONARY COMPUTATION (2018)

Article Computer Science, Artificial Intelligence

The Compact Genetic Algorithm is Efficient Under Extreme Gaussian Noise

Tobias Friedrich et al.

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION (2017)

Proceedings Paper Computer Science, Artificial Intelligence

Google Vizier: A Service for Black-Box Optimization

Daniel Golovin et al.

KDD'17: PROCEEDINGS OF THE 23RD ACM SIGKDD INTERNATIONAL CONFERENCE ON KNOWLEDGE DISCOVERY AND DATA MINING (2017)

Article Computer Science, Software Engineering

Robustness of Populations in Stochastic Environments

Christian Giessen et al.

ALGORITHMICA (2016)

Article Computer Science, Software Engineering

Runtime Analysis of Non-elitist Populations: From Classical Optimisation to Partial Information

Duc-Cuong Dang et al.

ALGORITHMICA (2016)

Article Computer Science, Artificial Intelligence

Robustness of Ant Colony Optimization to Noise

Tobias Friedrich et al.

EVOLUTIONARY COMPUTATION (2016)

Proceedings Paper Computer Science, Theory & Methods

When Non-Elitism Outperforms Elitism for Crossing Fitness Valleys

Pietro S. Oliveto et al.

GECCO'16: PROCEEDINGS OF THE 2016 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (2016)

Proceedings Paper Computer Science, Artificial Intelligence

Self-adaptation of Mutation Rates in Non-elitist Populations

Duc-Cuong Dang et al.

PARALLEL PROBLEM SOLVING FROM NATURE - PPSN XIV (2016)

Article Computer Science, Theory & Methods

Runtime analysis of ant colony optimization on dynamic shortest path problems

Andrei Lissovoi et al.

THEORETICAL COMPUTER SCIENCE (2015)

Proceedings Paper Computer Science, Theory & Methods

The Benefit of Recombination in Noisy Evolutionary Search

Tobias Friedrich et al.

ALGORITHMS AND COMPUTATION, ISAAC 2015 (2015)

Article Computer Science, Software Engineering

Multiplicative Drift Analysis

Benjamin Doerr et al.

ALGORITHMICA (2012)

Article Computer Science, Artificial Intelligence

On the Impact of Mutation-Selection Balance on the Runtime of Evolutionary Algorithms

Per Kristian Lehre et al.

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION (2012)

Article Computer Science, Artificial Intelligence

A Survey of Evolutionary Algorithms for Decision-Tree Induction

Rodrigo Coelho Barros et al.

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART C-APPLICATIONS AND REVIEWS (2012)

Review Computer Science, Artificial Intelligence

A Survey of Evolutionary Algorithms for Clustering

Eduardo Raul Hruschka et al.

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART C-APPLICATIONS AND REVIEWS (2009)

Article Computer Science, Theory & Methods

Upper and lower bounds for randomized search heuristics in black-box optimization

Stefan Droste et al.

THEORY OF COMPUTING SYSTEMS (2006)

Review Computer Science, Artificial Intelligence

Evolutionary optimization in uncertain environments - A survey

Y Jin et al.

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION (2005)

Article Automation & Control Systems

Evolutionary algorithms in control systems engineering: a survey

PJ Fleming et al.

CONTROL ENGINEERING PRACTICE (2002)