关键词: 0-1背包问题, NP-hard问题, 仿生算法, 元启发式算法, 生态平衡机制

Abstract: To extend the methods for solving the 0-1 knapsack problem, one of classical NP hard problems, simulating the natural mechanism of achieving dynamic equilibrium by interdependence and mutual restriction among species in an ecosystem, this paper puts forward a novel bionic algorithm: the interdependence balance algorithm. The algorithm describes the designed variables with the population size, uses the interdependence relationship as the optimization driving force, and aims to achieve a steady-state of a system. Self-growth functions, interdependence functions and growth functions are designed to describe the variation patterns of the designed variables and promote the optimization process of solutions. The results of the interdependence balance algorithm for solving 10 different scale 0-1 knapsack problems are compared with the literature data in recent years. Results show that the algorithm can obtain the currently known optimal solution in 8 different scale problems, which verifies the convergence and solution performance of the interdependence balance algorithm, and shows that the algorithm is effective and competitive for solving 0-1 knapsack problems.

Key words: 0-1 knapsack problem, NP-hard problem, bionic algorithms, metaheuristic algorithm, ecological balance mechanism