一种结合贪婪因子求解0-1背包问题的分布估计算法

An Estimation of Distribution Algorithm Solving the 0-1 Knapsack Problem with Greed Factors

针对0-1背包问题,在分布估计算法的基础上提出了一种结合传统贪婪方法的新算法。通过计算物品的重量价值比后获得物品的贪婪因子值,并将贪婪因子融入基本的分布估计算法之中,在保证收敛速度的基础上进一步平衡了个体间的竞争,相较对比算法而言取得了更好的优化结果。

Aiming at the 0-1 knapsack problem, this paper proposes a new algorithm combined with traditional greedy approach based on estimation of distribution algorithm. It obtains the greedy factor values of the goods by calculating the weight-to-value ratio. It also integrates the greedy factor into the basic estimation of distribution algorithm. While ensuring the rate of convergence, it keeps the competition between individuals in balance, making better optimization results compared with the comparison algorithm.