An Improved Genetic Algorithm And Its Applications For Solving Knapsack Problem

Genetic Algorithm is a bionic optimization method which simulates the process of biological evolution that characterized by'survival of the fittest'. It had outstanding performance in solving small scale knapsack problems in its earlier times, and was successfully applied to solve some complex optimization problems also. However, due to its inborn defects, the accuracy and efficiency are not good enough in solving large scale knapsack problems. Chaos is a good searching optimization approach, which can effectively prevent solution falling into local optimal value during searching process. Based on this, the paper tries to introduce chaotic disturbance into traditional genetic algorithm to improve its efficiency. An improved genetic algorithm based on chaotic disturbance and inner point penalty function is proposed in this paper.Knapsack Problem is one classical combinatorial optimization problem and has been extensively applied in all kinds of fields. Researches on methods for solving knapsack problem have significant values both in theories and practical applications. This paper makes some research and analysis of solving knapsack problem under small population condition by using genetic algorithm.With the help of a well designed appropriate fitness function, the improved genetic algorithm, which proposed in the paper, is successfully applied to resolve 0-1 knapsack problem, and a transportation problem which can be modeled as knapsack problem. By comparing with multiple algorithm samples, our algorithm gives outstanding performance both in overcoming premature convergence and accuracy of solutions.