背包问题的分布估计算法

Solving knapsack problem by estimation of distribution algorithm

背包问题经常应用在资源约束条件下的资源分配中,并在组合数学、计算机科学、复杂性理论和密码学中也有应用。给出了常见的几种背包问题,将分布估计算法应用于背包问题。分布估计算法提供了一个新的进化模式,它从有前途的候选解建立概率模型来引导搜索过程。分析个体种群数量、选择比例对算法的影响。仿真结果表明:分布估计算法求解背包问题是可靠有效的;此方法具有较好的可扩展性,修改此算法可解决其他背包问题。

The knapsack problem often arises in resource allocation where there are financial constraints and is studied in fields such as combinatorial mathematics,computer science,complexity theory and cryptography.Several mathematical models of the knapsack problem were proposed and the estimation of distribution algorithms(EDAs) was applied to solve the knapsack problem.Estimation of distribution algorithms(EDAs) offers a novel evolutionary paradigm and makes use of a probabilistic model from the promising solutions to guide the search process.The influence of several parameter design strategies such as population and selection proportion was analyzed.It is concluded that the algorithm with a moderate population and a moderate selection proportion can efficiently find the converged solution among those algorithms.Simulation results show that the EDA is reliable and effective for solving the knapsack problem.This method has good scalability,and it can solve general knapsack problems.