article

Diagnostic assessment of search controls and failure modes in many-objective evolutionary optimization

Authors:

Patrick ReedAuthors Info & Claims

Evolutionary Computation, Volume 20, Issue 3

Pages 423 - 452

https://doi.org/10.1162/EVCO_a_00053

Published: 01 September 2012 Publication History

Abstract

The growing popularity of multiobjective evolutionary algorithms (MOEAs) for solving many-objective problems warrants the careful investigation of their search controls and failure modes. This study contributes a new diagnostic assessment framework for rigorously evaluating the effectiveness, reliability, efficiency, and controllability of MOEAs as well as identifying their search controls and failure modes. The framework is demonstrated using the recently introduced Borg MOEA, <inline-formula><inline-graphic xlink="EVCO_a_00053inline1.gif" mimetype="image" xlink:type="simple"/></inline-formula>-NSGA-II, <inline-formula><inline-graphic xlink="EVCO_a_00053inline2.gif" mimetype="image" xlink:type="simple"/></inline-formula>-MOEA, IBEA, OMOPSO, GDE3, MOEA/D, SPEA2, and NSGA-II on 33 instances of 18 test problems from the DTLZ, WFG, and CEC 2009 test suites. The diagnostic framework exploits Sobol's variance decomposition to provide guidance on the algorithms' non-separable, multi-parameter controls when performing a many-objective search. This study represents one of the most comprehensive empirical assessments of MOEAs ever completed.

References

[1]

Adra, S. F., and Fleming, P. J. (2009). A diversity management operator for evolutionary many-objective optimisation. In Evolutionary multi-criterion optimization (pp. 81-94). Berlin: Springer.

[2]

Archier, G., Saltelli, A., and Sobol, I. (1997). Sensitivity measures, ANOVA-like techniques and the use of bootstrap. Journal of Statistical Computation and Simulation, 58:99-120.

[3]

Baker, G. L., and Gollub, J. P. (1990). Chaotic dynamics: An introduction. Cambridge, UK: Cambridge University Press.

[4]

Bosman, P. A., and Thierens, D. (2003). The balance between proximity and diversity in multiobjective evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 7(2):174-188.

[5]

Brockhoff, D., Friedrich, T., Hebbinghaus, N., Klein, C., Neumann, F., and Zitzler, E. (2007). Do additional objectives make a problem harder? In Genetic and Evolutionary Computation Conference (GECCO 2007), pp. 765-772.

[6]

Coello Coello, C. A., Lamont, G. B., and Van Veldhuizen, D. A. (2007). Evolutionary algorithms for solving multi-objective problems. New York: Springer Science and Business Media.

[7]

Corne, D. W., and Knowles, J. D. (2000). The Pareto-envelope based selection algorithm for multiobjective optimization. In Parallel Problem Solving from Nature (PPSN VI), pp. 839-848.

[8]

Corne, D. W., and Knowles, J. D. (2007). Techniques for highly multiobjective optimisation: Some nondominated points are better than others. In Genetic and Evolutionary Computation Conference (GECCO 2007), pp. 773-780.

[9]

Deb, K., and Jain, S. (2002). Running performance metrics for evolutionary multi-objective optimization. KanGAL Report No. 2002004, Kanpur Genetic Algorithms Laboratory (KanGAL).

[10]

Deb, K., Mohan, M., and Mishra, S. (2003). A fast multi-objective evolutionary algorithm for finding well-spread Pareto-optimal solutions. KanGAL Report No. 2003002, Kanpur Genetic Algorithms Laboratory (KanGAL).

[11]

Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2000). A fast elitist multi-objective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182-197.

[12]

Deb, K., and Saxena, D. K. (2006). Searching for Pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems. In The 2006 IEEE Congress on Evolutionary Computation, pp. 3353-3360.

[13]

Deb, K., Thiele, L., Laumanns, M., and Zitzler, E. (2001). Scalable test problems for evolutionary multi-objective optimization. TIK-Technical Report No. 112, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH).

[14]

Deb, K., Thiele, L., Laumanns, M., and Zitzler, E. (2002). Scalable multi-objective optimization test problems. In Congress on Evolutionary Computation (CEC 2002), pp. 825-830.

[15]

