Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms

Chao QIAN, Yang YU, Ke TANG, Xin YAO, Zhi-Hua ZHOU

Research output: Journal PublicationsJournal Article (refereed)peer-review

36 Citations (Scopus)

Abstract

Evolutionary algorithms (EAs) are a kind of nature-inspired general-purpose optimization algorithm, and have shown empirically good performance in solving various real-word optimization problems. During the past two decades, promising results on the running time analysis (one essential theoretical aspect) of EAs have been obtained, while most of them focused on isolated combinatorial optimization problems, which do not reflect the general-purpose nature of EAs. To provide a general theoretical explanation of the behavior of EAs, it is desirable to study their performance on general classes of combinatorial optimization problems. To the best of our knowledge, the only result towards this direction is the provably good approximation guarantees of EAs for the problem class of maximizing monotone submodular functions with matroid constraints. The aim of this work is to contribute to this line of research. Considering that many combinatorial optimization problems involve non-monotone or non-submodular objective functions, we study the general problem classes, maximizing submodular functions with/without a size constraint and maximizing monotone approximately submodular functions with a size constraint. We prove that a simple multi-objective EA called GSEMO-C can generally achieve good approximation guarantees in polynomial expected running time. © 2019
Original languageEnglish
Pages (from-to)279-294
Number of pages16
JournalArtificial Intelligence
Volume275
Early online date26 Jun 2019
DOIs
Publication statusPublished - Oct 2019
Externally publishedYes

Bibliographical note

The authors want to thank the associate editor and anonymous reviewers for their helpful comments and suggestions. C. Qian, Y. Yu and K. Tang were supported by the NSFC (61603367, 61672478, 61876077). X. Yao was supported by the Program for Guangdong Introducing Innovative and Enterpreneurial Teams (2017ZT07X386) and Shenzhen Peacock Plan (KQTD2016112514355531). Z.-H. Zhou was supported by the National Key R&D Program of China (2018YFB1004300) and Collaborative Innovation Center of Novel Software Technology and Industrialization.

Keywords

  • Computational complexity
  • Evolutionary algorithms
  • Multi-objective evolutionary algorithms
  • Running time analysis
  • Submodular optimization

Fingerprint

Dive into the research topics of 'Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms'. Together they form a unique fingerprint.

Cite this