An Algorithm for Solving Knapsack Problems Utilizing Knowledge Evolution Principle

Knapsack problem is regarded as a difficult NP problem in computer algorithms. According to the characteristics of knapsack problems, an algorithm (called KP-KEA) for solving knapsack problems utilizing knowledge evolution principle is proposed. In this algorithm, an initial knowledge base is formed at first. The next work is to inherit excellent knowledge individuals by inheritance operator, produce novel knowledge individuals by innovation operator, update knowledge-base by update operator, and accordingly realize knowledge evolution. At last, the optimal solution of knapsack problems can be gained from the optimal knowledge individual. The successful experimental results show that it is an effective algorithm for solving knapsack problems. Compared with genetic algorithm, the convergence speed and the optimal solution of this algorithm are all better. This algorithm is also suited to solve other constraint optimization problems.