Full-Text Download    
Subscribe Now
Recommend the Paper
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  
 
 

Subscribe Now

Email :    
Subscribe to receive free TOC's JSCSE by email
Subscribe

Recommend To Friend

Email :     People