More Web Proxy on the site http://driver.im/

article

Free access

Multiobjective Evolutionary Algorithms: Analyzing the State-of-the-Art

Authors:

David A. Van Veldhuizen,

Gary B. LamontAuthors Info & Claims

Evolutionary Computation, Volume 8, Issue 2

Pages 125 - 147

https://doi.org/10.1162/106365600568158

Published: 01 June 2000 Publication History

Abstract

Solving optimization problems with multiple (often conflicting) objectives is, generally, a very difficult goal. Evolutionary algorithms (EAs) were initially extended and applied during the mid-eighties in an attempt to stochastically solve problems of this generic class. During the past decade, a variety of multiobjective EA (MOEA) techniques have been proposed and applied to many scientific and engineering applications. Our discussion's intent is to rigorously define multiobjective optimization problems and certain related concepts, present an MOEA classification scheme, and evaluate the variety of contemporary MOEAs. Current MOEA theoretical developments are evaluated; specific topics addressed include fitness functions, Pareto ranking, niching, fitness sharing, mating restriction, and secondary populations. Since the development and application of MOEAs is a dynamic and rapidly growing activity, we focus on key analytical insights based upon critical MOEA evaluation of current research and applications. Recommended MOEA designs are presented, along with conclusions and recommendations for future work.

References

[1]

Bäack, T. (1996). Evolutionary Algorithms in Theory and Practice. Oxford University Press, New York, New York.

[2]

Bäck, T., Fogel, D. and Michalewicz, Z. (1997). Handbook of Evolutionary Computation, Volume 1, Oxford University Press, Oxford, England.

[3]

Benson, H. P. and Sayin, S. (1997). Towards Finding Global Representations of the Efficient Set in Multiple Objective Mathematical Programming. Naval Research Logistics, 44:47-67.

[4]

Cantú-Paz, E. (1997). A Survey of Parallel Genetic Algorithms. Technical Report 97003, Illinois Genetic Algorithms Laboratory, Department of General Engineering, University of Illinois, Urbana, Illinois.

[5]

Coello, C. A. C. (1999a). A Comprehensive Survey of Evolutionary-Based Multiobjective Optimization Techniques. Knowledge and Information Systems, 1(3):269-308.

[6]

Coello, C. A. C. (1999b). List of References on Evolutionary Multiobjective Optimization. Available: http://www.lania.mx/~ccoello/EMOO/EMOObib.html.

[7]

Coello, C. A. C. (2000). Treating Constraints as Objectives for Single-Objective Evolutionary Optimization. Engineering Optimization, 32(3):275-308.

[8]

Deb, K. (1999a). Construction of Test Problems for Multi-Objective Optimization. In Banzhaf, W., Daida, J., Eiben, A. E., Garzon, M. H., Honavar, V., Jakiela, M. and Smith, R. E., editors, GECCO-99: Proceedings of the Genetic and Evolutionary Computation Conference, Volume 1, pages 164-171, Morgan Kaufmann, San Francisco, California.

[9]

Deb, K. (1999b). Multi-ObjectiveGenetic Algorithms: Problem Difficulties and Construction of Test Problems. Evolutionary Computation, 7(3):205-230.

[10]

Deb, K. and Goldberg, D. E. (1989). An Investigation of Niche and Species Formation in Genetic Function Optimization. In Schaffer, J. D., editor, Proceedings of the Third International Conference on Genetic Algorithms, pages 42-50, Morgan Kaufmann, San Mateo, California.

[11]

Fonseca, C. M. and Fleming, P. J. (1993). Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion, and Generalization. In Forrest, S., editor, Proceedings of the Fifth International Conference on Genetic Algorithms, pages 416-423, Morgan Kaufmann, San Mateo, California.

[12]

Fonseca, C. M. and Fleming, P. J. (1995a). An Overview of Evolutionary Algorithms in Multiobjective Optimization. Evolutionary Computation, 3(1):1-16.

[13]

Fonseca, C.M. and Fleming, P. J. (1995b). Multiobjective Genetic Algorithms Made Easy: Selection, Sharing, and Mating Restriction. In Proceedings of the First International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications, pages 45-52, IEE, London, England.

[14]

Fonseca, C. M. and Fleming, P. J. (1997a). Multiobjective Optimization. In Bäck, T., Fogel, D. and Michalewicz, Z., editors, Handbook of Evolutionary Computation, Volume 1, pages C4.5:1 - C4.5:9, Oxford University Press, Oxford, England.

[15]

