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.
Despite the existence of suitable approximation concepts, investigations on the of particular algorithms towards such approximation sets, that is, their ability to obtain a suitable Pareto set approximation in the limit, have remained rare. In @cite_15 @cite_1 the stochastic search procedure proposed by earlier by @cite_7 was analyzed and proved to converge to an @math -Pareto set with @math in case of a finite search space. Obviously, the solution set maintained by this algorithm might in the worst case grow as large as the Pareto set @math itself. Thus, a different version with bounded memory of at most @math elements was proposed and shown to converge to some subset of @math of size at most @math , but no guarantee about the approximation quality could be given. Similar results were obtained by @cite_8 for continuous search spaces.
@cite_15 @cite_1 @cite_7 @cite_8
2168196445 2150881546 70304834 1980272771
The task of finding minimal elements of a partially ordered set is a generalization of the task of finding the global minimum of a real-valued function or of finding Pareto-optimal points of a multicriteria optimization problem. It is shown that evolutionary algorithms are able to converge to the set of minimal elements in finite time with probability one, provided that the search space is finite, the time-invariant variation operator is associated with a positive transition probability function and that the selection operator obeys the so-called ‘elite preservation strategy.’ We present four abstract evolutionary algorithms for multi-objective optimization and theoretical results that characterize their convergence behavior. Thanks to these results it is easy to verify whether or not a particular instantiation of these abstract evolutionary algorithms offers the desired limit behavior. Several examples are given. Abstract We consider the usage of evolutionary algorithms for multiobjective programming (MOP), i.e. for decision problems with alternatives taken from a real-valued vector space and evaluated according to a vector-valued objective function. Selection mechanisms, possibilities of temporary fitness deterioration, and problems of unreachable alternatives for such multiobjective evolutionary algorithms (MOEAs) are studied. Theoretical properties of MOEAs such as stochastic convergence with probability 1 are analyzed.