|
An Estimation of Distribution Algorithm for solving the Knapsack problem
|
|
1Ricardo Pérez, 2S. Jöns, 3Arturo Hernández, 4Carlos A. Ochoa
*1, PICYT-CIATEC A.C., León City, México
2, CONACYT, México City, México
3CIMAT A.C., Guanajuato City, México
4UACJ, Ciudad Juárez City, México
Email: 1rperez.picyt@ciatec.mx, 2jons_sanchez@hotmail.com, 3artha@cimat.mx, 4alberto.ochoa@uacj.mx
|
|
|
|
Abstract
.The knapsack problem, a NP-hard problem, has been solved by different ways during many years. However, its combinatorial nature is still interesting for many academics. In this paper, an Estimation of Distribution Algorithm is applied for solving the Knapsack problem. KEDA for simplicity is called. It contains a probabilistic model of type chain for sampling new offsprings to solve the problem. In addition, we use a Greedy Algorithm and a Genetic Algorithm to compare the performance of the KEDA algorithm. According to the experiments, the genetic algorithm and the KEDA provide good solutions, but the performance from this evolutionary algorithm was able to give better results.
|
|
|
|
Keywords
:
Estimation of Distribution Algorithm ; Knapsack problem ; genetic algorithm ; greedy algorithm
|
|
|
|
URL: http://dx.doi.org/10.7321/jscse.v4.n5.1
|
|
|
|
|