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

DOI10.1016/J.ARTINT.2019.06.005zbMATH Open1482.90187arXiv1711.07214OpenAlexW2954938754WikidataQ115462417 ScholiaQ115462417MaRDI QIDQ2321329FDOQ2321329

Authors: Chao Qian, Yang Yu, Ke Tang, Xin Yao, Zhi-Hua Zhou 

Publication date: 28 August 2019

Published in: Artificial Intelligence (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1711.07214

Recommendations

• Multi-objective evolutionary algorithms are generally good: maximizing monotone submodular functions over sequences
• Analysis of a simple evolutionary algorithm for the multiobjective shortest path problem
• On the approximation ability of evolutionary optimization with application to minimum set cover
• Fast algorithms for maximizing monotone nonsubmodular functions
• Evolutionary algorithms and matroid optimization problems

zbMATH Keywords

computational complexityevolutionary algorithmsmulti-objective evolutionary algorithmsrunning time analysissubmodular optimization

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Combinatorial optimization (90C27)

Cites Work

• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Applied multivariate statistical analysis.
• Determinantal point processes for machine learning
• Title not available (Why is that?)
• Some optimal inapproximability results
• Title not available (Why is that?)
• STACS 2005
• An analysis of approximations for maximizing submodular set functions—I
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Non-monotone submodular maximization under matroid and knapsack constraints
• Drift analysis and average time complexity of evolutionary algorithms
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Computing minimum cuts by randomized search heuristics
• Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
• Maximizing Non-monotone Submodular Functions
• Minimum spanning trees made easier via multi-objective optimization
• An 0. 828-approximation algorithm for the uncapacitated facility location problem
• On the analysis of the \((1+1)\) evolutionary algorithm
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem
• An analysis on recombination in multi-objective evolutionary optimization
• Evolutionary algorithms and matroid optimization problems
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• Submodular maximization with cardinality constraints
• Evolutionary learning: advances in theories and algorithms
• Restricted strong convexity implies weak submodularity

Cited In (5)

• Pareto optimization for subset selection with dynamic cost constraints
• Result diversification by multi-objective evolutionary algorithms with theoretical guarantees
• Mathematical runtime analysis for the non-dominated sorting genetic algorithm II (NSGA-II)
• Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations
• Multi-objective evolutionary algorithms are generally good: maximizing monotone submodular functions over sequences

This page was built for publication: Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2321329)