Analysis of Evolutionary Algorithms in Dynamic and Stochastic Environments

Abstract

Many real-world optimization problems occur in environments that change dynamically or involve stochastic components. Evolutionary algorithms and other bio-inspired algorithms have been widely applied to dynamic and stochastic problems. This survey gives an overview of major theoretical developments in the area of runtime analysis for these problems. We review recent theoretical studies of evolutionary algorithms and ant colony optimization for problems where the objective functions or the constraints change over time. Furthermore, we consider stochastic problems under various noise models and point out some directions for future research.

arXiv commentThis book chapter is to appear in the book "Theory of Randomized Search Heuristics in Discrete Search Spaces", which is edited by Benjamin Doerr and Frank Neumann and is scheduled to be published by Springer in 2018

References in corpus (2)

• On the Runtime of Randomized Local Search and Simple Evolutionary Algorithms for Dynamic Makespan Scheduling
• Solving Problems with Unknown Solution Length at (Almost) No Extra Cost

Cited by in corpus (7)

• A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete Optimization
• Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise
• First Steps Towards a Runtime Analysis When Starting With a Good Solution
• Runtime Analysis of RLS and the (1+1) EA for the Chance-constrained Knapsack Problem with Correlated Uniform Weights
• On the Impact of Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson Problem
• Fast Re-Optimization of LeadingOnes with Frequent Changes
• Pareto Optimization for Subset Selection with Dynamic Partition Matroid Constraints