Presentation Information
[N-1-03]Application of Set-Based Differential Evolution to Multidimensional Knapsack Problem
◎Yuto Kuninaga1, Michiharu Maeda1 (1. Graduate School of Engineering, Fukuoka Institute of Technology)
Keywords:
multidimensional knapsack problem,combinatorial optimization problem,metaheuristics,set-based differential evolution
Multidimensional knapsack problem (MKP) is a combinatorial optimization problem that aims to maximize profit under multiple constraints and is classified into an NP-hard problem. Therefore, many metaheuristic approaches have been proposed for solving large-scale instances. However, conventional methods may suffer from search stagnation and premature convergence to local optima. To address these issues, we propose a set-based differential evolution (SDE) approach for the MKP to improve search performance. In the proposed method, mutation is performed using difference information among individuals, and crossover operations are applied to the generated sets to explore the search space. Numerical experiments on several benchmark instances demonstrate that the proposed method outperforms conventional approaches, including DPSO, Ant Algorithm, and SCLPSO. We confirm the effectiveness of the proposed method.