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

Chao QianEvol. Comput 2021 · OpenReview

TL;DR

This paper investigates whether multi-objective evolutionary algorithms (MOEAs), specifically the GSEMO, can effectively optimize functions that are a difference between a "nearly" submodular function and a modular function, a problem class that can be non-monotone and non-submodular. The authors demonstrate that by optimizing a "distorted" version of the objective function, GSEMO achieves a state-of-the-art approximation guarantee, outperforming greedy algorithms in practice. However, they also show that using the original objective function directly with GSEMO can lead to poor performance.

What Problem Does This Paper Address?

Evolutionary Algorithms (EAs) are powerful general-purpose optimization tools. Recent research has focused on understanding their theoretical performance for specific classes of problems, particularly those involving submodular functions. Submodular functions exhibit a "diminishing returns" property and have wide applications. While EAs have shown strong theoretical guarantees for maximizing monotone submodular functions, and even approximately submodular functions, a crucial question remains: can they maintain this performance when the objective function is a difference between a monotone approximately submodular function and a modular function? This difference can result in an objective that is neither monotone nor submodular, posing a significant challenge. This paper aims to bridge this gap by analyzing the performance of a simple MOEA, GSEMO, on this challenging problem class.

Methods

The core of this paper lies in analyzing the GSEMO algorithm's performance on the problem of maximizing $g(X) - c(X)$ subject to a size constraint $|X| \le k$, where $g$ is a monotone approximately submodular function and $c$ is a modular function.

  • Distorted Objective Function: The key innovation is the use of a "distorted" objective function: $f_1(x) = (1 - \gamma/k)^{k-|x|}g(x) - c(x) + (|x|/k)c(V)$. By simultaneously maximizing this distorted objective and minimizing the subset size $|x|$ (represented as $-|x|$), the GSEMO is shown to achieve a theoretical approximation guarantee of $(1 - e^{-\gamma}) \cdot g(X^*) - c(X^*)$, matching the best known guarantee from the distorted greedy algorithm.
  • GSEMO Algorithm: The paper utilizes the GSEMO (Generalized Single-Objective MOEA), a simple multi-objective evolutionary algorithm known for its theoretical analysis. It maintains a population of non-dominated solutions and iteratively improves them through bit-wise mutation.
  • Theoretical Analysis: The authors provide a rigorous theoretical analysis, including lemmas and theorems, to derive the expected running time of the GSEMO to reach the desired approximation guarantee. This analysis involves concepts like population size bounds and the probability of successful events that increase the objective value or the approximation guarantee.
  • GSEMO with Original Objective: To highlight the importance of the distorted objective, the paper also analyzes the GSEMO when directly optimizing the original objective function $g(X) - c(X)$. This analysis demonstrates that the GSEMO fails to achieve the desired approximation guarantee in polynomial time for this case.

Datasets

The paper uses two types of datasets for empirical evaluation:

  • Bayesian Experimental Design with Costs: Two datasets are used: "housing" (506 instances, 14 features) and "segment" (2,310 instances, 19 features). These datasets are used to generate problem instances with varying degrees of approximate submodularity by manipulating parameters like $\sigma$ and $\gamma$.
  • Directed Vertex Cover with Costs: Three benchmark graphs are used: "email-Eu-core" (1,005 vertices, 25,571 edges), "frb45-21-mis" (945 vertices, 59,186 edges), and "frb53-24-mis" (1,272 vertices, 94,227 edges). These datasets are used to evaluate the algorithms on a problem where the function $g$ is exactly submodular ($\gamma=1$).

Key Insights and Ideas

  • The Power of Distortion: The most significant insight is that by strategically "distorting" the objective function, a standard MOEA like GSEMO can achieve state-of-the-art approximation guarantees for a challenging problem class. This highlights the flexibility of MOEAs and the importance of problem reformulation.
  • GSEMO's Robustness: The GSEMO, by maintaining a population of non-dominated solutions, proves to be more robust than algorithms like NSGA-II in certain scenarios, especially when dealing with potentially dominated solutions in the population.
  • Direct Optimization is Risky: The theoretical and empirical results clearly show that directly optimizing the non-monotone, non-submodular objective $g(X) - c(X)$ with GSEMO can lead to poor performance and a failure to achieve the desired approximation guarantee, underscoring the necessity of the distorted objective.
  • Practical Efficiency: Despite theoretical worst-case running time bounds, the GSEMO demonstrates practical efficiency, often finding good solutions much faster than its theoretical limits suggest, especially when compared to greedy algorithms.

Key Results

  • Theoretical Guarantee: The GSEMO, when optimizing the distorted objective function, achieves an expected approximation guarantee of $(1 - e^{-\gamma}) \cdot g(X^*) - c(X^*)$ in $O(n^2(\log n + k))$ expected running time. This matches the best known guarantee from the distorted greedy algorithm.
  • Failure of Direct Optimization: The paper proves that using the original objective function $g(X) - c(X)$ with GSEMO does not guarantee the same approximation performance in polynomial time. This is supported by an example where it leads to exponential running time.
  • Empirical Performance:
    • On Bayesian experimental design and directed vertex cover problems, the GSEMO (with the distorted objective) consistently outperforms greedy algorithms (DG, SDG) and often performs better than or comparably to other MOEAs like NSGA-II.
  • The GSEMO using the original objective function ($GSEMO_{g-c}$) shows significantly worse performance in some cases, validating the theoretical findings.
  • The GSEMO demonstrates practical efficiency, achieving good objective values with a reasonable number of function evaluations.

Limitations and Future Work

  • Limitations:
    • The theoretical analysis for the GSEMO's running time is based on expected values and worst-case scenarios. While practical performance is good, there might be specific instances where it is less efficient.
  • The paper focuses on a specific MOEA (GSEMO). Further research could explore other advanced MOEAs and their performance on this problem class.
  • The submodularity ratio $\gamma$ is required for the theoretical analysis and for implementing the algorithms. In practice, estimating or bounding $\gamma$ can be challenging.
  • Future Work:
    • Investigate whether more advanced MOEAs can further improve performance, possibly by tuning their parameters.
  • Explore the performance of EAs on extensions of submodular optimization, such as problems involving multisets or sequences as solutions.
  • Study the behavior of EAs for submodular optimization under uncertain environments, such as dynamic constraints or noisy objective functions.

Summary updated

BibTeX
@inproceedings{qian2021multiobjective,
  author = {Chao Qian},
  title = {{Multiobjective Evolutionary Algorithms Are Still Good: Maximizing Monotone Approximately Submodular Minus Modular Functions}},
  booktitle = {Evol. Comput},
  year = {2021},
  url = {https://openreview.net/forum?id=5e_a-mTwGG},
}
Figure