求解0-1背包问题的牵制平衡算法

An Interdependence Balance Algorithm for Solving 0-1 Knapsack Problems

为扩充对于经典NP-hard问题中的0-1背包问题的求解方法,模拟生态系统中各物种间相互依存、牵制,最终达到动态平衡的自然机制,提出一种新型仿生算法:牵制平衡算法。算法以种群规模描述设计变量,以牵制关系为优化驱动力,以系统达到稳态为优化目标,设计了自成长函数、牵制函数、成长函数用以描述设计变量的变化规律,促进解的寻优进程。将牵制平衡算法对于10个不同规模0-1背包问题的求解结果与近年来文献数据进行对比,结果显示算法在8个不同规模的问题中能获得当前已知最优解,验证了牵制平衡算法的收敛性与求解性能,表明算法对于0-1背包问题的求解具有有效性和竞争力。

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.