Hyper-Construction: Evolving Evaluation Networks to Regulate Constructive Heuristics for 0-1 Knapsack Problem [Research Frontier]

In combinatorial optimization problems (COPs), a solution is an arrangement of the elements (solution components) following a specific representation (e.g., array, tree, and graph). Therefore, progressively assembling the solution components according to their importance provides a new constructive paradigm for achieving the optimal solution. Taking the classic 0-1 knapsack problem (0-1 KP) as an example, this paper proposes a hyper-construction framework, which employs a lightweight radial basis function network as the high-level evaluation model for evaluating the importance of items to regulate the low-level construction process. For implementation, an evolutionary hyper-construction heuristic is designed, integrating an advanced variant of differential evolution algorithm to optimize the network parameters on the basis of the feedback from the 0-1 KP objective value. This method presents a novel optimization approach to solving COPs, which not only significantly reduces the dimensionality of the search space but also effectively uses the constructive knowledge contained in the constraints. Comparative computational experiments via 63 benchmark 0-1 KP instances confirm that the proposed method outperforms various state-of-the-art KP algorithms in terms of accuracy and robustness.