Solving knapsack problem by estimation of distribution algorithm
Shang Gao · Journal of Central South University(Science and Technology) · 2013
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.