  As evolutionary algorithms (EAs) are general-purpose optimization algorithms,
recent theoretical studies have tried to analyze their performance for solving
general problem classes, with the goal of providing a general theoretical
explanation of the behavior of EAs. Particularly, a simple multi-objective EA,
i.e., GSEMO, has been shown to be able to achieve good polynomial-time
approximation guarantees for submodular optimization, where the objective
function is only required to satisfy some properties but without explicit
formulation. Submodular optimization has wide applications in diverse areas,
and previous studies have considered the cases where the objective functions
are monotone submodular, monotone non-submodular, or non-monotone submodular.
To complement this line of research, this paper studies the problem class of
maximizing monotone approximately submodular minus modular functions (i.e.,
$f=g-c$) with a size constraint, where $g$ is a non-negative monotone
approximately submodular function and $c$ is a non-negative modular function,
resulting in the objective function $f$ being non-monotone non-submodular. We
prove that the GSEMO can achieve the best-known polynomial-time approximation
guarantee. Empirical studies on the applications of Bayesian experimental
design and directed vertex cover show the excellent performance of the GSEMO.
