Interactive evolutionary multi-objective optimization and decision-making using reference direction method

ABSTRACT

In this paper, we borrow the concept of reference direction approach from the multi-criterion decision-making literature and combine it with an EMOprocedure to develop an algorithm for finding a single preferred solution in a multi-objective optimization scenario efficiently. EMO methodologies are adequately used to find a set of representative efficient solutions over the past decade. This study is timely in addressing the issue of optimizing and choosing a single solution using certain preference information. In this approach, the user supplies one or more reference directions in the objective space. The population approach of EMO methodologies is exploited to find a set of efficient solutions corresponding to a number of representative points along the reference direction. By using a utility function, a single solution is chosen for further analysis. This procedure is continued till no further improvement is possible. The working of the procedure is demonstrated on a set of test problems having two to ten objectives and on an engineering design problem. Results are verified with theoretically exact solutions on two-objective test problems.

REFERENCES

• 1: J. Branke and K. Deb. Integrating user preferences into evolutionary multi-objective optimization. In Y. Jin, editor, Knowledge Incorporation in Evolutionary Computation pages 461--477. Hiedelberg, Germany:Springer, 2004.
• 2: J. Branke, T. Kauβler, and H. Schmeck. Guidance in evolutionary multi-objective optimization. Advances in Engineering Software 32:499--507, 2001.
• 3: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 4: K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan. A fast and elitist multi-objective genetic algorithm:NSGA-II. IEEE Transactions on Evolutionary Computation 6(2):182--197, 2002.
• 5: Kalyanmoy Deb , Shamik Chaudhuri , Kaisa Miettinen, Towards estimating nadir objective vector using evolutionary approaches, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144113]
• 6: K. Deb, D. Padmanabhan, S. Gupta, and A. K. Mall. Reliability-based multi-objective optimization using evolutionary algorithms. In Proceedings of the Fourth International Conference on Evolutionary Multi-Criterion Optimization (EMO-2007) (LNCS, Springer) pages 66--80, 2007.
• 7: K. Deb and D. Saxena. Searching for pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems. In Proceedings of the World Congress on Computational Intelligence (WCCI-2006) pages 3352--3360, 2006.
• 8: K. Deb, J. Sundar, N. Uday, and S. Chaudhuri. Reference point based multi-objective optimization using evolutionary algorithms. International Journal of Computational Intelligence Research (IJCIR) 2(6):273--286, 2006.
• 9: K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Scalable test problems for evolutionary multi-objective optimization. In A. Abraham, L. Jain, and R. Goldberg, editors, Evolutionary Multiobjective Optimization pages 105--145. London: Springer-Verlag, 2005.
• 10: C. M. Fonseca and P. J. Fleming. Multiobjective optimization and multiple constraint handling with evolutionary algorithms. Part II:Application example. IEEE Transactions on Systems, Man, and Cybernetics: Part A: Systems and Humans 28(1):38--47, 1998.
• 11: P. Korhonen. The specification of a reference direction using the analytic hierarchy process. Mathematical Modelling 9(3-5):361--368, 1987.
• 12: P. Korhonen. A visual reference direction approach to solving discrete multiple criteria problems. European Journal of Operational Reseaech 34:152--159, 1988.
• 13: P. Korhonen and J. Karaivanova. An algorithm for projecting a reference direction onto the nondominated set of given points. IEEE Trans. on Systems, Man and Cybernetics-Part A: Systems and Humans 29(5):429--435, 1999.
• 14: P. Korhonen and J. Laakso. Solving generalized goal programming problems using a visual interactive approach. European Journal of Operational Reseaech 26:355--363, 1986.
• 15: P. Korhonen and J. Laakso. A visual interactive method for solving the multiple criteria problem. European Journal of Operational Reseaech 24:277--287, 1986.
• 16: P. Korhonen and G. Y. Yu. A reference direction approach to multiple objective quadratic-linear programming. European Journal of Operational Reseaech 102:601--610, 1997.
• 17: M. Luque, K. Miettinen, P. Eskelinen, and F. Ruiz. Three different ways for incorporating preference information in interactive reference point based methods. Technical Report W-410, Helsinki School of Economics, Helsinki, Finland, 2006.
• 18: K. Miettinen. Nonlinear Multiobjective Optimization Kluwer, Boston, 1999.
• 19: Selcen (Pamuk) Phelps , Murat Köksalan, An Interactive Evolutionary Metaheuristic for Multiobjective Combinatorial Optimization, Management Science, v.49 n.12, p.1726-1738, December 2003 [doi>10.1287/mnsc.49.12.1726.25117]
• 20: Kay Chen Tan , Eik Fun Khor , Tong Heng Lee, Multiobjective Evolutionary Algorithms and Applications (Advanced Information and Knowledge Processing), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 21: K. C. Tan, T. H. Lee, and E. F. Khor. Evolutionary Algorithms with goal and priority information for multi-objective optimization. In Proceedings of the 1999 Congress on Evolutionary Computation (CEC99) pages 106--113, 1999.
• 22: L. Thiele, K. Miettinen, P. Korhonen, and J. Molina. A preference-based interactive evolutionary algorithm for multiobjective optimization. Helsinki School of Economics Technical Report Number W-412, Finland, 2007.
• 23: A. P. Wierzbicki. The use of reference objectives in multiobjective optimization. In G. Fandel and T. Gal, editors, Multiple Criteria Decision Making Theory and Applications pages 468--486. Berlin:Springer-Verlag, 1980.

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

Keywords:
EMO, MCDM, decision-making, engineering design, hybrid EMO, interactive EMO, multi-objective optimization, reference direction, reference point