Multi-objective evolutionary algorithms are generally good: Maximizing monotone submodular functions over sequences

Qian, Chao1; Liu, Dan-Xuan1; Feng, Chao2; Tang, Ke3

2023-01-17

10.1016/j.tcs.2022.12.011

THEORETICAL COMPUTER SCIENCE   Impact Factor & Quartile

0304-3975

1879-2294

Evolutionary algorithms (EAs) are general-purpose optimization algorithms, inspired by natural evolution. Recent theoretical studies have shown that EAs can achieve good approximation guarantees for solving the problem classes of submodular optimization, which have a wide range of applications, such as maximum coverage, sparse regression, influence maximization, document summarization and sensor placement, just to name a few. Though they have provided some theoretical explanation for the general-purpose nature of EAs, the considered submodular objective functions are defined only over sets or multisets. To complement this line of research, this paper studies the problem class of maximizing monotone submodular functions over sequences, where the objective function depends on the order of items. We prove that for each kind of previously studied monotone submodular objective functions over sequences, i.e., prefix monotone submodular functions, weakly monotone and strongly submodular functions, and DAG monotone submodular functions, a simple multi-objective EA, i.e., GSEMO, can always reach or improve the best known approximation guarantee after running polynomial time in expectation. Note that these best-known approximation guarantees can be obtained only by different greedy-style algorithms before. Empirical studies on various applications, e.g., accomplishing tasks, maximizing information gain, search-and-tracking and recommender systems, show the excellent performance of the GSEMO.(c) 2022 Elsevier B.V. All rights reserved.

Evolutionary algorithms Multi-objective evolutionary algorithms Submodular optimization Sequences Computational complexity Approximation ratio Experimental studies

SCI

English

Corresponding

National Science Foundation of China["62022039","62276124","61921006"] ; Shenzhen Peacock Plan[KQTD2016112514355531]

Computer Science

Computer Science, Theory & Methods

WOS:000913673300001

ELSEVIER

COMPUTER SCIENCE

Web of Science

1.Nanjing Univ, State Key Lab Novel Software Technol, Nanjing 210023, Peoples R China
2.Univ Sci & Technol China, Sch Comp Sci & Technol, Hefei 230027, Peoples R China
3.Southern Univ Sci & Technol, Dept Comp Sci & Engn, Shenzhen Key Lab Computat Intelligence, Shenzhen 518055, Peoples R China

Qian, Chao,Liu, Dan-Xuan,Feng, Chao,et al. Multi-objective evolutionary algorithms are generally good: Maximizing monotone submodular functions over sequences[J]. THEORETICAL COMPUTER SCIENCE,2023,943.

Qian, Chao,Liu, Dan-Xuan,Feng, Chao,&Tang, Ke.(2023).Multi-objective evolutionary algorithms are generally good: Maximizing monotone submodular functions over sequences.THEORETICAL COMPUTER SCIENCE,943.

Qian, Chao,et al."Multi-objective evolutionary algorithms are generally good: Maximizing monotone submodular functions over sequences".THEORETICAL COMPUTER SCIENCE 943(2023).