Single-objective and multi-objective formulations of solution selection for hypervolume maximization

ABSTRACT

A new trend in evolutionary multi-objective optimization (EMO) is the handling of a multi-objective problem as an optimization problem of an indicator function. A number of approaches have been proposed under the name of indicator-based evolutionary algorithms (IBEAs). In IBEAs, the entire population usually corresponds to a solution of the indicator optimization problem. In this paper, we show how hypervolume maximization can be handled as single-objective and multi-objective problems by coding a set of solutions of the original multi-objective problem as an individual. Our single-objective formulation maximizes the hypervolume under constraint conditions on the number of nondominated solutions. On the other hand, our multi-objective formulation minimizes the number of non-dominated solutions while maximizing their Hypervolume.

REFERENCES

• 1: Anne Auger , Johannes Bader , Dimo Brockhoff , Eckart Zitzler, Theory of the hypervolume indicator: optimal μ-distributions and the choice of the reference point, Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms, January 09-11, 2009, Orlando, Florida, USA [doi>10.1145/1527125.1527138]
• 2: Beume, N., Naujoks, B., and Emmerich M. SMS-EMOA: multiobjective selection based on dominated hypervolume. European J. Operational Research 180, 3 (2007) 1653--1669.
• 3: Emmerich, M., Beume, N., and Naujoks, B. An EMO algorithm using the hypervolume measure as selection criterion. Proc. of EMO 2005, 62--76.
• 4: Ishibuchi, H., Tsukamoto, N., and Nojima, Y. Iterative approach to indicator-based multiobjective optimization. Proc. of CEC 2007, 3697--3704.
• 5: Wagner, T., Beume, N., and Naujoks, B. Pareto-, aggregation-, and indicator-based methods in many-objective optimization. Proc. of EMO 2007, 742--756.
• 6: Zhang, Q., and Li, H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Trans. on Evolutionary Computation 11, 6 (2007) 712--731.
• 7: Zitzler, E., and Künzli, S. Indicator-based selection in multiobjective search. Proc. of PPSN 2004, 832--842.

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:
evolutionary multi-objective optimization, indicator-based evolutionary algorithm, solution selection, solution set optimization