A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete Optimization

Abstract

The theory of evolutionary computation for discrete search spaces has made significant progress in the last ten years. This survey summarizes some of the most important recent results in this research area. It discusses fine-grained models of runtime analysis of evolutionary algorithms, highlights recent theoretical insights on parameter tuning and parameter control, and summarizes the latest advances for stochastic and dynamic problems. We regard how evolutionary algorithms optimize submodular functions and we give an overview over the large body of recent results on estimation of distribution algorithms. Finally, we present the state of the art of drift analysis, one of the most powerful analysis technique developed in this field.

References in corpus (17)

• Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
• Non-monotone submodular maximization under matroid and knapsack constraints
• A Hybrid Cooperative Co-evolution Algorithm Framework for Optimising Power Take Off and Placements of Wave Energy Converters
• Self-Adjusting Evolutionary Algorithms for Multimodal Optimization
• Sharp Bounds for Genetic Drift in Estimation of Distribution Algorithms
• Does Comma Selection Help To Cope With Local Optima
• A Tight Runtime Analysis for the cGA on Jump Functions---EDAs Can Cross Fitness Valleys at No Extra Cost
• From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm
• Runtime Analysis of the Univariate Marginal Distribution Algorithm under Low Selective Pressure and Prior Noise
• Runtime Analysis of a Heavy-Tailed $(1+(\lambda ,\lambda ))$ Genetic Algorithm on Jump Functions
• An Exponential Lower Bound for the Runtime of the cGA on Jump Functions
• Evolving Boolean Functions with Conjunctions and Disjunctions via Genetic Programming
• Evolutionary Bi-objective Optimization for the Dynamic Chance-Constrained Knapsack Problem Based on Tail Bound Objectives
• Maximizing Submodular or Monotone Functions under Partition Matroid Constraints by Multi-objective Evolutionary Algorithms
• Adaptivity in Adaptive Submodularity
• More Effective Randomized Search Heuristics for Graph Coloring Through Dynamic Optimization
• Advanced Ore Mine Optimisation under Uncertainty Using Evolution