Fonseca, C. M. and Fleming, P. J. (1997b). Non-Linear System Identification with Multiobjective Genetic Algorithms. In Proceedings of the Thirteenth Triennial World Congress of the International Federation of Automatic Control, pages 187-192, Pergamon, London, England.

[16]

Fonseca, C. M. and Fleming, P. J. (1998). Multiobjective Optimization and Multiple Constraint Handling with Evolutionary Algorithms - Part I: A Unified Formulation. IEEE Transactions on Systems, Man and Cybernetics - Part A: Systems and Humans, 28(1):26-37.

[17]

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison Wesley, Reading, Massachusetts.

[18]

Goldberg, D. E. (1998). From Genetic and Evolutionary Optimization to the Design of Conceptual Machines. Technical Report 98008, Department of General Engineering, University of Illinois, Urbana, Illinois.

[19]

Horn, J. (1997). Multicriterion Decision Making. In Bäck, T., Fogel, D. and Michalewicz, Z., editors, Handbook of Evolutionary Computation, Volume 1, pages F1.9:1 - F1.9:15, Oxford University Press, Oxford, England.

[20]

Horn, J. and Nafpliotis, N. (1993). Multiobjective Optimization Using the Niched Pareto Genetic Algorithm. Technical Report 930005, Illinois Genetic Algorithms Laboratory (IlliGAL), University of Illinois, Urbana, Illinois.

[21]

Horn, J., Nafpliotis, N. and Goldberg, D. E. (1994). A Niched Pareto Genetic Algorithm for Multiobjective Optimization. In Michalewicz, Z., editor, Proceedings of the First IEEE Conference on Evolutionary Computation, pages 82-87, IEEE Press, Piscataway, New Jersey.

[22]

Hwang, C.-L. and Masud, A. S. M. (1979). Multiple Objective Decision Making - Methods and Applications. Springer Verlag, Berlin, Germany.

[23]

Ishibuchi, H. and Murata, T. (1998). Multi-Objective Genetic Local Search for Minimizing the Number of Fuzzy Rules for Pattern Classification Problems. In Fogel, D., editor, Proceedings of the Fifth IEEE International Conference on Evolutionary Computation, pages 1100-1105, IEEE Press, Piscataway, New Jersey.

[24]

Michalewicz, Z. and Nazhiyath, G. (1995).Genocop III: A Co-Evolutionary Algorithm for Numerical Optimization Problems with Nonlinear Constraints. In Fogel, D., editor, Proceedings of the Second IEEE Conference on Evolutionary Computation, pages 647-651, IEEE Press, Piscataway, New Jersey.

[25]

Michielssen, E. and Weile, D. S. (1995). Electromagnetic System Design Using Genetic Algorithms. In Winter, G., Periaux, J., Galan, M. and Cuesta, P., editors, Genetic Algorithms in Engineering and Computer Science, pages 345-369, John Wiley and Sons, Chichester, England.

[26]

Parks, G.T. and Miller, I. (1998). Selective Breeding in a Multiobjective Genetic Algorithm. In Eiben, A. E., Bäck, T., Schoenauer, M. and Schwefel, H.-P., editors, Parallel Problem Solving from Nature - PPSN V. Springer, Berlin, Germany.

[27]

Pohlheim, H. (1998).GEATbx: Genetic and Evolutionary AlgorithmToolbox for use with MATLAB. Available: http://www.geatbx.com/index.html.

[28]

Rowe, J., Vinsen, K. and Marvin, N. (1996). Parallel GAs for Multiobjective Functions. In Alander, J. T., editor, Second Nordic Workshop on Genetic Algorithms and Their Applications (2NWGA), pages 61-70, University of Vaasa, Vaasa, Finland.

[29]

Rudolph, G. (1998a). Evolutionary Search for Minimal Elements in Partially Ordered Finite Sets. In Porto, V. W., Saravanan, N., Waagen, D. and Eiben, A. E., editors, Proceedings of the Seventh Annual Conference on Evolutionary Programming, pages 345-353, Springer, Berlin, Germany.

[30]

Rudolph, G. (1998b). On a Multi-Objective Evolutionary Algorithm and Its Convergence to the Pareto Set. In Proceedings of the Fifth IEEE Conference on Evolutionary Computation, pages 511- 516, IEEE Press, Piscataway, New Jersey.

[31]

Sandgren, E. (1994). Multicriteria Design Optimization by Goal Programming. In Adeli, H., editor, Advances in Design Optimization, pages 225-265, Chapman and Hall, London, England.

