Abstract
In this work we investigate the convergence of stochastic search algorithms toward the Pareto set of continuous multi-objective optimization problems. The focus is on obtaining a finite approximation that should capture the entire solution set in a suitable sense, which will be defined using the concept of ε-dominance. Under mild assumptions about the process to generate new candidate solutions, the limit approximation set will be determined entirely by the archiving strategy. We propose and analyse two different archiving strategies which lead to a different limit behavior of the algorithms, yielding bounds on the obtained approximation quality as well as on the cardinality of the resulting Pareto set approximation.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Evtushenko Y.G. and Potapov M.A. (1987). Methods of numerical solution of multicriterion problem. Soviet Math. doklady 34: 420–423
Gomes da Silva, C., Climaco, J., Figueira, J.: Geometrical configuration of the Pareto frontier of bi-criteria {0,1}-knapsack problems. Research Report 16, INESC-COIMBRA (2004)
Hanne T. (1999). On the convergence of multiobjective evolutionary algorithms. Euro. J. Operat. Res. 117(3): 553–564
Helbig S. and Pateva D. (1994). On several concepts for ε-efficiency. OR Spektrum 16(3): 179–186
Knowles, J.D.: Local-search and hybrid evolutionary algorithms for Pareto optimization. PhD thesis, The University of Reading, Department of Computer Science, Reading, UK (2002)
Knowles J.D. and Corne D. (2003). Properties of an adaptive archiving algorithm for storing nondominated vectors. IEEE Trans. Evol. Comput. 7(2): 100–116
Knowles J.D. and Corne D.W. (2000). Approximating the non-dominated front using the Pareto Archived Evolution Strategy. Evol. Comput. 8(2): 149–172
Laumanns M., Thiele L., Deb K. and Zitzler E. (2002). Combining convergence and diversity in evolutionary multiobjective optimization. Evol. Comput. 10(3): 263–282
Pottharst, A., Baptist, K., Schütze, O., Böcker, J., Fröhlecke, N., Dellnitz, M.: Operating point assignment of a linear motor driven vehicle using multiobjective optimization methods. In: Proceedings of the 11th International Conference EPE-PEMC 2004, Riga, Latvia (2004)
Reuter H. (1990). An approximation method for the efficiency set of multiobjective programming problems. Optimization 21: 905–911
Rudolph G. (1998). Finite Markov chain results in evolutionary computation: A tour d’horizon. Fundamenta Informaticae 35: 67–89
Rudolph G., Agapie A.: On a multi-objective evolutionary algorithm and its convergence to the Pareto set. In: Congress on Evolutionary Computation (CEC2000), pp. 1010–1016 (2000)
Ruhe G. and Fruhwirt B. (1990). ε-optimality for bicriteria programs and its application to minimum cost flows. Computing 44: 21–34
Schütze, O.: Set oriented methods for global optimization. PhD thesis, University of Paderborn (2004). < http://ubdata.uni-paderborn.de/ediss/17/2004/schuetze/ >
Schütze, O., Laumanns, M., Tantar, E., Coello Coello, C.A., Talbi, E.-G.: Convergence of stochastic search algorithms to gap-free Pareto front approximations. In: GECCO ’07: Proceedings of the 9th annual Conference on Genetic and Evolutionary Computation, pp. 892–901. ACM Press, New York, NY, USA (2007)
Zitzler E., Thiele L., Laumanns M., Fonseca C. and Fonseca V. (2003). Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evol. Comput. 7(2): 117–132
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Schütze, O., Laumanns, M., Coello Coello, C.A. et al. Convergence of stochastic search algorithms to finite size pareto set approximations. J Glob Optim 41, 559–577 (2008). https://doi.org/10.1007/s10898-007-9265-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-007-9265-7