A new hybrid combinatorial genetic algorithm for multidimensional knapsack problems

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