di Pierro, F. (2006). Many-objective evolutionary algorithms and applications to water resources engineering. PhD thesis, University of Exeter, UK.

[16]

di Pierro, F., Khu, S.-T., and Savic, D. A. (2007). An investigation on preference order ranking scheme for multiobjective evolutionary optimization. IEEE Transactions on Evolutionary Computation, 11(1):17-45.

[17]

Drechsler, N., Drechsler, R., and Becker, B. (2001). Multi-objective optimisation based on relation favour. In Evolutionary Multi-Criterion Optimization (pp. 154-166). Berlin: Springer.

[18]

Edwards, A. L. (1993). An introduction to linear regression and correlation. New York: W. H. Freeman.

[19]

Farina, M., and Amato, P. (2004). A fuzzy definition of "optimality" formany-criteria optimization problems. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, 34(3):315-326.

[20]

Ferringer, M. P., Spencer, D. B., and Reed, P. (2009). Many-objective reconfiguration of operational satellite constellations with the large-cluster epsilon non-dominated sorting genetic algorithm-II. In IEEE Congress on Evolutionary Computation (CEC 2009), pp. 340-349.

[21]

Fleming, P. J., Purshouse, R. C., and Lygoe, R. J. (2005). Many-objective optimization: An engineering design perspective. In Evolutionary Multi-Criterion Optimization. Lecture Notes in Computer Science, Vol. 3410 (pp. 14-32). Berlin: Springer.

[22]

Fonseca, C. M., and Fleming, P. J. (1993). Genetic algorithms for multiobjective optimization: Formulation, discussion and generalization. In Genetic Algorithms: Proceedings of the Fifth International Conference, pp. 416-423.

[23]

Fonseca, C. M., and Fleming, P. J. (1998). Multiobjective optimization and multiple constraint handling with evolutionary algorithms--Part 1: A unified formulation. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, 28(1):26-37.

[24]

Goh, C.-K., and Tan, K. C. (2009). Evolutionary multi-objective optimization in uncertain environments. Berlin: Springer.

[25]

Goldberg, D. E. (1989a). Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley.

[26]

Goldberg, D. E. (1989b). Sizing populations for serial and parallel genetic algorithms. In Proceedings of the 3rd International Conference on Genetic Algorithms, pp. 70-79.

[27]

Grassberger, P., and Procaccia, I. (1983). Measuring the strangeness of strange attractors. Physica D Nonlinear Phenomena, 9:189-208.

[28]

Hadka, D., and Reed, P. (In press.). Borg: An auto-adaptive many-objective evolutionary computing framework. Evolutionary Computation.

[29]

Harik, G. R., and Lobo, F. G. (1999). A parameter-less genetic algorithm. In Proceedings of the IEEE Transactions on Evolutionary Computation, pp. 523-528.

[30]

Holland, J. H. (1975). Adaptation in natural and artificial systems. Ann Arbor, MI: University of Michigan Press.

[31]

Horn, J., and Nafpliotis, N. (1993). Multiobjective optimization using the niched Pareto genetic algorithm. Technical Report 93005, University of Illinois.

[32]

Huband, S., Hingston, P., Barone, L., and While, L. (2006). A review of multiobjective test problems and a scalable test problem toolkit. IEEE Transactions on Evolutionary Computation, 10(5):477-506.

[33]

Hughes, E. J. (2005). Evolutionary many-objective optimisation:Many once or one many? In The 2005 IEEE Congress on Evolutionary Computation, Vol. 1, pp. 222-227.

[34]

Iorio, A., and Li, X. (2008). Improving the performance and scalability of differential evolution. In Simulated Evolution and Learning. Lecture Notes in Computer Science, Vol. 5361 (pp. 131-140). Berlin: Springer.

[35]

Ishibuchi, H., Tsukamoto, N., Hitotsuyanagi, Y., and Nojima, Y. (2008). Effectiveness of scalability improvement attempts on the performance of NSGA-II for many-objective problems. In Genetic and Evolutionary Computation Conference (GECCO 2008), pp. 649-656.

[36]

Ishibuchi, H., Tsukamoto, N., and Nojima, Y. (2008). Behavior of evolutionary many-objective optimization. In Proceedings of the Tenth International Conference on Computer Modeling and Simulation (UKSIM 2008), pp. 266-271.

