Analysis of coevolution for worst-case optimization

ABSTRACT

The problem of finding entities with the best worst-case performance across multiple scenarios arises in domains ranging from job shop scheduling to designing physical artifacts. In spite of previous successful applications of evolutionary computation techniques, particularly coevolution, to such domains, little work has examined utilizing coevolution for optimizing worst-case behavior. Previous work assesses certain algorithm mechanisms using aggregate performance on test problems. We examine fitness and population trajectories of individual algorithm runs, making two observations: first, that aggregate plots wash out important effects that call into question what these algorithms can produce; and second, that none of the mechanisms is generally better than the rest. More importantly, our dynamics analysis explains how the interplay of algorithm properties and problem properties influences performance. These contributions argue in favor of a reassessment of what makes for a good worst-case coevolutionary algorithm and suggest how to design one.

REFERENCES

• 1: H. Barbosa. A coevolutionary genetic algorithm for constrained optimization. In CEC IEEE Press, 1999.
• 2: Jürgen Branke , Johanna Rosenbusch, New Approaches to Coevolutionary Worst-Case Optimization, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_15]
• 3: Sevan Gregory Ficici , Jordan B. Pollack, Solution concepts in coevolutionary algorithms, Brandeis University, Waltham, MA, 2004
• 4: J. W. Hermann. A genetic algorithm for minimax optimization problems. In CEC IEEE Press, 1999.
• 5: W. D. Hillis. Co-evolving parasites improve simulated evolution as an optimization Procedure. In Artificial Life II Addison-Wesley, 1992.
• 6: M. Jensen. Finding worst-case flexible schedules using coevolution. In GECCO Morgan Kaufmann, 2001.
• 7: Mikkel T. Jensen, A new look at solving minimax problems with coevolutionary genetic algorithms, Metaheuristics: computer decision-making, Kluwer Academic Publishers, Norwell, MA, 2004
• 8: Elena Popovici , Kenneth De Jong, Monotonicity versus performance in co-optimization, Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms, January 09-11, 2009, Orlando, Florida, USA [doi>10.1145/1527125.1527145]
• 9: Travis C. Service, Unbiased coevolutionary solution concepts, Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms, January 09-11, 2009, Orlando, Florida, USA [doi>10.1145/1527125.1527142]
• 10: D. Wolpert and W. Macready. Coevolutionary free lunches. IEEE Trans. on Evolutionary Computation 9(6):721--735, December 2005.

INDEX TERMS

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

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

General Terms:
Algorithms

Keywords:
best worst-case, coevolution, coevolutionary algorithms, dynamics analysis, minimax, worst-case optimization