Abstract
This article describes a set function that maps a set of Pareto optimal points to a scalar. A theorem is presented that shows that the maximization of this scalar value constitutes the necessary and sufficient condition for the function’s arguments to be maximally diverse Pareto optimal solutions of a discrete, multi-objective, optimization problem. This scalar quantity, a hypervolume based on a Lebesgue measure, is therefore the best metric to assess the quality of multiobjective optimization algorithms. Moreover, it can be used as the objective function in simulated annealing (SA) to induce convergence in probability to the Pareto optima. An efficient, polynomial-time algorithm for calculating this scalar and an analysis of its complexity is also presented.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Fleischer, M.A.: The measure of pareto optima: Applications to multiobjective metaheuristics. Technical Report 2002-32, Institute for Systems Research, University of Maryland, College Park, MD. (2002) This is an unabridged version of the instant article.
Zitzler, E., Thiele, L.: Multiobjective optimization using evolutionary algorithms—a comparative case study. In A.E. Eiben, T. Bäck, M.S.H.S., ed.: Proceedings of the Fifth International Conference on Parallel Problem Solving from Nature—PPSN V, Berlin, Germany (1998)
M. Laumanns, G.R., Schwefel, H.: Approximating the pareto set: Diversity issues and performance assessment. (1999)
Zitzler, E.: Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. Ph.d. dissertation, Swiss Federal Institute fo Technology (ETH), Zurich, Switzerland (1999) The relevant part pertaining to our Lebesgue measure is discussed in Ch. 3.
Wu, J., Azarm, S.: Metrics for quality assessment of a multiobjective design optimization solution set. Transactions of the ASME 123 (2001) 18–25
Fonseca, C., Fleming, P.: On the performance assessment and comparison of stochastic multiobjective optimizers. In G. Goos, J.H., van Leeuwen, J., eds.: Proceedings of the Fourth International Conference on Parallel Problem Solving from Nature—PPSN IV, Berlin, Germany (1998) 584–593
Mitra, D., Romeo, F., Sangiovanni-Vincentelli, A.: Convergence and finite-time behavior of simulated annealing. Advances in Applied Probability 18 (1986) 747–771
M. Laumanns, L. Thiele, K.D., Zitzler, E.: Archiving with guaranteed convergence and diversity in multi-objective optimization. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO). (2002) 439–447
Coello, C.: Bibliograph on evolutionary multiobjective optimization. http://www.lania.mx/~coello/EMOO/EMOObib.html (2001)
Veldhuizen, D.V., Lamont, G.B.: Multiobjective evolutionary algorithms: Analyzing the state-of-the-art. Evolutionary Computation 8 (2000) 125–147
Czyzak, P., Jaskiewicz, A.: Pareto simulated annealing—a metaheuristic technique for multiple-objective combinatorial optimization. Journal of Multi-criteria Decision Analysis 7 (1998) 34–47
Reeves, C.: Modern Heuristic Techniques for Combinatorial Problems. John Wiley & Sons, Inc., New York, NY (1993)
Knowles, J.D., Corne, D.W.: Approximating the nondominated front using the pareto archived evolution strategy. Evolutionary Computation 8 (2000) 149–172
Williams, D.: Probability with Martingales. Cambridge University Press, Cambridge, England (1991)
Wu, J.: Quality Assisted Multiobjective and Multi-disciplinary Genetic Algorithms. Department of mechanical engineering, University of Maryland, College Park, College Park, Maryland (2001) S. Azarm, Ph.D. advisor.
Knowles, J.: Local Search and Hybrid Evolutionary Algorithms for Pareto Optimization. PhD thesis, The University of Reading, Reading, UK (2002) Department of Computer Science.
Kapoor, S.: Dynamic maintenance of maxima of 2-d point sets. SIAM Journal on Computing 29 (2000) 1858–1877
Frederickson, G., Rodger, S.: A new approach to the dynamic maintenance of maximal points in a plane. Discrete and Computational Geometry 5 (1990) 365–374
Hildebrand, F.B.: Introduction to Numerical Analysis. 2nd edn. Dover Publications, Inc., Mineola, NY (1987)
Fleischer, M.A.: 28: Generalized Cybernetic Optimization: Solving Continuous Variable Problems. In: Metaheuristics: Advances and Trends in Local Search Paradigms for Optimization. Kluwer Academic Publishers (1999) 403–418
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fleischer, M. (2003). The Measure of Pareto Optima Applications to Multi-objective Metaheuristics. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Thiele, L., Deb, K. (eds) Evolutionary Multi-Criterion Optimization. EMO 2003. Lecture Notes in Computer Science, vol 2632. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36970-8_37
Download citation
DOI: https://doi.org/10.1007/3-540-36970-8_37
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-01869-8
Online ISBN: 978-3-540-36970-7
eBook Packages: Springer Book Archive