International Journal of

Soft Computing and Software Engineering [JSCSE]

ISSN: 2251-7545

Prefix DOI : 10.7321/jscse

URL: http://JSCSE.com

A Peer-Reviewed Journal

The International Journal of

Soft Computing and Software Engineering [JSCSE]

UserName:

Password:

Publication Year:

[ 2011 ] [ 2012 ] [ 2013 ] [ 2014 ] [ 2015 ] [ 2016 ] [ 2017 ]

[Vol. 4, No.1, Jan] [Vol. 4, No.2, Feb] [Vol. 4, No.3, Mar] [Vol. 4, No.4, Apr] [Vol. 4, No.5, May] [Vol. 4, No.6, Jun] [Vol. 4, No.7, Jul] [Vol. 4, No.8, Aug] [Vol. 4, No.12, Dec]

Advance Search
Table of Contents [Vol. 4, No.5, May]

An Estimation of Distribution Algorithm for solving the Knapsack problem

Ricardo Pérez, S. Jöns, Arturo Hernández, Carlos A. Ochoa
Doi : 10.7321/jscse.v4.n5.1
Page : 78 - 84

Show Summary

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.
Keyword : Estimation of Distribution Algorithm ; Knapsack problem ; genetic algorithm ; greedy algorithm