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

The classical 0/1 Knapsack Problem is a well-known optimization problem occurring in many real-world problems and is considered to be nonpolynomial-hand (NP-hard) by mathematicians. Different knapsack algorithms have already been studied and used to solve for the optimal solution in the knapsack problem with great considerations to its performance in terms of running time and quality of the optimal solution returned by the algorithm. Because of this, a recent breed of algorithms, called heuristic methods, is popularly used in knapsack optimization problems because of its good performance in yielding good results and the Particle Swarm Optimization (PSO) is one of these. The PSO algorithm is a population-based stochastic search technique that is modelled after the social behavior of a bird flock and fish school. Recent mathematical researches have embarked on the use of PSO in solving for the Classical 0/1 Knapsack Problem. The results of these studies showed that the Knapsack Particle Swarm Optimization (KPSO) algorithm is good in solving for the optimal solution in three benchmark sample knapsack problems. Local hill climbing techniques such as Tabu Search (TS) is also popular in solving various optimization problems. The TS method has already been studied and used in solving the Classical 0/1 Knapsack Problem and has been shown that the TS method is a promising algorithm to find the optimal (or near optimal) solution in a knapsack problem. This research study has made us of the successes of the PSO and TS algorithms and has combined both algorithms to solve for the optimum in the Classical 0/1 Knapsack Problem using three benchmark sample knapsack problems. The results of the research showed that the PSO-TS hybrid algorithm has the capacity to return more optimal hits to the known knapsack optimal solution than the pure PSO algorithm alone. Thus, this study has shown that the PSO-TS hybrid algorithm performs better in finding the optimal solution to the three benchmark knapsack sample problems compared to the pure PSO algorithm