article

Objective reduction for many-objective optimization problems using objective subspace extraction

Authors:

Qiuzhen LinAuthors Info & Claims

Soft Computing - A Fusion of Foundations, Methodologies and Applications, Volume 22, Issue 4

Pages 1159 - 1173

https://doi.org/10.1007/s00500-017-2498-6

Published: 01 February 2018 Publication History

Abstract

Multi-objective evolutionary algorithms (MOEAs) have shown their effectiveness in exploring a well converged and diversified approximation set for multi-objective optimization problems (MOPs) with 2 and 3 objectives. However, most of them perform poorly when tackling MOPs with more than 3 objectives [often called many-objective optimization problems (MaOPs)]. This is mainly due to the fact that the number of non-dominated individuals increases rapidly in MaOPs, leading to the loss of selection pressure in population update. Objective reduction can be used to lower the difficulties of some MaOPs, which helps to alleviate the above problem. This paper proposes a novel objective reduction framework for MaOPs using objective subspace extraction, named OSEOR. A new conflict information measurement among different objectives is defined to sort the relative importance of each objective, and then an effective approach is designed to extract several overlapped subspaces with reduced dimensionality during the execution of MOEAs. To validate the effectiveness of the proposed approach, it is embedded into a well-known and frequently used MOEA (NSGA-II). Several test MaOPs, including four irreducible problems (i.e. DTLZ1---DTLZ4) and a reducible problem (i.e. DTLZ5), are used to assess the optimization performance. The experimental results indicate that the performance of NSGA-II can be significantly enhanced using OSEOR on both irreducible and reducible MaOPs.

References

[1]

Aguirre H and Tanaka K (2009) Adaptive e-ranking on MNKlandscapes. In: Computational intelligence in miulti-criteria decision-making, pp 104-111.

[2]

Al MN, Petrovski A et al (2013) D2MOPSO: MOPSO based on decomposition and dominance with archiving using crowding distance in objective and solution spaces. Evol Comput 22(1):47-77.

[3]

Auger A and Bader J, et al (2009) Theory of the hypervolume indicator: optimal µ-distributions and the choice of the reference point. In: Tenth ACM Sigevo workshop on foundations of genetic algorithms, pp 87-102.

[4]

Bader J, Zitzler E (2011) HypE: an algorithm for fast hypervolume-based many-objective optimization. Evol Comput 19(1):45-76.

[5]

Brockhoff D, Zitzler E (2006) Are all objectives necessary? On dimensionality reduction in evolutionary multiobjective optimization. Lect Notes Comput Sci 4193(1):533-542.

Digital Library

[6]

Brockhoff D, Zitzler E (2009) Objective reduction in evolutionary multiobjective optimization: theory and applications. Evol Comput 17(2):135-166.

Digital Library

[7]

Chen J, Lin Q et al (2011) Chaos-based multi-objective immune algorithm with a fine-grained selection mechanism. Soft Comput 15(7):1273-1288.

Digital Library

[8]

Chen XH, Li X et al (2014) Improved population partitioning method in multi-objective shuffled frog leaping algorithm. J Signal Process 30(10):1134-1142.

[9]

Coello CAC, Lechuga MS (2002) MOPSO: a proposal for multiple objective particle swarm optimization. In: Proceedings of the 2002 congress on evolutionary computation. CEC'02, pp 1051-1056.

[10]

Coello CAC (2005) Recent trends in evolutionary multiobjective optimization. Evolutionary multiobjective optimization. Springer, London.

[11]

Coello CAC, Van Veldhuizen DA et al (2006) Evolutionary algorithms for solving multi-objective problems (Genetic and Evolutionary Computation). Springer, New York.

[12]

Corne DW, Knowles JD (2009) Techniques for highly multiobjective optimisation: some nondominated points are better than others. In: Proceedings Gecco ACM, pp 773-780.

[13]

Czyzzak P, Jaszkiewicz A (1998) Pareto simulated annealing: a metaheuristic technique formultiple-objective combinatorial optimization. J Multi Criteria Decis Anal 7(7):34-47.

[14]

