Computing finite size representations of the set of approximate solutions of an MOP with stochastic search algorithms

ABSTRACT

In this work we study the convergence of generic stochastic search algorithms toward the entire set of approximate solutions of continuous multi-objective optimization problems. Since the dimension of the set of interest is typically equal to the dimension of the parameter space, we focus on obtaining a finite and tight approximation, measured by the Hausdorff distance. Under mild assumptions about the process to generate new candidate solutions, the limit approximation set will be determined entirely by the archiving strategy. We propose and investigate a novel archiving strategy theoretically and empirically. For this, we analyze the convergence behavior of the algorithm, yielding bounds on the obtained approximation quality as well as on the cardinality of the resulting approximation, and present some numerical results.

REFERENCES

• 1: Rafael Blanquero , Emilio Carrizosa, A D.C. biobjective location model, Journal of Global Optimization, v.23 n.2, p.139-154, June 2002 [doi>10.1023/A:1015579208736]
• 2: Kalyanmoy Deb , Manikanth Mohan , Shikhar Mishra, Evaluating the ε-Domination Based Multi-Objective Evolutionary Algorithm for a Quick Computation of Pareto-Optimal Solutions, Evolutionary Computation, v.13 n.4, p.501-525, December 2005 [doi>10.1162/106365605774666895]
• 3: A. Engau and M. M. Wiecek. Generating epsilon-efficient solutions in multiobjective programming. European Journal of Operational Research, 177(3):1566--1579, 2007.
• 4: J. D. Knowles and D. W. Corne. Metaheuristics for Multiobjective Optimisation, volume 535 of Lecture Notes in Economics and Mathematical Systems, chapter Bounded Pareto Archiving: Theory and Practice, pages 39--64. Springer, 2004.
• 5: 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]
• 6: P. Loridan. ε-solutions in vector minimization problems. Journal of Optimization, Theory and Application, 42:265--276, 1984.
• 7: Günter Rudolph and Alexandru Agapie. Convergence Properties of Some Multi-Objective Evolutionary Algorithms. In Proceedings of the 2000 Conference on Evolutionary Computation, volume 2, pages 1010--1016, Piscataway, New Jersey, July 2000. IEEE Press.
• 8: G. Ruhe , Bernd Fruhwirth, &egr;-optimality for bicriteria programs and its application to minimum cost flows, Computing, v.44 n.1, p.21-34, March 1990 [doi>10.1007/BF02247962]
• 9: S. Schäffler , R. Schultz , K. Weinzierl, Stochastic method for the solution of unconstrained vector optimization problems, Journal of Optimization Theory and Applications, v.114 n.1, p.209-222, July 2002 [doi>10.1023/A:1015472306888]
• 10: O. Schütze, C. A. Coello Coello, and E.-G. Talbi. Approximating the ε-efficient set of an MOP with stochastic search algorithms. In A. Gelbukh and A. F. Kuri Morales, editors, Mexican International Conference on Artificial Intelligence (MICAI-2007), pages 128--138. Springer-Verlag Berlin Heidelberg, 2007.
• 11: O. Schütze, M. Laumanns, C. A. Coello Coello, M. Dellnitz, and E.-G. Talbi. Convergence of stochastic search algorithms to finite size Pareto set approximations. To appear in Journal of Global Optimization, 2007.
• 12: W. Stadler and J. Dauer. Multicriteria optimization in engineering: A tutorial and survey. In M. P. Kamat, editor, Structural Optimization: Status and Future, pages 209--249. American Institute of Aeronautics and Astronautics, 1992.
• 13: M. Tanaka. GA-based decision support system for multi-criteria optimization. In Proceedings of International Conference on Systems, Man and Cybernetics, pages 1556--1561, 1995.
• 14: E. Tantar, O. Schütze, J. R. Figueira, C. A. Coello Coello, and E.-G. Talbi. Computing and selecting ε-efficient solutions of {0,1}-knapsack problems. To appear in Proceedings of the 19th International Conference on Multiple Criteria Decision Making (MCDM-2008), 2008.
• 15: D J White, Epsilon efficiency, Journal of Optimization Theory and Applications, v.49 n.2, p.319-337, May 1986 [doi>10.1007/BF00940762]
• 16: D. J. White. Epsilon-dominating solutions in mean-variance portfolio analysis. European Journal of Operational Research, 105(3):457--466, 1998.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

General Terms:
Algorithms, Design, Performance

Keywords:
approximate solution, convergence, multi-objective optimization, pareto set, stochastic search algorithms