[37]

Ishibuchi, H., Tsukamoto, N., Sakane, Y., and Nojima, Y. (2010). Indicator-based evolutionary algorithm with hypervolume approximation by achievement scalarizing functions. In Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, GECCO '10, pp. 527-534.

[38]

Kasprzyk, J., Reed, P., Kirsch, B., and Characklis, G. (2011). Many-objective de novo water supply portfolio planning under deep uncertainty. Environmental Modelling & Software.

[39]

Kasprzyk, J. R., Reed, P. M., Kirsch, B. R., and Characklis, G. W. (2009). Managing population and drought risks using many-objective water portfolio planning under uncertainty. Water Resources Research, 45. W12401.

[40]

Khare, V., Yao, X., and Deb, K. (2003). Performance scaling of multi-objective evolutionary algorithms. In Evolutionary Multi-Criterion Optimization (pp. 376-390). Berlin: Springer.

[41]

Knowles, J., and Corne, D. (2002). On metrics for comparing non-dominated sets. In Congress on Evolutionary Computation (CEC 2002), Vol. 1, pp. 711-716.

[42]

Knowles, J., and Corne, D. (2007). Quantifying the effects of objective space dimension in evolutionary multiobjective optimization. In Evolutionary Multi-Criterion Optimization. Lecture Notes in Computer Science, Vol. 4403 (pp. 757-771). Berlin: Springer.

[43]

Knowles, J. D., and Corne, D.W. (1999). Approximating the nondominated front using the Pareto archived evolution strategy. Evolutionary Computation, 8(2):149-172.

[44]

Kollat, J., Reed, P., and Maxwell, R. (2011). Many-objective groundwater monitoring network design using bias-aware ensemble Kalman filtering, evolutionary optimization, and visual analytics. Water Resources Research, 47. W02529.

[45]

Kollat, J. B., and Reed, P. M. (2006). Comparison of multi-objective evolutionary algorithms for long-term monitoring design. Advances in Water Resources, 29(6):792-807.

[46]

Kollat, J. B., and Reed, P. M. (2007). A computational scaling analysis of multiobjective evolutionary algorithms in long-term groundwater monitoring applications. Advances in Water Resources, 30(3):408-419.

[47]

Kukkonen, S., and Deb, K. (2006). A fast and effective method for pruning of nondominated solutions in many-objective problems. In Parallel Problem Solving from Nature (PPSN IX). Lecture Notes in Computer Science, Vol. 4193 (pp. 553-562). Berlin: Springer.

[48]

Kukkonen, S., and Lampinen, J. (2005). GDE3: The third evolution step of generalized differential evolution. In The 2005 IEEE Congress on Evolutionary Computation, Vol. 1, pp. 443-450.

[49]

Laumanns, M., Thiele, L., Deb, K., and Zitzler, E. (2002). Combining convergence and diversity in evolutionary multi-objective optimization. Evolutionary Computation, 10(3): 263-282.

[50]

Nayfeh, A. H., and Balachandran, B. (1995). Applied nonlinear dynamics: Analytical, computational, and experimental methods. New York: Wiley Inter-Science.

[51]

Praditwong, K., and Yao, X. (2007). How well do multi-objective evolutionary algorithms scale to large problems? In Congress on Evolutionary Computation (CEC 2007), pp. 3959-3966.

[52]

Purshouse, R. C., and Fleming, P. J. (2003). Evolutionary many-objective optimisation: An exploratory analysis. In Congress on Evolutionary Computation (CEC 2003), Vol. 3, pp. 2066-2073.

[53]

Purshouse, R. C., and Fleming, P. J. (2007). On the evolutionary optimization of many conflicting objectives. IEEE Transactions on Evolutionary Computation, 11(6):770-784.

[54]

Saltelli, A., Ratto, M., Andres, T., Campolongo, F., Cariboni, J., Gatelli, D., Saisana, M., and Tarantola, S. (2008). Global sensitivity analysis: The primer. New York: Wiley.

[55]

Schaffer, D. J. (1984). Multiple objective optimization with vector evaluated genetic algorithms. PhD thesis, Vanderbilt University.

[56]

Sheskin, D. J. (2004). Handbook of parametric and nonparametric statistical procedures. Boca Raton, FL: Chapman & Hall/CRC.

