Title :
Solving 0-1Knapsack Problem Based on Rough Set Theory
Author :
Zhijun, Zhang ; Yan, Wu ; Gaowei, Yan
Author_Institution :
Coll. of Inf. Eng., Taiyuan Univ. of Technol., Taiyuan, China
Abstract :
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. Finally, 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.
Keywords :
genetic algorithms; knapsack problems; rough set theory; directed evolution; genetic algorithm; knapsack problem; knowledge discovery function; rough set theory; searching efficiency improvement; searching space; Algorithm design and analysis; Approximation algorithms; Europe; Gallium; Genetic algorithms; Heuristic algorithms; Set theory; genetic algorithm; knapsack problem; rough set;
Conference_Titel :
Computational Aspects of Social Networks (CASoN), 2010 International Conference on
Conference_Location :
Taiyuan
Print_ISBN :
978-1-4244-8785-1
DOI :
10.1109/CASoN.2010.52
