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.
As relative deviation is essentially equivalent to absolute deviation on a logarithmically scaled objective space, this choice should not affect the convergence results obtained but rather depend on the actual application problem at hand. The nice property of relative deviation is that it allows to prove that, under very mild assumptions, there is always an @math -Pareto set whose size is polynomial in the input length @cite_5 @cite_11 . Further approximation results for particular combinatorial multiobjective optimization problems are given in @cite_10 , where the question was how well a single solution can approximate the whole Pareto set, which is a special case of our question restricted to @math and with focus on deterministic algorithms.
@cite_5 @cite_10 @cite_11
1963770385 2060645964
Abstract The computational complexity of combinatorial multiple objective programming problems is investigated. NP -completeness and #P-completeness results are presented. Using two definitions of approximability, general results are presented, which outline limits for approximation algorithms. The performance of the well-known tree and Christofides’ heuristics for the traveling salesman problem is investigated in the multicriteria case with respect to the two definitions of approximability. For multiobjective optimization problems, it is meaningful to compute a set of solutions covering all possible trade-offs between the different objectives. The multiobjective knapsack problem is a generalization of the classical knapsack problem in which each item has several profit values. For this problem, efficient algorithms for computing a provably good approximation to the set of all nondominated feasible solutions, the Pareto frontier, are studied.For the multiobjective one-dimensional knapsack problem, a practical fully polynomial-time approximation scheme (FPTAS) is derived. It is based on a new approach to the single-objective knapsack problem using a partition of the profit space into intervals of exponentially increasing length. For the multiobjectivem-dimensional knapsack problem, the first known polynomial-time approximation scheme (PTAS), based on linear programming, is presented.