A new hybrid combinatorial genetic algorithm for multidimensional knapsack problems |
| |
Authors: | Guoming Lai Dehui Yuan Shenyun Yang |
| |
Affiliation: | 1. Computer Engineering Technical College, Guangdong Institute of Science and Technology, Zhuhai, ?519090, China 2. Department of Mathematics, Hanshan Normal University, Chaozhou?, 521041, Guangdong, China 3. Department of Computer Science and Engineering, Hanshan Normal University, Chaozhou, ?521041, China
|
| |
Abstract: | 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-lambda ) u_j+ lambda x^mathrm{LP}_j) of both the pseudo-utility ratios of MKP and the optimal solution (x^mathrm{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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|