[32]

Schaffer, J. D. (1985). Multiple Objective Optimization with Vector Evaluated Genetic Algorithms. In Grefenstette, J. J., editor, Proceedings of the First International Conference on Genetic Algorithms and Their Applications, pages 93-100, Lawrence Erlbaum, Hillsdale, New Jersey.

[33]

Shaw, K. J. and Fleming, P. J. (1996). Initial Study of Multi-Objective Genetic Algorithms for Scheduling the Production of Chilled Ready Meals. In Proceedings of the Second International Mendel Conference on Genetic Algorithms, Technical University of Brno, Brno, Czech Republic.

[34]

Shaw, K. J., Nortcliffe, A. L., Thompson, M., Love, J., Fonseca, C. M. and Fleming, P. J. (1999). Assessing the Performance of Multiobjective Genetic Algorithms for Optimization of a Batch Process Scheduling Problem. In Angeline, P., editor, 1999 Congress on Evolutionary Computation, pages 37-45, IEEE Press, Piscataway, New Jersey.

[35]

Srinivas, N. and Deb, K. (1994). Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms. Evolutionary Computation, 2(3):221-248.

[36]

Thomas, M. W. (1998). A Pareto Frontier for Full Stern Submarines via Genetic Algorithm. Ph.D. thesis, Ocean Engineering Department, Massachusetts Institute of Technology, Cambridge, Massachusetts.

[37]

Todd, D. S. and Sen, P. (1997). A Multiple Criteria Genetic Algorithm for Containership Loading. In Bäck, T., editor, Proceedings of the Seventh International Conference on Genetic Algorithms, pages 674-681, Morgan Kaufmann, San Francisco, California.

[38]

Van Veldhuizen, D. A. (1999). Multiobjective Evolutionary Algorithms: Classifications, Analyses, and New Innovations. Ph.D. thesis, AFIT/DS/ENG/99-01, Air Force Institute of Technology, Wright-Patterson AFB, Ohio.

[39]

Van Veldhuizen, D. A. and Lamont, G. B. (1999). Multiobjective Evolutionary Algorithm Test Suites. In Carroll, J., Haddad, H., Oppenheim, D., Bryant, B. and Lamont, G. B., editors, Proceedings of the 1999 ACM Symposium on Applied Computing, pages 351-357, ACM, New York, New York.

[40]

Van Veldhuizen, D. A., Sandlin, B. S., Marmelstein, R. E., Lamont, G. B. and Terzuoli, A. J. (1998). Finding Improved Wire-Antenna Geometries with Genetic Algorithms. In Fogel, D., editor, Proceedings of the Fifth IEEE International Conference on Evolutionary Computation, pages 102-107, IEEE Press, Piscataway, New Jersey.

[41]

Vedarajan, G., Chan, L. C. and Goldberg, D. E. (1997). Investment Portfolio Optimization using Genetic Algorithms. In Koza, J. R., editor, Late Breaking Papers at the Genetic Programming 1997 Conference, pages 255-263, Stanford Bookstore, Stanford University, California.

[42]

Wienke, D., Lucasius, C. and Kateman, G. (1992). Multicriteria Target Vector Optimization of Analytical Procedures Using a Genetic Algorithm. Analytica Chimica Acta, 265:211-225.

[43]

Wolpert, D. H. and Macready, W. G. (1997). No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation, 1(1):67-82.

[44]

Zitzler, E. and Thiele, L. (1998). Multiobjective Optimization Using Evolutionary Algorithms - A Comparative Case Study. In Eiben, A. E., Bäck, T., Schoenauer, M. and Schwefel, H.-P., editors, Parallel Problem Solving from Nature - PPSN V, Springer, Berlin, Germany.

[45]

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.

Cited By

Wang HHuang W(2023)A Coevolution Algorithm Based on Spatial Division and Hybrid Matching StrategyInternational Journal of Cognitive Informatics and Natural Intelligence10.4018/IJCINI.32675217:1(1-17)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.4018/IJCINI.326752
Zheng TJiang Y(2023)Driver-rider matching and route optimization in carpooling service for delivering intercity commuters to the high-speed railway stationExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.120231227:COnline publication date: 11-Jul-2023
https://dl.acm.org/doi/10.1016/j.eswa.2023.120231
Awad ACoghill GPang W(2023)A novel Physarum-inspired competition algorithm for discrete multi-objective optimisation problemsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-08505-127:20(14699-14719)Online publication date: 26-Jun-2023
https://dl.acm.org/doi/10.1007/s00500-023-08505-1
Show More Cited By

