The First Proven Performance Guarantees for the Non-Dominated Sorting
Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem
- URL: http://arxiv.org/abs/2305.13459v2
- Date: Fri, 9 Jun 2023 11:00:15 GMT
- Title: The First Proven Performance Guarantees for the Non-Dominated Sorting
Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem
- Authors: Sacha Cerf, Benjamin Doerr, Benjamin Hebras, Yakob Kahane, Simon
Wietheger
- Abstract summary: The Non-dominated Sorting Genetic Algorithm-II (NSGA-II) is one of the most prominent algorithms to solve multi-objective optimization problems.
We give the first proven performance guarantees for a classic optimization problem, the NP-complete bi-objective minimum spanning tree problem.
- Score: 6.793248433673384
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Non-dominated Sorting Genetic Algorithm-II (NSGA-II) is one of the most
prominent algorithms to solve multi-objective optimization problems. Recently,
the first mathematical runtime guarantees have been obtained for this
algorithm, however only for synthetic benchmark problems.
In this work, we give the first proven performance guarantees for a classic
optimization problem, the NP-complete bi-objective minimum spanning tree
problem. More specifically, we show that the NSGA-II with population size $N
\ge 4((n-1) w_{\max} + 1)$ computes all extremal points of the Pareto front in
an expected number of $O(m^2 n w_{\max} \log(n w_{\max}))$ iterations, where
$n$ is the number of vertices, $m$ the number of edges, and $w_{\max}$ is the
maximum edge weight in the problem instance. This result confirms, via
mathematical means, the good performance of the NSGA-II observed empirically.
It also shows that mathematical analyses of this algorithm are not only
possible for synthetic benchmark problems, but also for more complex
combinatorial optimization problems.
As a side result, we also obtain a new analysis of the performance of the
global SEMO algorithm on the bi-objective minimum spanning tree problem, which
improves the previous best result by a factor of $|F|$, the number of extremal
points of the Pareto front, a set that can be as large as $n w_{\max}$. The
main reason for this improvement is our observation that both multi-objective
evolutionary algorithms find the different extremal points in parallel rather
than sequentially, as assumed in the previous proofs.
Related papers
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - Theoretical Advantage of Multiobjective Evolutionary Algorithms for Problems with Different Degrees of Conflict [4.8951183832371]
OneMaxMin$_k$ benchmark class is a generalized variant of COCZ and OneMinMax.
Two typical non-MOEA approaches, scalarization (weighted-sum approach) and $epsilon$-constraint approach, are considered.
We prove that (G)SEMO, MOEA/D, NSGA-II, and SMS-EMOA can cover the full Pareto front in $O(maxk,1nln n)$ expected number of function evaluations.
arXiv Detail & Related papers (2024-08-08T04:09:52Z) - Analyzing the Runtime of the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) on the Concatenated Trap Function [2.038038953957366]
GOMEA is an evolutionary algorithm that leverages linkage learning to efficiently exploit problem structure.
We show that GOMEA can solve the problem in $O(m32k)$ with high probability, where $m$ is the number of subfunctions and $k$ is the subfunction length.
This is a significant speedup compared to the (1+1) Evolutionary EA, which requires $O(ln(m)(mk)k)$ expected evaluations.
arXiv Detail & Related papers (2024-07-11T09:37:21Z) - An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
We study the complexity of producing neither smooth nor convex points of Lipschitz objectives which are possibly using only zero-order evaluations.
Our analysis is based on a simple yet powerful.
Goldstein-subdifferential set, which allows recent advancements in.
nonsmooth non optimization.
arXiv Detail & Related papers (2023-07-10T11:56:04Z) - A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic
Composite Optimization [10.762749887051546]
We propose two-time scale algorithms: ProxDAS-A and Proxcal$DASA-GT.
Unlike prior work, our algorithms achieve comparable complexity without requiring large batch sizes, more complex per-it operations, or stronger assumptions.
arXiv Detail & Related papers (2023-02-20T05:16:18Z) - Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel [17.462968952951883]
Main algorithm is assembled from two components which may be of independent interest.
A variant of LINEARSEQ is shown to have adaptive complexity of $O(log(n))$ smaller than that of any previous algorithm in the literature.
arXiv Detail & Related papers (2021-11-15T17:10:40Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
Bilevel optimization has been widely applied in many important machine learning applications.
We propose two new algorithms for bilevel optimization.
We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
arXiv Detail & Related papers (2021-06-08T21:05:30Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
The current practical BO algorithms have regret bounds ranging from $mathcalO(fraclogNsqrtN)$ to $mathcal O(e-sqrtN)$, where $N$ is the number of evaluations.
This paper explores the possibility of improving the regret bound in the noiseless setting by intertwining concepts from BO and tree-based optimistic optimisation.
We propose the BOO algorithm, a first practical approach which can achieve an exponential regret bound with order $mathcal O(N-sqrt
arXiv Detail & Related papers (2021-05-10T13:07:44Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
Motivated by recent increased interest in analysis of optimization algorithms for non- optimization in deep networks and other problems in data, we give an overview of recent results of theoretical optimization algorithms for non- optimization.
arXiv Detail & Related papers (2020-12-11T08:28:51Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
Bilevel optimization is a class of problems which exhibit a two-level structure.
We propose a two-timescale approximation (TTSA) algorithm for tackling such a bilevel problem.
We show that a two-timescale natural actor-critic policy optimization algorithm can be viewed as a special case of our TTSA framework.
arXiv Detail & Related papers (2020-07-10T05:20:02Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers.
We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
arXiv Detail & Related papers (2020-02-26T16:19:09Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.