Optimising Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-objective Algorithms

被引：33
作者：
Neumann, Aneta [1 ]
Neumann, Frank [1 ]
机构：
[1] Univ Adelaide, Sch Comp Sci, Optimisat & Logist, Adelaide, SA, Australia
来源：
PARALLEL PROBLEM SOLVING FROM NATURE - PPSN XVI, PT I | 2020年 / 12269卷
基金：
澳大利亚研究理事会;
关键词：
OPTIMIZATION;
D O I：
10.1007/978-3-030-58112-1_28
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
Many real-world optimisation problems can be stated in terms of submodular functions. A lot of evolutionary multi-objective algorithms have recently been analyzed and applied to submodular problems with different types of constraints. We present a first runtime analysis of evolutionary multi-objective algorithms for chance-constrained submodular functions. Here, the constraint involves stochastic components and the constraint can only be violated with a small probability of a. We show that the GSEMO algorithm obtains the same worst case performance guarantees as recently analyzed greedy algorithms. Furthermore, we investigate the behavior of evolutionary multi-objective algorithms such as GSEMO and NSGA-II on different submodular chance constrained network problems. Our experimental results show that this leads to significant performance improvements compared to the greedy algorithm.
引用
收藏
页码：404 / 417
页数：14
相关论文
共 36 条
[31]  
Roostapour V, 2019, AAAI CONF ARTIF INTE, P2354
[32]  
Vondrak J., 2010, Research Institute for Mathematical Sciences Kyoto University, V23, P253
[33]  
Xie Y, 2020, Arxiv, DOI arXiv:2004.03205
[34]   Evolutionary Algorithms for the Chance-Constrained Knapsack Problem [J].
Xie, Yue ;
Harper, Oscar ;
Assimi, Hirad ;
Neumann, Aneta ;
Neumann, Frank .
PROCEEDINGS OF THE 2019 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'19), 2019, :338-346
[35]  
Zhang HF, 2016, AAAI CONF ARTIF INTE, P819
[36]  
Zhou Z., 2019, Evolutionary Learning: Advances in Theories and Algorithms, DOI DOI 10.1007/978-981-13-5956-9
1234