Population size matters: rigorous runtime results for maximizing the hypervolume indicator

DOI10.1016/J.TCS.2014.06.023MaRDI QIDQ477080zbMATH OpenOpenAlexFDO

Authors Anh Quang Nguyen, Andrew M. Sutton, F. Neumann

Publication date 2 December 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.06.023

zbMATH Keywords

theoryevolutionary multi-objective optimizationgenetic programminghypervolume indicatorruntime time analysis

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Population size versus runtime of a simple evolutionary algorithm
• The Sample Complexity of Search Over Multiple Populations
• Estimation of the population size in the classical occupancy problem
• Estimating population size of heterogeneous populations with large data sets and a large number of parameters
• Population size modeling for GA in time-critical task scheduling
• A survey of size counting in population protocols
• A population-based fast algorithm for a billion-dimensional resource allocation problem with integer variables

Cites work

• scientific article; zbMATH DE number 2046100 (Why is no real title available?)
• scientific article; zbMATH DE number 795587 (Why is no real title available?)
• Approximating the volume of unions and intersections of high-dimensional geometric objects
• Approximation quality of the hypervolume indicator
• Computational complexity analysis of simple genetic programming on two problems modeling isolated program semantics
• Convergence of set-based multi-objective optimization, indicators and deteriorative cycles
• Evolutionary Multi-Criterion Optimization
• Hypervolume-based multiobjective optimization: theoretical foundations and practical implications
• Multi-objective optimization using evolutionary algorithms
• Probability with Martingales
• Running time analysis of evolutionary algorithms on a simplified multiobjective knapsack problem
• SMS-EMOA: multiobjective selection based on dominated hypervolume
• Theory of the hypervolume indicator: optimal \(\mu\)-distributions and the choice of the reference point

Cited in

(6)

• Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial
• Plateaus can be harder in multi-objective optimization
• Mathematical runtime analysis for the non-dominated sorting genetic algorithm II (NSGA-II)
• Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMax
• Tight bounds for the approximation ratio of the hypervolume indicator
• Design and analysis of diversity-based parent selection schemes for speeding up evolutionary multi-objective optimisation

Describes a project that uses

Uses Software

• DataModeler
• SMS-EMOA

This page was built for publication: Population size matters: rigorous runtime results for maximizing the hypervolume indicator

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477080)