2007/11/19 by Marco Laumanns, Laumanns, Marco
Computer Science · Decision Sciences · Mathematics · #Advanced Multi-Objective Optimization Algorithms #FOS: Mathematics #Metaheuristic Optimization Algorithms Research #Optimization and Control (math.OC) #Probabilistic and Robust Engineering Design #math.OC
paper · pdf · doi:10.48550/arxiv.0711.2949
Corrected typo in Definition 4
openalex publication_date 2007/11/19 · arxiv created 2007/11/23 · arxiv updated 2011/11/09 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
This paper presents the first convergence result for random search algorithms to a subset of the Pareto set of given maximum size k with bounds on the approximation quality. The core of the algorithm is a new selection criterion based on a hypothetical multilevel grid on the objective space. It is shown that, when using this criterion for accepting new search points, the sequence of solution archives converges with probability one to a subset of the Pareto set that epsilon-dominates the entire Pareto set. The obtained approximation quality epsilon is equal to the size of the grid cells on the finest level of resolution that allows an approximation with at most k points within the family of grids considered. While the convergence result is of general theoretical interest, the archiving algorithm might be of high practical value for any type iterative multiobjective optimization method, such as evolutionary algorithms or other metaheuristics, which all rely on the usage of a finite on-line memory to store the best solutions found so far as the current approximation of the Pareto set.