A new hybrid combinatorial genetic algorithm for multidimensional knapsack problems

摘要

Multidimensional knapsack problem (MKP) is known to be a NP-hard problem, more specifically a NP-complete problem, which cannot be resolved in polynomial time up to now. MKP can be applicable in many management, industry and engineering fields, such as cargo loading, capital budgeting and resource allocation, etc. In this article, using a combinational permutation constructed by the convex combinatorial value M_j = (1 - λ)u_j + λ_j~(LP) of both the pseudo-utility ratios of MKP and the optimal solution x~(LP) of relaxed LP, we present a new hybrid combinatorial genetic algorithm (HCGA) to address multidimensional knapsack problems. Comparing to Chu's GA (J Heuristics 4:63-86, 1998), empirical results show that our new heuristic algorithm HCGA obtains better solutions over 270 standard test problem instances.