Stochastic convergence of random search methods to fixed size Pareto front approximations |
| |
Authors: | Marco Laumanns Rico Zenklusen |
| |
Institution: | a IBM Research-Zurich, Department of Mathematical and Computational Sciences, Saeumerstrasse 4, CH-8803 Rueschlikon, Switzerland b MIT, Department of Mathematics, Cambridge, MA 02139, USA |
| |
Abstract: | In this paper we investigate to what extent random search methods, equipped with an archive of bounded size to store a limited amount of solutions and other data, are able to obtain good Pareto front approximations. We propose and analyze two archiving schemes that allow for maintaining a sequence of solution sets of given cardinality that converge with probability one to an ?-Pareto set of a certain quality, under very mild assumptions on the process used to sample new solutions. The first algorithm uses a hierarchical grid to define a family of approximate dominance relations to compare solutions and solution sets. Acceptance of a new solution is based on a potential function that counts the number of occupied boxes (on various levels) and thus maintains a strictly monotonous progress to a limit set that covers the Pareto front with non-overlapping boxes at finest resolution possible. The second algorithm uses an adaptation scheme to modify the current value of ? based on the information gathered during the run. This way it will be possible to achieve convergence to the best (smallest) ? value, and to a corresponding solution set of k solutions that ?-dominate all other solutions, which is probably the best possible result regarding the limit behavior of random search methods or metaheuristics for obtaining Pareto front approximations. |
| |
Keywords: | Multiple criteria analysis Multiobjective optimization Metaheuristics Search theory |
本文献已被 ScienceDirect 等数据库收录! |
|