Deb K, Pratap A et al (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182-197.

Digital Library

[15]

Deb K, Saxena DK (2005) On finding pareto-optimal solutions through dimensionality. Reduction for certain large-dimensional multiobjective optimization problems, KanGAL Report.

[16]

Deb K, Thiele L et al (2006) Scalable test problems for evolutionary multiobjective optimization. Evolutionary Multiobjective Optimization, Springer, London, pp 105-145.

[17]

Fonseca CM, Fleming PJ (1995) An overview of evolutionary algorithms in multiobjective optimization. Evol Comput 3(1):1-16.

Digital Library

[18]

Gal T, Hanne T (1999) Consequences of dropping nonessential objectives for the application of MCDM methods. Eur J Oper Res 119(2):373-378.

[19]

Giagkiozis I, Fleming PJ (2014) Pareto front estimation for decision making. Evol Comput 22(4):651-678.

Digital Library

[20]

Hadka D, Reed PM et al (2012) Diagnostic assessment of the borg MOEA for many-objective product family design problems. Evolutionary computation, pp 1-10.

[21]

Hadka D, Reed P (2011) Diagnostic assessment of search controls and failure modes in many-objective evolutionary optimization. Evol Comput 20(3):423-452.

Digital Library

[22]

Huaping Y, Yao W (2013) A new multi-objective particle swarm optimization algorithm based on decomposition. J Syst Eng Electron 325(2):541-557.

[23]

Ishibuchi H, Akedo N et al (2011) Behavior of EMO algorithms on many-objective optimization problems with correlated objectives. In: IEEE congress on evolutionary computation, Cec 2011, New Orleans, LA, USA, 5-8 June, pp 1465-1472.

[24]

Ishibuchi H, Tsukamoto N et al (2008) Evolutionary many-objective optimization: a short review. In: Proc. of 2008 IEEE Congress on Evolutionary Computation, Hong Kong, pp 2424-2431.

[25]

Ishibuchi H, Sakane Y et al (2009) Evolutionary many-objective optimization by NSGA-II and MOEA/D with large populations. In: IEEE international conference on systems, man and cybernetics, pp 1758-1763.

[26]

Jaimes AL, Coello CAC et al (2008) Objective reduction using a feature selection technique. In: Genetic and evolutionary computation conference, GECCO 2008, Proceedings, Atlanta, GA, USA, pp 673-680.

[27]

Jaimes AL, Coello CAC et al (2014) Objective space partitioning using conflict information for solving many-objective problems. Inf Sci 268(2):305-327.

[28]

Jaimes AL, Coello CAC (2015) Many-objective problems: challenges and methods. Springer handbook of computational intelligence. Springer Berlin, Heidelberg, pp 1033-1046.

[29]

Joshi R, Deshpande B (2014) Empirical and analytical study of many-objective optimization problems: analysing distribution of nondominated solutions and population size for scalability of randomized heuristics. Memet Comput 6(2):133-145.

[30]

Li H, Landasilva D (2011) An adaptive evolutionary multi-objective approach based on simulated annealing. Evol Comput 19(4):561- 595.

Digital Library

[31]

Li H, Zhang Q (2009) Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II. IEEE Trans Evol Comput 13(2):284-302.

Digital Library

[32]

Li X, Luo J et al (2012) An improved shuffled frog-leaping algorithm with extremal optimisation for continuous optimisation. Inf Sci 192(6):143-151.

Digital Library

[33]

Lin Q, Chen J (2013) A novelmicro-population immune multiobjective optimization algorithm. Comput Oper Res 40(6):1590-1601.

Digital Library

[34]

Lin Q, Zhu Q et al (2015) A novel hybrid multi-objective immune algorithm with adaptive differential evolution. Comput Oper Res 62:95-111.

Digital Library

[35]

Lin Q, Chen J et al (2016) A hybrid evolutionary immune algorithm for multiobjective optimization problems. IEEE Trans Evol Comput 20(5):711-729.

[36]

Lotov AV, Bushenkov VA et al (2004) Introduction to interactive decision maps. Interactive decision maps. Springer, New York.

[37]

Mashwani WK, Salhi A (2014) Multi objective memetic algorithm based on decomposition. Appl Soft Comput 21(8):221-243.

[38]

Obayashi S, Sasaki D (2003) Visualization and data mining of pareto solutions using self-organizing map. Int Conf Evo Multi Criterion Optim 2632:796-808.

[39]

Parmee IC, Cvetkovic D (2002) Preferences and their application in evolutionary multiobjective optimisation. IEEE Trans Evol Comput 6(1):42-57.

Digital Library

[40]

Powell WB (2011) Approximate dynamic programming: solving the curse of dimensionality, 2nd edn. Wiley, London.

[41]

Saxena DK, Duro JX et al (2013) Objective reduction in many-objective optimization: linear and nonlinear algorithms. IEEE Trans Evol Comput 17(1):77-99.

Digital Library

[42]

Saxena DK, Deb K (2007) Non-linear dimensionality reduction procedures for certain large-dimensional multi-objective optimization problems: employing correntropy and a novel maximum variance unfolding. Evol Multi Criter Optim 4403:772-787.

[43]

Saxena D (2006) Searching for Pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems. In: IEEE congress on evolutionary computation.

[44]

Schaffer JD (1985) Multiple objective optimization with vector evaluated genetic algorithms. In: International conference on genetic algorithms, Pittsburgh, PA, USA, July, pp 93-100.

[45]

Schott JR (1995) Fault tolerant design using single and multicriteria genetic algorithm optimization. Cell Immunol 37(1):1-13.

[46]

Walker DJ, Everson R et al (2012) Visualizingmutually nondominating solution sets in many-objective optimization. IEEE Trans Evol Comput 17(2):165-184.

Digital Library

[47]

Wang G, Wu JJ (2007) A new fuzzy dominance GA applied to solve many-objective optimization problem. In: International conference on innovative computing, information and control, IEEE computer society.

[48]

Wang H, Jiao L et al (2015) A memetic optimization strategy based on dimension reduction in decision space. Evol Comput 23(1):69-100.

Digital Library

[49]

Wang R, PurshouseRCet al (2013) Preference-inspired co-evolutionary algorithm using adaptively generated goal vectors. Evolutionary computation, pp 916-923.

[50]

Wolpert DH, Macready WG (1997) No free lunch theorems for optimization. IEEE Trans Evol Comput 1(1):67-82.

Digital Library

[51]

Zhan ZH, Li J et al (2013) Multiple populations for multiple objectives: a coevolutionary technique for solving multiobjective optimization problems. IEEE Trans Syst Man Cybernet Part B Cybernet Publ IEEE Syst Man Cybernet Soc 43(2):445-463.

[52]

Zhang Q, Li H (2007) MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 11(6):712-731.

Digital Library

[53]

Zitzler E, Thiele L et al (2003) Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Comput 7(2):117-132.

Digital Library

[54]

Zitzler E, Laumanns M et al (2001) SPEA2: improving the strength pareto evolutionary algorithm for multi-objective optimization. Evolutionary methods for design, optimization and control with applications to industrial problems. In: Proceedings of the Eurogen 2001, Athens, Greece, September.

[55]

Zitzler E, Künzli S (2015) Indicator-based selection in multiobjective search. Lect Notes Comput Sci 3242:832-842.

[56]

Zou X, Chen Y et al (2008) A new evolutionary algorithm for solving many-objective optimization problems. IEEE Trans Syst Man Cybernet Part B Cybernet Publ IEEE Syst Man Cybernet Soc 38(5):1402-1412.

Cited By

Li GWang ZZhang QSun J(2023)Offline and Online Objective Reduction via Gaussian Mixture Model ClusteringIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.316883627:2(341-354)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TEVC.2022.3168836
Sun WLi J(2021)A strengthened diversity indicator and reference vector-based evolutionary algorithm for many-objective optimizationSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-021-05981-125:15(10257-10273)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s00500-021-05981-1
Gupta ARoss B(2020)Age-Layered Strategies for Many-Objective Optimization2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC)10.1109/SMC42975.2020.9283294(1544-1551)Online publication date: 11-Oct-2020
https://dl.acm.org/doi/10.1109/SMC42975.2020.9283294

