Solving 0-1 Knapsack Problem Based On Rough Set Theory And Genetic Algorithm

Rough Set Theory(RST) and Genetic Algorithm(GA) are mainly researched on this paper,it belongs to the cross disciplines of computer science,intelligent information process,and evolution computing. This study embeds rough set theory into genetic algorithm and uses 0-1 knapsack problem as test problem. Rough set theory is used to analyze the knowledge and information hidden in genetic algorithm process,which result in the rapid discovery of important genes,then used to determine the evolution direction.0-1 knapsack problem (KP) is a typical combinatorial optimization problem,which has very wide background. Many problems can be described by knapsack problem,such as resourse allocation,warehouse loading,capital budget, storage distribution and project selection,etc. And it is often as a sub problem of other complex combinatorial optimization problems. However, for large scale 0-1 knapsack problem, people still can not find the perfect solution method. It is extremely difficult to get the the optimal solution. Therefore,it is a significant work of studying the large scale 0-1 knapsack problem.In the past the methods to solve knapsack problem can be divided into two categories: exact algorithms and approximate algorithms.Exact algorithms has a great lot of calculation in the large scale problem, which is often not practical in engineering. The genetic algorithm as the representative of the approximate algorithms can obtain the approximate optimal solution, but may be premature convergence in the large scale problem, plunged into a local optimal solution.Further study is made based on the experiences of predecessors. A new kind of algorithm for 0-1 knapsack problem is proposed which embeds rough set theory in genetic algorithm. Rough set theory is used to analyze the information hidden in genetic algorithm process,then the important genes are discovered which is used in crossover process of genetic algorithm. The new algorithm is able to improve the searching efficiency and the quality of GA.The main work is listed as follows:Firstly,the basic thoughts and developments of several exact algorithms and approximate algorithms for solving KP are discussed. Then, the advantages and disadvantages of the given methods are respectively indicated. At last,the development trend of knapsack problem is provided.Secondly, a basic theoretical analysis of genetic algorithm is given in the paper. The liminations of GA leads to a new direction-the hybrid evolution based on knowledge discovery.Thirdly,to avoid the disadvantages of genetic algorithm,a new algorithm is proposed which embeds knowledge discovery algorithm into genetic algorithm. The study is to utilize the reduct function of rough set theory to find the important genes. Then the crossover in GA can be operated according to the gene positions. The goal is to determine the evolution direction. Test the rough set-genetic algorithm (RSGA) in Matlab simulation platform,and it is applied into the 0-1 knapsack problem. The experiment results show that the algorithm which is based on RSGA changes the way of crossover in GA randomly. The new algorithm is able to improve the searching efficiency and quality of GA.