Thesis (BS Computer Science) -- University of the Philippines Mindanao, 2008

The knapsack problem is one of the most studied problems in combinatorial optimization because analyzing this problem can help in solving other complex optimization problems. The knapsack problem entails forming a combination of items from a set that gives the maximum total profit without exceeding the weight capacity of the knapsack. This study settled on solving the bounded knapsack problem (BKP) since only a few dedicated algorithms for BKP have been published. In this study, an evolutionary algorithm (EA) called the shuffled frog leaping algorithm (SFLA) was applied to the BKP. The experimental results in terms of the probability of convergence to a global optimal solution and the speed of solution imply that the SFLA can be an efficient tool for solving combinatorial optimization problems comparable to a genetic algorithm. The test data used in this study were generated using the algorithm specified in the study of Pisinger (1994). Furthermore, the parameters used in this study were based on the study of Amiri et.al. (2005). This study also utilized a genetic algorithm operator called the single-point crossover operator. The original SFLA (OSFLA) and the modified SFLA (MSLFA) with crossover were the only main algorithm used. The evaluation of the efficiency of the SFLA variants was limited to the generated test data only. Generally, MSLFA provided more optimal results than OSFLA except for data sets with a data range of 10000 paired with problem types ss and sc. MSLFA also consistently performed significantly faster than OSFLA. Accordingly, MSFLA is a promising approach in solving the bounded knapsack problem if further improvements can be done