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

Qian, Chao1; Yu, Yang1; Tang, Ke2; Yao, Xin2; Zhou, Zhi-Hua1

2019-10

10.1016/j.artint.2019.06.005

ARTIFICIAL INTELLIGENCE   影响因子和分区

0004-3702

1872-7921

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. (C) 2019 Elsevier B.V. All rights reserved.

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

SCI ; EI

英语

其他

National Key R&D Program of China[2018YFB1004300]

Computer Science

Computer Science, Artificial Intelligence

WOS:000485208100011

ELSEVIER

20192607112508

Combinatorial optimization ; Computational complexity ; Optimization ; Polynomial approximation

Computer Theory, Includes Formal Logic, Automata Theory, Switching Theory, Programming Theory:721.1 ; Optimization Techniques:921.5 ; Numerical Methods:921.6

COMPUTER SCIENCE

Web of Science

1.Nanjing Univ, Natl Key Lab Novel Software Technol, Nanjing 210023, Jiangsu, Peoples R China
2.Southern Univ Sci & Technol, Shenzhen Key Lab Computat Intelligence, Dept Comp Sci & Engn, Shenzhen 518055, Peoples R China

Qian, Chao,Yu, Yang,Tang, Ke,et al. Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms[J]. ARTIFICIAL INTELLIGENCE,2019,275:279-294.

Qian, Chao,Yu, Yang,Tang, Ke,Yao, Xin,&Zhou, Zhi-Hua.(2019).Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms.ARTIFICIAL INTELLIGENCE,275,279-294.

Qian, Chao,et al."Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms".ARTIFICIAL INTELLIGENCE 275(2019):279-294.