Abstract
A 0-1 multidimensional knapsack problem (MKP) aims to choose a set of items satisfied the m knapsack capacity conditions into the bag from a given group of n items with weights and prices such that the total prices in the bag is maximal simultaneously. The 0-1 MKP is a NP-hard problem; that is, no polynomial algorithm for any NP-hard problem has yet been found. Hence, various population-based search algorithms are applied to solve these problems. Particle swarm optimization (PSO), which is an efficient population-based optimization algorithm, is based on the metaphors of social interaction and communication (e.g., fish schooling and bird flocking). In the classic PSO model, the cognition learning factor and social learning factor are constant. Thus, it is easy for particles to get trapped in the local optimum. Therefore, this dissertation proposes three novel binary PSO algorithms with dynamic learning factors to prevent particles from being trapped in the local optimum and improves the quality of the solutions of the 0-1 MKPs. The computational results have shown that the proposed algorithms are capable of finding the optimal or near optimal solutions and can outperform the other existing BPSO algorithms in a reasonable time for solving low- and high-dimensional 0-1 MKPs from OR-Library.