Initial studies on the hybridization of particle swarm optimization-simulated annealing (PSO-SA) approach applied to the classical 0/1knapsack problem /
Dari Jayne Mingoy Espera.
- 2006
- 79 leaves.
Thesis (BS Computer Science) -- University of the Philippines Mindanao, 2006
The program developed verifies solutions to the results of the Knapsack Particle Swarm Optimization (KPSO) algorithm conducted by Grosan et. al. (2003). The program used to heuristic methods which are the Particle Swarm Optimization (PSO) and Simulated Annealing (SA) algorithm in validating solutions to known optimum solutions of the Classical 0/1 Knapsack Problem. Three knapsack sample test were considered in this study. It accepts an input file of the given knapsack parameters: number of items, knapsack capacity, weight list, profit list, optimal weight and optimal profit. The output of each run gives the decimal values and equivalent binary values that determine which item is included in to the knapsack. Moreover, the program also validates other knapsack problems provided that proper parameters are given. Additional feature of this program is it can specify parameters of both PSO and Sa algorithms without the need of recompiling the entire code. The program also generates other possible solutions to the Classical 0/1 Knapsack Problem since it deals with verifying the known optimum solutions. Numerical experiments show the effectiveness of this hybrid approach. This hybrid of meta-heuristic techniques can indeed be a powerful tool in the future to solve other optimization problems in the fast-changing world of applied mathematics and computer science. Scalability of the developed algorithms, however, needs to be verified for number of items larger than twenty (20)