Summary
Dimensionality reduction methods are used routinely in statistics, pattern recognition, data mining, and machine learning to cope with high-dimensional spaces. Also in the case of high-dimensional multiobjective optimization problems, a reduction of the objective space can be beneficial both for search and decision making. New questions arise in this context, e.g., how to select a subset of objectives while preserving most of the problem structure. In this chapter, two different approaches to the task of objective reduction are developed, one based on assessing explicit conflicts, the other based on principal component analysis (PCA). Although both methods use different principles and preserve different properties of the underlying optimization problems, they can be effectively utilized either in an a posteriori scenario or during search. Here, we demonstrate the usability of the conflict-based approach in a decision-making scenario after the search and show how the principal-component-based approach can be integrated into an evolutionary multicriterion optimization (EMO) procedure.
This is a preview of subscription content, log in via an institution to check access.
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
The Journal of Machine Learning Research: Special Issue on Variable and Feature Selection. MIT Press, 2003.
P. J. Agrell. On redundancy in multi criteria decision making. European Journal of Operational Research, 98(3):571–586, 1997.
N. Beume and G. Rudolph. Faster S-Metric Calculation by Considering Dominated Hypervolume as Klee’s Measure Problem. Technical Report CI-216/06, Sonderforschungsbereich 531 Computational Intelligence, Universitát Dortmund, July 2006.
D. Brockhoff and E. Zitzler. Are All Objectives Necessary? On Dimensionality Reduction in Evolutionary Multiobjective Optimization. In Parallel Problem Solving from Nature (PPSN-IX), volume 4193 of LNCS, pages 533–542. Springer, 2006. ISBN 3-540-38990-3.
D. Brockhoff and E. Zitzler. Dimensionality Reduction in Multiobjective Optimization with (Partial) Dominance Structure Preservation: Generalized Minimum Objective Subset Problems. TIK Report 247, Institut für Technische Informatik und Kommunikationsnetze, ETH Zürich, April 2006.
D. Brockhoff and E. Zitzler. Dimensionality Reduction in Multiobjective Optimization: The Minimum Objective Subset Problem. In Proceedings of the Operations Research 2006 conference, 2007. to appear.
D. Brockhoff and E. Zitzler. Offline and Online Objective Reduction in Evolutionary Multiobjective Optimization Based on Objective Conflicts. TIK Report 269, Institut fúr Technische Informatik und Kommunikationsnetze, ETH Zúrich, Apr. 2007.
M. Charikar, V. Guruswami, R. Kumar, S. Rajagopalan, and A. Sahai. Combinatorial feature selection problems. In IEEE Symposium on Foundations of Computer Science, pages 631–640, 2000. URL citeseer.ist.psu.edu/376451.html.
C. Coello Coello and A. Hernández Aguirre. Design of Combinational Logic Circuits through an Evolutionary Multiobjective Optimization Approach. Artificial Intelligence for Engineering, Design, Analysis and Manufacture, 16 (1): 39–53, 2002.
C. A. Coello Coello, D. A. Van Veldhuizen, and G. B. Lamont. Evolutionary Algorithms for Solving Multi-Objective Problems. Kluwer Academic Publishers, New York, 2002.
J. J. Dai, L. Lieu, and D. Rocke. Dimension Reduction for Classification with Gene Expression Microarray Data. Statistical Applications in Genetics and Molecular Biology, 5 (1), 2006.
M. Dash and H. Liu. Feature selection for classification. Intelligent Data Analysis, 1 (3): 131–156, 1997.
K. Deb. Multi-objective optimization using evolutionary algorithms. Wiley, Chichester, UK, 2001.
K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In Parallel Problem Solving from Nature (PPSN-VI), pages 849–858, 2000.
K. Deb and D. Saxena. Searching For Pareto-Optimal Solutions Through Dimensionality Reduction for Certain Large-Dimensional Multi-Objective Optimization Problems. In IEEE Congress on Evolutionary Computation (CEC 2006), pages 3352–3360, 2006.
K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Scalable Test Problems for Evolutionary Multi-Objective Optimization. In A. Abraham, R. Jain, and R. Goldberg, editors, Evolutionary Multiobjective Optimization: Theoretical Advances and Applications, pages 105–145. Springer, 2005. ISBN 1-85233-787-7.
M. Ehrgott and S. Nickel. On the number of criteria needed to decide Pareto-optimality. Mathematical Methods of Operations Research, 55(3): 329–345, 2002.
M. Emmerich, N. Beume, and B. Naujoks. An EMO Algorithm Using the Hypervolume Measure as Selection Criterion. In Evolutionary Multi-Criterion Optimization (EMO 2005), volume 3410 of LNCS, pages 62–76. Springer, 2005.
C. M. Fonseca, L. Paquete, and M. López-Ibáñez. An Improved Dimension-Sweep Algorithm for the Hypervolume Indicator. In IEEE Congress on Evolutionary Computation (CEC 2006), pages 1157–1163, 2006.
T. Gal and T. Hanne. Consequences of dropping nonessential objectives for the application of MCDM methods. European Journal of Operational Research, 119: 373–378, 1999.
T. Gal and H. Leberling. Redundant objective functions in linear vector maximum problems and their determination. European Journal of Operational Research, 1 (3): 176–184, 1977.
T. Goel, R. Vaidyanathan, R. T. Haftka, N. Queipo, W. Shyy, and K. Tucker. Response surface approximation of Pareto-optimal front in multi-objective optimization. Technical report, Department of Mechanical and Aerospace Engineering, University of Florida, USA, 2004.
E. J. Hughes. Radar Waveform Optimization as a Many-Objective Application Benchmark. In Evolutionary Multi-Criterion Optimization (EMO 2007), volume 4403 of LNCS, pages 700–714, 2007.
A. Hyvárinen, J. Karhunen, and E. Oja. Independent Component Analysis. John Wiley & Sons, 2001.
I. T. Jolliffe. Principal component analysis. Springer, 2002. ISBN 0-387-95442-2.
P. Langley. Selection of relevant features in machine learning. In Proceedings of the AAAI Fall Symposium on Relevance, pages 140–144, 1994.
H. Liu and H. Motoda, editors. Feature Extraction, Construction and Selection: A Data Mining Perspective. Kluwer Academic Publishers, Norwell, MA, USA, 1998.
B. Paechter, R. C. Rankin, A. Cumming, and T. C. Fogarty. Timetabling the Classes of an Entire University with an Evolutionary Algorithm. In Parallel Problem Solving From Nature (PPSN-V), pages 865–874. Springer, 1998.
R. C. Purshouse and P. J. Fleming. Conflict, Harmony, and Independence: Relationships in Evolutionary Multi-criterion Optimisation. In Evolutionary Multi-Criterion Optimization (EMO 2003), volume 2632 of LNCS, pages 16–30. Springer, 2003.
D. K. Saxena and K. Deb. Non-linear Dimensionality Reduction Procedures for Certain Large-Dimensional Multi-Objective Optimization Problems: Employing Correntropy and a Novel Maximum Variance Unfolding. In Evolutionary Multi-criterion Optimization (EMO 2007), 2007.
K. C. Tan, E. F. Khor, and T. H. Lee. Multiobjective Evolutionary Algorithms and Applications. Springer, London, UK, 2005.
H. Vafaie and K. De Jong. Robust feature selection algorithms. In Tools with Artificial Intelligence (TAI ’93), pages 356–363, 1993.
T. Wagner, N. Beume, and B. Naujoks. Pareto-, Aggregation-, and Indicator-based Methods in Many-objective Optimization. In Evolutionary Multi-Criterion Optimization (EMO 2007), volume 4403 of LNCS, pages 742–756. Springer, 2007.
L. While. A New Analysis of the LebMeasure Algorithm for Calculating Hypervolume. In Evolutionary Multi-Criterion Optimization (EMO 2005), volume 3410 of LNCS, pages 326–340. Springer, 2005.
L. While, L. Bradstreet, L. Barone, and P. Hingston. Heuristics for Optimising the Calculation of Hypervolume for Multi-objective Optimisation Problems. In IEEE Congress on Evolutionary Computation (CEC 2005), pages 2225–2232, 2005.
E. Zitzler and S. Künzli. Indicator-Based Selection in Multiobjective Search. In Parallel Problem Solving from Nature (PPSN-VIII), September 2004.
E. Zitzler, L. Thiele, M. Laumanns, C. M. Foneseca, and V. Grunert da Fonseca. Performance Assessment of Multiobjective Optimizers: An Analysis and Review. IEEE Transactions on Evolutionary Computation, 7 (2): 117–132, 2003.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Brockhoff, D., Saxena, D.K., Deb, K., Zitzler, E. (2008). On Handling a Large Number of Objectives A Posteriori and During Optimization. In: Knowles, J., Corne, D., Deb, K. (eds) Multiobjective Problem Solving from Nature. Natural Computing Series. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72964-8_18
Download citation
DOI: https://doi.org/10.1007/978-3-540-72964-8_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72963-1
Online ISBN: 978-3-540-72964-8
eBook Packages: Computer ScienceComputer Science (R0)