[57]

Sierra, M. R., and Coello Coello, C. A. (2005). Improving PSO-based multi-objective optimization using crowding, mutation and ¿-dominance. In Evolutionary Multi-Criterion Optimization. Lecture Notes in Computer Science, Vol. 3410 (pp. 505-519). Berlin: Springer.

[58]

Srinivas, N., and Deb, K. (1993). Multiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation, 2(3):221-248.

[59]

Srivastava, R. P. (2002). Time continuation in genetic algorithms. Technical report, Illinois Genetic Algorithm Laboratory.

[60]

Sülflow, A., Drechsler, N., and Drechsler, R. (2007). Robust multi-objective optimization in high dimensional spaces. In Evolutionary Multi-Criterion Optimization (pp. 715-726). Berlin: Springer.

[61]

Tang, Y., Reed, P., Wagener, T., and van Werkhoven, K. (2007). Comparing sensitivity analysis methods to advance lumped watershed model identification and evaluation. Hydrology and Earth System Sciences, 11(2):793-817.

[62]

Teytaud, O. (2006). How entropy-theorems can show that on-line approximating high-dim Pareto-fronts is too hard. In PPSN BTP Workshop.

[63]

Teytaud, O. (2007). On the hardness of offline multi-objective optimization. Evolutionary Computation, 15(4):475-491.

[64]

Vrugt, J. A., and Robinson, B. A. (2007). Improved evolutionary optimization from genetically adaptive multimethod search. Proceedings of the National Academy of Sciences, 104(3): 708-711.

[65]

Vrugt, J. A., Robinson, B. A., and Hyman, J. M. (2009). Self-adaptive multimethod search for global optimization in real-parameter spaces. IEEE Transactions on Evolutionary Computation, 13(2):243-259.

[66]

Wagner, T., Beume, N., and Naujoks, B. (2007). Pareto-, aggregation-, and indicator-based methods in many-objective optimization. In Evolutionary Multi-Criterion Optimization (pp. 742-756). Berlin: Springer.

[67]

Zhang, Q., Liu, W., and Li, H. (2009). The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances. In Congress on Evolutionary Computation (CEC 2009), pp. 203-208.

[68]

Zhang, Q., and Suganthan, P. N. (2009). Final report on the CEC '09 MOEA competition. In Congress on Evolutionary Computation (CEC 2009).

[69]

Zhang, Q., Zhou, A., Zhao, S., Suganthan, P. N., Liu, W., and Tiwari, S. (2009). Multiobjective optimization test instances for the CEC 2009 special session and competition. Technical Report CES-487, University of Essex.

[70]

Zitzler, E., and Künzli, S. (2004). Indicator-based selection in multiobjective search. In Parallel Problem Solving from Nature (PPSN VIII). Lecture Notes in Computer Science, Vol. 3242 (pp. 832-842). Berlin: Springer.

[71]

Zitzler, E., Laumanns, M., and Thiele, L. (2002). SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization. CIMNE.

[72]

Zitzler, E., Laumanns, M., Thiele, L., Fonseca, C. M., and da Fonseca, V. G. (2002). Why quality assessment of multiobjective optimizers is difficult. In Genetic and Evolutionary Computation Conference (GECCO 2002), pp. 666-674.

[73]

Zitzler, E., and Thiele, L. (1999). Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation, 3(4):257-271.

[74]

Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C. M., and da Fonseca, V. G. (2002). Performance assessment of multiobjective optimizers: An analysis and review. IEEE Transactions on Evolutionary Computation, 7(2):117-132.

Cited By

Gan WLi HHao P(2025)Many-objective optimization algorithm based on the similarity principle and multi-mechanism collaborative searchThe Journal of Supercomputing10.1007/s11227-024-06553-481:1Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s11227-024-06553-4
Gan WLi HHao PLiu L(2025)Multi-indicator collaborative evolutionary algorithm for many-objective optimizationCluster Computing10.1007/s10586-024-04739-228:1Online publication date: 1-Feb-2025
https://dl.acm.org/doi/10.1007/s10586-024-04739-2
Zatarain Salazar JKwakkel JWitvliet M(2024)Evaluating the choice of radial basis functions in multiobjective optimal control applicationsEnvironmental Modelling & Software10.1016/j.envsoft.2023.105889171:COnline publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1016/j.envsoft.2023.105889
Show More Cited By

