Analysis of Quality Diversity Algorithms for the Knapsack Problem

• URL: http://arxiv.org/abs/2207.14037v1
• Date: Thu, 28 Jul 2022 12:15:33 GMT
• Title: Analysis of Quality Diversity Algorithms for the Knapsack Problem
• Authors: Adel Nikfarjam, Anh Viet Do, Frank Neumann
• Abstract summary: We apply the QD paradigm to simulate dynamic programming behaviours on knapsack problem. We show that they are able to compute an optimal solution within expected pseudo-polynomial time.
• Score: 14.12876643502492
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quality diversity (QD) algorithms have been shown to be very successful when dealing with problems in areas such as robotics, games and combinatorial optimization. They aim to maximize the quality of solutions for different regions of the so-called behavioural space of the underlying problem. In this paper, we apply the QD paradigm to simulate dynamic programming behaviours on knapsack problem, and provide a first runtime analysis of QD algorithms. We show that they are able to compute an optimal solution within expected pseudo-polynomial time, and reveal parameter settings that lead to a fully polynomial randomised approximation scheme (FPRAS). Our experimental investigations evaluate the different approaches on classical benchmark sets in terms of solutions constructed in the behavioural space as well as the runtime needed to obtain an optimal solution.

Related papers

• Analysis of the Non-variational Quantum Walk-based Optimisation Algorithm [0.0]
  This paper introduces in detail a non-variational quantum algorithm designed to solve a wide range of optimisation problems. The algorithm returns optimal and near-optimal solutions from repeated preparation and measurement of an amplified state.
  arXiv  Detail & Related papers  (2024-07-29T13:54:28Z)
• Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
  Quality-Diversity (QD) algorithms aim to find a set of high-performing, yet diverse solutions. This paper tries to shed some light on the optimization ability of QD algorithms via rigorous running time analysis.
  arXiv  Detail & Related papers  (2024-01-19T07:40:24Z)
• Don't Bet on Luck Alone: Enhancing Behavioral Reproducibility of Quality-Diversity Solutions in Uncertain Domains [2.639902239625779]
  We introduce Archive Reproducibility Improvement Algorithm (ARIA) ARIA is a plug-and-play approach that improves the quality of solutions present in an archive. We show that our algorithm enhances the quality and descriptor space coverage of any given archive by at least 50%.
  arXiv  Detail & Related papers  (2023-04-07T14:45:14Z)
• Doubly Stochastic Matrix Models for Estimation of Distribution Algorithms [2.28438857884398]
  We explore the use of Doubly Matrices (DSM) for matching and assignment nature permutation problems. Specifically, we adopt the framework of estimation of distribution algorithms and compare DSMs to some existing proposals for permutation problems. Preliminary experiments on instances of the quadratic assignment problem validate this line of research and show that DSMs may obtain very competitive results.
  arXiv  Detail & Related papers  (2023-04-05T14:36:48Z)
• Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
  We focus on optimisation programming (SP), Optimal Control (SOC) and Decision Processes (MDP) Recent progress in solving convex multistage Markov problems is based on cutting planes approximations of the cost-to-go functions of dynamic programming equations. Cutting plane type methods can handle multistage problems with a large number of stages, but a relatively smaller number of state (decision) variables.
  arXiv  Detail & Related papers  (2023-03-28T01:30:40Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  We propose to reformulate the result diversification problem as a bi-objective search problem, and solve it by a multi-objective evolutionary algorithm (EA) We theoretically prove that the GSEMO can achieve the optimal-time approximation ratio, $1/2$. When the objective function changes dynamically, the GSEMO can maintain this approximation ratio in running time, addressing the open question proposed by Borodin et al.
  arXiv  Detail & Related papers  (2021-10-18T14:00:22Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  Two-stage algorithmic optimization plays a critical role in various engineering and scientific applications. There still lack efficient algorithms, especially when the long-term and short-term variables are coupled in the constraints. We show that PDD-SSCA can achieve superior performance over existing solutions.
  arXiv  Detail & Related papers  (2021-05-05T03:36:00Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Single- and Multi-Objective Evolutionary Algorithms for the Knapsack Problem with Dynamically Changing Constraints [13.896724650508087]
  We investigate single- and multi-objective baseline evolutionary algorithms for the classical knapsack problem. Our results show that the multi-objective approaches using a population that caters for dynamic changes have a clear advantage on many benchmarks scenarios.
  arXiv  Detail & Related papers  (2020-04-27T03:50:24Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  We present a modified Cross-Entropy Method (CEM) that uses a masked auto-regressive neural network for modeling uniform distributions over the solution space. Our algorithm is able to express complicated solution spaces, thus allowing it to track a variety of different solution regions.
  arXiv  Detail & Related papers  (2020-02-17T20:21:20Z)

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.