Techniques for highly multiobjective optimisation: some nondominated points are better than others
Inhaltsverzeichnis
Reference
Corne, D., Knowles, J.: Techniques for highly multiobjective optimisation: some nondominated points are better than others. In: Proceedings of GECCO 2007, pp. 773–780. ACM Press (2007)
DOI
http://dx.doi.org/10.1145/1276958.1277115
Abstract
The research area of evolutionary multiobjective optimization (EMO) is reaching better understandings of the properties and capabilities of EMO algorithms, and accumulating much evidence of their worth in practical scenarios. An urgent emerging issue is that the favoured EMO algorithms scale poorly when problems have "many" (e.g. five or more) objectives. One of the chief reasons for this is believed to be that, in many-objective EMO search, populations are likely to be largely composed of nondominated solutions. In turn, this means that the commonly-used algorithms cannot distinguish between these for selective purposes. However, there are methods that can be used validly to rank points in a nondominated set, and may therefore usefully underpin selection in EMO search. Here we discuss and compare several such methods. Our main finding is that simple variants of the often-overlooked "Average Ranking" strategy usually outperform other methods tested, covering problems with 5-20 objectives and differing amounts of inter-objective correlation.
Extended Abstract
Bibtex
@inproceedings{Corne:2007:THM:1276958.1277115,
author = {Corne, David W. and Knowles, Joshua D.},
title = {Techniques for Highly Multiobjective Optimisation: Some Nondominated Points Are Better Than Others},
booktitle = {Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation},
series = {GECCO '07},
year = {2007},
isbn = {978-1-59593-697-4},
location = {London, England},
pages = {773--780},
numpages = {8},
url = {http://doi.acm.org/10.1145/1276958.1277115, http://de.evo-art.org/index.php?title=Techniques_for_highly_multiobjective_optimisation:_some_nondominated_points_are_better_than_others },
doi = {10.1145/1276958.1277115},
acmid = {1277115},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {multiobjective optimization, ranking, selection},
}
Used References
1 Zhi-Dong Bai , Luc Devroye , Hsien-Kuei Hwang , Tsung-Hsi Tsai, Maxima in hypercubes, Random Structures & Algorithms, v.27 n.3, p.290-309, October 2005 http://dl.acm.org/citation.cfm?id=1145860&CFID=558819604&CFTOKEN=68186175 http://dx.doi.org/10.1002/rsa.20053
2 J. L. Bentley , H. T. Kung , M. Schkolnick , C. D. Thompson, On the Average Number of Maxima in a Set of Vectors and Applications, Journal of the ACM (JACM), v.25 n.4, p.536-543, Oct. 1978 http://dl.acm.org/citation.cfm?id=322095&CFID=558819604&CFTOKEN=68186175 http://dx.doi.org/10.1145/322092.322095
3 Bentley, P.J. and Wakefield, J.P. Finding acceptable solutions in the Pareto-optimal range using multiobjective genetic algorithms. In (Chawdry et al, eds.) Soft Computing in Eng'g Design and Manufacturing, Springer Verlag, 1997.
4 Bonferroni, C.E. Il calcolo della assicurazioni su gruppi di teste. In Studi in onore del Professore Salvatore Ortu Carbone. Rome, Italy, pp. 13--60, 1935.
5 Dimo Brockhoff , Eckart Zitzler, Are all objectives necessary? on dimensionality reduction in evolutionary multiobjective optimization, Proceedings of the 9th international conference on Parallel Problem Solving from Nature, September 09-13, 2006, Reykjavik, Iceland http://dl.acm.org/citation.cfm?id=2079789&CFID=558819604&CFTOKEN=68186175 http://dx.doi.org/10.1007/11844297_54
6 Coello, C.A.C. Handling preferences in evolutionary multiobjective optimization: a survey. In Proc. of the 2000 Congress on Evo. Computation, vol 1, pp. 30--37, 2000.
7 Corne, D.W., Knowles, J.D. and Oates, M.J. The Pareto-Envelope based selection algorithm for multiobjective optimization, in (Schoenauer et al, eds) PPSN VI, Springer LNCS pp. 869--878, 2000.
8 D. Cvetkovic , I. C. Parmee, Preferences and their application in evolutionary multiobjective optimization, IEEE Transactions on Evolutionary Computation, v.6 n.1, p.42-57, February 2002 http://dl.acm.org/citation.cfm?id=2221573&CFID=558819604&CFTOKEN=68186175 http://dx.doi.org/10.1109/4235.985691
9 Deb, K. and Saxena, D.K. On finding Pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems. KanGAL Report No. 2005011, IIT, Kanpur, 2005.
10 di Pierro, F. Many-objective evolutionary algorithms and applications to water resources engineering. PhD thesis, University of Exeter, UK, August 2006.
11 di Pierro, F., Djordjevic, S., Khu, S.-T, Savic, D. and Walters, G.A. Automatic calibration of urban drainage model using a novel multi-objective GA. In Krebs & Fuchs (eds.) Urban Drainage Modelling'04, pp. 41--52, 2004.
12 Drechsler, D., Drechsler, R., Becker, B. Multi-objective optimisation based on relation favour. In Proc. 1st EMO, pp. 154--166, Springer Verlag, 2001.
13 Farina, M. and Amato, P. A fuzzy definition of "optimality" for many-criteria optimization problems, IEEE Trans SMC Part A, 34(3):315--326.
14 Carlos M. Fonseca , Peter J. Fleming, Genetic Algorithms for Multiobjective Optimization: FormulationDiscussion and Generalization, Proceedings of the 5th International Conference on Genetic Algorithms, p.416-423, June 01, 1993 http://dl.acm.org/citation.cfm?id=657757&CFID=558819604&CFTOKEN=68186175
15 C. M. Fonseca , P. J. Fleming, Multiobjective optimization and multiple constraint handling with evolutionary algorithms. I. A unified formulation, IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, v.28 n.1, p.26-37, January 1998 http://dl.acm.org/citation.cfm?id=2229446&CFID=558819604&CFTOKEN=68186175 http://dx.doi.org/10.1109/3468.650319
16 David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989 http://dl.acm.org/citation.cfm?id=534133&CFID=558819604&CFTOKEN=68186175
17 Hanne, T. On the convergence of multiobjective evolutionary algorithms, EJOR 117(3): 553--564, 1999.
18 Hwang, C.L. and Yoon, K. Multiple Attribute Decision Making: Methods and Applications, A State-of-the-Art Survey. Springer, (1981)
19 Joshua D. Knowles , David W. Corne, Approximating the Nondominated Front Using the Pareto Archived Evolution Strategy, Evolutionary Computation, v.8 n.2, p.149-172, June 2000 http://dl.acm.org/citation.cfm?id=1108875&CFID=558819604&CFTOKEN=68186175 http://dx.doi.org/10.1162/106365600568167
20 Knowles, J.D. and Corne, D.W. On metrics for comparing non-dominated sets. In Proceedings of the 2002 Congress on Evolutionary Computation, pp. 711--716, 2002.
21 Kuntinee Maneeratana , Kittipong Boonlong , Nachol Chaiyaratana, Compressed-objective genetic algorithm, Proceedings of the 9th international conference on Parallel Problem Solving from Nature, September 09-13, 2006, Reykjavik, Iceland http://dl.acm.org/citation.cfm?id=2079783&CFID=558819604&CFTOKEN=68186175 http://dx.doi.org/10.1007/11844297_48
22 Robin C. Purshouse , Peter J. Fleming, An adaptive divide-and-conquer methodology for evolutionary multi-criterion optimisation, Proceedings of the 2nd international conference on Evolutionary multi-criterion optimization, April 08-11, 2003, Faro, Portugal http://dl.acm.org/citation.cfm?id=1760113&CFID=558819604&CFTOKEN=68186175
23 J. David Schaffer, Multiple Objective Optimization with Vector Evaluated Genetic Algorithms, Proceedings of the 1st International Conference on Genetic Algorithms, p.93-100, July 01, 1985 http://dl.acm.org/citation.cfm?id=657079&CFID=558819604&CFTOKEN=68186175
24 Srinivas, N. and Deb, K. Multiobjective optimization using nondominated sorting genetic algorithm. Evolutionary Computation, 2(3):221--248, 1994.
25 Teytaud, O. How entropy theorems can show that offline approximating high--dim Pareto fronts is too hard. Presented at PPSN BTP Workshop, PPSN 2006, http://www.lri.fr/~teytaud/pareto2.pdf
26 Van Veldhuizen, D.V. and Lamont, G.B. On measuring multiobjective evolutionary algorithm performance. In Proc. CEC 2000, vol 1, pp. 204--211, 2000.
27 E. Zitzler , L. Thiele, Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach, IEEE Transactions on Evolutionary Computation, v.3 n.4, p.257-271, November 1999 http://dl.acm.org/citation.cfm?id=2221470&CFID=558819604&CFTOKEN=68186175 http://dx.doi.org/10.1109/4235.797969
28 E. Zitzler , L. Thiele , M. Laumanns , C. M. Fonseca , V. G. da Fonseca, Performance assessment of multiobjective optimizers: an analysis and review, IEEE Transactions on Evolutionary Computation, v.7 n.2, p.117-132, April 2003 http://dl.acm.org/citation.cfm?id=2221632&CFID=558819604&CFTOKEN=68186175 http://dx.doi.org/10.1109/TEVC.2003.810758
Links
Full Text
http://arxiv.org/ftp/arxiv/papers/0908/0908.3025.pdf
