Multiobjective Evolutionary Algorithms Are Still Good: Maximizing Monotone Approximately Submodular Minus Modular...

Area of Science:

• Optimization Algorithms
• Theoretical Computer Science
• Machine Learning Theory

Background:

• Evolutionary algorithms (EAs) are general optimization tools analyzed for various problem classes.
• The GSEMO algorithm shows promise for submodular optimization, achieving polynomial-time approximation guarantees.
• Previous research covered monotone and non-monotone submodular functions.

Purpose of the Study:

• Analyze the performance of the GSEMO algorithm for maximizing monotone approximately submodular minus modular functions (g-c) with a size constraint.
• Investigate the approximation guarantees of GSEMO for this non-monotone, non-submodular function class.
• Determine if modifications to the optimization approach can improve GSEMO's performance.

Main Methods:

• Theoretical analysis of the GSEMO algorithm's performance on the (g-c) objective function class.
• Proving approximation guarantees for optimizing the original (g-c) function and size simultaneously.
• Proving approximation guarantees for optimizing a distorted objective function and size simultaneously.

Main Results:

• GSEMO fails to achieve a good polynomial-time approximation guarantee when optimizing the original (g-c) function and size directly.
• GSEMO achieves the best-known polynomial-time approximation guarantee when optimizing a distorted objective function and size.
• Empirical validation on Bayesian experimental design and directed vertex cover demonstrates GSEMO's effectiveness.

Conclusions:

• Direct optimization of (g-c) functions with GSEMO does not yield strong theoretical guarantees.
• Optimizing a distorted objective function allows GSEMO to achieve state-of-the-art approximation guarantees for this problem class.
• The findings have implications for applying EAs to complex optimization problems in areas like experimental design.