Multiobjective Evolutionary Algorithms: Analyzing the State-of-the-Art

Recommendations

Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach

Evolutionary algorithms (EAs) are often well-suited for optimization problems involving several, often conflicting objectives. Since 1985, various evolutionary approaches to multiobjective optimization have been developed that are capable of searching ...
Behavior of Multiobjective Evolutionary Algorithms on Many-Objective Knapsack Problems
We examine the behavior of three classes of evolutionary multiobjective optimization (EMO) algorithms on many-objective knapsack problems. They are Pareto dominance-based, scalarizing function-based, and hypervolume-based algorithms. NSGA-II, MOEA/D, SMS-...
Coevolutionary Multiobjective Evolutionary Algorithms: Survey of the State-of-the-Art
In the last 20 years, evolutionary algorithms (EAs) have shown to be an effective method to solve multiobjective optimization problems (MOPs). Due to their population-based nature, multiobjective EAs (MOEAs) are able to generate a set of tradeoff ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Evolutionary Computation

Evolutionary Computation Volume 8, Issue 2

June 2000

124 pages

ISSN:1063-6560

EISSN:1530-9304

Issue’s Table of Contents

Publisher

MIT Press

Cambridge, MA, United States

Publication History

Published: 01 June 2000

Published in EVOL Volume 8, Issue 2

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

190
Total Citations
View Citations
1,053
Total Downloads

Downloads (Last 12 months)105
Downloads (Last 6 weeks)14

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang HHuang W(2023)A Coevolution Algorithm Based on Spatial Division and Hybrid Matching StrategyInternational Journal of Cognitive Informatics and Natural Intelligence10.4018/IJCINI.32675217:1(1-17)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.4018/IJCINI.326752
Zheng TJiang Y(2023)Driver-rider matching and route optimization in carpooling service for delivering intercity commuters to the high-speed railway stationExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.120231227:COnline publication date: 11-Jul-2023
https://dl.acm.org/doi/10.1016/j.eswa.2023.120231
Awad ACoghill GPang W(2023)A novel Physarum-inspired competition algorithm for discrete multi-objective optimisation problemsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-08505-127:20(14699-14719)Online publication date: 26-Jun-2023
https://dl.acm.org/doi/10.1007/s00500-023-08505-1
Colomine Durán FCotta CFernández-Leiva A(2023)Epoch-Based Application of Problem-Aware Operators in a Multiobjective Memetic Algorithm for Portfolio OptimizationApplications of Evolutionary Computation10.1007/978-3-031-30229-9_14(210-222)Online publication date: 12-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30229-9_14
Deist TGrewal MDankers FAlderliesten TBosman P(2023)Multi-objective Learning Using HV MaximizationEvolutionary Multi-Criterion Optimization10.1007/978-3-031-27250-9_8(103-117)Online publication date: 20-Mar-2023
https://dl.acm.org/doi/10.1007/978-3-031-27250-9_8
Hu JWhitman JTravers MChoset H(2022)Modular Robot Design Optimization with Generative Adversarial Networks2022 International Conference on Robotics and Automation (ICRA)10.1109/ICRA46639.2022.9812091(4282-4288)Online publication date: 23-May-2022
https://dl.acm.org/doi/10.1109/ICRA46639.2022.9812091
Belna MNdiaye ATaillandier FFernandez CAgabriel LGésan-Guiziou G(2022)Multiobjective optimization of skim milk microfiltration based on expert knowledgeExpert Systems with Applications: An International Journal10.1016/j.eswa.2022.117624205:COnline publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.eswa.2022.117624
Al Ani ZGujarathi AAl-Muhtaseb A(2022)A state of art review on applications of multi-objective evolutionary algorithms in chemicals production reactorsArtificial Intelligence Review10.1007/s10462-022-10219-z56:3(2435-2496)Online publication date: 19-Jul-2022
https://dl.acm.org/doi/10.1007/s10462-022-10219-z
Chen YYuan XCang X(2022)A new gradient stochastic ranking-based multi-indicator algorithm for many-objective optimizationSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-018-3642-723:21(10911-10929)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/s00500-018-3642-7
Tan WMohamad-Saleh J(2022)MO-NFSA for solving unconstrained multi-objective optimization problemsEngineering with Computers10.1007/s00366-020-01223-438:3(2527-2548)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s00366-020-01223-4
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Issue’s Table of Contents