Convergence of Hypervolume-Based Archiving Algorithms

Karl Bringmann

doi:10.1109/TEVC.2014.2341711

Return

Convergence of Hypervolume-Based Archiving Algorithms

2014-10-01

PRE

Karl Bringmann *

Tobias Friedrich

DOI：10.1109/TEVC.2014.2341711

Original

Original request for help

Save

Abstract

En 中文

Multiobjective evolutionary algorithms typically maintain a set of solutions. A crucial part of these algorithms is the archiving, which decides what solutions to keep. A (mu + lambda)archiving algorithm defines how to choose in each generation mu children from mu parents and lambda offspring together. We study mathematically the convergence behavior of hypervolume-based archiving algorithms. We distinguish two cases for the offspring generation. A best-case view leads to a study of the effectiveness of archiving algorithms. It was known that all (mu + 1)-archiving algorithms are ineffective, which means that a set with maximum hypervolume is not necessarily reached. We prove that for lambda < mu, all archiving algorithms are ineffective. We also present upper and lower bounds for the achievable hypervolume for different classes of archiving algorithms. On the other hand, a worst-case view on the offspring generation leads to a study of the competitive ratio of archiving algorithms. This measures how much smaller hypervolumes are achieved due to not knowing the future offspring in advance. We present upper and lower bounds on the competitive ratio of different archiving algorithms and present an archiving algorithm, which is the first known computationally efficient archiving algorithm with constant competitive ratio.

Keywords:

Hypervolume indicator

multiobjective optimization

optimization methods

performance measures

selection

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.