Evolutionary Multi-Objective Algorithms for the Knapsack Problems with Stochastic Profits

• URL: http://arxiv.org/abs/2303.01695v1
• Date: Fri, 3 Mar 2023 03:28:51 GMT
• Title: Evolutionary Multi-Objective Algorithms for the Knapsack Problems with Stochastic Profits
• Authors: Kokila Perera and Aneta Neumann and Frank Neumann
• Abstract summary: We consider a version of the knapsack problem with profits to guarantee a certain level of confidence in the profit of an item. We introduce multi-objective formulations of the profit chance constrained knapsack problem and design three bi-objective fitness evaluation methods. We show the effectiveness of our approaches on several benchmarks for both settings.
• Score: 13.026567958569965
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Evolutionary multi-objective algorithms have been widely shown to be successful when utilized for a variety of stochastic combinatorial optimization problems. Chance constrained optimization plays an important role in complex real-world scenarios, as it allows decision makers to take into account the uncertainty of the environment. We consider a version of the knapsack problem with stochastic profits to guarantee a certain level of confidence in the profit of the solutions. We introduce the multi-objective formulations of the profit chance constrained knapsack problem and design three bi-objective fitness evaluation methods that work independently of the specific confidence level required. We evaluate our approaches using well-known multi-objective evolutionary algorithms GSEMO and NSGA-II. In addition, we introduce a filtering method for GSEMO that improves the quality of the final population by periodically removing certain solutions from the interim populations based on their confidence level. We show the effectiveness of our approaches on several benchmarks for both settings where the knapsack items have fixed uniform uncertainties and uncertainties that are positively correlated with the expected profit of an item.

Related papers

• Multi-Objective Evolutionary Algorithms with Sliding Window Selection for the Dynamic Chance-Constrained Knapsack Problem [2.5690340428649328]
  We propose multi-objective evolutionary approaches for the knapsack problem with profits under static and dynamic weight constraints. We consider a bi-objective formulation that maximises expected profit and minimises variance. We derive a three-objective formulation by relaxing the weight constraint into an additional objective.
  arXiv  Detail & Related papers  (2024-04-12T03:07:15Z)
• Using 3-Objective Evolutionary Algorithms for the Dynamic Chance Constrained Knapsack Problem [9.617143859697322]
  We explore the use of 3-objective evolutionary algorithms for the chance constrained knapsack problem with dynamic constraints. We introduce a 3-objective formulation that is able to deal with the dynamic components at the same time and is independent of the confidence level required for the constraint. Our analysis highlights the advantages of the 3-objective formulation over the 2-objective formulation in addressing the dynamic chance constrained knapsack problem.
  arXiv  Detail & Related papers  (2024-04-09T04:47:01Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
  arXiv  Detail & Related papers  (2023-11-08T00:10:21Z)
• Multi-Objective GFlowNets [59.16787189214784]
  We study the problem of generating diverse candidates in the context of Multi-Objective Optimization. In many applications of machine learning such as drug discovery and material design, the goal is to generate candidates which simultaneously optimize a set of potentially conflicting objectives. We propose Multi-Objective GFlowNets (MOGFNs), a novel method for generating diverse optimal solutions, based on GFlowNets.
  arXiv  Detail & Related papers  (2022-10-23T16:15:36Z)
• Evolutionary Algorithms for Limiting the Effect of Uncertainty for the Knapsack Problem with Stochastic Profits [14.352521012951865]
  We consider the knapsack problem where the profits involve uncertainties. We introduce different ways of dealing with profits based on tail inequalities that allow to limit the impact of uncertainties.
  arXiv  Detail & Related papers  (2022-04-12T07:56:50Z)
• Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables [13.264683014487376]
  We study the scenario of components that are independent and Normally distributed. We show that imposing an additional uniform constraint already leads to local optima. We prove that this approach can also be used to compute a set of optimal solutions for the chance constrained minimum spanning tree problem.
  arXiv  Detail & Related papers  (2021-09-13T09:24:23Z)
• Policy Gradient Bayesian Robust Optimization for Imitation Learning [49.881386773269746]
  We derive a novel policy gradient-style robust optimization approach, PG-BROIL, to balance expected performance and risk. Results suggest PG-BROIL can produce a family of behaviors ranging from risk-neutral to risk-averse.
  arXiv  Detail & Related papers  (2021-06-11T16:49:15Z)
• Near-Optimal High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity with bounds dependence on the confidence level that is either negative-power or logarithmic. We propose novel stepsize rules for two gradient methods with clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds Globally Optimal Policy [95.98698822755227]
  We make the first attempt to study risk-sensitive deep reinforcement learning under the average reward setting with the variance risk criteria. We propose an actor-critic algorithm that iteratively and efficiently updates the policy, the Lagrange multiplier, and the Fenchel dual variable.
  arXiv  Detail & Related papers  (2020-12-28T05:02:26Z)
• Robust, Accurate Stochastic Optimization for Variational Inference [68.83746081733464]
  We show that common optimization methods lead to poor variational approximations if the problem is moderately large. Motivated by these findings, we develop a more robust and accurate optimization framework by viewing the underlying algorithm as producing a Markov chain.
  arXiv  Detail & Related papers  (2020-09-01T19:12:11Z)
• Evolutionary Bi-objective Optimization for the Dynamic Chance-Constrained Knapsack Problem Based on Tail Bound Objectives [12.634782111072585]
  We consider the dynamic chance-constrained knapsack problem where the weight of each item is the subject of a capacity constraint. The objective is to maximize the total profit subject to the probability that total weight exceeds the capacity. We introduce an additional objective which estimates the minimal capacity bound for a given solution that still meets the chance constraint.
  arXiv  Detail & Related papers  (2020-02-17T04:36:15Z)

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.