Solving Multidimensional Knapsack Problem using an improved Reptile Search Algorithm

Abstract

The Multidimensional Knapsack Problem (MKP) is a well-known NP-hard combinatorial optimization problem with broad applications in management and engineering, including logistics, finance, and resource allocation. MKP involves selecting a subset of items to maximize total profit while respecting multiple resource constraints simultaneously. Traditional and nature-inspired metaheuristic algorithms have been widely used to tackle its computational complexity. This study proposes the integration of Z-shaped transfer functions into the binary Reptile Search Algorithm (RSA) to enhance its performance in solving MKP. Empirical evaluations conducted on five widely-used MKP benchmark datasets demonstrate that RSA with Z-shaped transfer functions competes favorably or surpasses other state-of-the-art transfer function variants in terms of solution quality and convergence. These results underscore the potential of Z-shaped transfer functions in improving binary metaheuristic algorithms for solving complex multidimensional combinatorial problems.