Solving 0-1 Knapsack Problem Based on Rough Set Theory
A kind of algorithm is proposed in this paper to improve the searching efficiency, which combinates Rough Set Theory (RST) and Genetic Algorithm (GA) for 0-1 knapsack problem. The study is to utilize the knowledge discovery function of RST to find the important genes in GA. Then directed evolution is carried out according to the important genes. Finallyi an example of four knapsack problem is used to test. The searching space is reduced and the important genes ensure the effective information will not be lost. The algorithm is able to improve the searching efficiency and the quality of GA.
knapsack problem genetic algorithm rough set
Zhang Zhijun WuYan YanGaowei
College of Information Engineering Taiyuan University of Technology Taiyuan, PRC Center of Nework an College of Information Engineering Taiyuan University of Technology Taiyuan, PRC
国际会议
International Conference on Computational Aspects of Social Networks(国际社会网络计算会议 CASoN 2010)
太原
英文
200-203
2010-09-26（万方平台首次上网日期，不代表论文的发表时间）