Evolutionary multiobjective optimization

ABSTRACT

Many real-world search and optimization problems are naturally posed as non-linear programming problems having multiple conflicting objectives.

Due to lack of suitable solution techniques, such problems are usually artificially converted into a single-objective problem and solved. The difficulty arises because multi-objective optimization problems give rise to a set of Pareto-optimal solutions, each corresponding to a certain trade-off among the objectives. It then becomes important to find not just one Pareto-optimal solution but as many of them as possible.

Classical methods are found to be not efficient because they require repetitive applications to find multiple Pareto-optimal solutions and in some occasions repetitive applications do not guarantee finding distinct Pareto-optimal solutions. The population approach of evolutionary algorithms (EAs) allows an efficient way to find multiple Pareto-optimal solutions simultaneously in a single simulation run.

In this tutorial, we shall contrast the differences in philosophies between classical and evolutionary multi-objective methodologies and provide adequate fundamentals needed to understand and use both methodologies in practice.

Particularly, major state-of-the-art evolutionary multi-objective optimization (EMO) methodologies will be presented and various related issues such as performance assessment and preference articulation will be discussed. Thereafter, three main application areas of EMO will be discussed with adequate case studies from practice -- (i) applications showing better decision-making abilities through EMO, (ii) applications exploiting the multitude of trade-off solutions of EMO in extracting useful information in a problem, and (iii) applications showing better problem-solving abilities in various other tasks (such as, reducing bloating, solving single-objective constraint handling, and others).

Clearly, EAs have a niche in solving multi-objective optimization problems compared to classical methods. This is why EMO methodologies are getting a growing attention in the recent past. Since this is a comparatively new field of research, in this tutorial, a number of future challenges in the research and application of multi-objective optimization will also be discussed.

This tutorial is aimed for both novices and users of EMO. Those without any knowledge in EMO will have adequate ideas of the procedures and their importance in computing and problem-solving tasks. Those who have been practicing EMO will also have enough ideas and materials for future research, know state-of-the-art results and techniques, and make a comparative evaluation of their research.

REFERENCES

• 1: Bleuler, S., Brack, M.,Thiele, L., Zitzler, E. (2001). Multiobjective Genetic Programming: Reducing Bloat Using SPEA2. CEC-2001, pp. 536 -- 543.
• 2: Bleuler, S., Laumanns, M., Thiele, L., Zitzler, E.: PISA - A Platform and Programming Language Independent Interface for Search Algorithms. EMO 2003, pp. 494 -- 508.
• 3: Coello, C. (2000). Treating Constraints as Objectives for Single-Objective Evolutionary Optimization, Engineering Optimization, 32(3):275--308.
• 4: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 5: Deb, K., Pratap, A., Agarwal, S., Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, Volume 6, Issue 2, pp.182 -- 197.
• 6: Michael Eisenring , Lothar Thiele , Eckart Zitzler, Conflicting Criteria in Embedded System Design, IEEE Design & Test, v.17 n.2, p.51-59, April 2000 [doi>10.1109/54.844334]
• 7: 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
• 8: Fonseca, C. M., 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 28(1), pp. 26--37.
• 9: Fonseca, C., Knowles, J., Thiele, L., Zitzler, E. (2005). A Tutorial on the Performance Assessment of Stochastic Multiobjective Optimizers. EMO 2005.
• 10: Viviane Grunert da Fonseca , Carlos M. Fonseca , Andreia O. Hall, Inferential Performance Assessment of Stochastic Optimisers and the Attainment Function, Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization, p.213-225, March 07-09, 2001
• 11: Hubley, R., Zitzler, E., Roach, J. (2003). Evolutionary algorithms for the selection of single nucleotide polymorphisms. BMC Bioinformatics, Vol. 4, No. 30.
• 12: Marco Laumanns , Lothar Thiele , Kalyanmoy Deb , Eckart Zitzler, Combining convergence and diversity in evolutionary multiobjective optimization, Evolutionary Computation, v.10 n.3, p.263-282, Fall 2002 [doi>10.1162/106365602760234108]
• 13: Laumanns, M., Thiele, L., Zitzler, E. (2006). An Efficient Metaheuristic Based on the Epsilon-Constraint Method. European Journal of Operational Research, Volume 169, Issue 3 , pp 932--942.
• 14: Zbigniew Michalewicz, Genetic algorithms + data structures = evolution programs (3rd ed.), Springer-Verlag, London, 1996
• 15: 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
• 16: Silverman, B. W. (1986). Density estimation for statistics and data analysis, Chapman and Hall, London.
• 17: Jonathan Wright , Heather Loosemore, An Infeasibility Objective for Use in Constrained Pareto Optimization, Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization, p.256-268, March 07-09, 2001
• 18: Zitzler, E., Künzli, S. (2004). Indicator-Based Selection in Multiobjective Search. PPSN VIII, pp. 832--842.
• 19: Zitzler, E., Laumanns, M,, Thiele, L. (2002). SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization. Evolutionary Methods for Design, Optimisation, and Control, CIMNE, Barcelona, Spain, pages 95--100.
• 20: Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C., Grunert da Fonseca, V.: Performance Assessment of Multiobjective Optimizers: An Analysis and Review. IEEE Transactions on Evolutionary Computation, Vol. 7, No. 2, pages 117--132.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Performance

Keywords:
evolutionary computation, multiobjective optimization