Objective reduction for many-objective optimization problems using objective subspace extraction
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

An objective reduction algorithm using representative Pareto solution search for many-objective optimization problems

In recent years, many-objective optimization problems (i.e. more than three objectives) have attracted the interests of many researchers. The main difficulties of many-objective optimization problems lie in high computational cost, stagnation in search ...
Clustering Method using Pareto Corner Search Evolutionary Algorithm for Objective Reduction in Many-Objective Optimization Problems
SoICT '19: Proceedings of the 10th International Symposium on Information and Communication Technology

Many-objective optimization problems (MaOPs) have been gained considerable attention for researcher, recently. MaOPs make a number of difficulties for multi-objective optimization evolutionary algorithms (MOEAs) when solving them. Although, there exist ...
A New Objective Reduction Algorithm for Many-Objective Problems: Employing Mutual Information and Clustering Algorithm
CIS '12: Proceedings of the 2012 Eighth International Conference on Computational Intelligence and Security

Many-objective optimization problems involving a large number (more than four) of objectives have aroused extensive attention. It is known that problems with a high number of objectives cause additional difficulties in visualization of the objective ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Soft Computing - A Fusion of Foundations, Methodologies and Applications

Soft Computing - A Fusion of Foundations, Methodologies and Applications Volume 22, Issue 4

February 2018

336 pages

ISSN:1432-7643

EISSN:1433-7479

Issue’s Table of Contents

Copyright © Copyright © 2018 Springer-Verlag GmbH Germany, part of Springer Nature.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 February 2018

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li GWang ZZhang QSun J(2023)Offline and Online Objective Reduction via Gaussian Mixture Model ClusteringIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.316883627:2(341-354)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TEVC.2022.3168836
Sun WLi J(2021)A strengthened diversity indicator and reference vector-based evolutionary algorithm for many-objective optimizationSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-021-05981-125:15(10257-10273)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s00500-021-05981-1
Gupta ARoss B(2020)Age-Layered Strategies for Many-Objective Optimization2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC)10.1109/SMC42975.2020.9283294(1544-1551)Online publication date: 11-Oct-2020
https://dl.acm.org/doi/10.1109/SMC42975.2020.9283294

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents