Modified shuffled frog leaping algorithm with integer mutation applied to the bounded knapsack problem /
Ibañez, Princess Nelia Magdalena C.
Modified shuffled frog leaping algorithm with integer mutation applied to the bounded knapsack problem / Princess Nelia Magdalena C. Ibañez - 2010 - 86 leaves
Thesis (BS Computer Science) -- University of the Philippines Mindanao, 2010
The knapsack problem or rucksack problem is a problem in combinatorial optimization. It has been studied for centuries as it is the simplest prototype of a maximization problem. The term knapsack problem invokes of the backpacker who is constrained by a fixed-sized knapsack and so must fill it only with the most useful items. This study settled on solving the bounded knapsack problem (BKP) since only a few dedicated algorithms for BKP have been published. As reported in literatuire, hybrid methods have produced better results. Thus, evolutionary algorithms (EAs) called the shuffled frog leaping algorithm (SFLA) and integer mutation genetic algorithm (GA) were applied to the BKP. 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). The experimental results indicated that the MSFlA with integer mutation operation is a promising alternative to the OSFLA and MSFLA with one-point crossover operation in finding the global optimal solution. However, MSFLA with integer mutation failed to achieve optimal solution time. Moreover, other variations and modifications to the SFLA may be explored, and see if it produces better results than those achieved by this modified algorithm.
Bounded knapsack problem
Discrete optimization
Evolutionary algorithms
Genetic algorithm
Integer mutation
Shuffled frog leaping algorithm
Undergraduate Thesis --CMSC200,
Modified shuffled frog leaping algorithm with integer mutation applied to the bounded knapsack problem / Princess Nelia Magdalena C. Ibañez - 2010 - 86 leaves
Thesis (BS Computer Science) -- University of the Philippines Mindanao, 2010
The knapsack problem or rucksack problem is a problem in combinatorial optimization. It has been studied for centuries as it is the simplest prototype of a maximization problem. The term knapsack problem invokes of the backpacker who is constrained by a fixed-sized knapsack and so must fill it only with the most useful items. This study settled on solving the bounded knapsack problem (BKP) since only a few dedicated algorithms for BKP have been published. As reported in literatuire, hybrid methods have produced better results. Thus, evolutionary algorithms (EAs) called the shuffled frog leaping algorithm (SFLA) and integer mutation genetic algorithm (GA) were applied to the BKP. 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). The experimental results indicated that the MSFlA with integer mutation operation is a promising alternative to the OSFLA and MSFLA with one-point crossover operation in finding the global optimal solution. However, MSFLA with integer mutation failed to achieve optimal solution time. Moreover, other variations and modifications to the SFLA may be explored, and see if it produces better results than those achieved by this modified algorithm.
Bounded knapsack problem
Discrete optimization
Evolutionary algorithms
Genetic algorithm
Integer mutation
Shuffled frog leaping algorithm
Undergraduate Thesis --CMSC200,