On the effect of populations in evolutionary multi-objective optimization

ABSTRACT

Multi-objective evolutionary algorithms (MOEAs) have become increasingly popular as multi-objective problem solving techniques. An important open problem is to understand the role of populations in MOEAs. We present a simple bi-objective problem which emphasizes when populations are needed. Rigorous runtime analysis point out an exponential runtime gap between the population-based algorithm Simple Evolutionary Multi-objective Optimizer (SEMO) and several single individual-based algorithms on this problem. This means that among the algorithms considered, only the population-based MOEA is successful and all other algorithms fail.

REFERENCES

• 1: K. L. Chung. Elementary Probability Theory with Stochastic Processes. Springer, 1974.
• 2: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 3: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 4: Stefan Droste , Thomas Jansen , Ingo Wegener, On the analysis of the (1+ 1) evolutionary algorithm, Theoretical Computer Science, v.276 n.1-2, p.51-81, April 6, 2002 [doi>10.1016/S0304-3975(01)00182-7 ]
• 5: W. Feller. An Introduction to Probability Theory and Its Applications, volume 1. Wiley, 1968.
• 6: O. Giel. Expected runtimes of a simple multi-objective evolutionary algorithm. In Proc. of the 2003 Congress on Evolutionary Computation (CEC '03), volume 3, pages 1918--1925. IEEE, 2003.
• 7: B. Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied Probability, 14:502--525, 1982.
• 8: Drift analysis and average time complexity of evolutionary algorithms, Artificial Intelligence, v.127 n.1, p.57-85, March 2001 [doi>10.1016/S0004-3702(01)00058-3 ]
• 9: M. Laumanns, L. Thiele, and E. Zitzler. Running time analysis of multiobjective evolutionary algorithms on pseudo-boolean functions. IEEE Transactions on Evolutionary Computation, 8(2):170--182, 2004.
• 10: F. Neumann. Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem. In Proc. of the 8th Conference on Parallel Problem Solving from Nature (PPSN '04), volume 3242 of LNCS, pages 80--89. Springer, 2004.
• 11: T. Storch. On the choice of the population size. In Proc. of the Genetic and Evolutionary Computation Conference (GECCO '04), volume 3102 of LNCS, pages 748--760. Springer, 2004.
• 12: C. Witt. Population size vs. runtime of a simple EA. In Proc. of the 2003 Congress on Evolutionary Computation (CEC '03), volume 3, pages 1996--2003. IEEE Press, 2003.
• 13: C. Witt. An analysis of the (μ+1) EA on simple pseudo-boolean functions. In Proc. of the Genetic and Evolutionary Computation Conference (GECCO '04), volume 3102 of LNCS, pages 761--773. Springer, 2004.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory

Keywords:
evolutionary algorithms, multi-objective optimization, runtime analysis