On the Use of Bi-Objective Evolutionary Algorithms for the Stochastic MKP under Dynamic Constraints
For researchers in evolutionary computation and stochastic optimization, this paper provides a comparative analysis of MOEAs on a specific problem variant, but the results are incremental and lack concrete performance numbers.
This paper investigates a stochastic and dynamic variant of the multiple knapsack problem (MKP) with chance constraints, modeling item weights as independent normal random variables and knapsack capacities that change over time. It formulates the problem as a bi-objective optimization and empirically compares four multi-objective evolutionary algorithms, providing insights into their performance under varying uncertainty and dynamic settings.
The multiple knapsack problem (MKP) generalizes the classical knapsack problem by assigning items to multiple knapsacks subject to capacity constraints. It is used to model many real-world resource allocation and scheduling problems. In practice, these optimization problems often involve stochastic and dynamic components. Evolutionary algorithms provide a flexible framework for addressing such problems under uncertainty and dynamic changes. In this paper, we investigate a stochastic and dynamic variant of MKP with chance constraints, where the item weights are modeled as independent normally distributed random variables and knapsack capacities change during the optimization process. We formulate the problem as a bi-objective optimization formulation that balances profit maximization and probabilistic capacity satisfaction at a given confidence level. We conduct an empirical comparison of four widely used multi-objective evolutionary algorithms (MOEAs), representing both decomposition- and dominance-based search paradigms. The algorithms are evaluated under varying uncertainty levels, confidence thresholds, and dynamic change settings. The results provide comparative insights into the behavior of decomposition-based and dominance-based MOEAs for stochastic MKP under dynamic constraints.