Diagnostic assessment of search controls and failure modes in many-objective evolutionary optimization
1. Information systems
  1. Data management systems
    1. Database administration
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Approximate non-dominated sorting for evolutionary many-objective optimization

Non-dominated sorting has widely been adopted and shown to be very effective in dominance based evolutionary multi-objective optimization where the number of objectives is two or three. In dealing with many-objective optimization problems, where the ...
An improved NSGA-III procedure for evolutionary many-objective optimization
GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

Many-objective (four or more objectives) optimization problems pose a great challenge to the classical Pareto-dominance based multi-objective evolutionary algorithms (MOEAs), such as NSGA-II and SPEA2. This is mainly due to the fact that the selection ...
Evolutionary many-objective optimization based on linear assignment problem transformations

The selection mechanisms that are most commonly adopted by multi-objective evolutionary algorithms (MOEAs) are based on Pareto optimality. However, recent studies have provided theoretical and experimental evidence regarding the unsuitability of Pareto-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Evolutionary Computation

Evolutionary Computation Volume 20, Issue 3

Fall 2012

160 pages

ISSN:1063-6560

EISSN:1530-9304

Issue’s Table of Contents

Publisher

MIT Press

Cambridge, MA, United States

Publication History

Published: 01 September 2012

Published in EVOL Volume 20, Issue 3

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
379
Total Downloads

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

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gan WLi HHao P(2025)Many-objective optimization algorithm based on the similarity principle and multi-mechanism collaborative searchThe Journal of Supercomputing10.1007/s11227-024-06553-481:1Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s11227-024-06553-4
Gan WLi HHao PLiu L(2025)Multi-indicator collaborative evolutionary algorithm for many-objective optimizationCluster Computing10.1007/s10586-024-04739-228:1Online publication date: 1-Feb-2025
https://dl.acm.org/doi/10.1007/s10586-024-04739-2
Zatarain Salazar JKwakkel JWitvliet M(2024)Evaluating the choice of radial basis functions in multiobjective optimal control applicationsEnvironmental Modelling & Software10.1016/j.envsoft.2023.105889171:COnline publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1016/j.envsoft.2023.105889
Zhu QKang GWu XLin QTang HChen J(2024)A Kriging-assisted evolutionary algorithm with multiple infill sampling for expensive many-objective optimizationEngineering Applications of Artificial Intelligence10.1016/j.engappai.2024.108505135:COnline publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.engappai.2024.108505
Guo HZhu DZhou CZou C(2024)DNA sequences design under many objective evolutionary algorithmCluster Computing10.1007/s10586-024-04675-127:10(14167-14183)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s10586-024-04675-1
Wang PZecchin AMaier H(2023)Improved selection strategy for multi‐objective evolutionary algorithms with application to water distribution optimization problemsComputer-Aided Civil and Infrastructure Engineering10.1111/mice.1296438:10(1290-1306)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1111/mice.12964
De Moraes MCoelho G(2022)A Random Forest-Assisted Decomposition-Based Evolutionary Algorithm for Multi-Objective Combinatorial Optimization Problems2022 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC55065.2022.9870412(1-8)Online publication date: 18-Jul-2022
https://dl.acm.org/doi/10.1109/CEC55065.2022.9870412
Etemadi VBushehrian ORobles G(2022)Task assignment to counter the effect of developer turnover in software maintenanceInformation and Software Technology10.1016/j.infsof.2021.106786143:COnline publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1016/j.infsof.2021.106786
Gu QXu QLi X(2022)An improved NSGA-III algorithm based on distance dominance relation for many-objective optimizationExpert Systems with Applications: An International Journal10.1016/j.eswa.2022.117738207:COnline publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1016/j.eswa.2022.117738
de Moraes MCoelho G(2022)A diversity preservation method for expensive multi-objective combinatorial optimization problems using Novel-First Tabu Search and MOEA/DExpert Systems with Applications: An International Journal10.1016/j.eswa.2022.117251202:COnline publication date: 15-Sep-2022
https://dl.acm.org/doi/10.1016/j.eswa.2022.117251
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents